Abstract: 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.

Key words: sequence-dependent setup times, two-sided assembly line balancing problem, variable neighborhood search algorithm