工具约束下多目标拆卸线平衡问题的猫群模拟退火算法
|
摘要
针对已有研究中忽略拆卸工具的不足,基于多目标拆卸线平衡模型,考虑了作业过程中的工具更换因素,建立了包含最小化工具更换次数的多目标拆卸线平衡问题数学模型,并设计了一种多目标猫群模拟退火算法进行求解。提出基于序列交换的离散跟踪模式;将猫群优化算法与模拟退火算法相结合,以增强算法的全局寻优能力;引入拥挤距离筛选,提高算法运行效率的同时有效的保证外部档案集的多样性;采用精英保留策略加速算法的收敛。通过对已有算例进行求解,并与其他算法对比分析,验证了所提算法的有效性和高效性。最后,将所提模型和算法应用于某型号打印机拆卸线的设计,为决策者提供了多种平衡方案。
Aiming at the shortcoming that disassembly tool was ignored,a multi-objective disassembly line balancing problem mathematics model which contained minimum tools change number and considered tools changing factors in working was proposed,and a multi-objective cat swarm simulated annealing algorithm was designed to solve it.The dispersed tracking model based on sequence switching was adopted.Cat swarm optimization algorithm and simulated annealing algorithm were integrated to improve the global optimization ability.To improve the operating efficiency and ensure the diversity of external file effectively,crowded distance filtering was introduced.The elitism strategy was adopted to speed up the convergence rate of the algorithm.The effectiveness and high efficiency of the proposed algorithm were verified by testing existing examples and comparing with other algorithms.The proposed model and algorithm were adopted to design the disassembly line of a model printer,and the result provided a lot of balancing programs for the policymakers.
Aiming at the shortcoming that disassembly tool was ignored,a multi-objective disassembly line balancing problem mathematics model which contained minimum tools change number and considered tools changing factors in working was proposed,and a multi-objective cat swarm simulated annealing algorithm was designed to solve it.The dispersed tracking model based on sequence switching was adopted.Cat swarm optimization algorithm and simulated annealing algorithm were integrated to improve the global optimization ability.To improve the operating efficiency and ensure the diversity of external file effectively,crowded distance filtering was introduced.The elitism strategy was adopted to speed up the convergence rate of the algorithm.The effectiveness and high efficiency of the proposed algorithm were verified by testing existing examples and comparing with other algorithms.The proposed model and algorithm were adopted to design the disassembly line of a model printer,and the result provided a lot of balancing programs for the policymakers.
引文
[1] XU Binshi,DONG Shiyun,ZHU Sheng,et al.Prospects and developing of remanufacture forming technology[J].Journal of mechanical engineering,2012,48(15):96-105(in Chinese).[徐滨士,董世运,朱胜,等.再制造成形技术发展及展望[J].机械工程学报,2012,48(15):96-105.]
[2] GUNGOR A,GUPTA S M,POCHAMPALLY K,et al.Complications in disassembly line balancing[C]//Proceedings of the 1st International Conference on Environmentally Conscious Manufacturing.Washington,D.C.,USA:SPIE,2001:289-298.
[3] 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.
[4] SEIDI M,SAGHARI S.The balancing of disassembly line of automobile engine using genetic algorithm(GA)in fuzzy environment[J].Industrial Engineering and Management Systems,2016,15(4):364-373.
[5] 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(in Chinese).[丁力平,谭建荣,冯毅雄,等.基于Pareto蚁群算法的拆卸线平衡多目标优化[J].计算机集成制造系统,2009,15(7):1406-1413.]
[6] DING L,CHEN W,TAN J,et al.Multi-objective disassembly line balancing via modified ant colony optimization algorithm[C]//Proceedings of the IEEE 5th International Conference on Bio-Inspired Computing:Theories and Applications.Washington D.C.,USA:IEEE,2010:426-430.
[7] TIAN G D,ZHOU M C,CHU J W.Probability evaluation models of product disassembly cost subject to random removal time and different removal labor cost[J].IEEE Transactions on Automation Science and Engineering,2012,9(2):288-295.
[8] TIAN G D,ZHOU M C,CHU J W.A chance constrained programming approach to determine the optimal disassembly sequence[J].IEEE Transactions on Automation Science and Engineering,2013,10(4):1004-1013.
[9] 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 University-SCIENCE A,2015,16(9):724-736.
[10] ZHANG Z,WANG K,ZHU L,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.
[11] 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.
[12] KALAYCI C B,POLAT O,GUPTA S M.A variable neighborhood search algorithm for disassembly lines[J].Journal of Manufacturing Technology Management,2015,26(2):182-194.
[13] AVIKAL S,JAIN R,YADAV H,et al.A new heuristic for disassembly line balancing problems with AND/OR precedence relations[C]//Proceedings of the 2nd International Conference on Soft Computing for Problem Solving.Berlin,Germany:Springer-Verlag,2014:519-525.
[14] KALAYCI C B,GUPTA S M.A tabu search algorithm for balancing a sequence-dependent disassembly line[J].Production Planning&Control,2013,25(2):149-160.
[15] 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.
[16] ZHANG Zeqiang,HU Yang,CHEN Chong.Improved artificial bee colony algorithm for disassembly line balancing problem[J].Journal of Southwest Jiaotong University,2016,51(5):910-917(in Chinese).[张则强,胡扬,陈冲.求解拆卸线平衡问题的改进人工蜂群算法[J].西南交通大学学报,2016,51(5):910-917.]
[17] 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.
[18] 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.
[19] WANG Kaipu,ZHANG Zeqiang,MAO Lili,et al.Pareto artificial fish swarm algorithm for multi-objective disassembly line balancing problems[J].China Mechanical Engineering,2017,28(2):183-190(in Chinese).[汪开普,张则强,毛丽丽,等.多目标拆卸线平衡问题的Pareto人工鱼群算法[J].中国机械工程,2017,28(2):183-190.]
[20] WANG Kaipu,ZHANG Zeqiang,ZHU Lixia,et al.Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem[J].Computer Integrated Manufacturing Systems,2017,23(6):1277-1285(in Chinese).[汪开普,张则强,朱立夏,等.多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J].计算机集成制造系统,2017,23(6):1277-1285.]
[21] TSENG H E,CHANG C C,LI J D.Modular design to support green life-cycle engineering[J].Expert Systems with Applications.2008,34(4):2524-2537.
[22] CHEN Yiwen,CHEN Weida.Product disassembly sequence optimization based on profit-probability under uncertain environment[J].Computer Integrated Manufacturing Systems,2014,20(4):793-798(in Chinese).[陈弋文,陈伟达.基于收益概率的不确定环境下的产品拆卸序列优化[J].计算机集成制造系统,2014,20(4):793-798.]
[23] CHU S C,TSAI P,PAN J S.Cat swarm optimization[J].Lecture Notes in Computer Science,2006,6:854-858.
[24] DIANA D C,RANI S P.Novel cat swarm optimization algorithm to enhance channel equalization[J].Compel International Journal for Computation and Mathematics in Electrical and Electronic Engineering,2017,36(1):350-363.
[25] NIE Xiaohua,WANG Wei.Chaos improved cat swarm optimization and its application in the PV MPPT[J].Proceedings of The Chinese Society for Electrical Engineering,2016,36(22):6103-6110(In Chinese).[聂晓华,王薇.混沌改进猫群算法及其在光伏MPPT中的应用[J].中国电机工程学报,2016,36(22):6103-6110.]
[26] DHALIWAL K K,DHILLON J S.Integrated cat swarm optimization and differential evolution algorithm for optimal IIR filter design in multi-objective framework[J].Circuits Systems and Signal Processing,2017,36(1):270-296.
[27] SANKARARAO B,YOO C K.Development of a robust multiobjective simulated annealing algorithm for solving multiobjective optimization problems[J].Industrial&Engineering Chemistry Research,2011,50(11):6728-6742.
[28] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[29] KALAYCI C B,GUPTA S M.Simulated annealing algorithm for solving sequence-dependent disassembly line balancing problem[C]//Proceedings of the 7th IFAC Conference on Manufacturing Modelling,Management,and Control.Laxenburg,Austria:IFAC,2013:93-98.
[2] GUNGOR A,GUPTA S M,POCHAMPALLY K,et al.Complications in disassembly line balancing[C]//Proceedings of the 1st International Conference on Environmentally Conscious Manufacturing.Washington,D.C.,USA:SPIE,2001:289-298.
[3] 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.
[4] SEIDI M,SAGHARI S.The balancing of disassembly line of automobile engine using genetic algorithm(GA)in fuzzy environment[J].Industrial Engineering and Management Systems,2016,15(4):364-373.
[5] 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(in Chinese).[丁力平,谭建荣,冯毅雄,等.基于Pareto蚁群算法的拆卸线平衡多目标优化[J].计算机集成制造系统,2009,15(7):1406-1413.]
[6] DING L,CHEN W,TAN J,et al.Multi-objective disassembly line balancing via modified ant colony optimization algorithm[C]//Proceedings of the IEEE 5th International Conference on Bio-Inspired Computing:Theories and Applications.Washington D.C.,USA:IEEE,2010:426-430.
[7] TIAN G D,ZHOU M C,CHU J W.Probability evaluation models of product disassembly cost subject to random removal time and different removal labor cost[J].IEEE Transactions on Automation Science and Engineering,2012,9(2):288-295.
[8] TIAN G D,ZHOU M C,CHU J W.A chance constrained programming approach to determine the optimal disassembly sequence[J].IEEE Transactions on Automation Science and Engineering,2013,10(4):1004-1013.
[9] 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 University-SCIENCE A,2015,16(9):724-736.
[10] ZHANG Z,WANG K,ZHU L,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.
[11] 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.
[12] KALAYCI C B,POLAT O,GUPTA S M.A variable neighborhood search algorithm for disassembly lines[J].Journal of Manufacturing Technology Management,2015,26(2):182-194.
[13] AVIKAL S,JAIN R,YADAV H,et al.A new heuristic for disassembly line balancing problems with AND/OR precedence relations[C]//Proceedings of the 2nd International Conference on Soft Computing for Problem Solving.Berlin,Germany:Springer-Verlag,2014:519-525.
[14] KALAYCI C B,GUPTA S M.A tabu search algorithm for balancing a sequence-dependent disassembly line[J].Production Planning&Control,2013,25(2):149-160.
[15] 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.
[16] ZHANG Zeqiang,HU Yang,CHEN Chong.Improved artificial bee colony algorithm for disassembly line balancing problem[J].Journal of Southwest Jiaotong University,2016,51(5):910-917(in Chinese).[张则强,胡扬,陈冲.求解拆卸线平衡问题的改进人工蜂群算法[J].西南交通大学学报,2016,51(5):910-917.]
[17] 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.
[18] 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.
[19] WANG Kaipu,ZHANG Zeqiang,MAO Lili,et al.Pareto artificial fish swarm algorithm for multi-objective disassembly line balancing problems[J].China Mechanical Engineering,2017,28(2):183-190(in Chinese).[汪开普,张则强,毛丽丽,等.多目标拆卸线平衡问题的Pareto人工鱼群算法[J].中国机械工程,2017,28(2):183-190.]
[20] WANG Kaipu,ZHANG Zeqiang,ZHU Lixia,et al.Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem[J].Computer Integrated Manufacturing Systems,2017,23(6):1277-1285(in Chinese).[汪开普,张则强,朱立夏,等.多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J].计算机集成制造系统,2017,23(6):1277-1285.]
[21] TSENG H E,CHANG C C,LI J D.Modular design to support green life-cycle engineering[J].Expert Systems with Applications.2008,34(4):2524-2537.
[22] CHEN Yiwen,CHEN Weida.Product disassembly sequence optimization based on profit-probability under uncertain environment[J].Computer Integrated Manufacturing Systems,2014,20(4):793-798(in Chinese).[陈弋文,陈伟达.基于收益概率的不确定环境下的产品拆卸序列优化[J].计算机集成制造系统,2014,20(4):793-798.]
[23] CHU S C,TSAI P,PAN J S.Cat swarm optimization[J].Lecture Notes in Computer Science,2006,6:854-858.
[24] DIANA D C,RANI S P.Novel cat swarm optimization algorithm to enhance channel equalization[J].Compel International Journal for Computation and Mathematics in Electrical and Electronic Engineering,2017,36(1):350-363.
[25] NIE Xiaohua,WANG Wei.Chaos improved cat swarm optimization and its application in the PV MPPT[J].Proceedings of The Chinese Society for Electrical Engineering,2016,36(22):6103-6110(In Chinese).[聂晓华,王薇.混沌改进猫群算法及其在光伏MPPT中的应用[J].中国电机工程学报,2016,36(22):6103-6110.]
[26] DHALIWAL K K,DHILLON J S.Integrated cat swarm optimization and differential evolution algorithm for optimal IIR filter design in multi-objective framework[J].Circuits Systems and Signal Processing,2017,36(1):270-296.
[27] SANKARARAO B,YOO C K.Development of a robust multiobjective simulated annealing algorithm for solving multiobjective optimization problems[J].Industrial&Engineering Chemistry Research,2011,50(11):6728-6742.
[28] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[29] KALAYCI C B,GUPTA S M.Simulated annealing algorithm for solving sequence-dependent disassembly line balancing problem[C]//Proceedings of the 7th IFAC Conference on Manufacturing Modelling,Management,and Control.Laxenburg,Austria:IFAC,2013:93-98.