Operations Research Transactions >
2025 , Vol. 29 >Issue 1: 1 - 18
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.01.001
A survey of scheduling with maintenance periods
Received date: 2021-06-07
Online published: 2025-03-08
Copyright
In recent years, scheduling problems with maintenance periods have been attracting more and more researchers in the field of operational research. There are four types of maintenance period in the scheduling literature: fixed maintenance period, flexible maintenance period, floating maintenance period and rate-modifying maintenance period. At present, the vast majority of results have been arising about the scheduling problems with maintenance period, but there is no paper to summarize them. To be convenient for interested researchers, we make a summary about scheduling problems with maintenance period. In this paper, complexity results, exact algorithms and approximation algorithms in single machine, flow shop and open shop scheduling environment with different target are surveyed briefly.
Yuan YUAN, Yan LAN, Xin HAN . A survey of scheduling with maintenance periods[J]. Operations Research Transactions, 2025 , 29(1) : 1 -18 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.001
| 1 | Hall L A . Approximability of flow shop scheduling[J]. Mathematical Programming, 1998, 82 (1): 175- 190. |
| 2 | Williamson D P , Hall L A , Hoogeveen J A , et al. Short shop schedules[J]. Operations Research, 1997, 45 (2): 288- 294. |
| 3 | Adiri I , Bruno J , Frostig E , et al. Single machine flow-time scheduling with a single breakdown[J]. Acta Informatica, 1989, 26 (7): 679- 696. |
| 4 | Lee C Y . Machine scheduling with an availability constraint[J]. Journal of Global Optimization, 1996, 9 (3-4): 395- 416. |
| 5 | Lee C Y . Two-machine flowshop scheduling with availability constraints[J]. European Journal of Operational Research, 1999, 114 (2): 420- 429. |
| 6 | Yang D L , Hung C L , Hsu C J , et al. Minimizing the makespan in a single machine scheduling problem with a flexible maintenance[J]. Journal of the Chinese Institute of Industrial Engineers, 2002, 19 (1): 63- 66. |
| 7 | Kubzin M A , Vitaly A S . Planning machine maintenance in two-machine shop scheduling[J]. Operations Research, 2006, 54 (4): 789- 800. |
| 8 | Lee C Y , Leon V J . Machine scheduling with a rate-modifying activity[J]. European Journal of Operational Research, 2001, 128 (1): 119- 128. |
| 9 | Graham R L. Bounds on the performance of scheduling algorithms [M]//Computer and Job Scheduling Theory. New York: John Wiley & Sons, 1976: 165-227. |
| 10 | Graham R l , Lawler E L , Lenstra J K , et al. Optimization and approximation in deterministic sequencing and scheduling: A survey[J]. Annals of Discrete Mathematics, 1979, 5, 287- 326. |
| 11 | Moore J M . An n job, one machine sequencing algorithm for minimizing the number of late jobs[J]. Management Science, 1968, 15 (1): 102- 109. |
| 12 | Johnson S M . Optimal two-and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954, 1 (1): 61- 68. |
| 13 | Lee C Y . Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint[J]. Operations Research Letters, 1997, 20 (3): 129- 139. |
| 14 | Chen B , Strusevich V A . Approximation algorithms for three-machine open shop scheduling[J]. ORSA Journal on Computing, 1993, 5 (3): 321- 326. |
| 15 | Strusevich V A . A greedy open shop heuristic with job priorities[J]. Annals of Operations Research, 1998, 83, 253- 270. |
| 16 | Gonzalez T , Sahni S . Open shop scheduling to minimize finish time[J]. Journal of the ACM, 1976, 23 (4): 665- 679. |
| 17 | Pinedo M, Schrage L. Stochastic shop scheduling: A survey [M]//Deterministic and Stochastic Scheduling. Dordrecht: Springer, 1982. |
| 18 | Sevastianov S V , Woeginger G J . Makespan minimization in open shops: A polynomial time approximation scheme[J]. Mathematical Programming, 1998, 82 (1): 191- 198. |
| 19 | Lee C Y , Lei L , Pinedo M . Current trends in deterministic scheduling[J]. Annals of Operations Research, 1997, 70, 1- 41. |
| 20 | Sanlaville E , Schmidt G . Machine scheduling with availability constraints[J]. Acta Informatica, 1998, 35 (9): 795- 811. |
| 21 | Schmidt G . Scheduling with limited machine availability[J]. European Journal of Operational Research, 2000, 121 (1): 1- 15. |
| 22 | Ma Y , Chu C B , Zuo C R . A survey of scheduling with deterministic machine availability constraints[J]. Computers & Industrial Engineering, 2010, 58 (2): 199- 211. |
| 23 | Assia S , Ikram A , Abdellah B , et al. Joint scheduling of jobs and variable maintenance activities in the flowshop sequencing problems: Review, classification and opportunities[J]. International Journal of Engineering Research in Africa, 2018, 39, 170- 190. |
| 24 | Lee C Y , Liman S D . Single machine flow-time scheduling with scheduled maintenance[J]. Acta Informatica, 1992, 29 (4): 375- 382. |
| 25 | Sadfi C , Penz B , Rapine C , et al. An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints[J]. European Journal of Operational Research, 2005, 161 (1): 3- 10. |
| 26 | He Y , Zhong W , Gu H . Improved algorithms for two single machine scheduling problems[J]. Theoretical Computer Science, 2006, 363 (3): 257- 265. |
| 27 | Kacem I , Chu C . Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period[J]. European Journal of Operational Research, 2008, 187 (3): 1080- 1089. |
| 28 | Kacem I . Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval[J]. Computers & Industrial Engineering, 2008, 54 (3): 401- 410. |
| 29 | Kacem I , Chu C . Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint[J]. International Journal of Production Economics, 2008, 112 (1): 138- 150. |
| 30 | Kacem I , Chu C , Souissi A . Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times[J]. Computers & Operations Research, 2008, 35 (3): 827- 844. |
| 31 | Kellerer H , Strusevich V A . Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications[J]. Algorithmica, 2010, 57 (4): 769- 795. |
| 32 | He Y , Hi M , Cheng T C E . Single machine scheduling with a restricted rate-modifying activity[J]. Naval Research Logistics, 2005, 52 (4): 361- 369. |
| 33 | Breit J , Schmidt G , Strusevich V A . Non-preemptive two-machine open shop scheduling with non-availability constraints[J]. Mathematical Methods of Operations Research, 2003, 57 (2): 217- 234. |
| 34 | Wang G , Sun H , Chu C . Preemptive with availability constraints to minimize total weighted completion times[J]. Annals of Operations Research, 2005, 133, 183- 192. |
| 35 | Liao C J , Chen W J . Single-machine scheduling with periodic maintenance and nonresumable jobs[J]. Computers & Operations Research, 2003, 30 (9): 1335- 1347. |
| 36 | Chen W J . Minimizing total flow time in the single-machine scheduling problem with periodic maintenance[J]. Journal of the Operational Research Society, 2006, 57 (4): 410- 415. |
| 37 | Chen W J . An efficient algorithm for scheduling jobs on a machine with periodic maintenance[J]. The International Journal of Advanced Manufacturing Technology, 2007, 34 (11): 1173- 1182. |
| 38 | Ji M , He Y , Cheng T C E . Single-machine scheduling with periodic maintenance to minimize makespan[J]. Computers & Operations Research, 2007, 34 (6): 1764- 1770. |
| 39 | Xu D , Yin Y . On single-machine scheduling with flexible maintenance activities[J]. The International Journal of Advanced Manufacturing Technology, 2011, 56 (9-12): 1139- 1145. |
| 40 | Yu X , Zhang Y , Steiner G . Single-machine scheduling with periodic maintenance to minimize makespan revisited[J]. Journal of Scheduling, 2014, 17 (3): 263- 270. |
| 41 | Kubiak W , B?aewicz J , Formanowicz P , et al. Two-machine flow shops with limited machine availability[J]. European Journal of Operational Research, 2002, 136 (3): 528- 540. |
| 42 | Cheng T C E , Wang G . An improved heuristic for two-machine flowshop scheduling with an availability constraint[J]. Operations Research Letters, 2000, 26 (5): 223- 229. |
| 43 | Breit J . A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint[J]. Computers & Operations Research, 2006, 33 (8): 2143- 2153. |
| 44 | Ng C T , Kovalyov M Y . An FPTAS for scheduling a two-machine flowshop with one unavailability interval[J]. Naval Research Logistics, 2004, 51 (3): 307- 315. |
| 45 | B?a?ewicz J , Breit J , Formanowicz , et al. Heuristic algorithms for the two-machine flowshop with limited machine availability[J]. Omega, 2001, 29 (6): 599- 608. |
| 46 | Kubzin M A , Potts C N , Strusevich V A . Approximation results for flow shop scheduling problems with machine availability constraints[J]. Computers & Operations Research, 2009, 36 (2): 379- 390. |
| 47 | Hadda H . An improved algorithm for the two machine flow shop problem with several availability constraints[J]. 4OR, 2010, 8 (3): 271- 280. |
| 48 | Hadda H . A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints[J]. Optimization Letters, 2012, 6 (3): 559- 569. |
| 49 | Hadda H . A ($\frac{4}{3}$)-approximation algorithm for a special case of the two machine flow shop problem with several availability constraints[J]. Optimization Letters, 2009, 3 (4): 583- 592. |
| 50 | Hadda H . A PTAS for a particular case of the two-machine flow shop with limited machine availability[J]. Journal of Mathematical Modelling and Algorithms in Operations Research, 2014, 13 (4): 511- 522. |
| 51 | Cheng T C E , Wang G . Two-machine flowshop scheduling with consecutive availability constraints[J]. Information Processing Letters, 1999, 71 (2): 49- 54. |
| 52 | Hadda H , Dridi N , Hajri-Gabouj S . An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs[J]. 4OR, 2010, 8 (1): 87- 99. |
| 53 | Allaoui H , Artiba A , Elmaghraby S E , et al. Scheduling of a two-machine flow shop with availability constraints on the first machine[J]. Intenational Journal of Production Economics, 2006, 99, 16- 27. |
| 54 | Werra D . Graph-Theoretical Models for Preemptive Scheduling[M]. Amsterdam: Elsevier, 1989. |
| 55 | Soper A J . A cyclical search for the two machine flow shop and open shop to minimise finishing time[J]. Journal of Scheduling, 2015, 18 (3): 311- 314. |
| 56 | Breit J , Schmidt G , Strusevich V A . Two-machine open shop scheduling with an availability constraint[J]. Operations Research Letters, 2001, 29 (2): 65- 77. |
| 57 | Lu L , Posner M E . An NP-hard open shop scheduling problem with polynomial average time complexity[J]. Mathematics of Operations Research, 1993, 18 (1): 12- 38. |
| 58 | Lorigeon T , Billaut J C , Bouquard J L . A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint[J]. Journal of the Operational Research Society, 2002, 53 (11): 1239- 1246. |
| 59 | Kubzin M A , Strusevich V A , Breit J , et al. Polynomial-time approximation schemes for twomachine open shop scheduling with nonavailability constraints[J]. Naval Research Logistics, 2006, 53 (1): 16- 23. |
| 60 | Yuan Y , Lan Y , Ding N , et al. A PTAS for non-resumable open shop scheduling with an availability constraint[J]. Journal of Combinatorial Optimization, 2022, 43, 350- 362. |
| 61 | Chen J S . Single-machine scheduling with flexible and periodic maintenance[J]. Journal of the Operational Research Society, 2006, 57 (6): 703- 710. |
| 62 | Chen J S . Optimization models for the machine scheduling problem with a single flexible maintenance activity[J]. Engineering Optimization, 2006, 38 (1): 53- 71. |
| 63 | Chen J S . Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan[J]. European Journal of Operational Research, 2008, 190 (1): 90- 102. |
| 64 | Xu D , Yin Y , Li H . A note on scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan[J]. European Journal of Operational Research, 2009, 197 (2): 825- 827. |
| 65 | Xu D , Yin Y . On single-machine scheduling with flexible maintenance activities[J]. The International Journal of Advanced Manufacturing Technology, 2011, 56 (9-12): 1139- 1145. |
| 66 | Yang S , Ma Y , Xu D , et al. Minimizing total completion time on a single machine with a flexible maintenance activity[J]. Computers & Operations Research, 2011, 38 (4): 755- 770. |
| 67 | Mosheiov G , Sarig A , Strusevich V A , et al. Two-machine flow shop and open shop scheduling problems with a single maintenance window[J]. European Journal of Operational Research, 2018, 271 (2): 388- 400. |
| 68 | Aggoune R, Abdel H, Portmann M C. Genetic algorithms for the flow shop scheduling problem with availability constraints [C]//2001 IEEE International Conference on Systems, Man and Cybernetics, 2001: 2546-2551. |
| 69 | Aggoune R . Minimizing the makespan for the flow shop scheduling problem with availability constraints[J]. European Journal of Operational Research, 2004, 153 (3): 534- 543. |
| 70 | Luo W, Chen L, Zhang G. Approximation algorithms for scheduling with a variable machine maintenance [C]//International Conference on Algorithmic Applications in Management, 2010: 209-219. |
| 71 | Ying K , Lu C , Chen J . Exact algorithms for single-machine scheduling problems with a variable maintenance[J]. Computers & Industrial Engineering, 2016, 98, 427- 433. |
| 72 | He Y , Ji M , Cheng T C E . Single machine scheduling with a restricted rate-modifying activity[J]. Naval Research Logistics, 2005, 52 (4): 361- 369. |
/
| 〈 |
|
〉 |
