第Ⅱ类拆卸线平衡问题建模及优化

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

中国管理科学 ›› 2019, Vol. 27 ›› Issue (10): 120-127.doi: 10.16381/j.cnki.issn1003-207x.2019.10.012

第Ⅱ类拆卸线平衡问题建模及优化

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

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

收稿日期:2018-02-04 修回日期:2018-04-09 出版日期:2019-10-20 发布日期:2019-10-25
通讯作者: 郭秀萍(1977-),女(汉族),内蒙武川人,西南交通大学经济管理学院,副教授,博士生导师,研究方向:物流供应链管理、智能算法,E-mail:gxp@home.swjtu.edu.cn. E-mail:gxp@home.swjtu.edu.cn
基金资助:
国家自然科学基金资助项目（71471151）；四川省教育厅自然科学一般项目（18ZB0587）；四川省循环经济中心一般项目（XHJJ-1917）

Modeling and Optimizing the Disassembly Line Balancing Problem of Type II

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

Received:2018-02-04 Revised:2018-04-09 Online:2019-10-20 Published:2019-10-25

摘要/Abstract

摘要： 环境资源问题日益凸显、人们环保意识的增强以及经济利益的驱动，促使社会进行废旧产品回收再利用，以发展绿色经济。拆卸作为回收再利用过程中的核心环节，采用流水线的方式组织产品精细化拆卸，可实现资源最大化价值。然而，零部件作业任务在流水线上分配排序过程复杂，各工作站上的作业负荷需保持相对均衡，才能保证拆卸线高效运行。为此，本文在拆卸线工作站数量固定的情况下，以最短节拍时间和均衡任务在工作站上的分配为目标，建立第Ⅱ类拆卸线平衡问题优化模型，并提出一种并行动态邻域深度搜索算法进行求解。所提算法采用动态搜索机制实现解在各邻域结构集内的并行深度搜索；通过设置扰动阈值对解实施干扰，以加快跳出局部最优；在节拍时间调整过程中，采用基于二分法的定界策略，以实现向最优节拍时间的快速靠拢。最后，通过不同规模算例验证了模型的有效性以及算法的高效性。

关键词: 拆卸线, 拆卸线平衡问题, 并行动态邻域深度搜索, 第II类

Abstract: The increasing environment and resource problems, enhanced public environmental awareness, coupled with tremendous economic interests, force manufacturers to recycle and reuse the sharp growth of discarded products for reserving natural resources and reducing environmental pollution. Disassembly is one of the key processes in product recovery, which directly affects the benefit of remanufacturingand the harmful degree on environment. However, the unbalanced phenomenon often occurs when the tasks are distributed across the workstations in the process of disassembly, which affects the disassembly efficiency. Therefore, in this paper, to deal with returned products disassembled on the disassembly line with fixed number of workstations, a disassembly line balancing problem of type II (DLBP-II) is presented to minimize the cycle time and ensure the balance of workloads among workstations. Then a parallel dynamic neighborhood depth search (PDNDS) algorithm was proposed to solve it. In the PDNDS, two sets of neighborhood structure are constructed. A dynamic search strategy is applied to realize parallel search of the solutions. The solution can jump out of the local optimum rapidly by using the threshold value mechanism. During the adjustment of cycle time, a bound strategy based on binary search is introduced to accelerate the search speed. Finally,the validity of the constructed model and the superiority of the proposed algorithm are demonstrated by benchmark instances.

Key words: disassembly line, disassembly line balancing problem, parallel dynamic neighborhood depth search, type II

中图分类号:

TH166
TP18

王书伟, 郭秀萍, 刘佳. 第Ⅱ类拆卸线平衡问题建模及优化[J]. 中国管理科学, 2019, 27(10): 120-127.

WANG Shu-wei, GUO Xiu-ping, Liu Jia. Modeling and Optimizing the Disassembly Line Balancing Problem of Type II[J]. Chinese Journal of Management Science, 2019, 27(10): 120-127.

参考文献

[1] 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.
[2] Mcgovern S M, Gupta S M. Greedy algorithm for disassembly line scheduling[C]. IEEE International Conference on Systems, man, and Cybernetics, Crystal City, Oct. 5-8, IEEE, 2003:1737-1744.
[3] McGovern S M, Gupta S M. 2-opt heuristic for the disassembly line balancing problem[C]//Proceedings of the 2003 SPIE International Conference on Environmentally Conscious Manufacturing III. Octomber, Providence, Rhode Island, 2003.
[4] Altekin F T, Akkan C. Task-failure-driven rebalancing of disassembly lines[J]. International Journal of Production Research, 2012, 50(18):4955-4976.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] Kalayci C B, Gupta S M. A particle swarm optimization algorithm with neighborhood-based mutation for sequence-dependent disassembly line balancing problem[J]. The International Journal of Advanced Manufacturing Technology, 2013, 69(1):197-209.
[10] Kalayci C B, Polat O, Gupta S M. A variable neighbourhood search algorithm for disassembly lines[J]. Journal of Manufacturing Technology Management, 2015, 26(2):182-196.
[11] Agrawal S, Tiwari M. 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.
[12] 胡扬. 多目标拆卸线平衡问题的Pareto细菌觅食算法[J]. 计算机应用研究, 2016, 33(11):3265-3269.
[13] Kalayci C B, Hancilar A. Multi-objective fuzzy disassembly line balancing using a hybrid discrete artificial bee colony algorithm[J]. Journal of Manufacturing Systems, 2015, 37:672-682.
[14] McMullen P R. Using simulated annealing to solve a multi-objective assembly line balancing problem with parallel workstations[J]. International Journal of Production Research, 1998, 36(10):2717-2741.
[15] Bentaha M L, Battaïa O, Dolgui A. Disassembly line balancing problem with fixed number of workstations under uncertainty[J]. IFAC Proceedings Volumes, 2014, 47(3):3522-3526.
[16] Kalaycılar E G, Azizoǧlu M, Yeralan S. A disassembly line balancing problem with fixed number of workstations[J]. European Journal of Operational Research, 2016, 249(2):592-604.
[17] Mladenovic N, Hansen P. Variable neighborhood search[J]. Computers & Operations Research, 1997, 24(11):1097-1100.
[18] 王雷, 许绍云, 赵扬,等. 有限缓冲区的多节点订单接受模型与算法[J]. 中国管理科学, 2015, 23(12):135-141.
[19] 肖建华, 王超文, 陈萍,等. 基于城市道路限行的多能源多车型车辆路径优化[J]. 系统工程理论与实践, 2017, 37(5):1339-1348.
[20] Tapkan P, Özbakır L, Baykasoǧlu A. Bee algorithms for parallel two-sided assembly line balancing problem with walking times[J]. Applied Soft Computing, 2016, 39:275-291.
[21] Tang Qiuhua, Li Zixiang, Zhang Liping. An effective discrete artificial bee colony algorithm with idle time reduction techniques for two-sided assembly line balancing problem of type-II[J]. Computers & Industrial Engineering, 2016, 97:146-156.

第Ⅱ类拆卸线平衡问题建模及优化

Modeling and Optimizing the Disassembly Line Balancing Problem of Type II

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 10

[1]	马文建, 刘伟, 李传昭. 跨企业组织协同产品开发中供应商早期参与策略研究[J]. 中国管理科学, 2011, 19(2): 147-154.
[2]	张汉鹏, 邱菀华. 资源约束下多项目调度的改进遗传算法[J]. 中国管理科学, 2007, 15(5): 78-82.
[3]	姚建明, 张秀敏, 刘丽文. 基于改进蚂蚁算法的拉动式供应链动态调度分析[J]. 中国管理科学, 2006, (3): 20-26.