Iterated local search method and mathematical model for sequence-dependent u-shaped disassembly line balancing problem

Abstract

Disassembly lines play an important role in disassembling end-of-life products and retrieving the valuable components. Sequence-dependent time increments are inevitable due to the interactions between two tasks in some occasions. This research provides the first attempt to study the sequence-dependent U-shaped disassembly line balancing problem (SUDLBP) with multiple objectives. A mixed-integer programming model is developed to solve the small-size instances optimally, where new expressions are developed to formulate the AND/OR precedence relations. Due to the NP-hard nature of this problem, a simple and effective iterated local search algorithm is developed for the first time. This algorithm utilizes modified NEH heuristic to achieve a high-quality initial solution. A new local search technic with referenced permutation and two neighbor structures is also embedded into it to obtain the local optimum solution. Computational tests demonstrate that the U-shaped lines outperform traditional straight lines in terms of the objective values. The comparative study on two sets of instances demonstrates that the proposed method outperforms the CPLEX solver in search speed and achieves a competing performance in comparison with other eight re-implemented algorithms.