云制造环境下跨企业协同生产调度算法
|
摘要
为解决云制造环境下的跨企业协同生产调度问题,提出一种适用于云制造环境下生产资源调度的混合集合规划方法。该方法基于切削算法框架,综合考虑多种约束,提出一种有效的求解策略,实现了一种面向订单且适用于跨企业、多约束、多品种、小批量的有限能力调度算法,为供应链中供需企业提供了一份拖期小、费用低、跨度短的协同生产计划。利用多组制造企业真实数据对模型进行测试,结果表明,该模型可在合理时间内有效求解实际应用规模的跨企业协同生产调度问题。
Aiming at the collaborative production scheduling problem for cross-enterprises,a Mixed Set Programming(MSP)approach to modeling and solving the cross-enterprise planning problem for cloud manufacturing was proposed to generate collaborative production schedules with less delays,low costs and balanced resource allocations for both customers and suppliers.By considering a variety of constraints and based on an abstract data model of cloud manufacturing tasks and resources,an efficient search strategy was proposed to deal with a multi-variety,smallbatch and strongly capacitated resource planning problem.Computational results with real-world size showed that the proposed method could solve the practical collaborative production scheduling problem of cross-enterprises efficiently within reasonable time.
Aiming at the collaborative production scheduling problem for cross-enterprises,a Mixed Set Programming(MSP)approach to modeling and solving the cross-enterprise planning problem for cloud manufacturing was proposed to generate collaborative production schedules with less delays,low costs and balanced resource allocations for both customers and suppliers.By considering a variety of constraints and based on an abstract data model of cloud manufacturing tasks and resources,an efficient search strategy was proposed to deal with a multi-variety,smallbatch and strongly capacitated resource planning problem.Computational results with real-world size showed that the proposed method could solve the practical collaborative production scheduling problem of cross-enterprises efficiently within reasonable time.
引文
[1]LI Bohu,ZHANG Lin,WANG Shilong,et al.Cloud manufacturing:a new service-oriented networked manufacturing mode[J].Computer Integrated Manufacturing Systems,2010,16(1):1-7,16(in Chinese).[李伯虎,张霖,王时龙,等.云制造---面向服务的网络化制造新模式[J].计算机集成制造系统,2010,16(1):1-7,16.]
[2]LI Bohu,ZHANG Lin,CHAI Xudong.Smart cloud manufacturing(cloud manufacturing 2.0)-a new paradigm and approach of smart manufacturing[C]//Proceedings of the 21st ISPE Inc.International Conference on Concurrent Engineering.Amsterdam,the Netherlands:IOS Press,2014,1:26.
[3]LI Bohu.Smart cloud manufacturing(cloud manufacturing2.0)-a smart manufacturing mode and means of“internet manufacturing”[R].Beijing:Chinese Academy of Engineering,2015(in Chinese).[李伯虎.智慧云制造(云制造2.0)---“互联网+制造业”的一种智造模式和手段[R].北京:中国工程院,2015.]
[4]LI Bohu,ZHANG Lin,REN Lei,et al.Further discussion on cloud manufacturing[J].Computer Integrated Manufacturing Systems,2011,17(3):449-457(in Chinese).[李伯虎,张霖,任磊,等.再论云制造[J].计算机集成制造系统,2011,17(3):449-457]
[5]JACOBS F R,VOLLMANN T E,BERRY W L,et al.Manufacturing planning and control for supply chain management[M].5th ed.New York,N.Y.,USA:McGraw-Hill Professional,2011:483-486.
[6]LI Honglei.Features and trend of business model in industry4.0[J].Modern Management Science,2017(5):58-60(in Chinese).[李鸿磊.工业4.0时代商业模式的特征与趋势[J].现代管理科学,2017(5):58-60.]
[7]YU Shujiang,SONG Jiacheng.Current situation and challenges of traditional enterprises in the context of“Internet+”-taking manufacturing as an example[J].China Journal of Commerce,2016(26):15-16,19(in Chinese).[于树江,宋嘉诚.“互联网+”背景下传统企业当前的现状与面临的挑战---以制造业为例[J].中国商论,2016(26):15-16,19.]
[8]XIAO Bin,LAI Xinfeng.Research on flexible production of Chinese manufacturing in the context of“Internet+”[J].Enterprise Economy,2015(9):148-152(in Chinese).[肖斌,赖新峰.“互联网+”背景下中国制造业的柔性化生产研究[J].企业经济,2015(9):148-152.]
[9]GAREY M R,JOHNSON D S,SETHI R.The complexity of flowshop and job shop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
[10]ZHOU Jianyang.The NCL natural constraint language[M].Beijing:Science Press,2012:1-12.
[11]XIAO Yingying,LI Bohu,HOU Baocun,et al.Planning and scheduling technology review of supply chain management in smart manufacturing cloud[J].Computer Intergrated Manufacturing Systems,2016,22(7):1619-1634(in Chinese).[肖莹莹,李伯虎,侯宝存,等.智慧制造云中供应链管理的计划调度技术综述[J].计算机集成制造系统,2016,22(7):1619-1634.]
[12]GAREY M R,JOHNSON D S.Computers and intractability[M].New York,N.Y.,USA:W.H.Freeman,1979:47.
[13]POTTS C N,STRUSEVICH V A.Fifty years of scheduling:a survey of milestones[J].Journal of the Operational Research Society,2009,60(1):S41-S68.
[14]ZHOU Jianyang.Introduction to the constraint language NCL[J].Journal of Logic Programming,2000,45(1/2/3):71-103.
[15]FROMHERZ M P J.Constraint-based scheduling[C]//Proceedings of the American Control Conference.Washington,D.C.,USA:IEEE,2001.
[16]GRAHAM R L,LAWLER E L,LENSTRA J K,et al.Optimization and approximation in deterministic sequencing and scheduling:a survey[J].Annals of Discrete Mathematics,1979,5(1):287-326.
[17]ZHOU Longfei,ZHANG Lin,LIU Yongkui.Suervey on scheduling problem in cloud manufacturing[J].Computer Intergrated Manufacturing Systems,2017,23(6):1148-1166(in Chinese).[周龙飞,张霖,刘永奎.云制造调度问题研究综述[J].计算机集成制造系统,2017,23(6):1148-1166.]
[18]LIU T K,CHEN Y P,CHOU J H.Solving distributed and flexible job-shop scheduling problems for a real-world fastener manufacturer[J].IEEE Access,2015,2:1598-1606.
[19]CHENG Zhen,ZHAN Dechen,ZHAO Xibin,et al.Multitask oriented virtual resource integration and optimization scheduling in cloud manufacturing[J].Journal of Applied Mathematics,2014,2014(7):369-350
[20]LI Wenxiang,ZHU Chunsheng,YANG L T,et al.Subtask scheduling for distributed robots in cloud manufacturing[J].IEEE Systems Journal,2015,99:1-10.DOI:10.1109/JSYST.2015.2438054.
[21]LARTIGAU J,XU Xiaofei,ZHAN Dechen.Artificial bee colony optimized Scheduling framework based on resource service availability in cloud manufacturing[C]//Proceedings of the 2014International Conference on Service Sciences.Washington,D.C.,USA:IEEE,2014:181-186.
[22]JIAN C F,WANG Y.Batch task scheduling-oriented optimization Modeling and simulation in cloud manufacturing[J].International Journal of Simulation Modeling,2014,13(1):93-101.
[23]CAO Yang,WANG Shilong,KANG Ling,et al.A TQCS-based service selection and scheduling strategy in cloud manufacturing[J].International Journal of Advanced Manufacturing Technology,2016,82(1):235-251.
[24]LIU Yongkui,XU Xun,ZHANG Lin,et al.Workloadbased multi-task scheduling in cloud manufacturing[J].Robotics and Computer Integrated Manufacturing,2016,45:3-20.DOI:10.1016/j.Rcim.2016.09.008.
[25]LAN Boxiong,ZHANG Mi.Mixed set programming for crew pairing[J].Operations Research and Management Science,2014,23(2):175-182(in Chinese).[蓝伯雄,张米.机组排班的混合集合规划方法研究[J].运筹与管理,2014,23(2):175-182]
[26]ZHANG Hongtao,CUI Shanshan,LIU Guang,et al.Resource scheduling for air fleet operations[J].Systems Engineering-Theory&Practice,2015,35(4):1019-1026(in Chinese).[张洪涛,崔珊珊,刘广,等.机群保障资源配置建模与优化研究[J].系统工程理论与实践,2015,35(4):1019-1026.]
[27]LIU Xuan,SHANG Jun,BAI Ao.Production task rescheduling method for job shop based on equipment failure[J].Manufacturing Automation,2016,38(12):26-30(in Chinese).[刘轩,尚鋆,白翱.设备故障驱动的作业车间生产任务重调度方法研究[J].制造业自动化,2016,38(12):26-30.]
[2]LI Bohu,ZHANG Lin,CHAI Xudong.Smart cloud manufacturing(cloud manufacturing 2.0)-a new paradigm and approach of smart manufacturing[C]//Proceedings of the 21st ISPE Inc.International Conference on Concurrent Engineering.Amsterdam,the Netherlands:IOS Press,2014,1:26.
[3]LI Bohu.Smart cloud manufacturing(cloud manufacturing2.0)-a smart manufacturing mode and means of“internet manufacturing”[R].Beijing:Chinese Academy of Engineering,2015(in Chinese).[李伯虎.智慧云制造(云制造2.0)---“互联网+制造业”的一种智造模式和手段[R].北京:中国工程院,2015.]
[4]LI Bohu,ZHANG Lin,REN Lei,et al.Further discussion on cloud manufacturing[J].Computer Integrated Manufacturing Systems,2011,17(3):449-457(in Chinese).[李伯虎,张霖,任磊,等.再论云制造[J].计算机集成制造系统,2011,17(3):449-457]
[5]JACOBS F R,VOLLMANN T E,BERRY W L,et al.Manufacturing planning and control for supply chain management[M].5th ed.New York,N.Y.,USA:McGraw-Hill Professional,2011:483-486.
[6]LI Honglei.Features and trend of business model in industry4.0[J].Modern Management Science,2017(5):58-60(in Chinese).[李鸿磊.工业4.0时代商业模式的特征与趋势[J].现代管理科学,2017(5):58-60.]
[7]YU Shujiang,SONG Jiacheng.Current situation and challenges of traditional enterprises in the context of“Internet+”-taking manufacturing as an example[J].China Journal of Commerce,2016(26):15-16,19(in Chinese).[于树江,宋嘉诚.“互联网+”背景下传统企业当前的现状与面临的挑战---以制造业为例[J].中国商论,2016(26):15-16,19.]
[8]XIAO Bin,LAI Xinfeng.Research on flexible production of Chinese manufacturing in the context of“Internet+”[J].Enterprise Economy,2015(9):148-152(in Chinese).[肖斌,赖新峰.“互联网+”背景下中国制造业的柔性化生产研究[J].企业经济,2015(9):148-152.]
[9]GAREY M R,JOHNSON D S,SETHI R.The complexity of flowshop and job shop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
[10]ZHOU Jianyang.The NCL natural constraint language[M].Beijing:Science Press,2012:1-12.
[11]XIAO Yingying,LI Bohu,HOU Baocun,et al.Planning and scheduling technology review of supply chain management in smart manufacturing cloud[J].Computer Intergrated Manufacturing Systems,2016,22(7):1619-1634(in Chinese).[肖莹莹,李伯虎,侯宝存,等.智慧制造云中供应链管理的计划调度技术综述[J].计算机集成制造系统,2016,22(7):1619-1634.]
[12]GAREY M R,JOHNSON D S.Computers and intractability[M].New York,N.Y.,USA:W.H.Freeman,1979:47.
[13]POTTS C N,STRUSEVICH V A.Fifty years of scheduling:a survey of milestones[J].Journal of the Operational Research Society,2009,60(1):S41-S68.
[14]ZHOU Jianyang.Introduction to the constraint language NCL[J].Journal of Logic Programming,2000,45(1/2/3):71-103.
[15]FROMHERZ M P J.Constraint-based scheduling[C]//Proceedings of the American Control Conference.Washington,D.C.,USA:IEEE,2001.
[16]GRAHAM R L,LAWLER E L,LENSTRA J K,et al.Optimization and approximation in deterministic sequencing and scheduling:a survey[J].Annals of Discrete Mathematics,1979,5(1):287-326.
[17]ZHOU Longfei,ZHANG Lin,LIU Yongkui.Suervey on scheduling problem in cloud manufacturing[J].Computer Intergrated Manufacturing Systems,2017,23(6):1148-1166(in Chinese).[周龙飞,张霖,刘永奎.云制造调度问题研究综述[J].计算机集成制造系统,2017,23(6):1148-1166.]
[18]LIU T K,CHEN Y P,CHOU J H.Solving distributed and flexible job-shop scheduling problems for a real-world fastener manufacturer[J].IEEE Access,2015,2:1598-1606.
[19]CHENG Zhen,ZHAN Dechen,ZHAO Xibin,et al.Multitask oriented virtual resource integration and optimization scheduling in cloud manufacturing[J].Journal of Applied Mathematics,2014,2014(7):369-350
[20]LI Wenxiang,ZHU Chunsheng,YANG L T,et al.Subtask scheduling for distributed robots in cloud manufacturing[J].IEEE Systems Journal,2015,99:1-10.DOI:10.1109/JSYST.2015.2438054.
[21]LARTIGAU J,XU Xiaofei,ZHAN Dechen.Artificial bee colony optimized Scheduling framework based on resource service availability in cloud manufacturing[C]//Proceedings of the 2014International Conference on Service Sciences.Washington,D.C.,USA:IEEE,2014:181-186.
[22]JIAN C F,WANG Y.Batch task scheduling-oriented optimization Modeling and simulation in cloud manufacturing[J].International Journal of Simulation Modeling,2014,13(1):93-101.
[23]CAO Yang,WANG Shilong,KANG Ling,et al.A TQCS-based service selection and scheduling strategy in cloud manufacturing[J].International Journal of Advanced Manufacturing Technology,2016,82(1):235-251.
[24]LIU Yongkui,XU Xun,ZHANG Lin,et al.Workloadbased multi-task scheduling in cloud manufacturing[J].Robotics and Computer Integrated Manufacturing,2016,45:3-20.DOI:10.1016/j.Rcim.2016.09.008.
[25]LAN Boxiong,ZHANG Mi.Mixed set programming for crew pairing[J].Operations Research and Management Science,2014,23(2):175-182(in Chinese).[蓝伯雄,张米.机组排班的混合集合规划方法研究[J].运筹与管理,2014,23(2):175-182]
[26]ZHANG Hongtao,CUI Shanshan,LIU Guang,et al.Resource scheduling for air fleet operations[J].Systems Engineering-Theory&Practice,2015,35(4):1019-1026(in Chinese).[张洪涛,崔珊珊,刘广,等.机群保障资源配置建模与优化研究[J].系统工程理论与实践,2015,35(4):1019-1026.]
[27]LIU Xuan,SHANG Jun,BAI Ao.Production task rescheduling method for job shop based on equipment failure[J].Manufacturing Automation,2016,38(12):26-30(in Chinese).[刘轩,尚鋆,白翱.设备故障驱动的作业车间生产任务重调度方法研究[J].制造业自动化,2016,38(12):26-30.]