A POLYNOMIAL-APPROXIMATION SCHEME FOR A CONSTRAINED FLOWSHOP SCHEDULING PROBLEM

被引：22
作者：
HALL, LA
机构：
来源：
MATHEMATICS OF OPERATIONS RESEARCH | 1994年 / 19卷 / 01期
关键词：
SHOP SCHEDULING; APPROXIMATION ALGORITHMS; FLOW SHOPS; RELEASE DATES; POLYNOMIAL APPROXIMATION SCHEMES;
D O I：
10.1287/moor.19.1.68
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We present a polynomial approximation scheme for a two-machine flow shop scheduling problem with the additional constraint that each job has a release date, when it first becomes available for processing. This is one of the first such results for multiple-task scheduling problems; previously, the best approximation result for this problem was an algorithm guaranteed to deliver a schedule of length at most 5/3 times the optimal length. Our (1 + epsilon)-approximation algorithm is intuitively appealing because it is based on Johnson's algorithm, an optimization algorithm for the problem without release dates.
引用
收藏
页码：68 / 85
页数：18
相关论文
共 12 条
[1]  
Graham R. L., 1979, Discrete Optimisation, P287
[2]   BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].
GRAHAM, RL .
BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+
[3]  
HALL L, 1990, P 1 INT PROGR COMB O, P249
[4]   JACKSON RULE FOR SINGLE-MACHINE SCHEDULING - MAKING A GOOD HEURISTIC BETTER [J].
HALL, LA ;
SHMOYS, DB .
MATHEMATICS OF OPERATIONS RESEARCH, 1992, 17 (01) :22-35
[5]  
HALL LA, 1989, 2 TOPICS DISCRETE OP
[6]  
HALL LA, 1989, 30 ANN S FDN COMP SC, P134
[7]  
HGAREY MR, 1979, COMPUTERS INTRACTABI
[8]  
Johnson S.M., 1954, NAV RES LOG, V1, P61, DOI [10.1002/nav.3800010110, DOI 10.1002/NAV.3800010110]
[9]  
KOVALIEV MY, 1985, ISV AKAD NAUK BSSR P, V3, P118
[10]  
LAWLER EL, 1989, HDB OPERATIONS RES M, V4
12