The flow shop problem with no-idle constraints: A review and approximation

被引：33
作者：
Goncharov, Yaroslav [1 ]
Sevastyanov, Sergey [1 ]
机构：
[1] Novosibirsk State Univ, Sobolev Inst Math, Novosibirsk 630090, Russia
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2009年 / 196卷 / 02期
关键词：
Combinatorial optimization; Scheduling; Flow shop; Approximation algorithm; VECTOR SUMMATION; MAKESPAN; MACHINE;
D O I：
10.1016/j.ejor.2008.03.039
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time until all those operations are completed. The problem is known to be strongly NP-hard already for three machines. While being based on a geometrical approach, we propose several polynomial time heuristics (for the general case and for special cases of 3 and 4 machines) which provide asymptotically optimal solutions for the increasing number of jobs. A comprehensive review of relevant results is also presented. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：450 / 456
页数：7
相关论文
共 24 条
[1]   FLOWSHOP NO-IDLE OR NO-WAIT SCHEDULING TO MINIMIZE THE SUM OF COMPLETION TIMES [J].
ADIRI, I ;
POHORYLES, D .
NAVAL RESEARCH LOGISTICS, 1982, 29 (03) :495-504
[2]  
[Anonymous], SCHEDULING THEORY MU
[3]  
[Anonymous], 1994, SCHEDULING THEORY MU, DOI DOI 10.1007/978-94-011-1190-4
[4]  
BABUSHKIN AI, 1975, AVTOMAT TELEMEKH, V6, P161
[5]  
Baptiste P, 1997, P INT C IND ENG PROD, P429
[6]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
[7]   SEQUENCING 1 STATE-VARIABLE MACHINE - SOLVABLE CASE OF TRAVELING SALESMAN PROBLEM [J].
GILMORE, PC ;
GOMORY, RE .
OPERATIONS RESEARCH, 1964, 12 (05) :655-&
[8]   Two-machine no-wait flow shop scheduling with missing operations [J].
Glass, CA ;
Gupta, JND ;
Potts, CN .
MATHEMATICS OF OPERATIONS RESEARCH, 1999, 24 (04) :911-924
[9]  
Johnson S. M., 1954, Naval Research Logistics Quarterly, V1, P61, DOI [DOI 10.1002/NAV.3800010110, 10.1002/nav.3800010110]
[10]   A heuristic for minimizing the makespan in no-idle permutation flow shops [J].
Kalczynski, PJ ;
Kamburowski, J .
COMPUTERS & INDUSTRIAL ENGINEERING, 2005, 49 (01) :146-154
123