改进迭代局部搜索算法求解第Ⅰ类混流双边装配线平衡问题

Improved iterated local search algorithm for type I mixed-model two-sided assembly line balancing problem

基于第Ⅰ类混流双边装配线平衡具有生产品种多样性和生产过程复杂性的特点,研制了一种改进迭代局部搜索算法进行求解。在工位数量相同时引入新的二级目标,使前面工位承担更多负载,推进解的细微改进;提出基于工位的启发式解码方式,使成对工位内的负载更为均衡。在解码设计中,优先选择空闲时间较多的边作为分配操作的边,对每种产品优先选择不产生空闲时间的操作分配,然后通过最后成对工位调整策略进一步减少工位的数量。同时设计了新的改进启发式初始化和局部搜索方式,并通过参数校验验证改进的合理性。将所提解码方式与3种不同的解码方式进行对比,并将所提算法与7种不同算法进行对比,结果表明,基于工位的启发式解码优于对比解码,所提迭代局部搜索算法优于其他对比算法。

Aiming at the product diversity and the production process complexity of type-I mixed model two-sided as sembly line balancing, an improved Iterated Local Search （ILS） algorithm was proposed, in which the new seconda- ry objective was designed to preserve the solutions with more workload on former mated-station. A heuristic deco ding method was put forward to obtain the solution with balanced workloads on two sides of mated-station. The pro- posed decoding method selected the side with larger capacity, and then selected the tasks without resulting in idle time. A strategy to deal with the last mated-station was proposed for the purpose of further reducing the number of stations. Meanwhile, a new improved heuristic initialization and local search method were designed, and the ration- ality of the improved algorithm was verified through parameter calibration. The heuristic decoding method was corn pared with 3 different decoding schemes and the II.S algorithm compared with 7 different algorithms. Computational results demonstrated that the heuristic decoding method was more effective than other decoding schemes, and ILS algorithm showed superiority performance over the compared ones.