资源约束下拆卸线平衡问题的建模与改进混合蛙跳算法

摘要/Abstract

摘要： 针对实际拆卸线中涉及的资源约束和危害零件问题，以资源总数、工作站数和危害指数为目标函数，构建了多目标资源约束拆卸线平衡问题数学模型。基于AND/OR关系，在优先关系矩阵中添加OR关系的描述，解决了产生初始解仅考虑AND关系的不足问题。提出了一种融入Pareto思想的改进混合蛙跳算法，该算法采用基于满意度的改进排序分组策略来解决多目标优化种群分组问题；提出了一种新的交叉变异方式进行局部搜索以提高收敛性能；利用拥挤距离机制评价非劣解集以及有效地维护外部档案容量。采用田口实验和统计分析方法确定了算法最佳参数组合，将改进前后的混合蛙跳算法及NSGA-Ⅱ对测试算例的求解结果进行了多指标对比分析，研究结果表明：改进混合蛙跳算法具有良好的综合求解优势。最后，将所提算法应用到某电冰箱的资源约束拆卸线平衡问题中，为决策者提供了较优的拆卸方案。

关键词: 拆卸线平衡问题, 资源约束, 改进混合蛙跳算法, 多目标优化

Abstract: Aiming at the resource constraints and the hazardous parts involved in the actual disassembly lines, a mathematical model of multi-objective resource constraint disassembly line balancing problem was constructed considering the total number of resources, the number of stations and the hazard as index three objective functions to be optimized. Based on the AND/OR relation, the descriptions of the OR relation were added to the priority relation matrix, which solved the problems that the initial solution only took into account the AND relation. An improved SFLA incorporating the Pareto's idea was proposed. An improved ranking grouping strategy was adopted based on satisfaction to solve the multi-objective optimization population grouping problems for the proposed algorithm. A new cross-mutation method was proposed to implement the local search to improve the convergence. The crowded distance mechanism was used to evaluate the non-inferior solution sets and effectively maintain the size of the external file. And Taguchi experiment and statistical analysis method were used to determine the optimal combinations of algorithm parameters. The multi-index was used to compare and analyze the results of the testing instances obtained by the SFLA before and after the improvement as well as the NSGA-Ⅱ. The research results show that the improved SFLA has a good comprehensive solution. Finally, the algorithm was applied to a refrigerator disassembly line, which provided a better solution scheme for decision makers.

Key words: disassembly line balance problem, resource constraint, improved shuffled frog leaping algorithm(SFLA), multi-objective optimization

中图分类号:

蔡宁;张则强;张颖;朱立夏. 资源约束下拆卸线平衡问题的建模与改进混合蛙跳算法[J]. 中国机械工程.

CAI Ning;ZHANG Zeqiang;ZHANG Ying;ZHU Lixia. Modeling and Improved SFLA for Disassembly Line Balancing under Resource Constraints[J]. China Mechanical Engineering.

参考文献

[1]刘飞，李聪波，曹华军，等. 基于产品生命周期主线的绿色制造技术内涵及技术体系框[J]. 机械工程学报， 2009, 45(12)：115-120.
LIU Fei, LI Congbo, CAO Huajun, et al. Green Manufacturing Technology Connotation and System Framework Based on Product Life Cycle[J]. Journal of Mechanical Engineering, 2009, 45(12)：115-120.
[2]MCGOVERN S M, GUPTA S M. A Balancing Method and Genetic Algorithm for Disassembly Line Balancing[J]. European Journal of Operational Research, 2007, 179(3)：692-708.
[3]HEZER S, KARA Y. A Network-based Shortest Route Model for Parallel Disassembly Line Balancing Problem[J]. International Journal of Production Research, 2015, 53(6)：1849-1865.
[4]KOC A, SABUNCUOGLU I, EREL E. Two Exact Formulations for Disassembly Line Balancing Problems with Task Precedence Diagram Construction Using an AND/OR Graph[J]. IIE Transactions, 2009, 41(10)：866-881.
[5]RIGGS R J, BATTAIA O, HU S J. Disassembly Line Balancing under High Variety of End of Life States Using a Joint Precedence Graph Approach[J]. Journal of Manufacturing Systems, 2015, 37：638-648.
[6]ZHANG Z, WANG K, ZHU L, et al. A Pareto Improved Artificial Fish Swarm Algorithm for Solving a Multi-objective Fuzzy Disassembly Line Balancing Problem[J]. Expert Systems with Applications, 2017, 86：165-176.
[7]REN Y, YU D, ZHANG C, et al. An Improved Gravitational Search Algorithm for Profit-oriented Partial Disassembly Line Balancing Problem[J]. International Journal of Production Research, 2017, 55(24)：7302-7316.
[8]OZCEYLAN E, KALAYCI C B, GUNGOR A, et al. Disassembly Line Balancing Problem：a Review of the State of the Art and Future Directions[J]. International Journal of Production Research, 2018(1)：1-23.
[9]AVIKAL S, MISHRA P K, JAIN R. A Fuzzy AHP and PROMETHEE Method-based Heuristic for Disassembly Line Balancing Problems[J]. International Journal of Production Research, 2014, 52(5)：1306-1317.
[10]ALTEKIN F T, KANDILLER L, OZDEMIREL N E. Profit-oriented Disassembly Line Balancing[J]. International Journal of Production Research, 2008, 46(10)：2675-2693.
[11]BENTAHA M L, BATTAIA O, DOLGUI A. An Exact Solution Approach for Disassembly Line Balancing Problem under Uncertainty of the Task Processing Times[J]. International Journal of Production Research, 2015, 53(6)：1807-1818.
[12]李六柯，张则强，胡扬，等. 基于多目标算法与动态仿真的带调整时间的拆卸线平衡优化方法[J]. 中国机械工程, 2017, 28(17)：2115-2124.
LI Liuke, ZHANG Zeqiang, HU Yang, et al. Optimization of Disassembly Line Balancing Problems with Setup Times Based on Multi-objective Algorithm and Dynamic Simulation[J]. China Mechanical Engineering, 2017, 28(17)：2115-2124.
[13]丁力平，谭建荣，冯毅雄，等. 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统, 2009, 15(7)：1406-1413.
DING Liping, TAN Jianrong, FENG Yixiong, et al. Multi-objective Optimization for Disassembly Line Balancing Based on Pareto Ant Colony Algorithm[J]. Computer Integrated Manufacturing Systems, 2009, 15(7)：1406-1413.
[14]LIU J, WANG S. Balancing Disassembly Line in Product Recovery to Promote the Coordinated Development of Economy and Environment[J]. Sustainability， 2017, 9(3)：1-15.
[15]汪开普，张则强，毛丽丽，等. 多目标拆卸线平衡问题的Pareto人工鱼群算法[J]. 中国机械工程, 2017, 28(2)：183-190.
WANG Kaipu, ZHANG Zeqiang, MAO Lili, et al. Pareto Artificial Fish Swarm Algorithm for Multi-objective Disassembly Line Balance Problems[J]. China Mechanical Engineering, 2017, 28 (2)：183-190.
[16]李六柯，张则强，朱立夏，等.多目标不完全拆卸线平衡问题的建模与优化[J]. 机械工程学报, 2018, 54(3)：125-136.
LI Liuke, ZHANG Zeqiang, ZHU Lixia, et al. Modeling and Optimizing for Multi-objective Partial Disassembly Line Balancing Problem [J]. Journal of Mechanical Engineering, 2018, 54(3)：125-136.
[17]METE S, CIL Z A, OZCEYLAN E, et al. Resource Constrained Disassembly Line Balancing Problem[J]. IFAC Papers Online, 2016, 49(12)：921-925.
[18]崔文华，刘晓冰，王伟，等. 混合蛙跳算法研究综述[J]. 控制与决策, 2012, 27(4)：481-486.
CUI Wenhua, LIU Xiaobin, WANG Wei, et al. Survey on Shuffled Frog Leaping Algorithm[J]. Control and Decision, 2012, 27(4)：481-486.
[19]王松，孙振忠，郭建文，等. 基于混合蛙跳算法的复杂产品装配序列规划[J]. 计算机集成制造系统, 2014(12)：2991-2999.
WANG Song, SUN Zhenzhong, GUO Jianwen, et al. Assembly Sequence Planning Based on Shuffled Frog Leaping Algorithm[J]. Computer Integrated Manufacturing Systems, 2014(12)：2991-2999.
[20]DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multi-objective Genetic Algorithm：NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2)：182-197.
[21]KALAYCI C B, GUPTA S M. A Particle Swarm Optimization Algorithm for Solving Disassembly Line Balancing Problem[C]∥Proceedings for the Northeast Region Decision Sciences Institute. Newport, 2012：2142-2148.