带有维护窗口的调度问题的综述

doi:10.15960/j.cnki.issn.1007-6093.2025.01.001

Abstract

Abstract:

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.

Key words: scheduling problem, maintenance period, approximation algorithm, exact algorithm

CLC Number:

O157

Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods[J]. Operations Research Transactions, 2025, 29(1): 1-18.

Figures/Tables 4

问题	算法	Ratio	文献
$ 1, h_1\|nr-a\|\sum C_j $	SPT	$ \frac{5}{4} $, $ O(n\log n) $	[3]
	SPT	$\frac{9}{7}, O(n\log n)$	[24]
	MSPT	$\frac{20}{17}, O(n\log n)$	[25]
	PTAS	$O(n^{2k+1})$	[26]
$1, h_1\|nr-a\|\sum w_j C_j$	WSPT	$+\infty \; even if \; w_i=p_i$	[4]
	WSPT, MWSPT	2	[27]
	Approximation	2, $O(n^2)$	[28]
	Approximation	$(2+\varepsilon), O(n\log n)$	[31]
$1, h_1\|nr-a\|C_{\max}$	LPT	$\frac{4}{3}, O(n\log n)$	[4]
	FPTAS	$O(\frac{n^2}{\varepsilon})$	[32]
$1, h_1\|nr-a\|\sum U_j$	Moore	1, $O(n\log n)$	[4]
$1, h_1\|nr-a\|L_{\max}$	EDD	$p_{\max}, O(n\log n)$	[4]
$1, h_1\|r-a\|\sum w_j C_j$	WSPT	$+\infty$	[4]
	Combination	2, $O(n \log n)$	[4]
	Approximation	2, $O(n^2)$	[34]
$1, h_k\|r-a\|\sum w_j C_j$	LPT	2, $O(n\log n)$	[34]
$F2, h_{11}\|r-a\|C_{\max}$	Johnson Rule	2, $O(n\log n)$	[13]
	Approximation	$\frac{3}{2}, O(n\log n)$	[13]
	Approximation	$\frac{4}{3}, O(n\log n)$	[42]
	FPTAS	$O(\frac{n^5}{\varepsilon^4})$	[44]
$F2, h_{21}\|r-a\|C_{\max}$	Johnson Rule	$\frac{3}{2}, O(n\log n)$	[13]
	Approximation	$\frac{4}{3}, O(n\log n)$	[13]
	Approximation	$\frac{5}{4}, O(n\log n)$	[43]
	FPTAS	$O(\frac{n^5}{\varepsilon^4})$	[44]
$F2, h_{1k}\|r-a\|C_{\max}$	Approximation	2, $O(n\log n)$	[41]
	Approximation	$\frac{3}{2}, O(n\log n)$	[46]
	Approximation	$\frac{4}{3}, O(n\log n)$	[47]
	PTAS	$O(\lceil \frac{1}{\varepsilon}\rceil n^{\lceil \frac{1}{\varepsilon}\rceil+1})$	[48]
$F2, h_{2k}\|r-a\|C_{\max}$	Johnson Rule	2, $O(n\log n)$	[49]
	Approximation	$\frac{4}{3}, O(n\log n)$	[49]
	PTAS	$O(n^{\lceil \frac{1}{\varepsilon}\rceil+1})$	[50]
$F2, h_{11}\|sr-a\|C_{\max}$	Johnson Rule	2, $O(n\log n)$	[5]
	Approximation	2, $O(n\log n)$	[5]
	PTAS	Polynomial of $n_b, n_s$	[46]
$F2, h_{21}\|sr-a\|C_{\max}$	Johnson Rule	$\max\frac{3}{2}, 1+\alpha$	[5]
	Approximation	$\frac{3}{2}$	[5]
	PTAS	Polynomial of $n_b, n_s$	[46]
$F2, h_{11}\|nr-a\|C_{\max}$	Johnson Rule	2, $O(n\log n)$	[5]
	Approximation	$\frac{3}{2}, O(n\log n)$	[52]
$F2, h_{21}\|nr-a\|C_{\max}$	Approximation	$\frac{3}{2}, O(n\log n)$	[5]
$O2, h_{11}\|r-a\|C_{\max}$	Approximation	$\frac{4}{3}, O(n)$	[56]
	PTAS	Polynomial of n	[59]
$O2, h_{11}\|nr-a\|C_{\max}$	Approximation	$\frac{4}{3}, O(n)$	[33]
	PTAS	Polynomial of n	[60]
$O2, h_{1k}\|r-a\|C_{\max}$	PTAS	Polynomial of n	[59]
$O2, h_{2k}\|r-a\|C_{\max}$	PTAS	Polynomial of n	[59]
$O2, h_{j1}\|r-a\|C_{\max}$	PTAS	Polynomial of n	[59]
$O2, h_{j1}\|nr-a\|C_{\max}$	Approximation	2, $O(n)$	[33]
$1, h_k\|nr-pa\|T_{\max}$	Heuristic	$O(n^2 \sum_{i=1}^n p_i)$	[35]
$1, h_k\|r-pa\|Z$	Heuristic	$O(n^2 \sum_{i=1}^n p_i)$	[37]
$1, h_k\|nr-pa\|C_{\max}$	LPT	2, $O(n\log n)$	[38]
	LS	2, $O(n)$	[39]
$1, h_k\|nr-pa\| \sum C_j$	Heuristic		[36]
$1, h_k\|nr-pa\| C_{\max}$	LS	2, $O(n^2)$	[40]
$1, h_k\|nr-pa\| C_{\max}$	LPT	2, $O(n^2)$	[40]
$1, h_k\|nr-pa\| C_{\max}$	MLPT	2, $O(n^2)$	[40]
$1, h_1\|nr-f\|C_{\max}$	Heuristic	$O(n\log n)$	[6]
$1, h_1\|r-f\|\sum C_j$	SPT	$O(n\log n)$	[66]
$1, h_1\|nr-f\|\sum C_j$	SPT	$\frac{9}{7}$	[66]
$1, h_k\|nr-pf\|C_{\max}$	Heuristic	$O(n^2\log n)$	[61]
		2(best)	[64]
$1, h_k\|nr-pf\|C_{\max}$	LS(best)	2, $O(n)$	[65]
$1, h_k\|nr-pf, {\rm online}\|C_{\max}$	LS(best)	2, $O(n)$	[65]
$F2, h_{21}\|nr-f\|C_{\max}$	Approximation	$\frac{3}{2}, O(n\log n)$	[67]
	PTAS	Polynomial of n
$O2, h_{21}\|nr-f\|C_{\max}$	Approximation	$\frac{3}{2}, O(n)$	[67]
$F2, h_{j1}\|VM\|C_{\max}$	FPTAS	$O(\frac{n^5}{\varepsilon^4})$	[7]
	Approximation	$\frac{3}{2}, O(n\log n)$	[7]
$1, h_1\|VM\|\sum w_{j}C_{j}$	Approximation	2, $O(n^2)$	[70]
	Approximation	$1+\frac{\sqrt{2}}{2}+\varepsilon, O(n^2/\varepsilon)$	[70]

References 72

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. doi: 10.1287/opre.45.2.288
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. doi: 10.1007/BF00288977\|
4	Lee C Y . Machine scheduling with an availability constraint[J]. Journal of Global Optimization, 1996, 9 (3-4): 395- 416. doi: 10.1007/BF00121681
5	Lee C Y . Two-machine flowshop scheduling with availability constraints[J]. European Journal of Operational Research, 1999, 114 (2): 420- 429. doi: 10.1016/S0377-2217(97)00452-9
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. doi: 10.1080/10170660209509183
7	Kubzin M A , Vitaly A S . Planning machine maintenance in two-machine shop scheduling[J]. Operations Research, 2006, 54 (4): 789- 800. doi: 10.1287/opre.1060.0301
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. doi: 10.1016/S0377-2217(99)00066-1
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. doi: 10.1287/mnsc.15.1.102
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. doi: 10.1002/nav.3800010110
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. doi: 10.1016/S0167-6377(96)00041-7
14	Chen B , Strusevich V A . Approximation algorithms for three-machine open shop scheduling[J]. ORSA Journal on Computing, 1993, 5 (3): 321- 326. doi: 10.1287/ijoc.5.3.321
15	Strusevich V A . A greedy open shop heuristic with job priorities[J]. Annals of Operations Research, 1998, 83, 253- 270. doi: 10.1023/A:1018964131329
16	Gonzalez T , Sahni S . Open shop scheduling to minimize finish time[J]. Journal of the ACM, 1976, 23 (4): 665- 679. doi: 10.1145/321978.321985
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. doi: 10.1023/A:1018909801944
20	Sanlaville E , Schmidt G . Machine scheduling with availability constraints[J]. Acta Informatica, 1998, 35 (9): 795- 811. doi: 10.1007/s002360050143
21	Schmidt G . Scheduling with limited machine availability[J]. European Journal of Operational Research, 2000, 121 (1): 1- 15. doi: 10.1016/S0377-2217(98)00367-1
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. doi: 10.4028/www.scientific.net/JERA.39.170
24	Lee C Y , Liman S D . Single machine flow-time scheduling with scheduled maintenance[J]. Acta Informatica, 1992, 29 (4): 375- 382. doi: 10.1007/BF01178778
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. doi: 10.1016/j.ejor.2003.08.026
26	He Y , Zhong W , Gu H . Improved algorithms for two single machine scheduling problems[J]. Theoretical Computer Science, 2006, 363 (3): 257- 265. doi: 10.1016/j.tcs.2006.04.014
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. doi: 10.1016/j.ejor.2006.06.062
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. doi: 10.1016/j.ijpe.2007.01.013
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. doi: 10.1007/s00453-008-9248-1
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. doi: 10.1002/nav.20083
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. doi: 10.1007/s001860200267
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. doi: 10.1007/s10479-004-5032-z
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. doi: 10.1057/palgrave.jors.2601998
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. doi: 10.1007/s00170-011-3249-y
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. doi: 10.1007/s10951-013-0350-0
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. doi: 10.1016/S0377-2217(01)00083-2
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. doi: 10.1016/S0167-6377(00)00033-X
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. doi: 10.1002/nav.10107
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. doi: 10.1016/S0305-0483(01)00048-2
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. doi: 10.1007/s10288-010-0119-7
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. doi: 10.1007/s11590-011-0281-7
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. doi: 10.1007/s11590-009-0137-6
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. doi: 10.1007/s10852-013-9245-5
51	Cheng T C E , Wang G . Two-machine flowshop scheduling with consecutive availability constraints[J]. Information Processing Letters, 1999, 71 (2): 49- 54. doi: 10.1016/S0020-0190(99)00094-0
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. doi: 10.1007/s10288-009-0102-3
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. doi: 10.1016/j.ijpe.2004.12.003
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. doi: 10.1007/s10951-013-0356-7
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. doi: 10.1016/S0167-6377(01)00079-7
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. doi: 10.1287/moor.18.1.12
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. doi: 10.1057/palgrave.jors.2601421
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. doi: 10.1002/nav.20122
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. doi: 10.1007/s10878-021-00773-7
61	Chen J S . Single-machine scheduling with flexible and periodic maintenance[J]. Journal of the Operational Research Society, 2006, 57 (6): 703- 710. doi: 10.1057/palgrave.jors.2602043
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. doi: 10.1080/03052150500270594
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. doi: 10.1016/j.ejor.2007.06.029
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. doi: 10.1016/j.ejor.2008.07.021
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. doi: 10.1007/s00170-011-3249-y
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. doi: 10.1016/j.ejor.2018.04.019
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. doi: 10.1016/S0377-2217(03)00261-3
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. doi: 10.1002/nav.20083

算法	复杂性	问题	文献
SPT	$ O(n\log n) $	$ 1\|\|\sum C_j $, $ Pm\|\|\sum C_j $	-
WSPT	$ O(n\log n) $	$ 1\|\|\sum w_j C_j $	-
EDD	$ O(n\log n) $	$ 1\|d_j\|L_{\max} $	-
LPT	$ O(n\log n) $	$ 1\|\|C_{\max} $, $ Pm\|\|C_{\max} $	-
LS	$ O(n) $	$ Pm\|\|C_{\max} $	-
Moore-Hodgson	$ O(n\log n) $	$ 1\|\|\sum U_j $	[11]
Johnson Rule	$ O(n\log n) $	$ F2\|\|C_{\max} $	[12]
Ratio Rule	$ O(n\log n) $	$ F2\|\|C_{\max} $	[13]
Greedy Algorithm	$ O(n) $	$ O2\|\|C_{\max} $	[14-15]
Gonzalez-Sahni	$ O(n) $	$ O2\|\|C_{\max} $	[16]
Pinedo-Schrage	$ O(n) $	$ O2\|\|C_{\max} $	[17]

问题	复杂性	文献
$ 1, h_1\|nr-a\|\sum C_j $	NP-hard	[3, 24]
$ 1, h_1\|nr-a\|\sum w_j C_j $	NP-hard	-
$ 1, h_1\|nr-a\|C_{\max} $	NP-hard	[4]
$ 1, h_1\|nr-a\|\sum U_i $	NP-hard	[4]
$ 1, h_1\|nr-a\|L_{\max} $	NP-hard	[4]
$ 1, h_1\|r-a\|C_{\max} $	P(any sequence)	[4]
$ 1, h_1\|r-a\|\sum C_j $	P(SPT)	[4]
$ 1, h_1\|r-a\|L_{\max} $	P(EDD)	[4]
$ 1, h_1\|r-a\|\sum U_i $	P(Moore-Hodgson)	[4]
$ 1, h_1\|r-a\|\sum w_j C_j $	NP-hard	[4]
$ 1, h_k\|r-a\|\sum w_j C_j $	strongly NP-hard	[34]
$ F2, h_{11}\|r-a\|C_{\max} $	NP-hard	[13]
$ F2, h_{21}\|sr-a\|C_{\max} $	NP-hard	[5]
$ F2, h_{jk}\|r-a\|C_{\max} $	strongly NP-hard	[41]
$ O2, h_{11}\|r-a\|C_{\max} $	NP-hard	[56]
$ 1, h_1\|nr-f\|C_{\max} $	NP-hard	[6]
$ 1, h_k\|nr-pf\|\overline{F} $	strongly NP-hard	[61]
$ 1, h_1\|VM\|\sum w_{j}C_{j} $	NP-hard	[70]
$ 1, h_1\|rm\|C_{\max} $	P	[8]
$ 1, h_1\|rm\|\sum C_j $	P	[8]
$ 1, h_1\|rm\|L_{\max} $	EDD(if $ \alpha_j<1$)	[8]
$ 1, h_1\|rm\|L_{\max} $	NP-hard	[8]

问题	Exact	问题规模	文献
$1, h_1\|nr-a\|\sum w_j C_j$	Branch and Bound	1 000 jobs	[27]
	Branch and Bound	1 000 jobs	[30]
	IP	60 jobs	[30]
	Dynamic Programming	3 000 jobs, $O(n B)$	[30]
$1, h_1\|r-a\|\sum w_j C_j$	Dynamic Programming	$O(n p_{\max} B)$	[4]
$F2, h_{11}\|r-a\|C_{\max}$	Dynamic Programming	$O(n MS^2 B p_{\max})$	[13]
$F2, h_{1k}\|r-a\|C_{\max}$	Branch and Bound	100 jobs, 10 MPs	[41]
$F2, h_{11}\|sr-a\|C_{\max}$	Dynamic Programming	$O(n MS^2 B p_{\max})$	[5]
$F2, h_{11}\|nr-a\|C_{\max}$	Dynamic Programming	$O(2^{n_1} n \log n)$	[53]
$O2, h_{11}\|r-a\|C_{\max}$	Dynamic Programming	$O(n s^2 GSW^4 GSS^3)$	[58]
$1, h_k\|nr-pa\|T_{\max}$	Branch and Bound	30 jobs	[35]
$1, h_k\|r-pa\|Z$	Branch and Bound	25 jobs	[37]
$1, h_k\|r-pa\| \sum C_j$	Branch and Bound	30 jobs	[36]
$1, h_1\|r-f\|\sum _{j=1}^n T_j$	2 BIPs	120 jobs	[62]
$1, h_1\|nr-f\|\sum _{j=1}^n T_j$	2 BIPs	120 jobs	[62]
$1, h_k\|nr-pf\|\overline{F}$	4 BIPs	120 jobs	[61]
$1, h_1\|nr-f\|\sum C_j$	Dynamic Programming	$O(n\cdot(s+1))$	[66]
$1, h_1\|nr-f\|\sum C_j$	Branch and Bound	400 jobs	[66]
$1, h_k\|nr-pf\|C_{\max}$	2 BIPs	100 jobs	[61]
$1, h_1\|VM\|\overline{L}$	SPT-based	$O(n^2 )$	[71]
$1, h_1\|VM\|T_{\max}$	EDD-based	$O(n^2 )$	[71]
$1, h_1\|VM\|\sum C_j$	SPT-based	$O(n^2 )$	[71]
$1, h_1\|VM, d_j=d\|\overline{T}$	SPT-based	$O(n^2 )$	[71]
$1, h_1\|rm\|\sum w_j C_j$	Dynamic Programming	$O(n \cdot T^3 )$	[8]
	Dynamic Programming	$O(n \cdot T \cdot W )$	[8]
$1, h_1\|rm\|L_{\max}$	Dynamic Programming	$O(n \cdot T^3 )$	[8]

[1]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[2]	An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[3]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[4]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[5]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[6]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[7]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[8]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[9]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[10]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[11]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[12]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[13]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[14]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[15]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.

A survey of scheduling with maintenance periods

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 72

Related Articles 15

Recommended Articles

Metrics

Comments