An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset

David R. Morrison; Edward C. Sewell; Sheldon H. Jacobson

doi:10.1016/j.ejor.2013.11.033

An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset

David R. Morrison
, Edward C. Sewell
, Sheldon H. Jacobson

Research output: Contribution to journal › Article › peer-review

Abstract

The simple assembly line balancing problem (SALBP) is a well-studied NP-complete problem for which a new problem database of generated instances was published in 2013. This paper describes the application of a branch, bound, and remember (BB&R) algorithm using the cyclic best-first search strategy to this new database to produce provably exact solutions for 86% of the unsolved problems in this database. A new backtracking rule to save memory is employed to allow the BB&R algorithm to solve many of the largest problems in the database.

Original language	English (US)
Pages (from-to)	403-409
Number of pages	7
Journal	European Journal of Operational Research
Volume	236
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2013.11.033
State	Published - Jul 16 2014

Keywords

Assembly line balancing
Branch and bound
Combinatorial optimization

ASJC Scopus subject areas

General Computer Science
Modeling and Simulation
Management Science and Operations Research
Information Systems and Management

Online availability

10.1016/j.ejor.2013.11.033

Library availability

Discover UIUC Full Text

Cite this

@article{8c76ded864864dcba46ba06175316fe8,

title = "An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset",

abstract = "The simple assembly line balancing problem (SALBP) is a well-studied NP-complete problem for which a new problem database of generated instances was published in 2013. This paper describes the application of a branch, bound, and remember (BB\&R) algorithm using the cyclic best-first search strategy to this new database to produce provably exact solutions for 86\% of the unsolved problems in this database. A new backtracking rule to save memory is employed to allow the BB\&R algorithm to solve many of the largest problems in the database.",

keywords = "Assembly line balancing, Branch and bound, Combinatorial optimization",

author = "Morrison, \{David R.\} and Sewell, \{Edward C.\} and Jacobson, \{Sheldon H.\}",

note = "The computational results reported were obtained using the Simulation and Optimization Laboratory. This research has been supported in part by the Air Force Office of Scientific Research (FA9550-10-1-0387), the Department of Defense (DoD) through the National Defense Science \& Engineering Graduate Fellowship (NDSEG) Program, and the National Science Foundation through the Graduate Research Fellowship Program. The third author is supported in part by (while serving at) the National Science Foundation. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government. The authors would like to thank three anonymous referees and the associate editor for comments which significantly improved this paper.",

year = "2014",

month = jul,

day = "16",

doi = "10.1016/j.ejor.2013.11.033",

language = "English (US)",

volume = "236",

pages = "403--409",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset

AU - Morrison, David R.

AU - Sewell, Edward C.

AU - Jacobson, Sheldon H.

N1 - The computational results reported were obtained using the Simulation and Optimization Laboratory. This research has been supported in part by the Air Force Office of Scientific Research (FA9550-10-1-0387), the Department of Defense (DoD) through the National Defense Science & Engineering Graduate Fellowship (NDSEG) Program, and the National Science Foundation through the Graduate Research Fellowship Program. The third author is supported in part by (while serving at) the National Science Foundation. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government. The authors would like to thank three anonymous referees and the associate editor for comments which significantly improved this paper.

PY - 2014/7/16

Y1 - 2014/7/16

N2 - The simple assembly line balancing problem (SALBP) is a well-studied NP-complete problem for which a new problem database of generated instances was published in 2013. This paper describes the application of a branch, bound, and remember (BB&R) algorithm using the cyclic best-first search strategy to this new database to produce provably exact solutions for 86% of the unsolved problems in this database. A new backtracking rule to save memory is employed to allow the BB&R algorithm to solve many of the largest problems in the database.

AB - The simple assembly line balancing problem (SALBP) is a well-studied NP-complete problem for which a new problem database of generated instances was published in 2013. This paper describes the application of a branch, bound, and remember (BB&R) algorithm using the cyclic best-first search strategy to this new database to produce provably exact solutions for 86% of the unsolved problems in this database. A new backtracking rule to save memory is employed to allow the BB&R algorithm to solve many of the largest problems in the database.

KW - Assembly line balancing

KW - Branch and bound

KW - Combinatorial optimization

UR - https://www.scopus.com/pages/publications/84896488270

UR - https://www.scopus.com/pages/publications/84896488270#tab=citedBy

U2 - 10.1016/j.ejor.2013.11.033

DO - 10.1016/j.ejor.2013.11.033

M3 - Article

AN - SCOPUS:84896488270

SN - 0377-2217

VL - 236

SP - 403

EP - 409

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this