双机流水车间外包与调度联合优化问题的混合变邻域搜索算法
|
摘要
针对最小化内部完工期与总外包费用的双机流水车间外包与调度联合优化问题,开发了一种混合变邻域搜索算法。在该算法中,采用工件剔除型启发式方法产生初始联合决策解;基于3种新型邻域结构提出了最佳改进式局部搜索规程;引入概率式准则来决定下轮迭代的目标搜索邻域。通过算法校准实验分析,探索出合适的邻域变更次序和温度参数的计算方式。通过与CPLEX软件、隐枚举测试程序对比显示,对于工件数不超过30的算例,校准后所提算法求得最优解的耗用时间更少。通过与遗传算法、模拟退火算法、和声搜索3种对比算法在工件数不少于100的算例上进行对比发现,所提算法经校准后,在求解质量和解的鲁棒性上均具有显著优势。
Aiming at the two-machine flow shop outsourcing and scheduling integrated optimization problem of minimizing the sum of in-house makespan and total outsourcing cost, a Hybrid Variable Neighborhood Search(HVNS) algorithm was proposed. In this algorithm, the initial joint decision solutions were obtained by performing problem-specific job removal-related heuristic approach. Based on three novel neighborhood structures, a best-improvement local-search procedure was designed to improve the resulted solutions through shaking. Besides, the probabilistic moving criterion was introduced to decide the target neighborhood in the next iteration. The appropriate selections for the changing sequence of neighborhoods and the way of calculating temperature parameter were achieved via extensive calibration experiments. The comparison results with CPLEX optimizer and the Implicit Enumeration Testing Procedure(IETP) showed that the calibrated HVNS was capable of finding the optimal solutions to the instances with n≤30 and much less computation time. In comparison with three algorithms by respectively using the genetic algorithm, simulated annealing and harmony search techniques, the calibrated HVNS showed significant superiority over three compared ones in terms of both solution quality and robustness.
Aiming at the two-machine flow shop outsourcing and scheduling integrated optimization problem of minimizing the sum of in-house makespan and total outsourcing cost, a Hybrid Variable Neighborhood Search(HVNS) algorithm was proposed. In this algorithm, the initial joint decision solutions were obtained by performing problem-specific job removal-related heuristic approach. Based on three novel neighborhood structures, a best-improvement local-search procedure was designed to improve the resulted solutions through shaking. Besides, the probabilistic moving criterion was introduced to decide the target neighborhood in the next iteration. The appropriate selections for the changing sequence of neighborhoods and the way of calculating temperature parameter were achieved via extensive calibration experiments. The comparison results with CPLEX optimizer and the Implicit Enumeration Testing Procedure(IETP) showed that the calibrated HVNS was capable of finding the optimal solutions to the instances with n≤30 and much less computation time. In comparison with three algorithms by respectively using the genetic algorithm, simulated annealing and harmony search techniques, the calibrated HVNS showed significant superiority over three compared ones in terms of both solution quality and robustness.
引文
[1] DOLGUI A,PROTH J M.Outsourcing:definitions and analysis[J].International Journal of Production Research,2013,51(23/24):6769-6777.
[2] CHEN Zhilong.Scheduling with subcontracting options[J].IIE Transactions,2008,40(12):1171-1184.
[3] ZHONG Weiya,HUO Zhiming.Single machine scheduling problems with subcontracting options[J].Journal of Combinatorial Optimization,2013,26(3):489-498.
[4] MOKHTARI H.Manufacturing operations outsourcing through an artificial team process algorithm[J].Journal of Intelligent and Fuzzy Systems,2016,31(1):487-501.
[5] LEE Y H,JEONG C S,MOON C.Advanced planning and scheduling with outsourcing in manufacturing supply chain[J].Computers and Industrial Engineering,2002,43(1/2):351-374.
[6] 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.
[7] CHEN Rongjun,TANG Guochun.Two-machine open-shop scheduling with outsourcing[J].Advances in Mathematics(China),2014,43(6):887-894(in Chinese).[陈荣军,唐国春.可转包的两机自由作业排序问题[J].数学进展,2014,43(6):887-894.]
[8] CHEN Rongjun,TANG Guochun.Open-shop scheduling with option of outsourcing[J].Advances in Mathematics(China),2017,46(2):313-319(in Chinese).[陈荣军,唐国春.带转包选项的自由作业排序[J].数学进展,2017,46(2):313-319.]
[9] QI Xiangtong.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 Xiangtong.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] AHMADIZAR F,AMIRI Z.Outsourcing and scheduling for a two-machine flow shop with release times[J].Engineering Optimization,2018,50(3):483-498.
[13] 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.
[14] 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.
[15] BO Hongguang,ZHANG Xin,PAN Yutao.A disruption recovery model for no-wait flow shop with outsourcing option[J].Journal of Systems and Management,2015,24(4):485-495(in Chinese).[薄洪光,张鑫,潘裕韬.具有外包选择的无等待流水线干扰修复模型[J].系统管理学报,2015,24(4):485-495.]
[16] CHEN Guangting,CHEN Lei,ZHANG An,et al.Approximation algorithms for two-machine flow shop scheduling with an outsourcing option[J].Operations Research Transactions,2016,20(4):109-114(in Chinese).[陈光亭,陈蕾,张安,等.可转包两台流水作业机排序的近似算法[J].运筹学学报,2016,20(4):109-114.]
[17] 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.
[18] MLADENOVIC N,HANSEN P.Variable neighborhood search[J].Computers and Operations Research,1997,24(11):1097-1100.
[19] HANSEN P,MLADENOVIC N,TODOSIJEVIC R,et al.Variable neighborhood search:basics and variants[J].EURO Journal on Computational Optimization,2017,5(3):423-454.
[20] DRIESSEL R,MONCH L.Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times,precedence constraints,and ready times[J].Computers and Industrial Engineering,2011,61(2):336-345.
[21] KIRLIK G,OGUZ C.A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine[J].Computers and Operations Research,2012,39(7):1506-1520.
[22] BILYK A,MONCH L.A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines[J].Journal of Intelligent Manufacturing,2012,23(5):1621-1635.
[23] LI Junqing,PAN Quanke,WANG Fatao.A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem[J].Applied Soft Computing,2014,24:63-77.
[24] M’HALLAH R.An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop[J].International Journal of Production Research,2014,52(13):3802-3819.
[25] LEI Deming.Variable neighborhood search for two-agent flow shop scheduling problem[J].Computers and Industrial Engineering,2015,80:125-131.
[26] LI Kun,XU Zheng,TIAN Huixin.An adaptive variable neighborhood search algorithm for the hybrid flowshop scheduling problem[J].Systems Engineering,2015,33(11):121-129(in Chinese).[李坤,徐铮,田慧欣.基于自适应变邻域搜索算法的一类混合流水车间调度问题[J].系统工程,2015,33(11):121-129.]
[27] YANG Hongan,QI Liangliang,LI Jinyuan,et al.Hybrid algorithm of VNS/MP for JIT job-shop scheduling problem[J].Computer Integrated Manufacturing Systems,2014,20(2):414-423(in Chinese).[杨宏安,齐亮亮,李锦远,等.求解作业车间JIT调度问题的VNS/MP混合算法[J].计算机集成制造系统,2014,20(2):414-423.]
[28] YAZDANI M,AMIRI M,ZANDIEH M.Flexible job-shop scheduling with parallel variable neighborhood search algorithm[J].Expert Systems with Applications,2010,37(1):678-687.
[29] BAGHERI A,ZANDIEH M.Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—variable neighborhood search approach[J].Journal of Manufacturing Systems,2011,30(1):8-15.
[30] 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:287-326.
[31] QI X.Coordinated logistics scheduling for in-house production and outsourcing[J].IEEE Transactions on Automation Science and Engineering,2008,5(1):188-192.
[32] JOHNSON S M.Optimal two- and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1(1):61-68.
[33] LEE I S,SUNG C S.Single machine scheduling with outsourcing allowed[J].International Journal of Production Economics,2008,111(2):623-634.
[34] 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(in Chinese).[刘乐.单机单转包商调度与外包联合优化问题的改进启发式算法[J].运筹与管理,2017,26(11):49-58.]
[35] RUIZ R,STUTZLE T.A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[J].European Journal of Operational Research,2007,177(3):2033-2049.
[36] SIFALERAS A,KONSTANTARAS I,MIADENOVIC N.Variable neighborhood search for the economic lot sizing problem with product returns and recovery[J].International Journal of Production Economics,2015,160:133-143.
[2] CHEN Zhilong.Scheduling with subcontracting options[J].IIE Transactions,2008,40(12):1171-1184.
[3] ZHONG Weiya,HUO Zhiming.Single machine scheduling problems with subcontracting options[J].Journal of Combinatorial Optimization,2013,26(3):489-498.
[4] MOKHTARI H.Manufacturing operations outsourcing through an artificial team process algorithm[J].Journal of Intelligent and Fuzzy Systems,2016,31(1):487-501.
[5] LEE Y H,JEONG C S,MOON C.Advanced planning and scheduling with outsourcing in manufacturing supply chain[J].Computers and Industrial Engineering,2002,43(1/2):351-374.
[6] 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.
[7] CHEN Rongjun,TANG Guochun.Two-machine open-shop scheduling with outsourcing[J].Advances in Mathematics(China),2014,43(6):887-894(in Chinese).[陈荣军,唐国春.可转包的两机自由作业排序问题[J].数学进展,2014,43(6):887-894.]
[8] CHEN Rongjun,TANG Guochun.Open-shop scheduling with option of outsourcing[J].Advances in Mathematics(China),2017,46(2):313-319(in Chinese).[陈荣军,唐国春.带转包选项的自由作业排序[J].数学进展,2017,46(2):313-319.]
[9] QI Xiangtong.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 Xiangtong.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] AHMADIZAR F,AMIRI Z.Outsourcing and scheduling for a two-machine flow shop with release times[J].Engineering Optimization,2018,50(3):483-498.
[13] 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.
[14] 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.
[15] BO Hongguang,ZHANG Xin,PAN Yutao.A disruption recovery model for no-wait flow shop with outsourcing option[J].Journal of Systems and Management,2015,24(4):485-495(in Chinese).[薄洪光,张鑫,潘裕韬.具有外包选择的无等待流水线干扰修复模型[J].系统管理学报,2015,24(4):485-495.]
[16] CHEN Guangting,CHEN Lei,ZHANG An,et al.Approximation algorithms for two-machine flow shop scheduling with an outsourcing option[J].Operations Research Transactions,2016,20(4):109-114(in Chinese).[陈光亭,陈蕾,张安,等.可转包两台流水作业机排序的近似算法[J].运筹学学报,2016,20(4):109-114.]
[17] 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.
[18] MLADENOVIC N,HANSEN P.Variable neighborhood search[J].Computers and Operations Research,1997,24(11):1097-1100.
[19] HANSEN P,MLADENOVIC N,TODOSIJEVIC R,et al.Variable neighborhood search:basics and variants[J].EURO Journal on Computational Optimization,2017,5(3):423-454.
[20] DRIESSEL R,MONCH L.Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times,precedence constraints,and ready times[J].Computers and Industrial Engineering,2011,61(2):336-345.
[21] KIRLIK G,OGUZ C.A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine[J].Computers and Operations Research,2012,39(7):1506-1520.
[22] BILYK A,MONCH L.A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines[J].Journal of Intelligent Manufacturing,2012,23(5):1621-1635.
[23] LI Junqing,PAN Quanke,WANG Fatao.A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem[J].Applied Soft Computing,2014,24:63-77.
[24] M’HALLAH R.An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop[J].International Journal of Production Research,2014,52(13):3802-3819.
[25] LEI Deming.Variable neighborhood search for two-agent flow shop scheduling problem[J].Computers and Industrial Engineering,2015,80:125-131.
[26] LI Kun,XU Zheng,TIAN Huixin.An adaptive variable neighborhood search algorithm for the hybrid flowshop scheduling problem[J].Systems Engineering,2015,33(11):121-129(in Chinese).[李坤,徐铮,田慧欣.基于自适应变邻域搜索算法的一类混合流水车间调度问题[J].系统工程,2015,33(11):121-129.]
[27] YANG Hongan,QI Liangliang,LI Jinyuan,et al.Hybrid algorithm of VNS/MP for JIT job-shop scheduling problem[J].Computer Integrated Manufacturing Systems,2014,20(2):414-423(in Chinese).[杨宏安,齐亮亮,李锦远,等.求解作业车间JIT调度问题的VNS/MP混合算法[J].计算机集成制造系统,2014,20(2):414-423.]
[28] YAZDANI M,AMIRI M,ZANDIEH M.Flexible job-shop scheduling with parallel variable neighborhood search algorithm[J].Expert Systems with Applications,2010,37(1):678-687.
[29] BAGHERI A,ZANDIEH M.Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—variable neighborhood search approach[J].Journal of Manufacturing Systems,2011,30(1):8-15.
[30] 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:287-326.
[31] QI X.Coordinated logistics scheduling for in-house production and outsourcing[J].IEEE Transactions on Automation Science and Engineering,2008,5(1):188-192.
[32] JOHNSON S M.Optimal two- and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1(1):61-68.
[33] LEE I S,SUNG C S.Single machine scheduling with outsourcing allowed[J].International Journal of Production Economics,2008,111(2):623-634.
[34] 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(in Chinese).[刘乐.单机单转包商调度与外包联合优化问题的改进启发式算法[J].运筹与管理,2017,26(11):49-58.]
[35] RUIZ R,STUTZLE T.A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[J].European Journal of Operational Research,2007,177(3):2033-2049.
[36] SIFALERAS A,KONSTANTARAS I,MIADENOVIC N.Variable neighborhood search for the economic lot sizing problem with product returns and recovery[J].International Journal of Production Economics,2015,160:133-143.