Pareto Hybrid Ant Colony and Genetic Algorithm for Multi-Objective U-Shaped Disassembly Line Balancing Problem

ZHANG Zeqiang; WANG Kaipu; ZHU Lixia; CHENG Wenming

doi:10.3969/j.issn.0258-2724.2018.03.026

Volume 31 Issue 3

Jun. 2018

Turn off MathJax

Article Contents

Abstract

References

Journal of Southwest Jiaotong University > 2018 > 53(3): 628-637, 660.

HE Chuan, FENG Kun, FANG Yong. Review and Prospects on Constructing Technologies of Metro Tunnels Using Shield Tunnelling Method[J]. Journal of Southwest Jiaotong University, 2015, 28(1): 97-109. doi: 10.3969/j.issn.0258-2724.2015.01.015

Citation:

ZHANG Zeqiang, WANG Kaipu, ZHU Lixia, CHENG Wenming. Pareto Hybrid Ant Colony and Genetic Algorithm for Multi-Objective U-Shaped Disassembly Line Balancing Problem[J]. Journal of Southwest Jiaotong University, 2018, 53(3): 628-637, 660. doi: 10.3969/j.issn.0258-2724.2018.03.026

Citation:

PDF( 1987 KB)

Pareto Hybrid Ant Colony and Genetic Algorithm for Multi-Objective U-Shaped Disassembly Line Balancing Problem

doi: 10.3969/j.issn.0258-2724.2018.03.026

Received Date: 02 Aug 2016
Publish Date: 01 Jun 2018

Abstract

Abstract

Owing to the incapability of traditional methods in solving multi-objective U-shaped disassembly line balancing problem (UDLBP), a multi-objective ant colony genetic algorithm based on Pareto set is proposed to solve the UDLBP. In constructing the initial solution phase, the maximum operation time and the minimum disassembly cost difference were collaboratively considered as the heuristic information of the ants. The feasible disassembly sequence was searched using the ant colony algorithm, and the Pareto solution set was obtained based on the dominance relationship among the multiple objectives. Further, the Pareto non-inferior solutions of the ant colony algorithm were used as the chromosomes of the genetic operator. Moreover, the results of the genetic operator were fed back to the accumulation of pheromone on the optimal disassembly sequence. The crowding distance was regarded as the global pheromone update strategy to balance the effect of multi-objective function regarding the pheromone and thereby make the algorithm obtain better solutions readily. The proposed algorithm was applied to 52 disassembly task examples and a printer disassembly line instance. Compared with the Pareto ant colony algorithm, the performances of the three evaluation indicators of the 8 non-inferior solutions obtained using the proposed algorithm are improved by 50.43%, 3.25%, and 14.10%, respectively. In the example application, the proposed algorithm obtained eight balancing schemes, which verifies the effectiveness, superiority, and practicability of the proposed algorithm.
- U-shaped disassembly line balancing,
- multi-objective optimization,
- ant colony algorithm,
- genetic algorithm,
- Pareto set

FullText(HTML)

References(23)

References

国务院.国务院关于印发《中国制造2025》的通知[J].中华人民共和国国务院公报, 2015(16):10-26. http://www.cnki.com.cn/Article/CJFDTOTAL-ZQMP201503004.htm

GUNGOR A, GUPTA S M. Disassembly line in product recovery[J]. International Journal of Production Research, 2002, 40(11):2569-2589. doi: 10.1080/00207540210135622

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. doi: 10.1080/00207543.2013.831999

BENTAHA M L, BATTAIA O, DOLGUI A. Lagrangian relaxation for stochastic disassembly line balancing problem[J]. Procedia CIRP, 2014(17):56-60. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=CC0214534488

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. doi: 10.1016/j.ejor.2005.03.055

朱兴涛, 张则强, 朱勋梦, 等.求解多目标拆卸线平衡问题的一种蚁群算法[J].中国机械工程, 2014, 25(8):1075-1079. doi: 10.3969/j.issn.1004-132X.2014.08.016

ZHU Xingtao, ZHANG Zeqaing, 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. doi: 10.3969/j.issn.1004-132X.2014.08.016

MCGOVERN S M, GUPTA S M. Ant colony optimization for disassembly sequencing with multiple objectives[J]. The International Journal of Advanced Manufacturing Technology, 2006, 30(5):481-496. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f857d98cf5114ed7c4cd3ae30371f41e

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. [S. l.]: Newport, 2012: 347-357.

KALAYCI C B, GUPTA S M, NAKASHIMA K. Bees colony intelligence in solving disassembly line balancing problem[C]//Proceedings of the 2011 Asian Conference of Management Science and Applications. Sanya: [S. n.], 2011: 34-41.

张则强, 胡扬, 陈冲.求解拆卸线平衡问题的改进人工蜂群算法[J].西南交通大学学报, 2016, 51(5):910-917. doi: 10.3969/j.issn.0258-2724.2016.05.013

ZHANG Zeqiang, HU Yang, CHEN Chong. An improved artificial bee colony algorithm for disassembly line balancing problem[J]. Journal of Southwest Jiaotong University, 2016, 51(5):910-917. doi: 10.3969/j.issn.0258-2724.2016.05.013

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-194. doi: 10.1108/JMTM-11-2013-0168

TUNCEL E, ZEID A, KAMARTHI S. Solving large scale disassembly line balancing problem with uncertainty using reinforcement learning[J]. Journal of Intelligent Manufacturing, 2014, 25(4):647-659. doi: 10.1007/s10845-012-0711-0

KALAYCI C B, GUPTA S M. Tabu search for disassembly line balancing with multiple objectives[C]//Proceedings of the 41st International Conference on Computers & Industrial Engineering. Los Angeles: [S. n.], 2011: 477-482.

KALAYCI C B, GUPTA S M, NAKASHIMA K. A simulated annealing algorithm for balancing a disassembly line[C]//Proceedings of the Seventh International Symposium on Environmentally Conscious Design and Inverse Manufacturing. Netherlands: [S. n.], 2011: 713-718.

METE S, CIL Z A, AGPAK K, et al. A solution approach based on beam search algorithm for disassembly line balancing problem[J]. Journal of Manufacturing Systems, 2016, 41:188-200. doi: 10.1016/j.jmsy.2016.09.002

丁力平, 谭建荣, 冯毅雄, 等.基于Pareto蚁群算法的拆卸线平衡多目标优化[J].计算机集成制造系统, 2009, 15(7):1406-1413. http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200907022

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, 1429. http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200907022

ALAVIDOOST M, BABAZADEH H, SAYYARI S. An interactive fuzzy programming approach for bi-objective straight and U-shaped assembly line balancing problem[J]. Applied Soft Computing, 2016, 40:221-235. doi: 10.1016/j.asoc.2015.11.025

ALAVIDOOST M H, ZARANDI M H, TARIMORADI M, et al. Modified genetic algorithm for simple straight and U-shaped assembly line balancing with fuzzy processing times[J]. Journal of Intelligent Manufacturing, 2017, 28(2):313-336. doi: 10.1007/s10845-014-0978-4

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. doi: 10.1080/00207540600943985

李明, 张则强, 胡扬. U型布局的拆卸线平衡问题及其求解算法研究[J].现代制造工程, 2015(7):7-12. doi: 10.3969/j.issn.1671-3133.2015.07.003

LI Ming, ZHANG Zeqaing, HU Yang. Research on U-shaped disassembly line balancing problem and solving algorithm[J]. Modern Manufacturing Engineering, 2015(7):7-12. doi: 10.3969/j.issn.1671-3133.2015.07.003

张则强, 胡俊逸, 程文明.第Ⅰ类双边装配线平衡问题的改进蚁群算法[J].西南交通大学学报, 2013, 48(4):724-730. doi: 10.3969/j.issn.0258-2724.2013.04.020

ZHANG Zeqiang, HU Junyi, CHENG Wenming. Improved ant colony algorithms for two-sided assembly line balancing problem of type Ⅰ[J]. Journal of Southwest Jiaotong University, 2013, 48(4):724-730. doi: 10.3969/j.issn.0258-2724.2013.04.020

KUCUKKOC I, ZHANG D Z. Integrating ant colony and genetic algorithms in the balancing and scheduling of complex assembly lines[J]. The International Journal of Advanced Manufacturing Technology, 2016, 82(1/2/3/4):265-285. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=c6d8fd8411099bdee157fb11d60a377b

DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197. doi: 10.1109/4235.996017

Relative Articles

[1]	ZHANG Zeqiang, JIANG Jin, YIN Tao, XU Peiyu. Modeling and Optimization for U-shaped Partial Multi-Objective Disassembly Line Balancing Problem[J]. Journal of Southwest Jiaotong University, 2022, 57(2): 235-244. doi: 10.3969/j.issn.0258-2724.20200694
[2]	ZHANG Heshan, DENG Zhaoxiang, TUO Jiying, ZHANG Yu, TAO Shengchao. Multi-Objective Optimum Design for in-Wheel Motor Based on Improved Artificial Bee Colony Algorithm[J]. Journal of Southwest Jiaotong University, 2019, 54(4): 671-678. doi: 10.3969/j.issn.0258-2724.20170094
[3]	YANG Ming, SU Biao, SUN Zhijie, XU Yi. Model and Algorithm of Multi-objective Discrete Transportation Network Design under Stochastic Demand among OD Pairs[J]. Journal of Southwest Jiaotong University, 2014, 27(1): 119-125. doi: 10.3969/j.issn.0258-2724.2014.01.019
[4]	ZHANG Zeqiang, HU Junyi, CHENG Wenming. Improved Ant Colony Algorithm for Two-Sided Assembly Line Balancing Problem of Type I[J]. Journal of Southwest Jiaotong University, 2013, 26(4): 724-730. doi: 10.3969/j.issn.0258-2724.2013.04.020
[5]	PANG Xiaoping, CHEN Jin. Multi-objective Shape Optimization of Hydrodynamic Journal Bearings Using Non-dorminated Sorting Genetic Algorithm Ⅱ[J]. Journal of Southwest Jiaotong University, 2012, 25(4): 639-645. doi: 10.3969/j.issn.0258-2724.2012.04.017
[6]	LIU Jie, LI UDan, HE Yanfeng. Improved Ant Colony System Algorithm for Waste Collection Vehicle Routing Problem[J]. Journal of Southwest Jiaotong University, 2011, 24(2): 333-339. doi: 10.3969/j.issn.0258-2724.2011.02.026
[7]	LIU Jingyu, FANG Yanjun. Urban Vehicle Routing Based on Ant Colony Algorithm[J]. Journal of Southwest Jiaotong University, 2009, 22(6): 912-917.
[8]	MA Yongjie, JIANG Zhaoyuan, YANG Zhimin. Dynamic Location Assignment of AS/RS Based on Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2008, 21(3): 415-421.
[9]	LÜ, Hongxia, HE Dake, CHEN Tao. Method of Arrival and Departure Tracks Utilization Plan in Railroad Passenger Station Based on Ant Colony Algorithm[J]. Journal of Southwest Jiaotong University, 2008, 21(2): 153-158.
[10]	DAI Chaohua, ZHU Yunfang, CHEN Weirong. Cloud Theory-Based Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2006, 19(6): 729-732.
[11]	YANG Yan, ZHANG Zhaotao. Clustering Method Combining Threshold Algorithm with Ant Colony Algorithm[J]. Journal of Southwest Jiaotong University, 2006, 19(6): 719-722,742.
[12]	SHIYu-feng, SU Shi, PENG Qi-yuan. Optim ization ofM ilitary Transportation Routes Based on Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2005, 18(2): 241-243.
[13]	GAO Wei-zeng, ZHANG Bao-jian, CHEN Fu-gui, ZHU Jia-yi, . Optim ization ofCutting Path Based on Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2005, 18(4): 457-461.
[14]	FANG Lei, ZHANG Huan-chun, JING Ya-zhi. New Fuzzy Self-Tuning Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2005, 18(1): 22-25.
[15]	ZHANG Ge-xiang, JIN Wei-dong. Improvement of Quantum Genetic Algorithm and Its Application[J]. Journal of Southwest Jiaotong University, 2003, 16(6): 717-722.
[16]	QIUXiao-ping, TANG Yong-chuan, MENG Dan, XU Yang. Multivalue Coded Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2003, 16(2): 227-130.
[17]	LIUHai-yan, CHEN Gao-bo, PENG Chuan. Solving Multi-objective Programming Problems with Maximal Entropy Method and Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2003, 16(1): 8-11.
[18]	CHEN Yan-ru, PUYun. Solving Traffic Equilibrium Assignment Problem with Genetic Algorithm[J]. Journal of Southwest Jiaotong University, 2000, 13(1): 44-47.

Supplements(0)

Cited By

Cited by

Periodical cited type(8)

1.	脱阳，张则强，谢心澜，宋昊轩. 考虑工人移动的多人共站双边拆卸线平衡问题的建模与优化. 中国机械工程. 2025(01): 113-122+132 .
2.	脱阳，张则强，张裕，郑红斌，梁巍. 考虑可变时间的双边机器人拆卸线平衡问题建模与优化. 计算机集成制造系统. 2023(12): 4073-4088 .
3.	张则强，蒋晋，尹涛，许培玉. U型不完全多目标拆卸线平衡问题建模与优化. 西南交通大学学报. 2022(02): 235-244 . 本站查看
4.	刘俊琦，张则强，龚举华，张裕. 受约束的过道布置问题建模及优化方法. 西南交通大学学报. 2022(06): 1376-1385 . 本站查看
5.	谢梦柯，张则强，蒋晋. 考虑工位约束及能耗的双边拆卸线平衡问题建模与优化. 计算机集成制造系统. 2021(03): 701-715 .
6.	张则强，张颖，蒋晋，朱立夏. 考虑零件分类的U型拆卸线平衡问题与改进烟花算法求解. 信息与控制. 2020(04): 489-498 .
7.	董海，徐晓鹏，谢谢. 多目标优化算法求解多柔性作业车间调度问题. 计算机科学. 2020(12): 239-244 .
8.	张则强，蔡宁，曾艳清，李六柯，邹宾森. 面向再制造的拆卸线平衡问题建模理论及求解方法综述. 中国机械工程. 2018(21): 2636-2645 .

Other cited types(19)

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(5) / Tables(4)

Get Citation

PDF

XML

Article views(540) PDF downloads(116)

Pareto Hybrid Ant Colony and Genetic Algorithm for Multi-Objective U-Shaped Disassembly Line Balancing Problem

doi: 10.3969/j.issn.0258-2724.2018.03.026