A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint

被引：28

作者：

Breit, J ^{[1
]}

机构：

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

来源：

COMPUTERS & OPERATIONS RESEARCH | 2006年 / 33卷 / 08期

关键词：

approximation algorithms; flow shop scheduling; availability constraints;

D O I：

10.1016/j.cor.2005.01.004

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We study the problem of scheduling n preemptable jobs in a two-machine flow shop where the first machine is not available for processing during a given time interval. The objective is to minimize the makespan. We propose a polynomial-time approximation scheme for this problem. The approach is extended to solve the problem in which the second machine is not continuously available. (c) 2005 Elsevier Ltd. All rights reserved.

引用

页码：2143 / 2153

页数：11

共 10 条

[1] Heuristic algorithms for the two-machine flowshop with limited machine availability [J].

Blazewicz, J ;

Breit, J ;

Formanowicz, P ;

Kubiak, W ;

Schmidt, G .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2001, 29 (06) :599-608

[2] An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint [J].

Breit, J .

INFORMATION PROCESSING LETTERS, 2004, 90 (06) :273-278

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

Cheng, TCE ;

Wang, GQ .

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

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

[5]

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

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

[7] Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint [J].

Lee, CY .

OPERATIONS RESEARCH LETTERS, 1997, 20 (03) :129-139

[8]

LEE CY, 2004, HDB SCHEDULING

[9] An FPTAS for scheduling a two-machine flowshop with one unavailability interval [J].

Ng, CT ;

Kovalyov, MY .

NAVAL RESEARCH LOGISTICS, 2004, 51 (03) :307-315

[10] Scheduling with limited machine availability [J].

Schmidt, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 121 (01) :1-15

← 1 →