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.}",

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",

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.

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 - http://www.scopus.com/inward/record.url?scp=84896488270&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84896488270&partnerID=8YFLogxK

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