Two-machine open shop scheduling with an availability constraint

被引：27

作者：

Breit, J ^{[1
]}

Schmidt, G

Strusevich, VA

机构：

[1] Univ Saarland, Dept Informat & Technol Management, D-66041 Saarbrucken, Germany

[2] Tech Univ Clausthal, Inst Informat, D-38678 Clausthal Zellerfeld, Germany

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

来源：

OPERATIONS RESEARCH LETTERS | 2001年 / 29卷 / 02期

关键词：

open shop scheduling; availability constraints; worst-case analysis;

D O I：

10.1016/S0167-6377(01)00079-7

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study a two-machine open shop scheduling problem, in which one machine is not available for processing during a given time interval. The objective is to minimize the makespan. We show that the problem is NP-hard and present an approximation algorithm with a worst-case ratio of 4/3. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：65 / 77

页数：13

共 18 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

BREIT J, 2000, THESIS U SAARLAND

[3]

BREIT J, 2000, B2001 U SAARL DEP EC

[4] Two-machine flowshop scheduling with consecutive availability constraints [J].

Cheng, TCE ;

Wang, GQ .

INFORMATION PROCESSING LETTERS, 1999, 71 (02) :49-54

[5] PREEMPTIVE SCHEDULING OF INDEPENDENT JOBS WITH RELEASE AND DUE TIMES ON OPEN, FLOW AND JOB SHOPS [J].

CHO, Y ;

SAHNI, S .

OPERATIONS RESEARCH, 1981, 29 (03) :511-522

[6]

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

[7]

Johnson Selmer Martin., 1954, NAV RES LOG, V1, P61, DOI [10.1002/nav.3800010110, DOI 10.1002/NAV.3800010110, 10.1002/(ISSN)1931-9193]

[8]

KUBIAK W, 1997, IN PRESS EUROPEAN J

[9]

Lawler E.L, 1993, HDB OPERATIONS RES M, V4, P445, DOI 10.1016/S0927-0507(05)80189-6

[10] PREEMPTIVE SCHEDULING OF UNRELATED PARALLEL PROCESSORS BY LINEAR-PROGRAMMING [J].

LAWLER, EL ;

LABETOULLE, J .

JOURNAL OF THE ACM, 1978, 25 (04) :612-619

← 1 2 →