工程科学学报.第41卷.第11期：1450-1457.2019年11月 Chinese Journal of Engineering,Vol.41,No.11:1450-1457,November 2019 D0L:10.13374/.issn2095-9389.2018.11.27.002,http://journals.ustb.edu.cn 多日标多约束混合流水车间插单重调度问题研究 何小妹四，董绍华 北京科技大学机械工程学院，北京100083 ☒通信作者，E-mail:18813127630@163.com 摘要研究了多目标多阶段混合流水车间的紧急订单插单重调度问题，综合考虑工件批量、刀具换装时间、运输能力等约 束.先以最小化订单完工时间和最小化总运输时间为双目标建立静态初始订单调度模型，再针对紧急订单插单干扰，增加最 小化总加工机器偏差值目标，建立三目标重调度优化模型，并分别用NSGAⅡ算法与融合基于事件驱动的重调度策略和重排 插单策略的NSGAⅢI算法对两个模型进行求解，最后，以某实际船用管类零件生产企业为案例，先对NSGA-Ⅱ算法和 NSGA-ⅢI算法的性能进行评估，得到NSGA-Ⅱ算法更适用于解决双目标优化问题而NSGAⅢI算法在解决三目标优化问题时 表现更优的结论，再将所建模型与所提算法应用于该企业的十组插单案例中，所得优化率接近三分之一，验证了实用性和有 效性 关键词混合流水车间：紧急订单插单重调度：多目标：多约束：NSGAⅢ算法 分类号U673.2 Research on rush order insertion rescheduling problem under hybrid flow shop with multi-objective and multi-constraint HE Xiao-me,DONG Shao-hua School of Mechanical Engineering.University of Science and Technology Beijing.Beijing 100083,China Corresponding author,E-mail:18813127630@163.com ABSTRACT To study the multi-objective rush order insertion rescheduling problem under hybrid flow shop with multiple stages and multiple machines,the constraints,such as job lots,sequence-dependent set-up times,and round-trip transportation times,were simultaneously considered.A static optimal scheduling model of initial orders was first established to minimize the maximum order completion time and minimize the total transportation time.The non-dominated sorting genetic algorithm (NSGA)-II algorithm was applied to solve a two-objective optimal problem.Then,for the rush order insertion disturbance factor,the objective to minimize the total machine deviation between the initial scheduling and rescheduling plans was added as a stability index to establish an optimal rush order rescheduling model.The NSGA-III algorithm based on the event-driven rescheduling strategy and order rearrangement strategy was applied to solve a three-objective optimal problem.Finally,a realistic ship pipe parts manufacturing enterprise is regarded as a study case.Two sets of experiments are carried out to explain the motivation of the selected method.The performances of the NSGA-II and NSGA-III algorithms are evaluated by three metrics,including the mean ideal distance,spread of non-dominated solution,and percentage of domination.The results show that the NSGA-II algorithm is more suitable for solving two-objective optimal problem, whereas NSGA-III algorithm performs better in solving three-objective optimal problems.Then,the proposed model and method were applied to 10 rush order insertion cases of the enterprise.All the three objectives were improved according to the compared results obtained by the actual and optimal scheduling.The optimal rate is close to one third,which verifies the feasibility of the proposed model 收稿日期：2018-11-27 基金项目：国家自然科学基金资助项目(71301008)多目标多约束混合流水车间插单重调度问题研究 何小妹苣，董绍华 北京科技大学机械工程学院，北京 100083 苣通信作者，E-mail：18813127630@163.com 摘    要    研究了多目标多阶段混合流水车间的紧急订单插单重调度问题，综合考虑工件批量、刀具换装时间、运输能力等约 束. 先以最小化订单完工时间和最小化总运输时间为双目标建立静态初始订单调度模型，再针对紧急订单插单干扰，增加最 小化总加工机器偏差值目标，建立三目标重调度优化模型，并分别用 NSGA-II 算法与融合基于事件驱动的重调度策略和重排 插单策略的 NSGA-III 算法对两个模型进行求解. 最后，以某实际船用管类零件生产企业为案例，先对 NSGA-II 算法和 NSGA-III 算法的性能进行评估，得到 NSGA-II 算法更适用于解决双目标优化问题而 NSGA-III 算法在解决三目标优化问题时 表现更优的结论，再将所建模型与所提算法应用于该企业的十组插单案例中，所得优化率接近三分之一，验证了实用性和有 效性. 关键词    混合流水车间；紧急订单插单重调度；多目标；多约束；NSGA-III 算法 分类号    U673.2 Research on rush order insertion rescheduling problem under hybrid flow shop with multi-objective and multi-constraint HE Xiao-mei苣 ，DONG Shao-hua School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China 苣 Corresponding author, E-mail: 18813127630@163.com ABSTRACT    To study the multi-objective rush order insertion rescheduling problem under hybrid flow shop with multiple stages and multiple machines, the constraints, such as job lots, sequence-dependent set-up times, and round-trip transportation times, were simultaneously considered. A static optimal scheduling model of initial orders was first established to minimize the maximum order completion time and minimize the total transportation time. The non-dominated sorting genetic algorithm (NSGA)-II algorithm was applied to solve a two-objective optimal problem. Then, for the rush order insertion disturbance factor, the objective to minimize the total machine deviation between the initial scheduling and rescheduling plans was added as a stability index to establish an optimal rush order rescheduling model. The NSGA-III algorithm based on the event-driven rescheduling strategy and order rearrangement strategy was applied to solve a three-objective optimal problem. Finally, a realistic ship pipe parts manufacturing enterprise is regarded as a study case. Two sets of experiments are carried out to explain the motivation of the selected method. The performances of the NSGA-II and NSGA-III algorithms are evaluated by three metrics, including the mean ideal distance, spread of non-dominated solution, and percentage of domination. The results show that the NSGA-II algorithm is more suitable for solving two-objective optimal problem, whereas NSGA-III algorithm performs better in solving three-objective optimal problems. Then, the proposed model and method were applied to 10 rush order insertion cases of the enterprise. All the three objectives were improved according to the compared results obtained by the actual and optimal scheduling. The optimal rate is close to one third, which verifies the feasibility of the proposed model 收稿日期: 2018−11−27 基金项目: 国家自然科学基金资助项目 (71301008) 工程科学学报，第 41 卷，第 11 期：1450−1457，2019 年 11 月 Chinese Journal of Engineering, Vol. 41, No. 11: 1450−1457, November 2019 DOI：10.13374/j.issn2095-9389.2018.11.27.002; http://journals.ustb.edu.cn