作业时间依赖顺序的拆卸线平衡多目标优化

doi:10.16381/j.cnki.issn1003-207x.2019.2007

摘要/Abstract

摘要： 在废旧产品拆卸时无先后关系约束的任务之间可能存在拆卸干扰，使任务作业时间依赖于拆卸顺序，导致产品总作业时间不确定，从而影响拆卸线的平衡。为此，考虑拆卸过程中任务间的相互干扰，以最小化拆卸成本和环境危害为目标，构建作业时间依赖顺序的拆卸线平衡多目标优化模型，并提出一种Pareto人工蜂群算法进行求解，采用混合生成法保证种群质量与多样性，设计变邻域深度搜索策略以提高雇佣蜂局部开采效率，为降低侦察蜂探测的盲目性采用基于外部存档的单点变异算子进行搜索。最后通过算例与实例验证算法的有效性以及平衡任务在拆卸线上分配的重要性。

关键词: 拆卸线平衡, 顺序相依, 人工蜂群算法, 帕累托

Abstract: Remanufacturing is an effective way to realize the reutilization of resources. Disassembly plays a key role in remanufacturing since it allows for the selective separation of desired parts from the end-of-life (EOL) products. Disassembly line is the best choiceto deal with EOL products on a large scale, so it is essential that it be designed and balanced to work efficiently. However, in the disassembly process, some parts may interact with each other and their disassembly times will be incremented by additional operations, and this affects the balance of disassembly line. In order to solve the disassembly interference among parts, in this research a sequence-dependent disassembly line balancing problem is presented with two objectives including minimization of the disassembly cost and environmental hazards. Then, a Pareto artificial bee colony algorithm is proposed for addressing this multi-objective optimization problem. A mixed strategy is designed to build an initial population with high quality and diversity, and some improvements are made in local exploitation and global exploration to accelerate the search speed. Finally, aset of benchmark instances is used to test the performance of the proposed algorithm. Computational results evidently indicate the superior efficiency of the proposed algorithm.In addition, a case study is presented to illustrate that balancing the tasks among workstations can effectively avoid the tasks with more time increments being disassembled on priority.

Key words: disassembly line balancing problem, sequence-dependent, artificial bee colony, Pareto

中图分类号:

TH166
TP18

刘佳, 王书伟. 作业时间依赖顺序的拆卸线平衡多目标优化[J]. 中国管理科学, 2021, 29(4): 158-168.

LIU Jia, WANG Shu-wei. Multi-objective Optimization for Disassembly Line Balancing Problem with Sequence-dependent Part Removal Times[J]. Chinese Journal of Management Science, 2021, 29(4): 158-168.

参考文献

[1] Gupta S M, Gungor A. Product recovery using a disassembly line:Challenges and solution[C]//Proceedings of the IEEE International Symposium on Electronics and the Environment, Denver,CO,USA, May 7-9, 2001.
[2] Gungor A, Gupta S M. A solution approach to the disassembly line balancing problem in the presence of task failures[J]. International Journal of ProductionResearch, 2001, 39(7):1427-1467.
[3] Mcgovern S M, Gupta S M. Local search heuristics and greedy algorithm for balancing a disassembly line[J]. International Journal of Operations and Quantitative Management, 2005, 11(2):91-114.
[4] Ren Yaping, Zhang Chaoyong, Zhao Fu, et al. Disassembly line balancing problem using interdependent weights-based multi-criteria decision making and 2-Optimal algorithm[J]. Journal of Cleaner Production, 2018, 174:1475-1486.
[5] Ilgin M A, Akçay H, Araz C. Disassembly line balancing using linear physical programming[J]. International Journal of Production Research, 2017, 55(20):6108-6119.
[6] Bentaha M L, Dolgui A, Battaïa O, et al. Profit-oriented partial disassembly line design:Dealing with hazardous parts and task processing times uncertainty[J]. International Journal of Production Research, 2018, 56(24):7220-7242.
[7] Mcgovern S M, Gupta S M. Combinatorial optimization analysis of the unary NP-complete disassembly line balancing problem[J]. International Journal of Production Research, 2007, 45(18-19):4485-4511.
[8] Ren Yaping, Yu Daoyuan, Zhang Chaoyong, 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.
[9] Mete S, ÇilZ A, Özceylan E, et al. An optimization support for the design of hybrid production lines including assembly and disassembly tasks[J]. International Journal of Production Research, 2018, 56(24):7375-7389.
[10] Kalayci C B, Hancilar A, Gungor A, et al. Multi-objective fuzzy disassembly line balancing using a hybrid discrete artificial bee colony algorithm[J]. Journal of Manufacturing Systems, 2015, 37:672-682.
[11] 王书伟, 郭秀萍, 刘佳. 第Ⅱ类拆卸线平衡问题建模及优化[J].中国管理科学, 2019, 29(10):118-125.
[12] Kalayci C B, Polat O, Gupta S M. A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem[J]. Annals of Operations Research, 2016, 242(2):321-354.
[13] Kalayci C B, Gupta S M. A tabu search algorithm for balancing a sequence-dependent disassembly line[J]. Production Planning & Control, 2014, 25(2):149-160.
[14] 刘佳, 王书伟. 一种混合蜂群算法求解顺序相依拆卸线平衡问题[J].控制与决策, 2018, 33(4):698-904.
[15] 周愉峰,李志,刘思峰.基于随机p-鲁棒优化的国家血液战略储备库选址-库存模型[J].中国管理科学, 2018, 26(10):52-63.
[16] 方文婷,艾时钟,王晴,等.基于混合蚁群算法的冷链物流配送路径优化研究[J].中国管理科学, 2019, 27(11):107-115.
[17] Li Junqing, Bai Shunchang, Duan Peiyong, et al. An improved artificial bee colony algorithm for addressing distributed flow shop with distance coefficient in a prefabricated system[J]. International Journal of Production Research, 2019, 57(22):6922-6942.
[18] Choong S S, Wonga L P, Lim C P. An artificial bee colony algorithm with a Modified Choice Function for the traveling salesman problem[J]. Swarm and Evolutionary Computation, 2019, 44:622-635.
[19] Karaboga D. An idea based on honey bee swarm for numerical optimization. Technical Report TR06. Turkey:Computer Engineering Department, Engineering Faculty. Erciyes University:2005.
[20] Ding Liping, Feng Yixiong, Tan Jianrong, et al. A new multi-objective ant colony algorithm for solving the disassembly line balancing problem[J]. International Journal of Advanced Manufacturing Technology, 2010, 48(5):761-771.
[21] 丁力平, 谭建荣, 冯毅雄, 等. 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统, 2009, 15(7):1406-1413.