Branch, bound and remember algorithm for two-sided assembly line balancing problem

Zixiang Li, Ibrahim Kucukkoc and Zikai Zhang

European Journal of Operational Research, 2020, vol. 284, issue 3, 896-905

Abstract: This research presents a new branch, bound and remember (BBR) algorithm to minimize the number of mated-stations in two-sided assembly lines. The proposed methodology modifies the Hoffman heuristic to achieve high-quality upper bounds, and employs two new dominance rules, referred to as memory-based maximal load rule and memory-based extended Jackson rule, to prune the sub-problems. The BBR algorithm also employs several other improvements to enhance the performance, including renumbering the tasks and new lower bounds. Computational results demonstrate that BBR achieves the optimal solutions for all the tested instances within 1.0 s on average, including two optimal solutions for the first time. Comparative study shows that BBR outperforms the current best exact method (branch and bound algorithm) and the current best heuristic algorithm (iterated greedy search algorithm). As a consequence, the proposed BBR can be regarded as the state-of-the-art method for TALBP.

Keywords: Combinatorial optimization; Assembly line balancing; Two-sided assembly line; Branch and bound; Branch, bound and remember (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720300539
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:284:y:2020:i:3:p:896-905

DOI: 10.1016/j.ejor.2020.01.032

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().