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
Chen, B
Potts, CN
Strusevich, VA
[J]. MATHEMATICAL PROGRAMMING, 1998, 82 (1-2) : 255 - 271
[2] A new heuristic for three-machine flow shop scheduling
Chen, B
Glass, CA
Potts, CN
Strusevich, VA
[J]. 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
GONZALEZ, T
SAHNI, S
[J]. 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
LEV, V
ADIRI, I
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 18 (01) : 51 - 56
[10] IMPROVED APPROXIMATION ALGORITHMS FOR SHOP SCHEDULING PROBLEMS
SHMOYS, DB
STEIN, C
WEIN, J
[J]. SIAM JOURNAL ON COMPUTING, 1994, 23 (03) : 617 - 632

← 1 2 →