可外包条件下最大时间偏离受限的单机重调度
|
摘要
在一批新工件突然到达、单转包商可加工任意工件的条件下,研究最大时间偏离量与总外包费用不超过给定上限、使总完工时间与总外包费用加权和最小化的单机重调度问题.在构建0-1规划模型、分析NP困难性、提出若干优化性质的基础上,利用动态规划技术和两种不同的外包工件集决策方式,分别设计出工件添加型启发式算法和工件排除型启发式算法.在仿真实验中,通过系统生成大量测试算例,对比分析了两种启发式算法在求解质量、计算时间上的表现.实验结果表明,工件排除型启发式算法在优化质量与效率上均优于工件添加型启发式算法.
This paper considers the single-machine rescheduling addressing an unexpected arrival of new jobs with outsourcing of any jobs to a single subcontractor allowed, where the objective is to minimize the weighted sum of the total outsourcing cost and total completion time, while both the total outsourcing cost and the maximum time deviation are subject to an upper limit. Problem-specific 0-1 programming model, nondeterministic polynomial(NP) hardness, and several optimality properties are first established. Subsequently, by using dynamic programming technique and two different ways of deciding the set of outsourcing jobs, two heuristics are designed to solve this problem, i.e., job addition-related heuristic(JA-H) and job removal related heuristic(JR-H). In the simulation experiments, by systematically generating plenty of test instances, performances of the two heuristics in solution quality and computational times are comparatively analyzed. Experimental results show that JR-H algorithm outperforms JA-H algorithm in terms of both optimization quality and efficiency.
This paper considers the single-machine rescheduling addressing an unexpected arrival of new jobs with outsourcing of any jobs to a single subcontractor allowed, where the objective is to minimize the weighted sum of the total outsourcing cost and total completion time, while both the total outsourcing cost and the maximum time deviation are subject to an upper limit. Problem-specific 0-1 programming model, nondeterministic polynomial(NP) hardness, and several optimality properties are first established. Subsequently, by using dynamic programming technique and two different ways of deciding the set of outsourcing jobs, two heuristics are designed to solve this problem, i.e., job addition-related heuristic(JA-H) and job removal related heuristic(JR-H). In the simulation experiments, by systematically generating plenty of test instances, performances of the two heuristics in solution quality and computational times are comparatively analyzed. Experimental results show that JR-H algorithm outperforms JA-H algorithm in terms of both optimization quality and efficiency.
引文
[1] Mokhtari H, Abadi I N K. Scheduling with an outsourcing option on both manufacturer and subcontractors. Computers and Operations Research, 2013, 40(5):1234–1242.
[2] Lee I S, Sung C S. Single machine scheduling with outsourcing allowed. International Journal of Production Economics, 2008,111(2):623–634.
[3] Lee I S, Sung C S. Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed.European Journal of Operational Research, 2008, 186(3):931–952.
[4]仲维亚,刘晓蕾,霍志明.工件可转包加工的排序问题研究.运筹学学报, 2012, 16(1):121–126.Zhong W Y, Liu X L, Huo Z M. A single machine scheduling problem with subcontracting options. Operations Research Transactions, 2012, 16(1):121–126.(in Chinese)
[5] Chen R J, Qin L Z, Tang G C. Scheduling with outsourcing and variable time slot costs. Journal of Mathematics, 2015, 35(5):1068–1074.
[6] Tavares-Neto R F, Godinho-Filho M, Silva F M. An ant colony optimization approach for the parallel machine scheduling problem with outsourcing allowed. Journal of Intelligent Manufacturing, 2015, 26(3):527–538.
[7]孙超平,杨平,李凯.考虑外包的平行机调度问题的多目标遗传算法.中国机械工程, 2014, 25(23):3174–3179.Sun C P, Yang P, Li K. Multi-objective genetic algorithm for parallel machine scheduling problem with outsourcing. China Mechanical Engineering, 2014, 25(23):3174–3179.(in Chinese)
[8]陈荣军,张峰,唐国春.平行机及自由作业的排序与转包.系统工程学报, 2011, 26(5):649–655.Chen R J, Zhang F, Tang G. Scheduling with subcontracting options under parallel and open-shop machines. Journal of Systems Engineering, 2011, 26(5):649–655.(in Chinese)
[9] Chen Z L, Li C L. Scheduling with subcontracting options. IIE Transactions, 2008, 40(12):1171–1184.
[10]陈荣军,唐国春.同类机下的供应链排序及转包策略.系统科学与数学, 2012, 32(1):53–61.Chen R J, Tang G C. Supply chain scheduling with subcontracting options under uniform machines. Journal of Systems Science and Mathematical Sciences, 2012, 32(1):53–61.(in Chinese)
[11]王明春,凌光,刘鑫,等.考虑外包的并行调度随机期望值模型.系统工程学报, 2011, 26(1):91–97.Wang M C, Ling G, Liu X, et al. Stochastic expected value model about parallel scheduling considering outsourcing. Journal of Systems Engineering, 2011, 26(1):91–97.(in Chinese)
[12] Qi X T. Outsourcing and production scheduling for a two-stage flow shop. International Journal of Production Economics, 2011,129(1):43–50.
[13] Lee K, Choi B C. Two-stage production scheduling with an outsourcing option. European Journal of Operational Research, 2011,213(3):489–497.
[14] Choi B C, Chung J. Two-machine flow shop scheduling problem with an outsourcing option. European Journal of Operational Research, 2011, 213(1):66–72.
[15] Chung D Y, Choi B C. Outsourcing and scheduling for two-machine ordered flow shop scheduling problems. European Journal of Operational Research, 2013, 226(1):46–52.
[16] Tavares-Neto R F, Godinho-Filho M. An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed. Computers and Operations Research, 2011, 38(9):1286–1293.
[17] Mokhtari H, Abadi I N K, Amin-Naseri M R. Production scheduling with outsourcing scenarios:a mixed integer programming and efficient solution procedure. International Journal of Production Research, 2012, 50(19):5372–5395.
[18] Guo X P, Lei D M. Bi-objective job shop scheduling with outsourcing options. International Journal of Production Research, 2014,52(13):3832–3841.
[19] Lei D M, Guo X P. A shuffled frog-leaping algorithm for job shop scheduling with outsourcing options. International Journal of Production Research, 2016, 54(16):4793–4804.
[20]陈荣军,唐国春.可转包的两机自由作业排序问题.数学进展, 2014, 43(6):887–894.Chen R J, Tang G C. Two-machine open-shop scheduling with outsourcing. Advances in Mathematics(China), 2014, 43(6):887–894.(in Chinese)
[21] Vieira G E, Herrmann J W, Lin E. Rescheduling manufacturing systems:A framework of strategies, policies, and methods. Journal of Scheduling, 2003, 6(1):39–62.
[22] Unal A T, Uzsoy R, Kiran A S. Rescheduling on a single machine with part-type dependent setup times and deadlines. Annals of Operations Research, 1997, 70(0):93–113.
[23]郭艳东,王庆,黄敏.就绪时间受限的负荷单机环境下返工工件重调度方法.自动化学报, 2013, 39(12):2100–2110.Guo Y D, Wang Q, Huang M. Rescheduling with release time to minimize sum of waiting time considering waiting constraint of original loads. Acta Automatica Sinica, 2013, 39(12):2100–2110.(in Chinese)
[24]刘乐,周泓.新工件到达干扰下单机最大延迟时间重调度.系统工程学报, 2014, 29(4):494–506.Liu L, Zhou H. Single-machine rescheduling of minimizing the maximum lateness with the disruptive arrival of new jobs. Journal of Systems Engineering, 2014, 29(4):494–506.(in Chinese)
[25] Liu Z X, Ro Y K. Rescheduling for machine disruption to minimize makespan and maximum lateness. Journal of Scheduling, 2014,17(4):339–352.
[26]薄洪光,张鑫,潘裕韬.具有外包选择的无等待流水线干扰修复模型.系统管理学报, 2015, 24(4):485–495.Bo H G, Zhang X, Pan Y T. A disruption recovery model for no-wait flow shop with outsourcing option. Journal of Systems and Management, 2015, 24(4):485–495.(in Chinese)
[27] Fahmy S A, Balakrishnan S, Elmekkawy T Y. A generic deadlock-free reactive scheduling approach. International Journal of Production Research, 2009, 47(20):5657–5676.
[28] Hall N G, Potts C N. Rescheduling for new orders. Operations Research, 2004, 52(3):440–453.
[29] Hall N G, Potts C N. Rescheduling for job unavailability. Operations Research, 2010, 58(3):746–755.
[30] Mu Y D. Rescheduling problems with bicriteria. Chinese Quarterly Journal of Mathematics, 2009, 24(3):349–356.
[31] Zhao C L, Tang H Y. Rescheduling problems with deteriorating jobs under disruptions. Applied Mathematical Modeling, 2010,34(1):238–243.
[32] Hoogeveen H, Lente C, T’kindt V. Rescheduling for new orders on a single machine with setup times. European Journal of Operational Research, 2012, 223(1):40–46.
[33] Teghem J, Tuyttens D. A bi-objective approach to reschedule new jobs in a one machine model. International Transactions in Operational Research, 2014, 21(6):871–898.
[2] Lee I S, Sung C S. Single machine scheduling with outsourcing allowed. International Journal of Production Economics, 2008,111(2):623–634.
[3] Lee I S, Sung C S. Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed.European Journal of Operational Research, 2008, 186(3):931–952.
[4]仲维亚,刘晓蕾,霍志明.工件可转包加工的排序问题研究.运筹学学报, 2012, 16(1):121–126.Zhong W Y, Liu X L, Huo Z M. A single machine scheduling problem with subcontracting options. Operations Research Transactions, 2012, 16(1):121–126.(in Chinese)
[5] Chen R J, Qin L Z, Tang G C. Scheduling with outsourcing and variable time slot costs. Journal of Mathematics, 2015, 35(5):1068–1074.
[6] Tavares-Neto R F, Godinho-Filho M, Silva F M. An ant colony optimization approach for the parallel machine scheduling problem with outsourcing allowed. Journal of Intelligent Manufacturing, 2015, 26(3):527–538.
[7]孙超平,杨平,李凯.考虑外包的平行机调度问题的多目标遗传算法.中国机械工程, 2014, 25(23):3174–3179.Sun C P, Yang P, Li K. Multi-objective genetic algorithm for parallel machine scheduling problem with outsourcing. China Mechanical Engineering, 2014, 25(23):3174–3179.(in Chinese)
[8]陈荣军,张峰,唐国春.平行机及自由作业的排序与转包.系统工程学报, 2011, 26(5):649–655.Chen R J, Zhang F, Tang G. Scheduling with subcontracting options under parallel and open-shop machines. Journal of Systems Engineering, 2011, 26(5):649–655.(in Chinese)
[9] Chen Z L, Li C L. Scheduling with subcontracting options. IIE Transactions, 2008, 40(12):1171–1184.
[10]陈荣军,唐国春.同类机下的供应链排序及转包策略.系统科学与数学, 2012, 32(1):53–61.Chen R J, Tang G C. Supply chain scheduling with subcontracting options under uniform machines. Journal of Systems Science and Mathematical Sciences, 2012, 32(1):53–61.(in Chinese)
[11]王明春,凌光,刘鑫,等.考虑外包的并行调度随机期望值模型.系统工程学报, 2011, 26(1):91–97.Wang M C, Ling G, Liu X, et al. Stochastic expected value model about parallel scheduling considering outsourcing. Journal of Systems Engineering, 2011, 26(1):91–97.(in Chinese)
[12] Qi X T. Outsourcing and production scheduling for a two-stage flow shop. International Journal of Production Economics, 2011,129(1):43–50.
[13] Lee K, Choi B C. Two-stage production scheduling with an outsourcing option. European Journal of Operational Research, 2011,213(3):489–497.
[14] Choi B C, Chung J. Two-machine flow shop scheduling problem with an outsourcing option. European Journal of Operational Research, 2011, 213(1):66–72.
[15] Chung D Y, Choi B C. Outsourcing and scheduling for two-machine ordered flow shop scheduling problems. European Journal of Operational Research, 2013, 226(1):46–52.
[16] Tavares-Neto R F, Godinho-Filho M. An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed. Computers and Operations Research, 2011, 38(9):1286–1293.
[17] Mokhtari H, Abadi I N K, Amin-Naseri M R. Production scheduling with outsourcing scenarios:a mixed integer programming and efficient solution procedure. International Journal of Production Research, 2012, 50(19):5372–5395.
[18] Guo X P, Lei D M. Bi-objective job shop scheduling with outsourcing options. International Journal of Production Research, 2014,52(13):3832–3841.
[19] Lei D M, Guo X P. A shuffled frog-leaping algorithm for job shop scheduling with outsourcing options. International Journal of Production Research, 2016, 54(16):4793–4804.
[20]陈荣军,唐国春.可转包的两机自由作业排序问题.数学进展, 2014, 43(6):887–894.Chen R J, Tang G C. Two-machine open-shop scheduling with outsourcing. Advances in Mathematics(China), 2014, 43(6):887–894.(in Chinese)
[21] Vieira G E, Herrmann J W, Lin E. Rescheduling manufacturing systems:A framework of strategies, policies, and methods. Journal of Scheduling, 2003, 6(1):39–62.
[22] Unal A T, Uzsoy R, Kiran A S. Rescheduling on a single machine with part-type dependent setup times and deadlines. Annals of Operations Research, 1997, 70(0):93–113.
[23]郭艳东,王庆,黄敏.就绪时间受限的负荷单机环境下返工工件重调度方法.自动化学报, 2013, 39(12):2100–2110.Guo Y D, Wang Q, Huang M. Rescheduling with release time to minimize sum of waiting time considering waiting constraint of original loads. Acta Automatica Sinica, 2013, 39(12):2100–2110.(in Chinese)
[24]刘乐,周泓.新工件到达干扰下单机最大延迟时间重调度.系统工程学报, 2014, 29(4):494–506.Liu L, Zhou H. Single-machine rescheduling of minimizing the maximum lateness with the disruptive arrival of new jobs. Journal of Systems Engineering, 2014, 29(4):494–506.(in Chinese)
[25] Liu Z X, Ro Y K. Rescheduling for machine disruption to minimize makespan and maximum lateness. Journal of Scheduling, 2014,17(4):339–352.
[26]薄洪光,张鑫,潘裕韬.具有外包选择的无等待流水线干扰修复模型.系统管理学报, 2015, 24(4):485–495.Bo H G, Zhang X, Pan Y T. A disruption recovery model for no-wait flow shop with outsourcing option. Journal of Systems and Management, 2015, 24(4):485–495.(in Chinese)
[27] Fahmy S A, Balakrishnan S, Elmekkawy T Y. A generic deadlock-free reactive scheduling approach. International Journal of Production Research, 2009, 47(20):5657–5676.
[28] Hall N G, Potts C N. Rescheduling for new orders. Operations Research, 2004, 52(3):440–453.
[29] Hall N G, Potts C N. Rescheduling for job unavailability. Operations Research, 2010, 58(3):746–755.
[30] Mu Y D. Rescheduling problems with bicriteria. Chinese Quarterly Journal of Mathematics, 2009, 24(3):349–356.
[31] Zhao C L, Tang H Y. Rescheduling problems with deteriorating jobs under disruptions. Applied Mathematical Modeling, 2010,34(1):238–243.
[32] Hoogeveen H, Lente C, T’kindt V. Rescheduling for new orders on a single machine with setup times. European Journal of Operational Research, 2012, 223(1):40–46.
[33] Teghem J, Tuyttens D. A bi-objective approach to reschedule new jobs in a one machine model. International Transactions in Operational Research, 2014, 21(6):871–898.