A branch, bound, and remember algorithm for the simple disassembly line balancing problem. (May 2019)

• Record Type: Journal Article
• Authors: Li, Jinlin; Chen, Xiaohong; Zhu, Zhanguo; Yang, Caijun; Chu, Chengbin
• Is Part Of: Computers & operations research. Volume 105(2019)
• Page Start: 47
• Page End: 57
• Publication Date: 2019-05
• Subjects: Disassembly line balancing -- Lower bound -- Branch and bound -- Heuristic; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.01.003
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A special case of SDLBP-1 used in many studies is proved polynomial solvable. Two lower bounding schems and a strenghtened integer programing model are presented. A branch, bound, and remember algorithm is proposed to solve general SDLBP-1 instances. The proposed BB&R algorithm is a state-of-the-art exact algorithm for the SDLBP-1. The BB&R algorithm can be easily truncated into an efficient heuristic. Abstract: In this paper, we deal with a disassembly line balancing problem (DLBP), using an AND/OR graph (AOG) to represent the precedence relations between tasks. The decision maker needs to select a proper processing alternative and assign the corresponding tasks among stations to minimise the number of stations, without violating the cycle time constraint and the precedence relations. The problem was first formulated by Koc et al. (2009) and is denoted as type 1 simple DLBP (SDLBP-1) in this study. We prove that an SDLBP-1 with no parallel tasks is polynomially solvable and develop a branch, bound, and remember (BB&R) algorithm for the general SDLBP-1 with parallel tasks. Moreover, two lower bounding schemes, a strengthened Koc's integer programming (IP) model and a new benchmark instance generation scheme are proposed. Computational results show that the BB&R algorithm is the state-of-the-art exact algorithm for SDLBP-1, and that it can be easily truncated into a state-of-the-art heuristic which optimally solves most instances in very short time. In addition, the lower bounds and the strengthened IP model are also demonstrated to be effective.