Record |
Author |
Alvarez-Miranda, E.; Pereira, J. |
Title |
On the complexity of assembly line balancing problems |
Type |
|
Year |
2019 |
Publication |
Computers & Operations Research |
Abbreviated Journal |
Comput. Oper. Res. |
Volume |
108 |
Issue |
|
Pages |
182-186 |
Keywords |
Line balancing; Complexity; Bin packing |
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. (C) 2019 Elsevier Ltd. All rights reserved. |
Address |
[Alvarez-Miranda, Eduardo] Univ Talca, Dept Ind Engn, Curico, Chile, Email: jorge.pereira@uai.cl |
Corporate Author |
|
Thesis |
|
Publisher |
Pergamon-Elsevier Science Ltd |
Place of Publication |
|
Editor |
|
Language |
English |
Summary Language |
|
Original Title |
|
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
Series Volume |
|
Series Issue |
|
Edition |
|
ISSN |
0305-0548 |
ISBN |
|
Medium |
|
Area |
|
Expedition |
|
Conference |
|
Notes |
WOS:000471733300014 |
Approved |
|
Call Number |
UAI @ eduardo.moreno @ |
Serial |
1015 |
Permanent link to this record |