Type-II Two-Sided Assembly Line Balancing Problem with Alternative Precedence Relations

To solve the Type-II two-sided assembly line balancing problem with alternative precedence relations, a mixed-integer programming (MIP) model and a constraint programming (CP) model are established, respectively, based on precedence graphs and if–then rules. Some small-sized instances are tested to verify that the CP model performs faster and better than the MIP model. For the large-sized problems, an adaptive iterative greedy (AIG) algorithm is proposed by improving the existing iterative greedy (IG) algorithm. In the initialization phase, the insert operation based on not violating the precedence relations is adopted. The adaptive neighborhood and operator selection mechanism are introduced in the local search phase. Comparing the results of the AIG algorithm with the MIP model and CP model, the proposed algorithm can effectively solve this problem. Computational results also reveal that the AIG algorithm performs better than the original algorithm in terms of solution quality and stability. Nevertheless, as a heuristic, the AIG algorithm cannot guarantee global optimality.