On the complexity of assembly line balancing problems

Eduardo Álvarez-Miranda, Jordi Pereira

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Assembly line balancing is a family of combinatorial optimization problems that has been widely studied in the literature due to its simplicity and industrial applicability. Most line balancing problems are NP-hard as they subsume the bin packing problem as a special case. Nevertheless, it is common in the line balancing literature to cite [A. Gutjahr and G. Nemhauser, An algorithm for the line balancing problem, Management Science 11 (1964) 308–315] in order to assess the computational complexity of the problem. Such an assessment is not correct since the work of Gutjahr and Nemhauser predates the concept of NP-hardness. This work points at over 50 publications since 1995 with the aforesaid error.

Original languageEnglish
Pages (from-to)182-186
Number of pages5
JournalComputers and Operations Research
Volume108
DOIs
StatePublished - Aug 2019
Externally publishedYes

Keywords

  • Bin packing
  • Complexity
  • Line balancing

Fingerprint

Dive into the research topics of 'On the complexity of assembly line balancing problems'. Together they form a unique fingerprint.

Cite this