On the complexity of assembly line balancing problems

Eduardo Álvarez-Miranda, Jordi Pereira

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


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
StatePublished - Aug 2019
Externally publishedYes


  • Bin packing
  • Complexity
  • Line balancing


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

Cite this