| |
Record |
Links |
|
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 |
