Abstract: To handle the production disruptions and workload fluctuations caused by equipment failure and order's change,the multiple parallel optional equipment in key process and assistant in production line were set up.For decision variables,the benders decomposition method was adopted to divide the origin problem into the main problem on allocating equipments and assistants and the sub-problems on assign tasks,which reduced the complexity of model solution;the Benders-based rapid Non-dominated Sorting Genetic Algorithm (BNSGA-Ⅱ) was put forward with three layers of coding and decoding to adapt to decision variables;the hierarchy structure and crowding distance of non-backtracing Pareto method were used to implement population evaluation and selection;the hierarchical genetic operator based on probability was proposed to widen the neighborhood structure,improve the optimization ability and avoid the local optimization.The proposed algorithm was analyzed by ratio of non-dominated solution,convergence of Pareto frontier solution and spread metric,and the result showed that the algorithm could obtain the approximate non-dominated solutions of Pareto optimal frontier and had good convergence and diversity by a comparison with MOGA and NSGA.

Key words: U-shaped assembly line, resources assignment, multi-objective optimization, fast elisit non-dominated sorting genetic algorithm

摘要： 为处理因设备故障、订单变化等引起的任务量波动或生产中断问题,在关键工序设置多个并行可选设备、在生产子线设置助理,以保证装配线的生产率。针对该类问题,构建随机工时下基于资源分配的成本、效率双目标U型装配线平衡模型,并采用Benders分解法,将问题分解为设备和助理分配主问题、工序分配子问题,以降低模型求解的复杂度。提出基于Benders分解的快速非支配遗传算法,通过三层编码及解码来适应多决策变量;采用非回溯的Pareto层级构造和拥挤距离,实现种群评价与选择;提出基于概率的层次化遗传操作,以扩充邻域结构、增强寻优能力、避免局部优化。通过非支配解比率、Pareto前沿解收敛性和个体间距度量指标分析所提算法、多目标遗传算法和非支配排序遗传算法,证明算法获得了逼近Pareto最优前沿的非支配解集,且具有良好的收敛性和分布性。

关键词: U型装配线, 资源分配, 多目标优化, 快速非支配遗传算法