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

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

中图分类号:

O157

袁园, 兰艳, 韩鑫. 带有维护窗口的调度问题的综述[J]. 运筹学学报（中英文）, 2025, 29(1): 1-18.

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

图/表 4

表1

表2

表3

近似算法"

问题	算法	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]

表3

表4

参考文献 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]	高洁, 邹娟, 隋玉康, 张玉忠. 带有退化维护活动和工件可拒绝的非同类机排序问题[J]. 运筹学学报, 2023, 27(3): 137-149.
[2]	袁藩, 徐大川, 张冬梅. k-均值问题的差分隐私算法综述[J]. 运筹学学报, 2022, 26(3): 1-16.
[3]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.
[4]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[5]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[6]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[7]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[8]	刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报, 2022, 26(1): 99-112.
[9]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量k-均值问题的局部搜索算法[J]. 运筹学学报, 2022, 26(1): 113-124.
[10]	李小玮, 成夏炎, 李荣珩. 带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法[J]. 运筹学学报, 2021, 25(4): 31-44.
[11]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[12]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[13]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[14]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[15]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.