Complexity of cyclic scheduling problems: A state-of-the-art survey

被引：137

作者：

Levner, Eugene ^{[1
]}

Kats, Vladimir ^{[2
]}

Alcaide Lopez de Pablo, David ^{[3
]}

Cheng, T. C. E. ^{[4
]}

机构：

[1] Holon Inst Technol, Holon, Israel

[2] Inst Ind Math, Beer Sheva, Israel

[3] Univ La Laguna, Tenerife, Spain

[4] Hong Kong Polytech Univ, Kowloon, Hong Kong, Peoples R China

来源：

COMPUTERS & INDUSTRIAL ENGINEERING | 2010年 / 59卷 / 02期

关键词：

Cyclic scheduling problems; Complexity; Reducibility; Robotic scheduling; POLYNOMIAL ALGORITHM; ROBOTIC CELLS; JOB SHOPS; BATCH PLANTS; CONTINUOUS-TIME; SINGLE ROBOT; HOIST; OPTIMIZATION; CONSTRAINT; RETROFIT;

D O I：

10.1016/j.cie.2010.03.013

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this survey we review the current complexity status of basic cyclic scheduling models. We start with the formulations of three fundamental cyclic scheduling problems, namely the cyclic jobshop, cyclic flow-shop, and cyclic project scheduling problems. We present state-of-the-art results on the computational complexity of the problems, paying special attention to recent results on the unsolvability (NP-hardness) of various cyclic problems arising from the scheduling of robotic cells. (c) 2010 Elsevier Ltd. All rights reserved.

引用

页码：352 / 361

页数：10

共 132 条

[1] Part sequencing in three-machine no-wait robotic cells [J].