A solution approach based on beam search algorithm for disassembly line balancing problem. (October 2016) - Mete, Süleyman; Çil, Zeynel Abidin; Ağpak, Kürşad; Özceylan, Eren; Dolgui, Alexandre
Highlights: This is the first adaptation of beam search algorithm to solve the DLB problem. The algorithm was thoroughly tested on small and large sized instances. Comparison with shortest route model proves the superiority of the proposed method. The algorithm provides near optimal solution for this NP-complete problem. Abstract: The disassembly line balancing (DLB) problem is the process of allocating a set of disassembly tasks to an ordered sequence of workstations in such a way that optimizes some performance measures (e.g., cycle time, number of stations). Since DLB problems belong to the class of NP hard, many heuristic and meta-heuristic algorithms are applied to cope with the complexity of the DLB problems in order to obtain acceptable solutions in a reasonable amount of time. In this study, a beam search (BS) based approach for the DLB problem is proposed. Minimization of number of workstations is used as the performance measure. The proposed algorithm is compared with the optimal solutions of well-known real cases and generated test problems. The results indicate that the proposed approach based on BS is a very competitive and promising tool for further researches.