期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 312, 期 1, 页码 38-55出版社
ELSEVIER
DOI: 10.1016/j.ejor.2023.06.007
关键词
Scheduling; Assembly line balancing; Workload smoothing; Branch, bound, and remember; Combinatorial optimization
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据