An application of the branch,bound, and remember algorithm to a new simple assembly line balancing dataset |
| |
Authors: | David R Morrison Edward C Sewell Sheldon H Jacobson |
| |
Institution: | 1. University of Illinois, Urbana-Champaign, Dept. of Computer Science, 201 N. Goodwin Ave., Urbana, IL 61801, United States;2. Southern Illinois University Edwardsville, Dept. of Mathematics and Statistics, Edwardsville, IL 62026, United States |
| |
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 |
本文献已被 ScienceDirect 等数据库收录! |
|