面向不确定性的车间布局调度集成建模与优化

doi:10.3901/JME.2023.05.235

摘要/Abstract

摘要： 针对制造系统的不确定性和车间布局调度协同优化难题，研究了不确定环境下车间布局调度集成优化问题，旨在耦合车间布局调度中的不确定因素，实现制造系统的高效有序运作。选取工件需求、工序加工时间和设备故障作为影响布局调度集成优化的不确定因素，构建以制造过程中总费用、总完工时间最小和鲁棒指标最大为优化目标的面向不确定性的车间布局调度集成优化模型。设计了一种具有改进选择算子的NSGA-III(NSGA-III with improved selection operator, NSGA-III-ISO)，改进选择算子增强了算法的全局搜索能力和稳定性，同时引入PBI距离并改进其极小值取值方法。通过基准函数测试结果表明，新算法具有更好的前端分布性和收敛性。将集成模型和改进的求解算法应用于车间布局调度工程实例，其结果进一步验证了模型和算法的有效性和可行性。

关键词: 不确定性因素, 布局调度集成建模, 改进的NSGA-III, 多目标优化

Abstract: According to the uncertainty of manufacturing system and the integration optimization problem of workshop layout and scheduling, the integrated optimization of workshop layout and scheduling under uncertain environment is studied, which realized the efficient and orderly operation of manufacturing system by coupling the uncertain factors in shop floor scheduling. The uncertain factors including the workpiece requirements, processing time and equipment failures are selected, which affecting the integrated optimization of layout and scheduling. An uncertainty-oriented workshop layout scheduling integration optimization model is constructed, which taking the minimum total cost, total completion time and maximum robust indexes in the manufacturing process as the optimization objectives. An algorithm called NSGA-III with improved selection operator (NSGA-III-ISO) is designed, which could enhance the global search capability and stability of the algorithm. At the same time, PBI distance is introduced and the method of determining a minimum is improved. The effectiveness of NSGA-III-ISO is verified by DTLZ series test functions and numerical examples. Finally, the integrated model and the improved algorithm are applied to a workshop layout scheduling engineering example, and the results further verified the validity and feasibility of the model and algorithm.

Key words: uncertainty factors, layout and scheduling integrated optimization modeling, improved NSGA-III algorithm, multi-objective optimization

中图分类号:

TP391

王亚良, 高康洪, 范欣宇, 金寿松. 面向不确定性的车间布局调度集成建模与优化[J]. 机械工程学报, 2023, 59(5): 235-246.

WANG Yaliang, GAO Kanghong, FAN Xinyu, JIN Shousong. Uncertainty-oriented Workshop Layout and Scheduling Integration Optimization[J]. Journal of Mechanical Engineering, 2023, 59(5): 235-246.

参考文献

[1] 管超,张则强,李云鹏,等. 多行设备布局的一种多目标差分进化算法和线性规划混合方法[J]. 机械工程学报,2019,55(13):160-174.GUAN Chao,ZHANG Zeqiang,LI Yunpeng,et al. Combining multi-objective differential evolution algorithm and linear programming for multiple row facility layout problem[J]. Journal of Mechanical Engineering,2019,55(13):160-174.
[2] AIELLO G,ENEA M. Fuzzy approach to the robust facility layout in uncertain production environments[J]. International Journal of Production Research,2001,39(18):4089-4101.
[3] 张涛. 不确定环境下基于RTN框架的生产计划与调度集成[D]. 抚顺:辽宁石油化工大学,2019. ZHANG Tao. Integration of production planning and scheduling based on RTN representation under uncertainties[D]. Fushun:Liaoning Shihua University,2019.
[4] PENG Y,ZENG T,FAN L,et al. An improved genetic algorithm based robust approach for stochastic dynamic facility layout problem[J]. Discrete Dynamics in Nature and Society,2018,4:1-8.
[5] MOSLEMIPOUR G, LEE T S, LOONG Y T. Solving stochastic dynamic facility layout problems using proposed hybrid AC-CS-SA meta-heuristic algorithm[J]. International Journal of Industrial and Systems Engineering,2017,28(1):1-31.
[6] 马淑梅,蔡惠森,张一帆,等. 不确定需求下的设备动态布局方法[J]. 中国机械工程,2015,26(11):1494-1502. MA Shumei,CAI Huisen,ZHANG Yifan,et al. Dynamic facility layout method under uncertain product demands[J]. China Mechanical Engineering,2015,26(11):1494-1502.
[7] 查珊珊,郭宇,黄少华,等. 不确定需求下的车间设施动态布局[J]. 吉林大学学报,2017,47(6):1811-1821. ZHA Shanshan,GUO Yu,HUANG Shaohua,et al. Dynamic facility layout for workshop under uncertain product demands[J]. Journal of Jilin University,2017,47(6):1811-1821.
[8] 于晓义,孙树栋,王彦革. 面向随机加工时间的车间作业调度[J]. 中国机械工程,2008,19(19):2319-2324. YU Xiaoyi,SUN Shudong,WANG Yange. Research on stochastic processing time oriented job-shop scheduling[J]. China Mechanical Engineering,2008,19(19):2319-2324.
[9] 唐秋华,何明,何晓霞,等. 随机工时下柔性加工车间的鲁棒优化调度方法[J]. 计算机集成制造系统,2015,21(4):1002-1012. TANG Qiuhua,HE Ming,HE Xiaoxia,et al. Robust optimization scheduling of flexible job shops under stochastic processing times[J]. Computer Integrated Manufacturing Systems,2015,21(4):1002-1012.
[10] 王冰,李巧云,羊晓飞. 模糊车间作业调度的三点满意度模型[J]. 控制与决策, 2012, 27(7):1082-1086. WANG Bing,LI Qiaoyun,YANG Xiaofei. Three-point satisfaction-degree model for fuzzy job-shop scheduling problem[J]. Control and Decision,2012,27(7):1082-1086.
[11] 杨枫,叶春明,施明华. 基于模糊软集的中药制药车间不确定调度模型和算法求解[J]. 系统管理学报,2020,29(1):119-128. YANG Feng,YE Chunming,SHI Minghua. Uncertain scheduling model and algorithm solution for traditional chinese medicine pharmaceutical workshop scheduling based on fuzzy soft set[J]. Journal of Systems & Management,2020,29(1):119-128.
[12] 吴正佳,何海洋,黄灿超,等. 带机器故障的柔性作业车间动态调度[J]. 机械设计与研究,2015,31(3):94-98. WU Zhengjia,HE Haiyang,HUANG Canchao, et al. Flexible job shop dynamic scheduling problem research with machine fault[J]. Machine Design & Research,2015,31(3):94-98.
[13] 包博,张琳,张搏. 设备故障条件下柔性作业车间重调度方法[J]. 计算机工程与应用,2018,54(19):248-253. BAO Bo,ZHANG Lin,ZHANG Bo. Rescheduling method of flexible job shop under condition of equipment failure[J]. Computer Engineering and Applications,2018,54(19):248-253.
[14] 张国辉,吴立辉,聂黎,等. 考虑机器故障的柔性作业车间鲁棒调度方法[J]. 系统仿真学报,2016,28(4):867-873. ZHANG Guohui, WU Lihui, NIE Li, et al. Robust flexible job shop scheduling method with machine breakdowns[J]. Journal of System Simulation,2016,28(4):867-873.
[15] 薛冬娟,殷喜龙,潘颖. 基于柔性作业调度的离散制造车间布局优化研究[J]. 制造业自动化,2015,37(16):68-72,75. XUE Dongjuan, YIN Xilong, PAN Ying. A method of workshop layout optimization based on FJSP[J]. Manufacturing Automation,2015,37(16):68-72,75.
[16] MORINGAGA E, AKAMATSU H, IWASAKI K, et al. A facility layout planning method considering routing and temporal efficiency[C]//2016 International Symposium on Flexible Automation (ISFA). Cleveland:Institute of Electrical and Electronics Engineers Inc,2016:186-191.
[17] 刘琼,赵海飞. 基于多目标果蝇算法面向低碳的车间布局与调度协同优化[J]. 机械工程学报,2017,53(11):122-133. LIU Qiong,Zhao Haifei. Integrated optimization of workshop layout and scheduling to reduce carbon emissions based on a multi-objective fruit fly optimization algorithm[J]. Journal of Mechanical Engineering,2017,53(11):122-133.
[18] EBRAHIMI A,JEON H W,LEE S,et al. Minimizing total energy cost and tardiness penalty for a scheduling-layout problem in a flexible job shop system:A comparison of four metaheuristic algorithms[J]. Computers and Industrial Engineering,2020,141.
[19] 代文锋. 区间直觉模糊多属性群决策方法研究[D]. 大连:大连理工大学,2018. DAI Wenfeng. Research on the interval intuitionistic fuzzy multi-attribute group decision making method[D]. Dalin:Dalian University of Techology,2018.
[20] 李凡. 模糊专家系统[M]. 武汉:华中理工大学出版社,1995. LI Fan. Fuzzy expert system[M]. Wuhan:Huazhong University of Science and Technology Press,1995.
[21] 冉静学. 三角模糊数排序方法的研究[J]. 中央民族大学学报,2011,20(4):37-42. RAN Jingxue. The research of the rank of triangular fuzzy numbers[J]. Journal of Minzu University of China,2011,20(4):37-42.
[22] XU J,TU Y,ZENG Z. Bilevel optimization of regional water resources allocation problem under fuzzy random environment[J]. Journal of Water Resources Planning and Management,2013,139(3):246-264.
[23] XU J,SONG X. Multi-objective dynamic layout problem for temporary construction facilities with unequal-area departments under fuzzy random environment[J]. Knowledge-Based Systems,2015,81:30-45.
[24] BI X,WANG C. An improved NSGA-III algorithm based on elimination operator for many-objective optimization[J]. Memetic Computing,2017,9(4):361-383.
[25] LI K,DEB K,ZHANG Q,et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J]. IEEE Transactions on Evolutionary Computation,2015,19(5):694-716.
[26] ZHANG Q,LI H. MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[27] 王亚良,钱其晶,陈勇,等. 外部种群完全反馈的元胞差分算法设计及应用[J]. 计算机集成制造系统,2017,23(8):1679-1691. WANG Yaliang,QIAN Qijing,CHEN Yong,et al. Design and application of cellular differential algorithm based on complete feedback from external population[J]. Computer Integrated Manufacturing Systems,2017,23(8):1679-1691.
[28] Huband S,Hingston P,Barone L,et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation,2006,10(5):477-506.
[29] DEB K,JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I:solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation,2014,18(4):577-601.
[30] TIAN Y,CHENG R,ZHANG X,et al. PlatEMO:A Matlab platform for evolutionary multi-objective optimization[J]. IEEE Computational Intelligence Magazine,2017,12(4):73-87.