On the complexity of assembly line balancing problems

被引：30

作者：

Alvarez-Miranda, Eduardo ^{[1
]}

Pereira, Jordi ^{[2
]}

机构：

[1] Univ Talca, Dept Ind Engn, Curico, Chile

[2] Univ Adolfo Ibanez, Fac Engn & Sci, Vina Del Mar, Chile

来源：

COMPUTERS & OPERATIONS RESEARCH | 2019年 / 108卷

关键词：

Line balancing; Complexity; Bin packing; SIMULATED ANNEALING ALGORITHM; SHORTEST-ROUTE FORMULATION; DEPENDENT SETUP TIMES; GENETIC-ALGORITHM; SEQUENCING PROBLEMS; SCHEDULING PROBLEM; HEURISTIC SOLUTION; MODEL; OPTIMIZATION; DESIGN;

D O I：

10.1016/j.cor.2019.04.005

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：182 / 186

页数：5

共 101 条

[1] Applying genetic algorithms to the U-shaped assembly line balancing problem [J].

Ajenblit, DA ;

Wainwright, RL .

1998 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION - PROCEEDINGS, 1998, :96-101

[2] Modified genetic algorithm for simple straight and U-shaped assembly line balancing with fuzzy processing times [J].

Alavidoost, M. H. ;

Zarandi, M. H. Fazel ;

Tarimoradi, Mosahar ;

Nemati, Yaser .

JOURNAL OF INTELLIGENT MANUFACTURING, 2017, 28 (02) :313-336

[3] Fuzzy adaptive genetic algorithm for multi-objective assembly line balancing problems [J].

Alavidoost, M. H. ;

Tarimoradi, Mosahar ;

Zarandi, M. H. Fazel .

APPLIED SOFT COMPUTING, 2015, 34 :655-677

[4] Task-failure-driven rebalancing of disassembly lines [J].

Altekin, F. Tevhide ;

Akkan, Can .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2012, 50 (18) :4955-4976

[5] Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and lower bounds [J].

Amen, M .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 168 (03) :747-770

[6] Balancing and scheduling tasks in assembly lines with sequence-dependent setup times [J].

Andres, Carlos ;

Miralles, Cristobal ;

Pastor, Rafael .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 187 (03) :1212-1223

[7]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[8] Balancing stochastic U-lines using particle swarm optimization [J].

Aydogan, Emel Kizilkaya ;

Delice, Yilmaz ;

Ozcan, Ugur ;

Gencer, Cevriye ;

Bali, Ozkan .

JOURNAL OF INTELLIGENT MANUFACTURING, 2019, 30 (01) :97-111

[9] A novel meta-heuristic approach to solve fuzzy multi-objective straight and U-shaped assembly line balancing problems [J].

Babazadeh, Hossein ;

Javadian, Nikbakhsh .

SOFT COMPUTING, 2019, 23 (17) :8217-8245

[10] An enhanced NSGA-II algorithm for fuzzy bi-objective assembly line balancing problems [J].

Babazadeh, Hossein ;

Alavidoost, M. H. ;

Zarandi, M. H. Fazel ;

Sayyari, S. T. .

COMPUTERS & INDUSTRIAL ENGINEERING, 2018, 123 :189-208

← 1 2 3 4 5 6 7 8 9 10 →