Variable neighborhood search for the second type of two-sided assembly line balancing problem

Previous studies of two-sided assembly line balancing problem (TALBP) are mainly about the first type of the problem.TALBP-II which is to minimize cycle time for a given number of stations is seldom investigated. In this study an effective variable neighborhood search (VNS) is proposed to solve TALBP-II. A novel two-string representation is used, which is composed of a precedence- based task string and a side selection string. New solutions are produced by using a side selection operator and two precedence-based operators. A novel comparison principle is applied to guarantee the feasibility of the solutions and approximate the optimal solution. VNS is tested on a number of instances and compared with the existing methods. The computational results show the promising advantage of VNS on the considered TALBP-II.