Non-preemptive two-machine open shop scheduling with non-availability constraints

被引：33

作者：

Breit, J ^{[1
]}

Schmidt, G

Strusevich, VA

机构：

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

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

来源：

MATHEMATICAL METHODS OF OPERATIONS RESEARCH | 2003年 / 57卷 / 02期

关键词：

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

D O I：

10.1007/s001860200267

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. No preemption is allowed in the processing of any operation. The objective is to minimize the makespan. We consider approximability issues of the problem with more than one non-availability intervals and present an approximation algorithm with a worst-case ratio of 4/3 for the problem with a single non-availability interval.

引用

页码：217 / 234

页数：18

共 23 条

[1]

AKSJONOV VA, 1988, UPRAVLYAEMYE SISTEMY, V28, P8

[2]

Barany I., 1982, Szigma, V15, P177

[3] Two-machine open shop scheduling with an availability constraint [J].

Breit, J ;

Schmidt, G ;

Strusevich, VA .

OPERATIONS RESEARCH LETTERS, 2001, 29 (02) :65-77

[4]

BREIT J, 2000, THESIS U SAARLAND SA

[5]

Chen B., 1993, ORSA Journal on Computing, V5, P321, DOI 10.1287/ijoc.5.3.321

[6] An improved heuristic for two-machine flowshop scheduling with an availability constraint [J].

Cheng, TEC ;

Wang, GQ .

OPERATIONS RESEARCH LETTERS, 2000, 26 (05) :223-229

[7] 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

[8]

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

[9] Two-machine flow shops with limited machine availability [J].

Kubiak, W ;

Blazewicz, J ;

Formanowicz, P ;

Breit, J ;

Schmidt, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 136 (03) :528-540

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

Lee, CY .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 114 (02) :420-429

← 1 2 3 →