单机单转包商调度与外包联合优化问题的改进启发式算法

doi:10.12005/orms.2017.0259

摘要/Abstract

摘要： 针对以总完工时间与总外包费用加权和为优化目标、总外包费用不超过给定上限的单机单转包商调度与外包联合优化问题,设计出一种改进的剔除型启发式算法。该算法通过运用动态规划技术求解新的辅助问题来获取初始外包工件集,并引入判定条件提前从初始外包工件集中剔除特定工件。为满足对总外包费用的上限约束,还利用新型的启发式筛选次序族逐一确定从当前外包工件集中剔除的工件。在仿真实验中,通过生成大量的测试算例,对比分析了改进算法与另2种已报道算法在求解质量、计算时间上的表现情况。实验结果表明所提出的改进算法在解的整体质量上具备显著的比较优势,并且能在5.6秒内完成对工件总数为1500的测试算例的求解。

关键词: 生产调度, 启发式算法, 动态规划, 外包, 单机

Abstract: This paper considers the single-machine single-subcontractor scheduling and outsourcing integrated optimization problem, where the objective is to minimize the weighted sum of the total completion time and total outsourcing cost, while the total outsourcing cost is subject to an upper limit. An improved removal heuristic (IRH) algorithm is developed to solve this problem. In this algorithm, the set of initial outsourcing jobs is obtained by solving new auxiliary problem with the dynamic programming technique, and specific jobs are removed from the initial outsourcing job set by introducing a judgement condition in advance. In view of the upper limit on the total outsourcing cost, there is a novel heuristic filtering sequence clan to determine the removed jobs in current outsourcing job set one by one. In simulation experiments, by generating plenty of test instances, the performance of IRH and two reported heuristics in solution quality and computational times is compared. As demonstrated in the results, IRH significantly outperforms two reported heuristics in terms of overall solution quality, and it is capable of solving test instance with up to 1500 jobs within 5.6 seconds.

Key words: production scheduling, heuristics, dynamic programming, outsourcing, single-machine

中图分类号:

O223

刘乐. 单机单转包商调度与外包联合优化问题的改进启发式算法[J]. 运筹与管理, 2017, 26(11): 49-58.

LIU Le. Improved Heuristic Algorithm for a Single-machine Single-subcontractor Scheduling and Outsourcing Integrated Optimization Problem[J]. Operations Research and Management Science, 2017, 26(11): 49-58.

参考文献

[1] Qi X T. Coordinated logistics scheduling for in-house production and outsourcing[J]. IEEE Transactions on Automation Science and Engineering, 2008, 5(1): 188-192.
[2] Chen Z L, Li C L. Scheduling with subcontracting options[J]. IIE Transactions, 2008, 40(12): 1171-1184.
[3] Mokhtari H, Abadi I N K. Scheduling with an outsourcing option on both manufacturer and subcontractors[J]. Computers and Operations Research, 2013, 40(5): 1234-1242.
[4] Lee I S, Sung C S. Single machine scheduling with outsourcing allowed[J]. International Journal of Production Economics, 2008, 111(2): 623- 634.
[5] Lee I S, Sung C S. 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.
[6] 仲维亚,刘晓蕾,霍志明.工件可转包加工的排序问题研究[J].运筹学学报,2012,16(1):121-126.
[7] Chen R J, Qin L Z, Tang G C. Scheduling with outsourcing and variable time slot costs[J]. Journal of Mathematics(PRC), 2015, 35(5): 1068-1074.
[8] Choi B C, Chung K. Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty[J]. European Journal of Operational Research, 2016, 252(2): 367-375.
[9] Qi X T. Two-stage production scheduling with an option of outsourcing from a remote supplier[J]. Journal of Systems Science and Systems Engineering, 2009, 18(1): 1-15.
[10] Qi X T. Outsourcing and production scheduling for a two-stage flow shop[J]. International Journal of Production Economics, 2011, 129(1): 43-50.
[11] Lee K, Choi B C. Two-stage production scheduling with an outsourcing option[J]. European Journal of Operational Research, 2011, 213(3): 489- 497.
[12] Choi B C, Chung J. Two-machine flow shop scheduling problem with an outsourcing option[J]. European Journal of Operational Research, 2011, 213(1): 66-72.
[13] Chung D Y, Choi B C. Outsourcing and scheduling for two-machine ordered flow shop scheduling problems[J]. European Journal of Operational Research, 2013, 226(1): 46-52.
[14] Yoo J, Lee I S. Minimizing total completion times in a two-machine flowshop scheduling with outsourcing strategy allowed[J]. Korean Management Science Review, 2016, 33(2): 1-10.
[15] 李琳.带有外包考虑的两阶段流水车间生产调度优化问题[J].运筹与管理,2016,25(5):75- 81.
[16] 陈荣军,唐国春.可转包的两机自由作业排序问题[J].数学进展,2014,43(6):887- 894.
[17] 陈荣军,张峰,唐国春.平行机及自由作业的排序与转包[J].系统工程学报,2011,26(5):649- 655.
[18] 孙超平,杨平,李凯.考虑外包的平行机调度问题的多目标遗传算法[J].中国机械工程,2014,25(23):3174-3179.
[19] Tavares-Neto R F, Godinho-Filho M, Silva F M. An ant colony optimization approach for the parallel machine scheduling problem with outsourcing allowed[J]. Journal of Intelligent Manufacturing, 2015, 26(3): 527-538.
[20] 王明春,凌光,刘鑫,等.考虑外包的并行调度随机期望值模型[J].系统工程学报,2011,26(1):91-97.
[21] Tavares-Neto R F, Godinho-Filho M. An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed[J]. Computers and Operations Research, 2011, 38(9): 1286-1293.
[22] Choi B C, Park M J. Outsourcing decisions in m-machine permutation flow shop scheduling problems with machine-dependent processing times[J]. Asia-Pacific Journal of Operational Research, 2014, 31(4): 1450028.
[23] Guo X P, Lei D M. Bi-objective job shop scheduling with outsourcing options[J]. International Journal of Production Research, 2014, 52(13): 3832-3841.
[24] Lei D M, Guo X P. A shuffled frog-leaping algorithm for job shop scheduling with outsourcing options[J]. International Journal of Production Research, 2016, 54(16): 4793- 4804.
[25] Mokhtari H. Manufacturing operations outsourcing through an artificial team process algorithm[J]. Journal of Intelligent and Fuzzy Systems, 2016, 31(1): 487-501.
[26] Mokhtari H, Abadi I N K, Amin-Naseri M R. Production scheduling with outsourcing scenarios: a mixed integer programming and efficient solution procedure[J]. International Journal of Production Research, 2012, 50(19): 5372-5395.
[27] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic machine scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5(0): 287-326.