Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

被引：14

作者：

Drobouchevitch, IG ^{[1
]}

Strusevich, VA ^{[1
]}

机构：

[1] Univ Greenwich, Sch Comp & Math Sci, London SE10 9LS, England

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2000年 / 123卷 / 02期

关键词：

job shop scheduling; approximation algorithm; worst-case analysis;

D O I：

10.1016/S0377-2217(99)00253-2

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The paper considers the job shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on one of m greater than or equal to 2 machines, while the other operation must be performed on a single bottleneck machine, the same for all jobs. For this strongly NP-hard problem we present two heuristics with improved worst-case performance. One of them guarantees a worst-case performance ratio of 3/2. The other algorithm creates a schedule with the makespan that exceeds the largest machine workload by at most the length of the largest operation. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：229 / 240

页数：12

共 19 条

[11]

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

[12] MINIMIZING MAKESPAN IN HYBRID FLOWSHOPS [J].

LEE, CY ;

VAIRAKTARAKIS, GL .

OPERATIONS RESEARCH LETTERS, 1994, 16 (03) :149-158

[13]

Neumytov Y.D., 1993, UPRAVLYAEMYE SISTEMY, V31, P53

[14] Two-stage flowshop scheduling with a common second-stage machine [J].

Oguz, C ;

Lin, BMT ;

Cheng, TCE .

COMPUTERS & OPERATIONS RESEARCH, 1997, 24 (12) :1169-1174

[15] THE 2-STAGE ASSEMBLY SCHEDULING PROBLEM - COMPLEXITY AND APPROXIMATION [J].

POTTS, CN ;

SEVASTJANOV, SV ;

STRUSEVICH, VA ;

VANWASSENHOVE, LN ;

ZWANEVELD, CM .

OPERATIONS RESEARCH, 1995, 43 (02) :346-355

[16] VECTOR SUMMATION IN BANACH-SPACE AND POLYNOMIAL ALGORITHMS FOR FLOW SHOPS AND OPEN SHOPS [J].

SEVASTJANOV, S .

MATHEMATICS OF OPERATIONS RESEARCH, 1995, 20 (01) :90-103

[17] ON SOME GEOMETRIC METHODS IN SCHEDULING THEORY - A SURVEY [J].

SEVASTJANOV, SV .

DISCRETE APPLIED MATHEMATICS, 1994, 55 (01) :59-82

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

SHMOYS, DB ;

STEIN, C ;

WEIN, J .

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

[19] Short shop schedules [J].

Williamson, DP ;

Hall, LA ;

Hoogeveen, JA ;

Hurkens, CAJ ;

Lenstra, JK ;

Sevastjanov, SV ;

Shmoys, DB .

OPERATIONS RESEARCH, 1997, 45 (02) :288-294

← 1 2 →