No Access

Flow Shop Resource Allocation Scheduling with Due Date Assignment, Learning Effect and Position-Dependent Weights

Wei-Wei Liu

Department of Basic, Shenyang Sport University, Shenyang 110102, P. R. China

School of Computer Science and Engineering, Northeastern University, Shenyang 110169, P. R. China

E-mail Address: liuww_2010@163.com

Corresponding author.

Search for more papers by this author

and

Chong Jiang

Department of Sport Education and Humanity, Nanjing Sport Institute, Nanjing 210014, P. R. China

E-mail Address: jiang0941@163.com

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0217595920500141Cited by:14 (Source: Crossref)

Abstract

In this paper, the flow shop resource allocation scheduling with learning effect and position-dependent weights on two-machine no-wait setting is considered. Under common due date assignment and slack due date assignment rules, a bi-criteria analysis is provided. The optimality properties and polynomial time algorithms are developed to solve four versions of the problem. For a special case of the problem, it is proved that the problem can be optimally solved by a lower order algorithm.

Keywords:

References

Ahmadizar, F and Z Amiri (2018). Outsourcing and scheduling for a two-machine flow shop with release times. Engineering Optimization, 50(3), 483–498. Crossref, Web of Science, Google Scholar
Allahverdi, A and T Aldowaisan (2002). No-wait flowshops with bicriteria of makespan and total completion time. Journal of the Operational Research Society, 53(9), 1004–1015. Crossref, Web of Science, Google Scholar
Allahverdi, A and T Aldowaisan (2004). No-wait flowshops with bicriteria of makespan and maximum lateness. European Journal of Operational Research, 152(1), 132–147. Crossref, Web of Science, Google Scholar
Azzouz, A, M Ennigrou and LB Said (2017). Scheduling problems under learning effects: Classification and cartography. International Journal of Production Research, 56(3), 1–20. Google Scholar
Biskup, D (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188(2), 315–329. Crossref, Web of Science, Google Scholar
Brucker, P (2001). Scheduling Algorithms, 3rd edn. Berlin, Springer. Crossref, Google Scholar
Gao, F, M Liu, J-J Wang and Y-Y Lu (2018). No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times. International Journal of Production Research, 56(6), 2361–2369. Crossref, Web of Science, Google Scholar
Geng, X-N, J-B Wang and D Bai (2019). Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect. Engineering Optimization, 51(8), 1301–1323. Crossref, Web of Science, Google Scholar
Graham, RL, EL Lawler, JK Lenstra and AHG Rinnooy Kan (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326. Crossref, Google Scholar
Hardy, GH, JE Littlewood and G Polya (1967). Inequalities, 2nd edn. Cambridge: Cambridge University Press. Google Scholar
Jiang, C, D Zou, D Bai and J-B Wang (2020). Proportionate flowshop scheduling with position-dependent weights. Engineering Optimization, 52(1), 37–52. Crossref, Web of Science, Google Scholar
Li, G, M-L Luo, W-J Zhang and X-Y Wang (2015). Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation. International Journal of Production Research, 53(4), 1228–1241. Crossref, Web of Science, Google Scholar
Liu, Y and Z Feng (2014). Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times. Computers & Industrial Engineering, 75, 170–175. Crossref, Web of Science, Google Scholar
Liu, W, X Hu and X-Y Wang (2017). Single machine scheduling with slack due dates assignment. Engineering Optimization, 49, 709–717. Crossref, Web of Science, Google Scholar
Liu, Z, Z Wang and Y-Y Lu (2017). A bicriteria approach for single machine scheduling with resource allocation, learning effect and a deteriorating maintenance activity. Asia-Pacific Journal of Operational Research, 34(2), 1750011. Link, Web of Science, Google Scholar
Lu, Y-Y, G Li, Y-B Wu and P Ji (2014). Optimal due-date assignment problem with learning effect and resource-dependent processing times. Optimization Letters, 8(1), 113–127. Crossref, Web of Science, Google Scholar
Lu, Y-Y and J-Y Liu (2018). A note on resource allocation scheduling with position-dependent workloads. Engineering Optimization, 50(10), 1810–1827. Crossref, Web of Science, Google Scholar
Lu, Y-Y, J-B Wang, P Ji and H He (2017). A note on resource allocation scheduling with group technology and learning effects on a single machine. Engineering Optimization, 49(9), 1621–1632. Crossref, Web of Science, Google Scholar
Nagano, MS, FL Rossi and NJ Martarelli (2019). High-performing heuristics to minimize flowtime in no-idle permutation flowshop. Engineering Optimization, 51(2), 185–198. Crossref, Web of Science, Google Scholar
Niu, Y-P, L Wan and J-B Wang (2015). A note on scheduling jobs with extended sum-of-processing-times-based and position-based learning effect. Asia-Pacific Journal of Operational Research, 32(2), 1550001. Link, Web of Science, Google Scholar
Shabtay, D (2016). Optimal restricted due date assignment in scheduling. European Journal of Operational Research, 252, 79–89. Crossref, Web of Science, Google Scholar
Shabtay, D and G Steiner (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155(13), 1643–1666. Crossref, Web of Science, Google Scholar
Sun, X, X-N Geng, J-B Wang and F Liu (2019). Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect. International Journal of Production Research, 57(6), 1873–1891. Crossref, Web of Science, Google Scholar
Tian, Y, M Xu, C Jiang, J-B Wang and X-Y Wang (2019). Two-machine no-wait resource allocation flowshop scheduling with learning effect under limited cost availability. The Computer Journal, 62(1), 90–96. Crossref, Web of Science, Google Scholar
T’kindt, V and J-C Billaut (2006). Multicriteria Scheduling: Theory, Models and Algorithms, 2nd edn. Berlin: Springer. Google Scholar
Wang, J-B, X-N Geng, L Liu, J-J Wang and Y-Y Lu (2018). Single machine CON/SLK due date assignment scheduling with controllable processing time and job-dependent learning effects. The Computer Journal, 61(9), 1329–1337. Crossref, Web of Science, Google Scholar
Wang, J-B, M Gao, J-J Wang, L Liu and H He (2019a). Scheduling with a position-weighted learning effect and job release dates. Engineering Optimization. https://doi.org/10.1080/0305215X.2019.1664498 Crossref, Web of Science, Google Scholar
Wang, J-B, P Ji, TCE Cheng and D Wang (2012a). Minimizing makespan in a two-machine flow shop with effects of deterioration and learning. Optimization Letters, 6, 1393–1409. Crossref, Web of Science, Google Scholar
Wang, X-R, J Jin, J-B Wang and P Ji (2014). Single machine scheduling with truncated job-dependent learning effect. Optimization Letters, 8(2), 669–677. Crossref, Web of Science, Google Scholar
Wang, J-B and X-X Liang (2019). Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint. Engineering Optimization, 51(2), 231–246. Crossref, Web of Science, Google Scholar
Wang, J-B, F Liu and J-J Wang (2019b). Research on m-machine flow shop scheduling with truncated learning effects. International Transactions in Operational Research, 26(3), 1135–1151. Crossref, Web of Science, Google Scholar
Wang, J-B, M Liu, N Yin and P Ji (2017a). Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial and Management Optimization, 13(2), 1025–1039. Crossref, Web of Science, Google Scholar
Wang, J-B and M-Z Wang (2013). Makespan minimization on three-machine flow shop with deteriorating jobs. Asia-Pacific Journal of Operational Research, 30(6), 1350022. Link, Web of Science, Google Scholar
Wang, J-B and M-Z Wang (2014). Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times. Asia-Pacific Journal of Operational Research, 31(5), 1450036. Link, Web of Science, Google Scholar
Wang, J-B and J-J Wang (2015). Research on scheduling with job-dependent learning effect and convex resource dependent processing times. International Journal of Production Research, 53(19), 5826–5836. Crossref, Web of Science, Google Scholar
Wang, J-B, M-Z Wang and P Ji (2012b). Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs. International Journal of Systems Science, 43, 861–868. Crossref, Web of Science, Google Scholar
Wang, J-B, M-Z Wang and P Ji (2012c). Scheduling jobs with processing times dependent on position, starting time and allotted resource. Asia-Pacific Journal of Operational Research, 29(5), 1250030. Link, Web of Science, Google Scholar
Wang, D, M-Z Wang and J-B Wang (2010). Single-machine scheduling with learning effect and resource-dependent processing times. Computers & Industrial Engineering, 59(3), 458–462. Crossref, Web of Science, Google Scholar
Wang, D-J, Y Yin and TCE Cheng (2017b). A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times. Naval Research Logistics, 64(1), 41–63. Crossref, Web of Science, Google Scholar
Wang, J-B, B Zhang, L Li, D Bai and Y-B Feng (2020). Due window assignment scheduling problems with position-dependent weights on a single machine. Engineering Optimization, 52(2), 185–193. Crossref, Web of Science, Google Scholar
Yin, Y, D-J Wang, TCE Cheng, C-C Wu (2016a). Bi-criterion single-machine scheduling and due window assignment with common flow allowances and resource allocation. Journal of the Operational Research Society, 67, 1169–1183. Crossref, Web of Science, Google Scholar
Yin, Y, W-H Wu, TCE Cheng and C-C Wu (2014). Due date assignment and single-machine scheduling with generalized positional deteriorating jobs and deteriorating multi-maintenance activities. International Journal of Production Research, 52(8), 2311–2326. Crossref, Web of Science, Google Scholar
Yin, Y, D-J Wang, C-C Wu and TCE Cheng (2016b). CON/SLK due date assignment and scheduling on a single machine with two agents. Naval Research Logistics, 63(5), 416–429. Crossref, Web of Science, Google Scholar
Yin, Y, Y Yang, D-J Wang, TCE Cheng and C-C Wu (2018). Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents. Naval Research Logistics, 65(5), 393–409. Crossref, Web of Science, Google Scholar