Minimizing the number of machines for scheduling jobs with equal processing times

被引：21

作者：

Kravchenko, Svetlana A. ^{[2
]}

Werner, Frank ^{[1
]}

机构：

[1] Otto Von Guericke Univ, Fak Math, D-39106 Magdeburg, Germany

[2] United Inst Informat Problems, Minsk 220012, BELARUS

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2009年 / 199卷 / 02期

关键词：

Parallel machine scheduling; Linear programming;

D O I：

10.1016/j.ejor.2008.10.008

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we consider a parallel machine environment when all jobs have the same processing time and arbitrary release dates and deadlines of the jobs are given. We suppose that the available number of machines, which can be used simultaneously, may vary over time. The aim is to construct a feasible schedule in such a way that the maximal number of simultaneously used machines is minimal. We give a polynomial algorithm for this problem. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：595 / 600

页数：6

共 7 条

[1]

Brucker P., 2005, SCHEDULING JOBS RELE

[2] Scheduling jobs with equal processing times and time windows on identical parallel machines [J].

Brucker, Peter ;

Kravchenko, Svetlana A. .

JOURNAL OF SCHEDULING, 2008, 11 (04) :229-237

[3]

Dantzig G.B., 1954, Nav. Res. Logist. Q, V1, P217, DOI [10.1002/nav.3800010309, DOI 10.1002/NAV.3800010309]

[4] Minimizing the number of machines for minimum length schedules [J].

Finke, Gerd ;

Lemaire, Pierre ;

Proth, Jean-Marie ;

Queyranne, Maurice .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 199 (03) :702-705

[5] Exact and approximation algorithms for the tactical fixed interval scheduling problem [J].

Kroon, LG ;

Salomon, M ;

VanWassenhove, LN .

OPERATIONS RESEARCH, 1997, 45 (04) :624-638

[6] On the minimum number of processors for scheduling problems with communication delays [J].

Moukrim, A .

ANNALS OF OPERATIONS RESEARCH, 1999, 86 (0) :455-472

[7] A FAST ALGORITHM FOR MULTIPROCESSOR SCHEDULING OF UNIT-LENGTH JOBS [J].

SIMONS, BB ;

WARMUTH, MK .

SIAM JOURNAL ON COMPUTING, 1989, 18 (04) :690-710

← 1 →