SOME NO-WAIT SHOPS SCHEDULING PROBLEMS - COMPLEXITY ASPECT

被引：60

作者：

SRISKANDARAJAH, C

LADET, P

机构：

[1] Inst Natl Polytechnique de Grenoble,, Lab d'Automatique de Grenoble, St., Martin-d'Heres, Fr, Inst Natl Polytechnique de Grenoble, Lab d'Automatique de Grenoble, St. Martin-d'Heres, Fr

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1986年 / 24卷 / 03期

关键词：

COMPUTER PROGRAMMING - Algorithms - INDUSTRIAL PLANTS - Flexible Manufacturing Systems;

D O I：

10.1016/0377-2217(86)90036-6

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We investigate the computational complexity of no-wait shops scheduling problems. The problem of finding optimal finish time schedules is shown to be NP-hard for flowshops with two machine centers where each machine center has one or more parallel machines for processing tasks. The complexity results are also reported for no-wait shops scheduling when all nonzero tasks have unit or identical processing time requirement. A polynomial time algorithm for 3-machine flowshops is proposed for optimal finish time schedules. Finding optimal finish time schedules in 2-machine jobshops is NP-hard. Also we establish NP-hard results for 3-machine jobshops for both optimal finish time and mean flow time schedules.

引用

页码：424 / 438

页数：15