并行分批排序综述

doi:10.12005/orms.2020.0027

摘要/Abstract

摘要： 并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。

关键词: 并行分批排序, 时间复杂性, 启发式算法, 智能算法, 近似算法, 综述

Abstract: Parallel batch scheduling arises from semiconductor manufacturing. In this type of scheduling, jobs are processed in batch and the batch processing machine is capable of processing up to B jobs simultaneously as a batch. The processing time of a batch is equal to the longest processing time of the jobs in the batch. Firstly, achievements of parallel batch scheduling with different traditional machine environments and objective functions are introduced, where machine environments mainly refer to single machine and parallel machines, and objective functions are makespan, total completion time, maximum lateness, number of tardy jobs, total tardiness and maximum tardiness; then 16 new problems derived from general problems by combining with new characteristics are classified, and they are parallel batch scheduling problems with non-identical job sizes, problems with multi-objectives or new objectives, problems subject to precedence constraints, problems with transportation time, discretely controllable processing time, deteriorating jobs, learning effect, forbidden intervals, due windows, energy consumption consideration, rejection, bathing cost, job processing time compatibilities, two-agent, rescheduling and semi-continuous respectively; and research directions of parallel batch scheduling in the future are looked forward to at last.

Key words: parallel batch scheduling, time complexity, heuristic, intelligent algorithm, approximation algorithm, review

中图分类号:

O226

井彩霞, 吴瑞强, 贾兆红. 并行分批排序综述[J]. 运筹与管理, 2020, 29(1): 223-239.

JING Cai-xia, WU Rui-qiang, JIA Zhao-hong. A Review of Parallel Batch Scheduling[J]. Operations Research and Management Science, 2020, 29(1): 223-239.

参考文献

[1] 张玉忠,曹志刚.并行分批排序问题综述[J].数学进展,2008,37(4):392-408.
[2] 李文华.关于分批排序问题的研究[D].河南:郑州大学,2006.
[3] 石永强.若干批处理机排序与装箱问题的算法研究[D].浙江:浙江大学,2005.
[4] 唐国春,张峰,罗守诚,刘丽丽.现代排序论[M].上海科学普及出版社,2003.
[5] 井彩霞,钱省三,马良.极小化最大完工时间的批到达同时加工排序问题[J].上海理工大学学报,2009,31(1):54-58.
[6] Potts C N, Van Wassenhove L N. Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity[J]. Journal of the Operational Research Society, 1992. 395-406.
[7] Ghosh J B, Gupta J N D. Batch scheduling to minimize maximum lateness[J]. Operations Research Letters, 1997, 21(2): 77-80.
[8] Ghazvini F J, Dupont L. Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes[J]. International Journal of Production Economics, 1998, 55(3): 273-280.
[9] Sung C, Choung Y. Minimizing makespan on a single burn-in oven in semiconductor manufacturing[J]. European Journal of Operational Research, 2000, 120(3): 559-574.
[10] Li S. Parallel batch scheduling with nested processing set restrictions[J]. Theoretical Computer Science, 2017, 689: 117-125.
[11] Wang J, Fan G, Zhang Y, et al. Two-agent scheduling on a single parallel-batching machine with equal processing time and nonidentical job sizes[J]. European Journal of Operational Research, 2017, 258(2): 478-490.
[12] Qi X, Yuan J. A further study on two-agent scheduling on an unbounded serial-batch machine with batch delivery cost[J]. Computers & Industrial Engineering, 2017, 111: 458-462.
[13] Pei J, Pardalos P M, Liu X, et al. Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan[J]. European Journal of Operational Research, 2015, 244(1): 13-25.
[14] Ikura Y, Gimple M. Efficient scheduling algorithms for a single batch processing machine[J]. Operations Research Letters, 1986, 5(2): 61-65.
[15] Lee C Y, Uzsoy R, Martin-vega L A. Efficient algorithms for scheduling semiconductor burn-in operations[J]. Operations Research, 1992, 40(4): 764-775.
[16] Brucker P, Gladky A, Hoogeveen H, et al. Scheduling a batching machine[J]. Journal of Scheduling, 1998, 1(1): 31-54.
[17] Webster S, Baker K R. Scheduling groups of jobs on a single machine[J]. Operations Research, 1995, 43(4): 692-703.
[18] Potts C N, Kovalyov M Y. Scheduling with batching: a review[J]. European Journal of Operational Research, 2000, 120(2): 228-249.
[19] Baptiste P. Batching identical jobs[J]. Mathematical Methods of Operations Research, 2000, 52(3): 355-367.
[20] 张玉忠.分批排序问题研究[C].中国运筹学会第七届学术交流会论文集 (上卷),2004.
[21] Mathirajan M, Sivakumar A I. A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor[J]. International Journal of Advanced Manufacturing Technology, 2006, 29(9-10): 990-1001.
[22] Lee C Y. Minimizing makespan on a single batch processing machine with dynamic job arrivals[J]. International Journal of Production Research, 1999, 37(1): 219-236.
[23] Poon C K, Zhang P. Minimizing makespan in batch machine scheduling[J]. Algorithmica, 2004, 39(2): 155-174.
[24] Yuan J, Liu Z, Ng C T, et al. The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan[J]. Theoretical Computer Science, 2004, 320(2-3): 199-212.
[25] 张玉忠.带批处理的排序问题[D].北京:中国科学院应用数学研究所,1996.
[26] Liu Z, Yu W. Scheduling one batch processor subject to job release dates[J]. Discrete Applied Mathematics, 2000, 105(1): 129-136.
[27] Deng X, Poon C, Zhang Y. Approximation algorithms in batch processing[J]. Algorithms and Computation, 1999. 153-162.
[28] 孙锦萍,李曙光,张少强.一个求分批排序最小时间表长的多项式时间近似方案[J].山东大学学报:理学版,2004,39(2):16-19.
[29] Li S, Li G, Wang X, et al. Minimizing makespan on a single batching machine with release times and non-identical job sizes[J]. Operations Research Letters, 2005, 33(2): 157-164.
[30] 李曙光,杨振光,亓兴勤.极小化最大完工时间的单机分批加工问题[J].运筹学学报,2006,10(1):31-37.
[31] 姜冠成.带到达时间分批排序问题的数学模型[J].苏州大学学报:自然科学版,2005,21(2):22-27.
[32] 曹国梅.一类无界的不相容工件族分批排序加权总完工时间问题[J].常熟理工学院学报,2009,23(4):22-24.
[33] Deng X, Feng H, Zhang P, et al. Minimizing mean completion time in a batch processing system[J]. Algorithmica, 2004, 38(4): 513-528.
[34] Li S, Li G, Zhao H. A linear time approximation scheme for minimizing total weighted completion time of unbounded batch scheduling[J]. Operations Research Transactions, 2004, 8(4): 27-32.
[35] Liu Z, Cheng T C E. Approximation schemes for minimizing total(weighted)completion time with release dates on a batch machine[J]. Theoretical computer science, 2005, 347(1): 288-298.
[36] Liu L, Ng C T, Cheng T C E. On scheduling unbounded batch processing machine(s)[J]. Computers & Industrial Engineering, 2010, 58(4): 814-817.
[37] Chandru V, Lee C Y, Uzsoy R. Minimizing total completion time on batch processing machines[J]. International Journal of Production Research, 1993, 31(9): 2097-2121.
[38] Poon C K, Yu W. On minimizing total completion time in batch machine scheduling[J]. International Journal of Foundations of Computer Science, 2004, 15(4): 593-607.
[39] Cai M, Deng X, Feng H, et al. A PTAS for minimizing total completion time of bounded batch scheduling[J]. Lecture Notes in Computer Science, 2002, 2337. 304-314.
[40] Chandru V, Lee C Y, Uzsoy R. Minimizing total completion time on a batch processing machine with job families[J]. Operations Research Letters, 1993, 13(2): 61-65.
[41] Hochbaum D S, Landy D. Scheduling semiconductor burn-in operations to minimize total flowtime[J]. Operations Research, 1997, 45(6): 874-885.
[42] Uzsoy R, Yang Y. Minimizing total weighted completion time on a single batch processing machine[J]. Production and Operations Management, 1997, 6(1): 57-73.
[43] Azizoglu M, Webster S. Scheduling a batch processing machine with incompatible job families[J]. Computers & Industrial Engineering, 2001, 39(3): 325-335.
[44] Liu L, Tang G. A branch and bound approach and heuristic algorithms for scheduling a batching machine[J]. Operations Research Transactions, 2004, 8(3): 39-44.
[45] 张召生,刘家壮.大规模集成电路预烧作业中分批排序问题的数学模型[J].中国管理科学,2003,11(4):32-36.
[46] 苗翠霞,张玉忠.极小化加权总完工时间的分批排序问题[J].运筹学学报,2005,9(2):82-86.
[47] 张玲玲,张玉忠,张智广.一种极小化Σw_jC_j的分批排序问题的算法[J].洛阳大学学报,2006,21(4):43-45.
[48] Lenstra J K, Kan A H G R, Brucker P. Complexity of machine scheduling problems[J]. Annals of Discrete Mathematics, 1977, 1: 343-362.
[49] 张玉忠,苗翠霞.复制法及其在分批排序问题中的应用[J].曲阜师范大学学报:自然科学版,2004,30(2):41-43.
[50] 丁际环,刘丽丽,姜宝山,等.1｜B,r_j∈{0,r}｜ΣC_j问题的复杂性及近似算法[J].曲阜师范大学学报: 自然科学版,2000,26(4):19-21.
[51] Chang P, Chen Y, Wang H. Dynamic scheduling problem of batch processing machine in semiconductor burn-in operations[C]//International Conference on Computational Science and Its Applications. Berlin: Springer, 2005. 172-181.
[52] Deng X, Feng H, Li G, et al. A PTAS for semiconductor burn-in scheduling[J]. Journal of Combinatorial Optimization, 2005, 9(1): 5-17.
[53] 任建锋,张玉忠.问题Pm｜r_j,B｜SC_j的PTAS算法[C].中国运筹学会第七届学术交流会论文集(下卷),2004.1149-1155.
[54] 苗翠霞,张玉忠.两个分批排序问题的 NP-完备性证明[J].曲阜师范大学学报:自然科学版,2008,34(4):1-5.
[55] Cheng T C E, Liu Z, Yu W. Scheduling jobs with release dates and deadlines on a batch processing machine[J]. IIE Transactions, 2001, 33(8): 685-690.
[56] Uzsoy R. Scheduling batch processing machines with incompatible job families[J]. International Journal of Production Research, 1995, 33(10): 2685-2708.
[57] 李文华,王炳顺.分批排序问题中最优解仅分一批的判定[J].河南科学,2007,25(1):14-16.
[58] Cabo M, Possani E, Potts C N, et al. Split-merge: using exponential neighborhood search for scheduling a batching machine[J]. Computers & Operations Research, 2015, 63: 125-135.
[59] Wang C, Uzsoy R. A genetic algorithm to minimize maximum lateness on a batch processing machine[J]. Computers & Operations Research, 2002, 29(12): 1621-1640.
[60] Zhang S, Ma X. An efficient PTAS for semiconductor burn-in scheduling with release dates to minimize maximum delivery time[J]. Mathematica Applicata, 2006, 19(2): 374-380.
[61] Liu Z, Yuan J, Cheng T C E. On scheduling an unbounded batch machine[J]. Operations Research Letters, 2003, 31(1): 42-48.
[62] Jolai F. Minimizing number of tardy jobs on a batch processing machine with incompatible job families[J]. European Journal of Operational Research, 2005, 162(1): 184-190.
[63] Li S, Chen R. Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs[J]. Computers & Industrial Engineering, 2014, 73: 5-10.
[64] 王春香,王曦峰.单机有界分批排序[J].齐鲁工业大学学报:自然科学版,2014,28(1):48-50.
[65] 刘丽丽,任韩,唐国春.有公共交货期的单机分批排序问题[J].重庆师范大学学报:自然科学版,2017,34(2):1-5.
[66] Li C L, Lee C Y. Scheduling with agreeable release times and due dates on a batch processing machine[J]. European Journal of Operational Research, 1997, 96(3): 564-569.
[67] 王曦峰,王春香.单机无界分批排序问题研究[J].佛山科学技术学院学报:自然科学版,2014,(3):21-23.
[68] Mehta S V, Uzsoy R. Minimizing total tardiness on a batch processing machine with incompatible job families[J]. IIE Transactions, 1998, 30(2): 165-178.
[69] 张玉忠,王忠志,王长钰.分批排序的 “转换引理” 及其应用[J].系统科学与数学,2002,22(3):328-333.
[70] 刘丽丽,张峰.机器容量无限的同型机分批排序问题[J].上海第二工业大学学报,2013,30(3):197-201.
[71] Li S, Li G, Wang X. Minimizing total weighted completion time on parallel unbounded batch machines[J]. Journal of Software, 2006, 17(10): 2063-2068.
[72] 李曙光,李国君,赵洪銮.极小化完工时间和的有界批调度问题[J].应用数学,2006,19(2):446-454.
[73] Miao C, Zhang Y, Ren J. Minimizing total weighted completion time on uniform machines with unbounded batch[J]. Lecture Notes in Operations Research, 2009, 402-408.
[74] 田乐,赵传立.极小化总完工时间的同时加工排序[J].数学的实践与认识,2009,(20):100-105.
[75] 苗翠霞,张玉忠,王成飞.无关机上极小化求和问题的平行分批排序[J].运筹学学报,2010,(4):11-20.
[76] 李海霞,朱路宁,赵晟珂.机器带准备时间的同类机分批排序算法[J].大学数学,2011,27(4):122-127.
[77] Li S, Li G, Zhang S. Minimizing maximum lateness on identical parallel batch processing machines[J]. Computing and Combinatorics, 2004. 229-237.
[78] Liu L, Ng C T, Cheng T C E. Scheduling jobs with release dates on parallel batch processing machines[J]. Discrete Applied Mathematics, 2009, 157(8): 1825-1830.
[79] 刘丽丽,张峰.机器容量无限的同型机分批排序问题[J].上海第二工业大学学报,2013,30(3):197-201.
[80] Mnch L, Balasubramanian H, Fowler J W, et al. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times[J]. Computers & Operations Research, 2005, 32(11): 2731-2750.
[81] Mnch L, Almeder C. Ant colony optimization for scheduling jobs with incompatible families on parallel batch machines[C]//Proceedings 4th multidisciplinary international conference on scheduling: Theory and applications (MISTA), Dublin, Ireland, 2009. 106-114.
[82] Bilyk A, M?nch L, Almeder C. Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics[J]. Computers & Industrial Engineering, 2014, 78: 175-185.
[83] 成岗,鲁习文.含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性[J].运筹学学报,2003,7(4):86-96.
[84] Tan Y, M?nch L, Fowler J W. A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines[J]. Journal of Scheduling, 2017. 1-18.
[85] Amin-naseri M R, Beheshti-nia M A. Hybrid flow shop scheduling with parallel batching[J]. International Journal of Production Economics, 2009, 117(1): 185-196.
[86] Ham A M, Cakici E. Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches[J]. Computers & Industrial Engineering, 2016, 102: 160-165.
[87] Uzsoy R. Scheduling a single batch processing machine with nonidentical job sizes[J]. International Journal of Production Research, 1994, 32(7): 1615-1635.
[88] Zhang G, Cai X, Lee C Y, Wong C K. Minimizing makespan on a single batch processing machine with nonidentical job sizes[J]. Naval Research Logistics, 2001, 48: 226-240.
[89] Dupont L, Dhaenens-flipo C. Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure[J]. Computers & Operations Research, 2002, 29(7): 807-819.
[90] Kashan A H, Karimi B, Ghomi S M T F. A note on minimizing makespan on a single batch processing machine with nonidentical job sizes[J]. Theoretical Computer Science, 2009, 410(27-29): 2754-2758.
[91] Melouk S, Damodaran P, Chang P Y. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing[J]. International Journal of Production Economics, 2004, 87(2): 141-147.
[92] Kashan A H, Karimi B, Jolai F. Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non- identical job sizes[J]. International Journal of Production Research, 2006, 44(12): 2337-2360.
[93] Damodaran P, Manjeshwar P K, Srihari K. Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms[J]. International Journal of Production Economics, 2006, 103(2): 882-891.
[94] Cheng B, Li K, Chen B. Scheduling a single batch-processing machine with non-identical job sizes in fuzzy environment using an improved ant colony optimization[J]. Journal of Manufacturing Systems, 2010, 29(1): 29-34.
[95] Chen H, Du B, Huang G Q. Scheduling a batch processing machine with non-identical job sizes: a clustering perspective[J]. International Journal of Production Research, 2011, 49(19): 5755-5778.
[96] Jia Z, Leung J Y T. An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes[J]. Computers & Operations Research, 2014, 46: 49-58.
[97] Cheng T C E, Kovalyov M Y. Single machine batch scheduling with deadlines and resource dependent processing times[J]. Operations Research Letters, 1995, 17(5): 243-249.
[98] Koh S G, Koo P H, Kim D C, et al. Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families[J]. International Journal of Production Economics, 2005, 98(1): 81-96.
[99] 程八一,陈华平,王栓狮.模糊制造系统中的不同尺寸工件单机批调度优化[J].计算机集成制造系统,2008,14(7):1322-1328.
[100] Chou F D, Chang P C, Wang H. A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2006, 31(3-4): 350-359.
[101] Xu R, Chen H, Li X. Makespan minimization on single batch-processing machine via ant colony optimization[J]. Computers & Operations Research, 2012, 39 (3): 582-593.
[102] 吴翠连.极小化分批排序问题的近似算法[D].山东:曲阜师范大学,2005.
[103] 张玉忠,柏庆国,徐健腾.工件有尺寸且分两批到达的单机分批排序[J].运筹学学报,2006,10(4):99-105.
[104] 马冉,张玉忠. 工件有优先约束和尺寸的单机分批排序问题[J].滨州学院学报,2006,22(3):18-22.
[105] Chang P Y, Damodaran P, Melouk S. Minimizing makespan on parallel batch processing machines[J]. International Journal of Production Research, 2004, 42(19), 4211-4220.
[106] Damodaran P, Chang P Y. Heuristics to minimize makespan of parallel batch processing machines[J]. International Journal of Advanced Manufacturing Technology, 2008, 37(9-10): 1005-1013.
[107] Shao H, Chen H, Huang G, et al. Minimizing makespan for parallel batch processing machines with non-identical job sizes using neural nets approach[C]//Proceedings of the 3rd IEEE Conference on Industrial Electronics and Applications. Piscataway: IEEE Press, 2008. 1921-1924.
[108] Kashan A H, Karimi B, Jenabi M. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes[J]. Computers & Operations Research, 2008, 35(4): 1084-1098.
[109] Damodaran P, Hirani N S, Velez-gallego M C. Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithms[J]. European Journal of Industrial Engineering, 2009, 3(2): 187-206.
[110] 杜冰,陈华平,杨勃,李小林.聚类视角下的差异工件平行机批调度问题[J].管理科学学报,2011,14(12):27-37.
[111] Jia Z, Leung J Y T. A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes[J]. European Journal of Operations Research, 2015, 240(3): 649-665.
[112] 张鑫,刘景昭,张玉忠.工件尺寸不同的平行机分批排序[J].曲阜师范大学学报:自然科学版,2005,31(3):10-12.
[113] Chen H, Du B, Huang G Q. Metaheuristics to minimize makespan on parallel batch processing machines with dynamic job arrivals[J]. International Journal of Computer Integrated Manufacturing, 2010, 23(10): 942-956.
[114] 吴翠连,陈俊.有尺寸的同型机分批排序问题的近似算法[J].运筹与管理,2013,(1):77-82.
[115] Zhou S, Chen H, Li X. Distance matrix based heuristics to minimize makespan of parallel batch processing machines with arbitrary job sizes and release times[J]. Applied Soft Computing, 2017, 52: 630-641.
[116] Li X, Huang Y, Tan Q, et al. Scheduling unrelated parallel batch processing machines with non-identical job sizes[J]. Computers & Operations Research, 2013, 40(12): 2983-2990.
[117] Arroyo J E C, Leung J Y T. Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times[J]. Computers & Operations Research, 2017, 78: 117-128.
[118] Damodaran P, Diyadawagamage D A, Ghrayeb O, et al. A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines[J]. International Journal of Advanced Manufacturing Technology, 2012, 58(9-12):1131-1140.
[119] Jia Z, Li K, Leung J Y T. Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities[J]. International Journal of Production Economics, 2015, 169: 1-10.
[120] 贾兆红,李晓浩,温婷婷,李龙澍.不同容量平行机下差异工件尺寸的批调度算法[J].控制与决策, 2015,30(12):2145-2152.
[121] Zhou S, Liu M, Chen H, et al. An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes[J]. International Journal of Production Economics, 2016, 179: 1-11.
[122] Xu S, Bean J C. A genetic algorithm for scheduling parallel non-identical batch processing machines[C]//Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling, IEEE, 2007, 143-150.
[123] Wang H, Chou F D. Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics[J]. Expert Systems with Applications, 2010, 37: 1510-1521.
[124] Jia Z, Li X, Leung J Y T. Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities[J]. Future Generation Computer Systems, 2017, 67: 22-34.
[125] Li S. Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities[J]. European Journal of Operational Research, 2017, 263(3): 815-826.
[126] Li S. Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan[J]. European Journal of Operational Research, 2017, 260(1): 12-20.
[127] Arroyo J E C, Leung J Y T. An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times[J]. Computers & Industrial Engineering, 2017, 105: 84-100.
[128] 张召生,孔淑兰,马建华.求解多目标单机分批排序问题[J].山东大学学报:理学版,2004,39(2):50-55.
[129] 李文华.主指标为最大延迟的主次指标分批排序问题[J].数学的实践与认识,2006,36(5):285-289.
[130] 李文华.一类具有三重指标的分批排序问题[J].工程数学学报,2007,24(1):183-186.
[131] He C, Lin Y, Yuan J. Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan[J]. Theoretical Computer Science, 2007, 381(1-3): 234-240.
[132] 焦峰亮,王磊,张玉忠.一种特殊的单机双目标分批排序问题[J].洛阳理工学院学报:社会科学版,2007,22(4):29-32.
[133] 焦峰亮,曹志刚,张玉忠.两类单机双目标分批排序问题研究[C].中国企业运筹学学术交流大会论文集,2008.
[134] Liu L, Ng C T, Cheng T C E. On the complexity of bi-criteria scheduling on a single batch processing machine[J]. Journal of Scheduling, 2010, 13(6): 629-638.
[135] 李小衬.单机不相容双目标最优批排序研究[J].长江大学学报:自然科学版,2013,10(13):3-5.
[136] Geng Z, Yuan J. A note on unbounded parallel-batch scheduling[J]. Information Processing Letters, 2015, 115(12): 969-974.
[137] Geng Z, Yuan J. Pareto optimization scheduling of family jobs on a p-batch machine to minimize makespan and maximum lateness [J]. Theoretical Computer Science, 2015, 570: 22-29.
[138] Zhang R, Chang P C, Song S, et al. A multi-objective artificial bee colony algorithm for parallel batch-processing machine scheduling in fabric dyeing processes[J]. Knowledge-Based Systems, 2017, 116: 114-129.
[139] 张玉忠,王琳.一类新的分批排序问题的 NP 完备性证明[J].系统科学与数学,2005,25(1):13-17.
[140] Cheng T C E, Yuan J, Yang A. Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times[J]. Computers & Operations Research, 2005, 32(4): 849-859.
[141] 邹娟,张玉忠.带有链优先序的分批排序问题[J].应用数学与计算数学学报,2006,20(1):19-24.
[142] 马冉,张玉忠,邹娟.带有链优先约束的分批排序[J].滨州学院学报,2007,23(6): 26-29.
[143] 卜宪敏,曹丽霞,刘层层.“合成链”算法与一类链优先约束的单机分批排序问题[J].洛阳理工学院学报:自然科学版,2012,22(4):79-83.
[144] 刘伟.带链优先约束的单机分批排序问题[J].高教学刊,2015,(9):49-50.
[145] Tang L, Gong H. The coordination of transportation and batching scheduling[J]. Applied Mathematical Modelling, 2009, 33(10): 3854-3862.
[146] 朱洪利,王迅娣,张玉忠.供应链管理中的一类分批调度问题[J].曲阜师范大学学报:自然科学版,2010,36(4):41-44.
[147] Zhu H, Leus R, Zhou H. New results on the coordination of transportation and batching scheduling[J]. Applied Mathematical Modelling, 2016, 40(5): 4016-4022.
[148] 刘勇,王成飞,张玉忠.工件带运输时间的单机分批排序问题[J].洛阳理工学院学报:社会科学版,2007,22(4):24-28.
[149] Lu L, Yuan J. Unbounded parallel batch scheduling with job delivery to minimize makespan[J]. Operations Research Letters, 2008, 36(4): 477-480.
[150] Li S, Yuan J, Fan B. Unbounded parallel-batch scheduling with family jobs and delivery coordination[J]. Information Processing Letters, 2011, 111(12): 575-582.
[151] 柏孟卓,唐国春.加工时间可控的同时加工排序问题[J].上海第二工业大学学报,2006,23(1):15-20.
[152] 王磊,张玉忠.加工时间离散可控的分批排序问题[J].曲阜师范大学学报:自然科学版,2008,34(3):37-41.
[153] Qi X, Zhou S, Yuan J. Single machine parallel-batch scheduling with deteriorating jobs[J]. Theoretical Computer Science, 2009, 410(8-10): 830-836.
[154] Miao C, Zhang Y, Cao Z. Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs[J]. Information Processing Letters, 2011, 111(16): 798-803.
[155] Li S, Ng C T, Cheng T C E, et al. Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan[J]. European Journal of Operational Research, 2011, 210(3): 482-488.
[156] Zou J, Miao C. Parallel batch scheduling of deteriorating jobs with release dates and rejection[J]. The Scientific World Journal, 2014, 2014: 1-7.
[157] 余英,罗永超,程明宝.带分批的一类具有恶化加工时间的排序问题的算法研究[J].湘潭大学自然科学学报,2013,35(2):14-16.
[158] Miao C, Xia Y, Zhang Y, et al. Batch scheduling with deteriorating jobs to minimize the total completion time[J]. Journal of the Operations Research Society of China, 2013, 1(3): 377-383.
[159] 韩翔凌.工件具有学习效应的分批排序问题[J].廊坊师范学院学报:自然科学版,2010,10(6):14-17.
[160] 余英,卢圳,曾春花.一类具有与位置有关的学习效应的分批排序问题[J].凯里学院学报,2015,33(6):14-16.
[161] Yuan J, Qi X, Lu L, et al. Single machine unbounded parallel-batch scheduling with forbidden intervals[J]. European Journal of Operational Research, 2008, 186(3): 1212-1217.
[162] 齐祥来,李展,原晋江.具有到达时间和禁用区间的单机平行批排序[J].郑州大学学报:理学版,2008,40(1):23-26.
[163] Zhao H, Li G. Unbounded batch scheduling with a common due window on a single machine[J]. Journal of Systems Science and Complexity, 2008, 21(2): 296.
[164] 韩国勇,赵洪銮,刘浩,等.交货期窗口待定的有界同时加工排序问题的最优算法[J].山东大学学报 (理学版),2012,47(3):77-80.
[165] 赵洪銮,韩国勇,张志军.最小化提前和延误惩罚的批处理问题[J].控制理论与应用,2012,29(4):519-523.
[166] 李文华,农庆琴,陈铁生.具有相同批容量和相同工期的单机准时分批排序问题[J].数学的实践与认识,2013,43(24):158-163.
[167] Mouzon G, Yildirim M B. A framework to minimize total energy consumption and total tardiness on a single machine[J]. International Journal of Sustainable Engineering, 2008, 1(2): 105-116.
[168] Yildirim M B, Mouzon G. Single-machine sustainable production planning to minimizing total energy consumption and total completion time using a multiple objective genetic algorithm[J]. IEEE Transactions on Engineering Management, 2012, 59(4): 585-597.
[169] Shrouf F, Ordieres-mere J, Garcia-sanchez A, Ortega-mier M. Optimizing the production scheduling of a single machine to minimize total energy consumption costs[J]. Journal of Cleaner Production, 2014, 67(6): 197-207.
[170] Liu C, Yang J, Lian J, Li W, Evans S, Yin Y. Sustainable performance oriented operational decision-making of single machine systems with deterministic product arrival time[J]. Journal of Cleaner Production, 2014, 85: 318-330.
[171] Che A, Zeng Y, Lyu K. An efficient greedy insertion heuristic for energy conscious single machine scheduling problem under time-of-use electricity tariffs[J]. Journal of Cleaner Production, 2016, 129: 565-577.
[172] Cheng J, Chu F, Chu C, et al. Bi-objective optimization of single-machine batch scheduling under time-of-use electricity prices[J]. RAIRO-Operations Research, 2016, 50(4): 715-732.
[173] Wang S, Liu M, Chu F, Chu C. Bi-objective optimization of a single machine batch scheduling problem with energy cost consideration[J]. Journal of Cleaner Production, 2016, 137: 1205-1215.
[174] Moon J Y, Shin K, Park J. Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency[J]. International Journal of Advanced Manufacturing Technology, 2013, 68(1): 523-535.
[175] Jia Z, Zhang Y, Leung J Y T, Li K. Bi-criteria ant colony optimization algorithm for minimizing makespan and energy consumption on parallel batch machines[J]. Applied Soft Computing, 2017, 55: 226-237.
[176] Luo H, Du B, Huang G Q, Chen H, Li X. Hybrid flow shop scheduling considering machine electricity consumption cost[J]. International Journal of Production Economics, 2013, 146(2): 423-439.
[177] 王珍,曹志刚,张玉忠.工件可拒绝的单机分批排序问题[C]. 第八届中国青年运筹信息管理学者大会论文集,2006.147-156.
[178] 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.
[179] Lu L, Cheng T C E, Yuan J, et al. Bounded single-machine parallel-batch scheduling with release dates and rejection[J]. Computers & operations research, 2009, 36(10): 2748-2751.
[180] 翟大伟.一种工件可拒绝的有界批量分批排序问题研究[J].枣庄学院学报,2010,(5):36-38.
[181] 李修倩,冯好娣,孙铮.最小化完成时间和加惩罚值和的批调度问题[J].计算机研究与发展,2013,50(8):1700-1709.
[182] He C, Leung J Y T, 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.
[183] Jia Z, Pei M, Leung J Y T. Multi-objective ACO algorithms to minimize the makespan and the total rejection cost on BPMs with arbitrary job weights[J]. International Journal of Systems Science, 2017, 48(16):3542-3557.
[184] 张喆,冯琪.两个带有分批费用的单机平行分批排序问题[J].佛山科学技术学院学报:自然科学版,2011,29(4):8-10.
[185] 张喆,冯琪,李文华.带有分批费用的容量有界的单机平行分批排序问题[J].数学的实践与认识,2014,44(21):192-196.
[186] 张喆,李文华.最小化总完工时间与分批费用之和的有界分批排序问题[J].数学的实践与认识,2011,41(21):93-97.
[187] 张喆,李文华.两个带有分批费用的平行分批排序问题的算法[J].工程数学学报,2013,30(4):629-632.
[188] Bellanger A, Janiak A, Kovalyov M Y, et al. Scheduling an unbounded batching machine with job processing time compatibilities[J]. Discrete Applied Mathematics, 2012, 160(1): 15-23.
[189] Li S, Cheng T C E, Ng C T, et al. Single-machine batch scheduling with job processing time compatibility[J]. Theoretical Computer Science, 2015, 583: 57-66.
[190] Feng Q, Yuan J, Liu H, et al. A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives[J]. Applied Mathematical Modelling, 2013, 37(10): 7071-7076.
[191] Tang L, Zhao X, Liu J, et al. Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine[J]. European Journal of Operational Research, 2017, 263, 401-411.
[192] 郭晓.分批排序的重新排序[D].河南:河南工业大学,2011.
[193] Xu X, Mu Y, Guo X, et al. Rescheduling to minimize total completion time under a limit time disruption for the parallel batch[J]. Chinese Quarterly Journal of Mathematics, 2015, (2): 274-279.
[194] Tang L, Zhao Y. Scheduling a single semi-continuous batching machine[J]. Omega, 2008, 36(6): 992-1004.
[195] 赵玉芳.链式约束下的一种半连续型批处理机调度问题[J].沈阳师范大学学报:自然科学版,2010,28(3):335-338.
[106] 吕绪华,尹婷,彭志凯.钢铁生产中管坯加热的单机连续型批调度策略研究[J].武汉科技大学学报:自然科学版,2011,34(5):321-324.
[105] 王松丽,赵玉芳,崔苗苗.带有释放时间的半连续型批处理机调度问题[J].重庆师范大学学报:自然科学版,2012,29(2):16-23.