一种自适应人工蜂群算法求解U型顺序相依拆卸线平衡问题

doi:10.12005/orms.2019.0062

运筹与管理 ›› 2019, Vol. 28 ›› Issue (3): 104-110.DOI: 10.12005/orms.2019.0062

一种自适应人工蜂群算法求解U型顺序相依拆卸线平衡问题

王书伟¹, 郭秀萍¹, 刘佳²

1.西南交通大学经济管理学院,四川成都 610031;
2.青岛理工大学商学院,山东青岛 266520

出版日期:2019-03-25
通讯作者: 郭秀萍(1977-)女,内蒙武川人,副教授,博士生导师,主要从事供应链管理,智能算法研究。
作者简介:王书伟(1985-),男,山东烟台人,副教授,博士生,研究方向:物流供应链管理、优化理论与算法;刘佳(1985-),女,山东淄博人,博士,研究方向:多目标决策、算法分析
基金资助:
国家自然科学基金资助项目(71471151);中央高校基本科研业务费专项资金(26816WCX04)

A Self-adaptive Artificial Bee Colony Algorithm for Solving U-shapedSequence-dependent Disassembly Line Balancing

WANG Shu-wei¹, GUO Xiu-ping¹, LIU Jia²

1.School of Economics & Management, Southwest Jiaotong University, Chengdu 610031 China;
2.Business School, Qingdao University of Technology, Qingdao 266520 China

Online:2019-03-25

摘要/Abstract

摘要： 产品拆卸过程中零部件之间会相互干扰影响任务作业时间,基于该情形构建了多目标U型SDDLBP优化模型,并提出一种自适应ABC算法。所提算法设计了自适应动态邻域搜索方法,以提高局部开发能力;采用了轮盘赌与锦标赛法结合的分段选择法,以有效评价并选择蜜源进行深度开发;建立了基于当前最优解的变异操作,以提高全局探索能力快速跳出局部最优。最后,通过算例测试和实例分析验证算法的高效性。

关键词: U型拆卸线, 顺序相依, ABC算法, 动态邻域搜索

Abstract: Considering interactions among precedence-free tasks in the disassembly process, a multi-objective U-shaped SDDLBP is presented, and a self-adaptive ABC algorithm is developed to solve it. In order to enhance the capability of local exploration, a dynamic neighborhood search method is proposed. A multi-stage evaluation method of roulette wheel selection and tournament selection is used to effectively choose food sources for further exploration. The mutation operator based on the current best solution is designed to improve the global exploitation and jump out of the local optimum rapidly. Finally, the performance of the proposed algorithm is tested by a set of benchmark instances and two case scenarios. Computational results indicate that the proposed algorithm has superior performance.

Key words: U-shaped disassembly line, sequence-dependent, artificial bee colony algorithm, dynamic neighborhood search

中图分类号:

TH165
TP18

王书伟, 郭秀萍, 刘佳. 一种自适应人工蜂群算法求解U型顺序相依拆卸线平衡问题[J]. 运筹与管理, 2019, 28(3): 104-110.

WANG Shu-wei, GUO Xiu-ping, LIU Jia. A Self-adaptive Artificial Bee Colony Algorithm for Solving U-shapedSequence-dependent Disassembly Line Balancing[J]. Operations Research and Management Science, 2019, 28(3): 104-110.

参考文献

[1] Ding L P. 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.
[2] Gupta S M, Gungor A. Product recovery using a disassembly line: challenges and solution[C]. Proceedings of the 2001 IEEE International Symposium on Electronics and the Environment. IEEE, 2001. 36-40.
[3] Gungor A, Gupta S M. A solution approach to the disassembly line balancing problem in the presence of task failures[J]. International Journal of Production Research, 2001, 39(7): 1427-1467.
[4] Mcgovern S M, Gupta S M. Greedy algorithm for disassembly line scheduling[C]. IEEE International Conference on Systems, 2003, 2: 1737-1744.
[5] Mcgovern S M, Gupta S M. Local search heuristics and greedy algorithm for balancing a disassembly line[J]. International Journal of Operations and Quantitative Manaeement, 2005, 11(2): 91-114.
[6] Mcgovern S M, Gupta S M. 2-opt heuristic for the disassembly line balancing problem[C]. Proceedings of the 2003 SPIE International Conference Disassembly Line Balancing on Environmentally Conscious Manufacturing III. Providence, Rhode Island, 2003. 71-84.
[7] Altekin, F T. A comparison of piecewise linear programming formulations for stochastic disassembly line balancing[J]. International Journal of Production Research, 2017, 46(10): 2675-93.
[8] 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.
[9] Gungor A, Gupta S M. Disassembly sequence plan generation using a branch-and-bound algorithm[J]. International Journal of Production Research, 2001, 39(3): 481-509.
[10] Altekin F T, Akkan C. Task-failure-driven rebalancing of disassembly lines[J]. International Journal of Production Research, 2012, 50(18): 4955-4976.
[11] 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.
[12] 丁力平,谭建荣,冯毅雄,高一聪.基于Pareto蚁群算法的拆卸线平衡多目标优化[J].计算机集成制造系统,2009,15(7):1406-1415,1429.
[13] 苏亚军,张则强,胡扬.求解拆卸线平衡问题的一种变邻域搜索算法[J].现代制造工程,2016,(10):19-25.
[14] Zhang Z Q, Wang K P, Zhu L X, 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.
[15] Kalayci C B, Hancilar A, Gungor A, Gupta S M. Multi-objective fuzzy disassembly line balancing using a hybrid discrete artificial bee colony algorithm[J]. Journal of Manufacturing Systems, 2014, 37: 672-682.
[16] Agrawal S, Tiwari M K. A collaborative ant colony algorithm to stochastic mixed-model U-shaped disassembly line balancing and sequencing problem[J]. International Journal of Production Research, 2008, 46(6): 1405-1429.
[17] 李明,张则强,胡扬.U型布局的拆卸线平衡问题及其求解算法研究[J].现代制造工程,2015,(7):7-12.
[18] 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.
[19] 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.
[20] 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.
[21] Aase G R, Schniederjans M J, Olson J R. U-OPT: an analysis of exact U-shaped line balancing procedures[J]. International Journal of Production Research, 2003, 41(17): 4185-4210.
[22] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Kayseri: Erciyes university, 2005.
[23] 唐秋华,林斌,何晓霞等.基于随机机会约束规划的U型装配线平衡优化[J].计算机集成制造系统,2016,22(4):955-964.
[24] Lei D M, Guo X P. A parallel neighborhood search for order acceptance and scheduling in flow shop environment[J]. International Journal of Production Economics, 2015, 165: 12-18.

一种自适应人工蜂群算法求解U型顺序相依拆卸线平衡问题

A Self-adaptive Artificial Bee Colony Algorithm for Solving U-shapedSequence-dependent Disassembly Line Balancing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

[1]	刘佳, 王书伟. 顺序相依拆卸线平衡多目标优化模型及算法研究[J]. 运筹与管理, 2018, 27(6): 82-90.
[2]	谷新军, 郭秀萍. 随机混流U型拆卸线平衡排序问题多目标进化算法优化[J]. 运筹与管理, 2017, 26(9): 52-61.