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

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

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.

算法	复杂性	问题	文献
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]	WU Hongyi, WANG Dong, WAN Long, LUO Wenchang. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions [J]. Operations Research Transactions, 2026, 30(1): 188-196.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[7]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[13]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[14]	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.
[15]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.

A survey of scheduling with maintenance periods

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References

Related Articles 15

Recommended Articles

Metrics

Comments