工件可拒绝排序问题综述

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

Abstract

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

CLC Number:

O221.7

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

References

[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.

A survey on job scheduling with rejection

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[2]	BAO Xiaoguang, LU Chao, HUANG Dongmei, YU Wei. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[3]	REN Jianfeng, TIAN Xiaoyun. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[4]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[5]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[6]	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.
[7]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[8]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[9]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[10]	LIU Yafeng. Two optimization problems in wireless communication system design and related optimization methods [J]. Operations Research Transactions, 2019, 23(3): 47-62.
[11]	ZHU Xihua, CHANG Qingqing, JIANG Bo. Introduction to high-order optimization methods [J]. Operations Research Transactions, 2019, 23(3): 63-76.
[12]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[13]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[14]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.
[15]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.