工件可拒绝排序问题综述

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

摘要/Abstract

摘要： 可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题，是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工，然而在实际中由于某些特殊原因，决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题，有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值，在理论上也有重要的意义.近年来该领域受到越来越广泛的关注，新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍，展示了已有的研究成果和新的问题，给出了此方面的比较重要的参考文献，旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.

关键词: 可拒绝排序, 在线排序, 离线排序, 近似算法, 复杂性, 竞争比, NP-难, PTAS, FPTAS

Abstract: Scheduling with rejection is a representative and applied scheduling that emerged around 2000. It is one of the generalizations of the classical scheduling problems. In classical scheduling problems, it is assumed that all jobs have to be processed. However, in practice, for some special reasons, policy makers will reject the processing of some jobs. That is what we called job scheduling with rejection. It is noteworthy that the problem has a certain application background and great application value, and also has important significance in theory. The problem is gaining more and more attention recently and new results are welling up.In this paper, we give a comprehensive introduction to online and offline scheduling with job rejection. We also give abundant references, including many existing research results and new research directions. It's designed to help the interested readers rapidly to the research frontier.

Key words: scheduling with rejection, online scheduling, offline scheduling, approximation algorithm, complexity, competitive ratio, NP-Hard, PTAS, FPTAS

中图分类号:

O221.7

张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.

ZHANG Yuzhong. A survey on job scheduling with rejection[J]. Operations Research Transactions, 2020, 24(2): 111-130.

参考文献

[1] 越民义, 韩继业. n个零件在m台机床上的加工排序问题[J]. 中国科学, 1975, 5:462-470.
[2] 唐国春, 张峰, 罗守成, 等. 现代排序论[M]. 上海:上海科学普及出版社, 2003.
[3] Bartal Y, Leonardi S, Marchetti-Spaccamela A, et al. Multiprocessor scheduling witn rejection[J]. SIAM Journal of Discrete Mathematics, 2000, 13(1):64-78.
[4] Shabtay D, Gaspar N, Kaspi M. A survey on offline scheduling with rejection[J]. Journal of Scheduling, 2013, 16(1):3-28.
[5] Graham R, Lawler E, Lenstra J, et al. Optimization and approximation in deterministic sequencing and scheduling:a survey[J]. Annals of Discrete Mathematics, 1979, 5:287-326.
[6] Garey M, Johnson D. Computers and Intractability:A Guide to the Theory of NP-Completeness[M]. San Francisco:Freeman, 1979.
[7] Brucker P, Brucker P. Scheduling Algorithms[M]. Berlin:Springer, 2007.
[8] Browne S, Yechiali U. Scheduling deteriorating jobs on a single processor[J]. Operations Research, 1990, 38(3):495-498.
[9] Gupta J, Gupta S. Single facility scheduling with nonlinear processing times[J]. Computers and Industrial Engineering, 1988, 14(4):387-393.
[10] Borodin A, El-Yaniv R. On-Line Computation and Competitive Analysis[M]. Cambridge:Cambridge University Press, 1998.
[11] Papadimitriou C, Steiglitz K. Combinatorial Optimization:Algorithms and Complexity[M]. Englewood Cliffs:Prentice-Hall, 1982.
[12] Hoogeveen H, Skutella M, Woeginger G J. Preemptive scheduling with rejection[J]. Mathematical Programming, 2003, 94(2-3):361-374.
[13] Cao Z, Zhang Y. Scheduling with rejection and non-identical job arrivals[J]. Journal of Systems Science and Complexity, 2007, 20(4):529-535.
[14] Ou J, Zhong X, Wang G. An improved heuristic for parallel machine scheduling with rejection[J]. European Journal of Operational Research, 2015, 241(3):653-661.
[15] Zhang L, Lu L, Yuan J. Single machine scheduling with release dates and rejection[J]. European Journal of Operational Research, 2009, 198(3):975-978.
[16] Lu L, Ng C, Zhang L. Optimal algorithms for single-machine scheduling with rejection to minimize the makespan[J]. International Journal of Production Economics, 2011, 130(2):153-158.
[17] Ou J, Zhong X, Li C. Faster algorithms for single machine scheduling with release dates and rejection[J]. Information Processing Letters, 2016, 116(8):503-507.
[18] Zhang L, Lu L. Parallel-machine scheduling with release dates and rejection[J]. 4OR-A Quarterly Journal of Operations Research, 2016, 14(2):165-172.
[19] Zhong X, Ou J. Improved approximation algorithms for parallel machine scheduling with release dates and job rejection[J]. 4OR-A Quarterly Journal of Operations Research, 2017, 15(4):387-406.
[20] Zhang Y, Ren J, Wang C. Scheduling with rejection to minimize the makespan[J]. Combinatorial Optimization and Applications, 2009:411-420.
[21] Li W, Li J, Zhang X, et al. Penalty cost constrained identical parallel machine scheduling problem[J]. Theoretical Computer Science, 2015, 607:181-192.
[22] Zhang L, Lu L, Yuan J. Single-machine scheduling under the job rejection constraint[J]. Theoretical Computer Science, 2010, 411(16-18):1877-1882.
[23] Jiang D, Tan J. Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines[J]. Theoretical Computer Science, 2016, 616:94-99.
[24] Zhong X, Ou J. Parallel machine scheduling with restricted job rejection[J]. Theoretical Computer Science, 2017, 690:1-11.
[25] Zhang X, Xu D, Du D, et al. Approximation algorithms for precedence-constrained identical machine scheduling with rejection[J]. Journal of Combinatorial Optimization, 2018, 35(1):318-330.
[26] Sengupta S. Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection[J]. Algorithms and Data Structures, 2003, 79-90.
[27] Engels D, Karger D, Kolliopoulos S, et al. Techniques for scheduling with rejection[J]. Journal of Algorithms, 2003, 49(1):175-191.
[28] 张峰, 范静. 工件可拒绝排序问题的线性松弛算法[J]. 上海第二工业大学学报, 2005, 22(5):13-20.
[29] 张峰, 唐国春. 工件可拒绝排序问题研究[J]. 同济大学学报:自然科学版, 2005, 34(1):116-119.
[30] Cao Z, Wang Z, Zhang Y, et al. On several scheduling problems with rejection or discretely compressible processing times[J]. Lecture Notes in Computer Science, 2006, 3959:90-98.
[31] Zhang S, Cao Z, Zhang Y. Scheduling with rejection to minimize the total weighted completion time[J]. ISORA, 2009, 9:111-114.
[32] Koulamas C, Panwalkar S. On the equivalence of single machine earliness/tardiness problems with job rejection[J]. Computers & Industrial Engineering, 2015, 87:1-3.
[33] 张峰. 具有就绪时间与先后约束的工件可拒绝排序[J]. 上海第二工业大学学报, 2009, 26(1):1-5.
[34] Bunde D. Scheduling on a single machine to minimize total flow time with job rejections[J]. Theory and Application, 2005, 562-572.
[35] Hall N, Potts C. Rescheduling for job unavailability[J]. Operations Research, 2010, 58(3):746-755.
[36] Wang D, Yin Y, Cheng T. Parallel-machine rescheduling with job unavailability and rejection[J]. Omega, 2018, 81:246-260.
[37] Wang D J, Liu F, Jin Y. A multi-objective evolutionary algorithm guided by directed search for dynamic scheduling[J]. Computers and Operations Research, 2017, 79:279-290.
[38] Shabtay D, Karhi S, Oron D. Multipurpose machine scheduling with rejection and identical job processing times[J]. Journal of Scheduling, 2015, 18(1):75-88.
[39] Cordone R, Hosteins P. A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization[J]. Computers and Operations Research, 2019, 102:130-140.
[40] Steiner G, Zhang, R. Revised delivery-time quotation in scheduling with tardiness penalties[J]. Operations Research, 2011, 59(6):1504-1511.
[41] Cordone R, Hosteins P, Righini G. A branch-and-bound algorithm for the prize-collecting singlemachine scheduling problem with deadlines and total tardiness minimization[J]. INFORMS Journal on Computing, 2018, 30(1):168-180.
[42] He Y, Min X. On-line uniform machine scheduling with rejection[J]. Computing, 2000, 65(1):1-12.
[43] Dósa G, He Y. Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines[J]. Computing, 2006, 76(1-2):149-164.
[44] Epstein L, Zebedat-Haider H. Online scheduling of unit jobs on three machines with rejection:A tight result[J]. Information Processing Letters, 2016, 116(3):252-255.
[45] Seiden S. Preemptive multiprocessor scheduling with rejection[J]. Theoretical Computer Science, 2001, 262(1-2):437-458.
[46] Epstein L, Noga J, Woeginger G. On-line scheduling of unit time jobs with rejection:Minimizing the total completion time[J]. Operations Research Letters, 2002, 30(6):415-420.
[47] Miao C, Zhang Y. On-line cheduling with rejection on identical parallel machines[J]. Journal of Systems Science & Complexity, 2006, 19(3):431-435.
[48] Liu S, Zhang Y. On-line scheduling of unit time jobs with rejection on uniform Machines[J]. Journal of Systems Science and Complexity, 2008, 21(1):114-118.
[49] Ma R, Yuan J. Online scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost[J]. Information Processing Letters, 2013, 113(17):593-598.
[50] 闵啸. 一特殊情形不可中断的两台可拒绝同型平行机在线排序问题[J] 数学的实践与认识, 2006, 36:163-169.
[51] 闵啸. 一特殊情形的三台可拒绝同型机在线排序问题[J]. 嘉兴学院学报, 2006, 18(3):44-47.
[52] Cao Q, Liu Z. Online scheduling with reassignment on two uniform machines[J]. Theoretical Computer Science, 2010, 411(31-33):2890-2898.
[53] Dósa G, Wang Y, Han X, et al. Online scheduling with rearrangement on two related machines[J]. Theoretical Computer Science, 2011, 412(8-10):642-653.
[54] Tan Z, Yu S. Online scheduling with reassignment[J]. Operations Research Letters, 2008, 36(2):250-254.
[55] Epstein L, Zebedat-Haider H. Online scheduling with rejection and withdrawal[J]. Theoretical Computer Science, 2011, 412(48):6666-6674.
[56] 闵啸, 孔祥庆. 两台可拒绝同型机半在线排序问题[J]. 运筹学学报, 2009, 13(1), 29-36.
[57] Min X, Liu J, Wang Y. Optimal Semi-online algorithm for scheduling with rejection on two uniform machines[J]. Journal of combinatorial optimization, 2011, 22(4):674-683.
[58] 闵啸, 刘静, 王玉青. 两台可中断同类机可拒绝半在线排序问题的近似算法[J]. 浙江大学学报:理学版, 2010, 37(5):519-523.
[59] 闵啸, 张玉才. 一个可中断两台可拒绝同型机半在线排序问题[J]. 浙江大学学报:理学版, 2007, 34(5):509-514.
[60] Min X, Wang Y, Liu J, et al. Semi-online scheduling on two identical machines with rejection[J]. Journal of Combinatorial Optimization, 2013, 26(3):472-479.
[61] Ikura Y, Gimple M. Efficient scheduling algorithms for a single batch processing machine[J]. Operations Research Letters, 1986, 5(2):61-65.
[62] 张玉忠, 曹志刚. 并行分批排序问题综述[J]. 数学进展, 2008, 37(4):392-408.
[63] Potts C, Kovalyov M. Scheduling with batching:a review[J]. European Journal of Operational Research, 2000, 120(2):228-249.
[64] 张玉忠, 苗翠霞. 复制法机器在分批排序问题中的应用[J]. 曲阜师范大学学报:自然科学版, 2004, 30(2):41-43.
[65] 王珍, 曹志刚, 张玉忠. 极小化最大完工时间及拒绝费用的单机可拒绝分批排序[J]. 曲阜师范大学学报:自然科学版, 2007, 33(2):35-38.
[66] Cao Z, Yang X. A PTAS for parallel batch scheduling with rejection and dynamic job arrivals[J]. Theoretical Computer Science, 2009, 410(27-29):2732-2745.
[67] Miao C, Zhang Y, Wang C. Bounded paralled-batch scheduling on unrelated parallel machines[J]. Lecture Notes in Computer Science, 2010, 6124:220-228.
[68] Lu L, Cheng T, Yuan J, et al. Bounded single-machine parallel-batch scheduling with release dates and rejection[J]. Computers and Operations Research, 2009, 36(10):2748-2751.
[69] 刘守鹏, 高明海, 张玉忠. 可拒绝的同类机在线排序(英文)[J]. 大学数学, 2012, 28(1):27-32.
[70] Brucker P, Gladky A, Hoogeveen H, et al. Scheduling a batching machine[J]. Journal of Scheduling, 1998, 1(1):31-54.
[71] Lu L, Zhang L, Yuan J. The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan[J]. Theoretical Computer Science, 2008, 396(1-3):283-289.
[72] Zhang X, Cai Z, Ren J. An unbounded batch scheduling with rejections[J]. Operations Research Transactions, 2009, 13(13):23-30.
[73] He C, Leung J, Lee K, et al. Scheduling a single machine with parallel batching to minimize makespan and total rejection cost[J]. Discrete Applied Mathematics, 2016, 204:150-163.
[74] Shabtay D. The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost[J]. European Journal of Operational Research, 2014, 233(1):64-74.
[75] Shabtay D, Gasper N. Two-machine flow-shop scheduling with rejection[J]. Computers Operations Research, 2012, 39(5):1087-1096.
[76] T'kindt V, Croce D. A note on "Two-machine flow-shop scheduling with rejection" and its link with flow-shop scheduling and common due date assignment[J]. Computers Operations Research, 2012, 39(12):3244-3246.
[77] Zhang L, Lu L, Li S. New results on two-machine flow-shop scheduling with rejection[J]. Journal of Combinatorial Optimization, 2016, 31(4):1493-1504.
[78] Dabiri M, Darestani S, Naderi B. Multi-machine flow shop scheduling problems with rejection using genetic algorithm[J]. International Journal of Services and Operations Management, 2006, 32(2):158-172.
[79] Zou J, Miao C. The single machine serial batch scheduling problems with rejection[J]. Operational Research, 2015, 16(2):211-221.
[80] Shabtay D, Oron D. Proportionate flow-shop scheduling with rejection[J]. Journal of the Operational Research Society, 2016, 67(5):752-769.
[81] Li S, Qian D. L, Chen, R. Proportionate flow shop scheduling with rejection[J]. Asia-Pacific Journal of Operational Research, 2017, 34(04):1-13.
[82] Kianfar K, Ghomi S, Karimi B. New dispatching rules to minimize rejection and tardiness costs in a dynamic flexible flow shop[J]. The International Journal of Advanced Manufacturing Technology, 2009, 45(7-8):759-771.
[83] Zhang L, Lu L, Yuan J. Two-machine open-shop scheduling with rejection to minimize the makespan[J]. Or Spectrum, 2016, 38(2):519-529.
[84] Imreh C, Noga J. Scheduling with machine cost[J]. Randomization and Approximation Techniques in Computer Science, 1999:168-176.
[85] Nagy-Györgya J, Imreh C. Online scheduling with machine cost and rejection[J]. Discrete Applied Mathematics, 2007, 155(18):2546-2554.
[86] Dósa G, He Y. Scheduling with machine cost and rejection[J]. Journal of Combinatorial Optimization, 2006, 12(4):337-350.
[87] Cheng Y, Sun S. Scheduling linear deteriorating jobs with rejection on a single machine[J]. European Journal of Operational Research, 2009, 194(1):18-27.
[88] Li S, Yuan J. Parallel-machine scheduling with deteriorating jobs and rejection[J]. Theoretical Computer Science, 2010, 411(40-42):3642-3650.
[89] 王成飞, 张玉忠, 柏庆国. 具有线性恶化效应的在线分批排序问题[J]. 运筹学学报, 2011, 15(3):107-114.
[90] Zhang M, Luo C. Parallel-machine scheduling with deteriorating jobs, rejection and a fixed non-availability interval[J]. Applied Mathematics and Computation, 2013, 224:405-411.
[91] Feng Q, Fan B, Li S, et al. Two-agent scheduling with rejection on a single machine[J]. Applied Mathematical Modelling, 2015, 39(3-4):1183-1193.
[92] Li W, Chai X, Song Y. A best possible on-line algorithm for scheduling on uniform parallelbatch machines[J]. Theoretical Computer Science, 2018, 740:68-75.
[93] Shabtay D, Gaspar N, Yedidsion L. A bicriteria approach to scheduling a single machine with job rejection and positional penalties[J]. Journal of Combinatorial Optimization, 2012, 23(4):395-424.
[94] Neto, R, Filho, M. An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed[J]. Computers & Operations Research, 2011, 38(9):1286-1293.
[95] Lee Y, Jeong C, Moon C. Advanced planning and scheduling with outsourcing in manufacturing supply chain[J]. Computers & Industrial Engineering, 2002, 43(1):351-374.
[96] Lee I, Sung C. Single machine scheduling with outsourcing allowed[J]. International Journal of Production Economics, 2008, 111(2):623-634.
[97] Lee I, Sung C. Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed[J]. European Journal of Operational Research, 2008, 186(3):931-952.
[98] Qi X. Coordinated logistics scheduling for In-House production and outsourcing[J]. IEEE Transactions on Automation Science and Engineering, 2008, 5(1):188-192.
[99] Qi X. Outsourcing and production scheduling for a two-stage flow shop[J]. International Journal of Production Economics, 2010, 129(1):43-50.
[100] Chung D. Choi B. Outsourcing and scheduling for two-machine ordered flow shop scheduling problems[J]. European Journal of Operational Research, 2013, 226(1):46-52.
[101] Lu L, Zhang L, Zhang J, Zuo L. Single machine scheduling with outsourcing under different fill rates or quantity discount rates[J]. Asia-Pacific Journal of Operational Research, 2020, 37(1):1950033.