Minimizing total completion time in two-machine flow shops with exact delays

被引：8

作者：

Huo, Yumei ^{[1
]}

Li, Holibing ^{[2
]}

Zhao, Hairong ^{[3
]}

机构：

[1] CUNY Coll Staten Isl, Dept Comp Sci, Staten Isl, NY 10314 USA

[2] Lehman Brothers Inc, New York, NY 10019 USA

[3] Purdue Univ Calumet, Dept Math Comp Sci & Stat, Hammond, IN 46323 USA

来源：

COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 06期

关键词：

Flow shop; Exact delay; NP-hard; Permutation schedule; Total completion time; Metaheuristics; SCHEDULING PROBLEMS; ALGORITHMS;

D O I：

10.1016/j.cor.2008.06.015

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We study the problem of minimizing total completion time in the two-machine flow shop with exact delay model. This problem is a generalization of the no-wait flow shop problem which is known to be strongly NP-hard. Our problem has many applications but little results are given in the literature so far. We focus on permutation schedules. We first prove that some simple algorithms can be used to find the optimal schedules for some special cases. Then for the general case, we design some heuristics as well as metaheuristics whose performance are shown to be effective by computational experiments. (C) 2008 Elsevier Ltd. All rights reserved.

引用

页码：2018 / 2030

页数：13

共 21 条

[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]

AGEEV AA, 2006, P 4 INT WORKSH WAOA, P1

[3] Approximation algorithms for UET scheduling problems with exact delays [J].

Ageev, Alexander A. ;

Baburin, Alexei E. .

OPERATIONS RESEARCH LETTERS, 2007, 35 (04) :533-540

[4]

[Anonymous], 1974, A I I E T

[5] Genetic algorithms applied to the continuous flow shop problem [J].

Chen, CL ;

Neppalli, RV ;

Aljaber, N .

COMPUTERS & INDUSTRIAL ENGINEERING, 1996, 30 (04) :919-929

[6] Solving the continuous flow-shop scheduling problem by metaheuristics [J].

Fink, A ;

Voss, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 151 (02) :400-414

[7]

Glover F., 1989, ORSA Journal on Computing, V1, P190, DOI [10.1287/ijoc.2.1.4, 10.1287/ijoc.1.3.190]

[8] UNIT EXECUTION TIME SHOP PROBLEMS [J].

GONZALEZ, T .

MATHEMATICS OF OPERATIONS RESEARCH, 1982, 7 (01) :57-66

[9]

Graham R. L., 1979, Discrete Optimisation, P287

[10] OPTIMAL FLOWSHOP SCHEDULES WITH NO INTERMEDIATE STORAGE SPACE [J].

GUPTA, JND .

NAVAL RESEARCH LOGISTICS, 1976, 23 (02) :235-243

← 1 2 3 →