A heuristic algorithm for two-machine re-entrant shop scheduling

被引：27

作者：

Drobouchevitch, IG ^{[1
]}

Strusevich, VA ^{[1
]}

机构：

[1] Univ Greenwich, Sch Comp & Math Sci, London SE18 6PF, England

来源：

ANNALS OF OPERATIONS RESEARCH | 1999年 / 86卷 / 0期

关键词：

re-entrant shop scheduling; approximation algorithm; worst-case analysis;

D O I：

10.1023/A:1018927407164

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper considers the problem of sequencing n jobs in a two-machine re-entrant shop with the objective of minimizing the maximum completion time. The shop consists of two machines, M-1 and M-2 , and each job has the processing route (M-1 , M-2 , M-1 ). An O(n log n) time heuristic is presented which generates a schedule with length at most 4/3 times that of an optimal schedule, thereby improving the best previously available worst-case performance ratio of 3/2.

引用

页码：417 / 439

页数：23

共 12 条

[1] Approximation algorithms for two-machine flow shop scheduling with batch setup times [J].

Chen, B ;

Potts, CN ;

Strusevich, VA .

MATHEMATICAL PROGRAMMING, 1998, 82 (1-2) :255-271

[2] A new heuristic for three-machine flow shop scheduling [J].

Chen, B ;

Glass, CA ;

Potts, CN ;

Strusevich, VA .

OPERATIONS RESEARCH, 1996, 44 (06) :891-898

[3]

Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117

[4]

GONZALEZ T, 1976, J ACM, V23, P665, DOI 10.1145/321978.321985

[5] FLOW-SHOP AND JOB-SHOP SCHEDULES - COMPLEXITY AND APPROXIMATION [J].

GONZALEZ, T ;

SAHNI, S .

OPERATIONS RESEARCH, 1978, 26 (01) :36-52

[6]

Johnson S.M., 1954, NAV RES LOG, V1, P61, DOI DOI 10.1002/NAV.3800010110

[7]

LANE DE, 1991, OPER RES, V41, P1091

[8]

Lawler E., 1993, HDB OPERATIONS RES M, V4, P455

[9] V-SHOP SCHEDULING [J].

LEV, V ;

ADIRI, I .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 18 (01) :51-56

[10] IMPROVED APPROXIMATION ALGORITHMS FOR SHOP SCHEDULING PROBLEMS [J].

SHMOYS, DB ;

STEIN, C ;

WEIN, J .

SIAM JOURNAL ON COMPUTING, 1994, 23 (03) :617-632

← 1 2 →