多目标不完全拆卸线平衡问题的建模与优化
|
摘要
针对实际生产中在满足约束条件下仅考虑拆卸需求零件和危害零件的特点,以工作站数目、空闲时间均衡指标和拆卸成本为优化目标,构建了不完全拆卸线平衡问题多目标模型。基于解的离散性和优化目标的多重性,提出一种Pareto解集思想的变邻域-粒子群融合算法。该算法通过建立拆卸任务和粒子群迭代搜索的对应关系,将变邻域搜索作为局部搜索策略,同时引入Pareto解集思想、拥挤距离机制处理多目标问题,以保证求解结果的多样性;通过Hyper-volume指标解决了多目标优化难以评价算法收敛性能及Pareto解集优劣等问题。采用所提算法求解不同规模完全拆卸线平衡问题测试算例,其中不同搜索深度的对比试验表明了变动搜索深度能很好地兼顾求解质量和求解效率,不同算法的对比试验表明了所提算法的优越性。最后,将所提模型与求解方法应用至某打印机不完全拆卸线的设计中。
Aiming at the disassembly characteristics of only considering the parts in demand and the hazardous parts in the actual production, a multi-objective mathematical model of the partial disassembly line balancing problem is constructed including the workstation number, smooth rate and disassembly cost three optimization objectives. And a Pareto based particle swarm algorithm incorporated with variable neighborhood is proposed considering the discrete nature of the solution and multiple optimization objectives. The mapping relationship between the disassembly tasks and the particle swarm iterative search is structured and the variable neighborhood search method is incorporated as the local search strategy in the proposed algorithm. To deal with the multiple objectives for the problem, the Pareto solution set and the crowding distance evaluation mechanism is introduced to ensure the diversity of the solution results. In addition, the Hyper-volume indicator is used to overcome the difficulty in evaluating the algorithm convergence performance and the Pareto muster in solving the multi-objective optimization problems. The superiority of the proposed algorithm is verified by different scale test cases of complete disassembly line balancing problem, and the contrast experiments show that the change of search depth of the proposed algorithm owns excellent performance the quality and computation efficiency. Finally, the proposed mathematical model and the presented algorithm is applied to the partial disassembly line design of a certain type of printer.
Aiming at the disassembly characteristics of only considering the parts in demand and the hazardous parts in the actual production, a multi-objective mathematical model of the partial disassembly line balancing problem is constructed including the workstation number, smooth rate and disassembly cost three optimization objectives. And a Pareto based particle swarm algorithm incorporated with variable neighborhood is proposed considering the discrete nature of the solution and multiple optimization objectives. The mapping relationship between the disassembly tasks and the particle swarm iterative search is structured and the variable neighborhood search method is incorporated as the local search strategy in the proposed algorithm. To deal with the multiple objectives for the problem, the Pareto solution set and the crowding distance evaluation mechanism is introduced to ensure the diversity of the solution results. In addition, the Hyper-volume indicator is used to overcome the difficulty in evaluating the algorithm convergence performance and the Pareto muster in solving the multi-objective optimization problems. The superiority of the proposed algorithm is verified by different scale test cases of complete disassembly line balancing problem, and the contrast experiments show that the change of search depth of the proposed algorithm owns excellent performance the quality and computation efficiency. Finally, the proposed mathematical model and the presented algorithm is applied to the partial disassembly line design of a certain type of printer.
引文
[1]GUNGOR A,GUPTA S M,POCHAMPALLY K,et al.Complications in disassembly line balancing[C]//Intelligent Systems and Smart Manufacturing.International Society for Optics and Photonics,2001:289-298.
[2]AVIKAL S,JAIN R,YADAV H C,et al.A new heuristic for disassembly line balancing problems with AND/OR precedence relations[C]//Proceedings of the Second International Conference on Soft Computing for Problem Solving,December 28-30,2012.Springer India,2014:519-525.
[3]MCGOVERN S M,GUPTA S M.2-opt heuristic for the disassembly line balancing problem[C]//Proceedings of the SPIE International Conference on Environmentally Conscious Manufacturing III,2004:71-84.
[4]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.
[5]KALAYCI C B,GUPTA S M.A tabu search algorithm for balancing a sequence-dependent disassembly line[J].Production Planning&Control,2013,25(25):149-160.
[6]MCGOVERN S M,GUPTA S M.Ant colony optimization for disassembly sequencing with multiple objectives[J].International Journal of Advanced Manufacturing Technology,2006,30(5):481-496.
[7]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,2012:347-357.
[8]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.
[9]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.
[10]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.
[11]丁力平,谭建荣,冯毅雄,等.基于Pareto蚁群算法的拆卸线平衡多目标优化[J].计算机集成制造系统,2009,15(7):1406-1413.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.
[12]方群,张则强,李明.面向多目标拆卸线平衡问题的一种改进粒子群优化算法[J].现代制造工程,2016,(4):8-15.FANG Qun,ZHANG Zeqiang,LI Ming.A developed PSO with mutation operators for multi_objective disassembly line balancing problems[J].Modern Manufacturing Engineering.2016,(4):8-15.
[13]ALTEKIN F T,KANDILLER L,OZDEMIREL N E.Profit-oriented disassembly-line balancing[J].International Journal of Production Research,2008,46(10):2675-2693.
[14]CLERC M.Discrete particle swarm optimization,illustrated by the traveling salesman problem[M].Berlin Heidelberg:Springer,2004.
[15]王丰产,孙有朝,李娜.多工位装配序列粒子群优化算法[J].机械工程学报,2012,48(9):155-162.WANG Fengchan,SUN Youchao,LI Na.Multi station assembly sequence planning based on particle swarm optimization algorithm[J].Journal of Mechanical Engineering,2012,48(9):155-162.
[16]侯媛彬,薛斐,郑茂全,等.基于多层编码的遗传-粒子群融合算法流水线优化控制[J].机械工程学报,2015,51(9):159-164.HOU Yuanbin,XUE Fei,ZHENG Maoquan,et al.Optimization of flow-shop control by using genetic-particle swarm algorithm of multilayer-coded[J].Journal of Mechanical Engineering,2015,51(9):159-164.
[17]CHENG R,GEN M,TSUJIMURA Y.A tutorial survey of job-shop scheduling problems using genetic algorithms—I.representation[J].Computers&Industrial Engineering,1996,30(4):983-997.
[18]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.
[19]BADER J,ZITZLER E.Hyp E:An algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation,2011,19(1):45-76.
[20]TAHERKHANI M,SAFABAKHSH R.A novel stability-based adaptive inertia weight for particle swarm optimization[J].Applied Soft Computing,2016,38:281-295.
[2]AVIKAL S,JAIN R,YADAV H C,et al.A new heuristic for disassembly line balancing problems with AND/OR precedence relations[C]//Proceedings of the Second International Conference on Soft Computing for Problem Solving,December 28-30,2012.Springer India,2014:519-525.
[3]MCGOVERN S M,GUPTA S M.2-opt heuristic for the disassembly line balancing problem[C]//Proceedings of the SPIE International Conference on Environmentally Conscious Manufacturing III,2004:71-84.
[4]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.
[5]KALAYCI C B,GUPTA S M.A tabu search algorithm for balancing a sequence-dependent disassembly line[J].Production Planning&Control,2013,25(25):149-160.
[6]MCGOVERN S M,GUPTA S M.Ant colony optimization for disassembly sequencing with multiple objectives[J].International Journal of Advanced Manufacturing Technology,2006,30(5):481-496.
[7]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,2012:347-357.
[8]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.
[9]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.
[10]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.
[11]丁力平,谭建荣,冯毅雄,等.基于Pareto蚁群算法的拆卸线平衡多目标优化[J].计算机集成制造系统,2009,15(7):1406-1413.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.
[12]方群,张则强,李明.面向多目标拆卸线平衡问题的一种改进粒子群优化算法[J].现代制造工程,2016,(4):8-15.FANG Qun,ZHANG Zeqiang,LI Ming.A developed PSO with mutation operators for multi_objective disassembly line balancing problems[J].Modern Manufacturing Engineering.2016,(4):8-15.
[13]ALTEKIN F T,KANDILLER L,OZDEMIREL N E.Profit-oriented disassembly-line balancing[J].International Journal of Production Research,2008,46(10):2675-2693.
[14]CLERC M.Discrete particle swarm optimization,illustrated by the traveling salesman problem[M].Berlin Heidelberg:Springer,2004.
[15]王丰产,孙有朝,李娜.多工位装配序列粒子群优化算法[J].机械工程学报,2012,48(9):155-162.WANG Fengchan,SUN Youchao,LI Na.Multi station assembly sequence planning based on particle swarm optimization algorithm[J].Journal of Mechanical Engineering,2012,48(9):155-162.
[16]侯媛彬,薛斐,郑茂全,等.基于多层编码的遗传-粒子群融合算法流水线优化控制[J].机械工程学报,2015,51(9):159-164.HOU Yuanbin,XUE Fei,ZHENG Maoquan,et al.Optimization of flow-shop control by using genetic-particle swarm algorithm of multilayer-coded[J].Journal of Mechanical Engineering,2015,51(9):159-164.
[17]CHENG R,GEN M,TSUJIMURA Y.A tutorial survey of job-shop scheduling problems using genetic algorithms—I.representation[J].Computers&Industrial Engineering,1996,30(4):983-997.
[18]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.
[19]BADER J,ZITZLER E.Hyp E:An algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation,2011,19(1):45-76.
[20]TAHERKHANI M,SAFABAKHSH R.A novel stability-based adaptive inertia weight for particle swarm optimization[J].Applied Soft Computing,2016,38:281-295.