多目标不完全拆卸线平衡问题的建模与优化

Modeling and Optimizing for Multi-objective Partial Disassembly Line Balancing Problem

针对实际生产中在满足约束条件下仅考虑拆卸需求零件和危害零件的特点,以工作站数目、空闲时间均衡指标和拆卸成本为优化目标,构建了不完全拆卸线平衡问题多目标模型。基于解的离散性和优化目标的多重性,提出一种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.