Parallel machine problems with equal processing times: a survey

被引：50

作者：

Kravchenko, Svetlana A. ^{[2
]}

Werner, Frank ^{[1
]}

机构：

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

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

来源：

JOURNAL OF SCHEDULING | 2011年 / 14卷 / 05期

关键词：

Parallel machine problem; Equal processing times; Non-preemptive problems; Preemptive problems; Polynomial algorithms; NP-hard problems; UNIT-LENGTH JOBS; SCHEDULING PROBLEMS; COMPLEXITY; ALGORITHM; RELEASE; NUMBER;

D O I：

10.1007/s10951-011-0231-3

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

The basic scheduling problem we are dealing with is the following. There are n jobs, each requiring an identical execution time. All jobs have to be processed on a set of parallel machines. Preemptions can be either allowed or forbidden. The aim is to construct a feasible schedule such that a given criterion is minimized. In this paper, we survey existing approaches for the problem class considered.

引用

页码：435 / 444

页数：10

共 46 条

[1]

[Anonymous], 1983, Mathematical Programming The State of the Art, DOI DOI 10.1007/978-3-642-68874-4_9

[2]

Baptiste P., 1999, Journal of Scheduling, V2, P245, DOI 10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO

[3]

2-5

[4] Scheduling equal-length jobs on identical parallel machines [J].

Baptiste, P .

DISCRETE APPLIED MATHEMATICS, 2000, 103 (1-3) :21-32

[5] Preemptive scheduling of equal-length jobs to maximize weighted throughput [J].

Baptiste, P ;

Chrobak, M ;

Dürr, C ;

Jawor, W ;

Vakhania, N .

OPERATIONS RESEARCH LETTERS, 2004, 32 (03) :258-264

[6]

Baptiste P, 2004, 4OR-Q J OPER RES, V2, P111

[7]

Baptiste P., 2004, HDB SCHEDULING ALGOR, P78

[8] The complexity of mean flow time scheduling problems with release times [J].

Baptiste, Philippe ;

Brucker, Peter ;

Chrobak, Marek ;

Durr, Christoph ;

Kravchenko, Svetlana A. ;

Sourd, Francis .

JOURNAL OF SCHEDULING, 2007, 10 (02) :139-146

[9]

Brucker P., 1977, Mathematics of Operations Research, V2, P275, DOI 10.1287/moor.2.3.275

[10]

BRUCKER P, 2010, COMPLEXITY RESULTS S

← 1 2 3 4 5 →