A polynomial algorithm for a two-machine no-wait job-shop scheduling problem

被引:7
作者
Kravchenko, SA [1 ]
机构
[1] Inst Engn Cybernet, Minsk 220012, BELARUS
关键词
job-shop; unit processing time; no-wait in process; optimal mean flow time schedule; polynomial algorithm;
D O I
10.1016/S0377-2217(97)00102-1
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper considers the no-wait scheduling of n jobs, where each job is a chain of unit processing time operations to be processed alternately on two machines. The objective is to minimize the mean flow time. We propose an O(n(6))-time algorithm to produce an optimal schedule. It is also shown that if zero processing time operations are allowed, then the problem is NP-hard in the strong sense. (C) 1998 Elsevier Science B.V.
引用
收藏
页码:101 / 107
页数:7
相关论文
共 11 条
[1]  
Blazewicz J., 1988, Annals of Operations Research, V16, P255, DOI 10.1007/BF02283747
[2]   SCHEDULING INDEPENDENT TASKS TO REDUCE MEAN FINISHING TIME [J].
BRUNO, J ;
COFFMAN, EG ;
SETHI, R .
COMMUNICATIONS OF THE ACM, 1974, 17 (07) :382-387
[3]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
[4]   SEQUENCING 1 STATE-VARIABLE MACHINE - SOLVABLE CASE OF TRAVELING SALESMAN PROBLEM [J].
GILMORE, PC ;
GOMORY, RE .
OPERATIONS RESEARCH, 1964, 12 (05) :655-&
[5]   UNIT EXECUTION TIME SHOP PROBLEMS [J].
GONZALEZ, T .
MATHEMATICS OF OPERATIONS RESEARCH, 1982, 7 (01) :57-66
[6]  
Goyal S. K., 1988, Opsearch, V25, P220
[7]   A survey of machine scheduling problems with blocking and no-wait in process [J].
Hall, NG ;
Sriskandarajah, C .
OPERATIONS RESEARCH, 1996, 44 (03) :510-525
[9]  
Rock H., 1984, Zeitschrift fur Operations Research, Serie A (Theorie), V28, P1, DOI 10.1007/BF01919082
[10]   SOME NO-WAIT SHOPS SCHEDULING PROBLEMS - COMPLEXITY ASPECT [J].
SRISKANDARAJAH, C ;
LADET, P .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 24 (03) :424-438