Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 312, Issue 1, Pages 38-55Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2023.06.007
Keywords
Scheduling; Assembly line balancing; Workload smoothing; Branch, bound, and remember; Combinatorial optimization
Ask authors/readers for more resources
This paper proposes an improved branch-and-bound algorithm, R-SALSA, for solving the simple assembly line balancing problem, which performs well in balancing workloads and providing initial solutions.
We consider a simple assembly line balancing problem with given cycle time and number of stations. A quadratic objective function based on a so-called smoothness index SX levels the workloads of the stations. For this problem, called SALBP-SX, only a few solution procedures have been proposed in literature so far. In this paper, we extend and improve the branch-and-bound procedure SALSA (Simple Assembly Line Smoothing Algorithm) of Walter et al. (2021) to a bidirectional branch, bound, and remember algorithm called R-SALSA (R for remember). Like SALSA, it is based on a dynamic programming scheme which pre-determines potential workloads of the stations and provides a construction plan for possible station loads. This scheme is extended by the new concept of supporters and preventers which significantly enhances branching, bounding, and logical tests. Furthermore, a tailored heuristic that searches for improved initial solutions, a bidirectional branching scheme and additional dominance rules are integrated. In extensive computational experiments, we find out that our new procedure clearly outperforms all former exact solution procedures on benchmark data sets with up to 1000 tasks. (c) 2023 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available