Heuristic algorithms for the two-machine flowshop with limited machine availability

被引：52
作者：
Blazewicz, J
Breit, J
Formanowicz, P
Kubiak, W
Schmidt, G
机构：
[1] Tech Univ Clausthal, Inst Informat, D-38678 Clausthal Zellerfeld, Germany
[2] Mem Univ Newfoundland, Fac Business Adm, St Johns, NF A1C 5S7, Canada
[3] Univ Saarland, Lehrstuhl Informat & Technol Management, D-66041 Saarbrucken, Germany
[4] Poznan Univ Technol, Inst Comp Sci, PL-60965 Poznan, Poland
来源：
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE | 2001年 / 29卷 / 06期
关键词：
flowshop; availability constraints; scheduling; heuristics;
D O I：
10.1016/S0305-0483(01)00048-2
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
The paper studies a flowshop scheduling problem where machines are not available in given time intervals. The objective is to minimize the makespan. The problem is known to be NP-hard for two machines. We analyze constructive and local search based heuristic algorithms for the two-machine case. The algorithms are tested on easy and difficult test problems with up to 100 jobs and 10 intervals of non-availability. Computational results show that the algorithms perform well. For many problems an optimum solution is found. (C) 2001 Elsevier Science Ltd. All rights reserved.
引用
收藏
页码：599 / 608
页数：10
相关论文
共 12 条
[1]   An improved heuristic for two-machine flowshop scheduling with an availability constraint [J].
Cheng, TEC ;
Wang, GQ .
OPERATIONS RESEARCH LETTERS, 2000, 26 (05) :223-229
[2]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
[3]   A comparison of local search methods for flow shop scheduling [J].
Glass, CA ;
Potts, CN .
ANNALS OF OPERATIONS RESEARCH, 1996, 63 :489-509
[4]  
Johnson Selmer Martin., 1954, NAV RES LOG, V1, P61, DOI [10.1002/nav.3800010110, DOI 10.1002/NAV.3800010110, 10.1002/(ISSN)1931-9193]
[5]  
KUBIAK W, IN PRESS EUROPEAN J
[6]   Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint [J].
Lee, CY .
OPERATIONS RESEARCH LETTERS, 1997, 20 (03) :129-139
[7]   CONVERGENCE OF AN ANNEALING ALGORITHM [J].
LUNDY, M ;
MEES, A .
MATHEMATICAL PROGRAMMING, 1986, 34 (01) :111-124
[8]   THE APPLICATION OF THE SIMULATED ANNEALING ALGORITHM TO THE SOLUTION OF THE N/M/CMAX FLOWSHOP PROBLEM [J].
OGBU, FA ;
SMITH, DK .
COMPUTERS & OPERATIONS RESEARCH, 1990, 17 (03) :243-253
[9]   SIMULATED ANNEALING FOR THE PERMUTATION FLOWSHOP PROBLEM [J].
OGBU, FA ;
SMITH, DK .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1991, 19 (01) :64-67
[10]   SIMULATED ANNEALING FOR PERMUTATION FLOWSHOP SCHEDULING [J].
OSMAN, IH ;
POTTS, CN .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1989, 17 (06) :551-557
12