A branch, bound, and remember algorithm for the simple disassembly line balancing problem

Jinlin Li

doi:10.1016/j.cor.2019.01.003

A branch, bound, and remember algorithm for the simple disassembly line balancing problem

2019-05-01

22

PRE

AI

DOI：10.1016/j.cor.2019.01.003

Original

Original request for help

Save

Abstract

En 中文

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. (C) 2019 Published by Elsevier Ltd.

Keywords:

Disassembly line balancing

Lower bound

Branch and bound

Heuristic

A branch, bound, and remember algorithm for the simple disassembly line balancing problem

Abstract

AI Summary

Journal

Organization