求解考虑顺序相关调整时间的双边装配线平衡问题的变邻域搜索算法

A Variable Neighborhood Search Algorithm for Solving Two-sided Assembly Line Balancing Problem with Sequence-dependent Setup Times

为有效解决带有顺序相关调整时间的双边装配线平衡问题,提出了一种简单高效的变邻域搜索算法。该算法通过将优先关系约束融入到交换、插入、交叉、变异等算子中,分别得到4个不同的邻域结构来保证搜索过程中解的可行性,避免过多重复邻域解的生成。4个邻域结构的搜索空间依次变大,以增强算法搜索能力。同时,结合装配线的特点,提出基于作业序列的编码和解码方式,在解码过程中,优先选择空闲时间较多的边,引入启发式目标加快算法收敛。分配结束后,对装配线末端的工作站组进行局部调整。通过将该算法先后用于求解无/有顺序相关调整时间的双边装配线平衡第一类问题,并与已有的算法进行对比,验证了所提的变邻域搜索算法的优越性和有效性。

To efficiently solve the two-sided assembly line balancing problem with sequence-dependent setup times, an effective and simple variable neighborhood search algorithm is proposed.To enhance the diversity of the variable neighborhood search algorithm and avoid generating too many replicated solutions, four precedence based neighborhood structures are designed, which include swap, insert, crossover and mutation operators. The search space of the four structures are getting larger successively to enhance the searching ability of the local search. What′s more, a task permutation decoding and coding method are adopted based on the features of assembly lines. For decoding, a side which has larger capacity is preferred to be selected. Some new heuristic objectives were added to speed up the convergence of the algorithm. When all tasks have been assigned, an adjustment for final mated workstation is made. The proposed algorithm is firstly applied to solving the two-sided assembly line balancing type-1 problem without considering the setup times and then two-sided assembly line balancing type-1 problem with sequence-dependent setup times is solved. A comprehensive comparative study is conducted and the results demonstrated that the proposed variable neighborhood search showed superiority performance over the compared ones.