基于多目标算法与动态仿真的带调整时间的拆卸线平衡优化方法

摘要/Abstract

摘要： 针对拆卸方向改变对作业时间的影响，以最小化拆卸成本、无效作业率和不平滑率为优化目标，构建了考虑调整时间的多目标拆卸线平衡问题模型，并提出了一种Pareto免疫遗传算法与仿真技术相结合的求解方法。算法融合了遗传算子和免疫算子，能有效避免解出现退化和陷入局部最优。通过求解25项拆卸任务算例，并与现有5种算法进行对比，验证了所提算法的有效性。进而将所提模型和算法应用于某打印机拆卸线实例，进一步考虑拆卸时间不确定、存在故障等实际情况，运用仿真技术分析与优化，结果表明所提方法能有效降低等待和堵塞造成的无效作业时间，提高拆卸效率。

关键词: 拆卸线平衡问题, 多目标优化, 调整时间, 免疫遗传算法, 仿真

Abstract: In view of the influences of disassembly direction changes on operation times, a multi-objective model of disassembly line balancing problem considering the setup times was established involving three optimization objectives, i.e. minimizing the disassembly costs, minimizing the invalid work rates and minimizing the non-smooth rates. And a Pareto immune genetic algorithm integrated with the simulation technology was proposed. The proposed algorithm introduced the genetic operator and the immune operator which might avoid the local optimum and ensure the global convergence. The proposed algorithm was applied to a 25-task disassembly case, the results of which indicate the effectiveness of the proposed algorithm by comparing with the other 5 algorithms. Further, the proposed model and the algorithm were applied to design a printer disassembly line. Finally, considering the uncertainty of the disassembly times and failures in the actual disassembly productions, simulation technology was used to analyze and optimize the disassembly line. And the simulation results show that the proposed method may effectively reduce the invalid times caused by waiting and blocking and improve the disassembly efficiency.

Key words: disassembly line balancing problem, multi-objective optimization, setup time, immune genetic algorithm, simulation

中图分类号:

TH165

李六柯;张则强;胡扬;邹宾森. 基于多目标算法与动态仿真的带调整时间的拆卸线平衡优化方法[J]. 中国机械工程.

LI Liuke;ZHANG Zeqiang;HU Yang;ZOU Binsen. Optimization of Disassembly Line Balancing Problems with Setup Times Based on Multi-objective Algorithm and Dynamic Simulation[J]. China Mechanical Engineering.

参考文献

[1]GUNGOR A, GUPTA S M. Disassembly Line in Product Recovery[J]. International Journal of Production Research,2002,40(11):2569-2589.

[2]GUPTA S M, MCGOVERN S M. Disassembly Sequencing Problem: a Case Study of a Cell Phone[C]// Proceedings of the 2004 SPIE International Conference on Environmentally Conscious Manufacturing. Bellingham, USA: SPIE,2004:43-52.

[3]MCGOVERN S M, GUPTA S M. 2-opt Heuristic for the Disassembly Line Balancing Problem[C]//Proceedings of the SPIE International Conference on Environmentally Conscious Manufacturing III. Bellingham, USA: SPIE,2004:71-84.

[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]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.

[6]ZHANG Z F, FENG Y X, TAN J R, et al. A Novel Approach for Parallel Disassembly Design Based on a Hybrid Fuzzy-time Model[J]. Journal of Zhejiang Universityence A,2015,16(9):724-736.

[7]MCGOVERN S M, GUPTA S M. Uninformed and Probabilistic Distributed Agent Combinatorial Searches for the Unary NP-complete Disassembly Line Balancing Problem[C]//Proceedings of SPIE-The International Society for Optical Engineering. Bellingham, USA: SPIE,2005:81-92.

[8]朱兴涛, 张则强, 朱勋梦, 等. 求解多目标拆卸线平衡问题的一种蚁群算法[J]. 中国机械工程,2014,25(8):1075-1079.
ZHU Xingtao, ZHANG Zeqiang, ZHU Xunmeng, et al. An Ant Colony Optimization Algorithm for Multi-objective Disassembly Line Balancing Problem[J]. China Mechanical Engineering,2014,25(8):1075-1079.

[9]KALAYCI C B, GUPTA S M. Artificial Bee Colony Algorithm for Solving Sequence-dependent Disassembly Line Balancing Problem[J]. Expert Systems with Applications,2013,40(18):7231-7241.

[10]KALAYCI C B, GUPTA S M. A Particle Swarm Optimization Algorithm with Neighborhood-based Mutation for Sequence-dependent Disassembly Line Balancing Problem[J]. Proceedings for the Northeast Region Decision Sciences Institute,2013,69(1/4):197-209.
[11]丁力平, 谭建荣, 冯毅雄, 等. 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统,2009,15(7):1406-1413.
DING Liping, TAN Jianrong, FENG Yixiong, et al. Multiobjective Optimization for Disassembly Line Balancing Based on Pareto Ant Colony Algorithm[J]. Computer Integrated Manufacturing Systems,2009,15(7):1406-1413.

[12]MCGOVERN S M, GUPTA S M. Ant Colony Optimization for Disassembly Sequencing with Multiple Objectives[J]. International Journal of Advanced Manufacturing Technology,2006,30(5/6):481-496.

[13]汤洪涛, 丁彬楚, 李修琳,等. 基于改进免疫遗传算法的混合车间调度研究[J]. 中国机械工程,2014,25(9):1189-1194.
TANG Hongtao, DING Binchu, LI Xiulin. Improved Immune Genetic Algorithm for Mixed-model Scheduling Problem[J]. China Mechanical Engineering,2014,25(9):1189-1194.

[14]PAN G, LI K, OUYANG A, et al. Hybrid Immune Algorithm Based on Greedy Algorithm and Delete-cross Operator for Solving TSP[J]. Soft Computing,2016,20(2):1-12.

[15]GHOSH T, DOLOI B, DAN P K. An Immune Genetic Algorithm for Inter-cell Layout Problem in Cellular Manufacturing System[J]. Production Engineering,2015,10(2):1-18.