A branch, bound, and remember algorithm for the simple assembly line balancing problem

Research output: Contribution to journalArticle

Abstract

We present a new exact algorithm for the assembly line balancing problem. The algorithm finds and verifies the optimal solution for every problem in the combined benchmarks of Hoffmann, Talbot, and Scholl in less than one-half second per problem, on average, including one problem that has remained open for over 10 years. The previous best-known algorithm is able to solve 257 of the 269 benchmarks. The new algorithm is based on a branch-and-bound method that uses memory to eliminate redundant subproblems.

Original languageEnglish (US)
Pages (from-to)433-442
Number of pages10
JournalINFORMS Journal on Computing
Volume24
Issue number3
DOIs
StatePublished - Jun 1 2012

Keywords

  • Branch and bound
  • Combinatorial optimization
  • Heuristics
  • Production
  • Programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A branch, bound, and remember algorithm for the simple assembly line balancing problem'. Together they form a unique fingerprint.

  • Cite this