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
Cheng, TEC
Wang, GQ
[J]. 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
Glass, CA
Potts, CN
[J]. 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
Lee, CY
[J]. OPERATIONS RESEARCH LETTERS, 1997, 20 (03) : 129 - 139
[7] CONVERGENCE OF AN ANNEALING ALGORITHM
LUNDY, M
MEES, A
[J]. 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
OGBU, FA
SMITH, DK
[J]. COMPUTERS & OPERATIONS RESEARCH, 1990, 17 (03) : 243 - 253
[9] SIMULATED ANNEALING FOR THE PERMUTATION FLOWSHOP PROBLEM
OGBU, FA
SMITH, DK
[J]. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1991, 19 (01): : 64 - 67
[10] SIMULATED ANNEALING FOR PERMUTATION FLOWSHOP SCHEDULING
OSMAN, IH
POTTS, CN
[J]. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1989, 17 (06): : 551 - 557

← 1 2 →