A note on scheduling multiprocessor tasks with identical processing times

被引：10

作者：

Baptiste, P ^{[1
]}

机构：

[1] Compiegne & Ecole Polytech, UTC, UMR 6599, CNRS Heudiasyc, F-60200 Palaiseau, France

来源：

COMPUTERS & OPERATIONS RESEARCH | 2003年 / 30卷 / 13期

关键词：

multiprocessor task scheduling; dynamic programming; identical processing times;

D O I：

10.1016/S0305-0548(02)00116-8

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We study the scheduling situation where n tasks with identical processing times have to be scheduled on m parallel processors. Each task is subjected to a release date and requires simultaneously a fixed number of processors. We show that, for each fixed value of m, the problem of minimizing total completion time can be solved in polynomial time. The complexity status of the corresponding problem Pm|r(i), p(i) = p,size(i)|SigmaC(i) was unknown before.

引用

页码：2071 / 2078

页数：8

共 11 条

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

Baptiste, P .

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

[2]

Blaewicz J., 2001, Scheduling computer and manufactoring processes

[3] Scheduling UET task systems with concurrency on two parallel identical processors [J].

Brucker, P ;

Knust, S ;

Roper, D ;

Zinder, Y .

MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2000, 52 (03) :369-387

[4]

BRUCKER P, 1998, SCHEDULING ALGORITHM

[5] Scheduling multiprocessor tasks for mean flow time criterion [J].

Drozdowski, M ;

Dell'Olmo, P .

COMPUTERS & OPERATIONS RESEARCH, 2000, 27 (06) :571-585

[6]

DROZDOWSKI M, 1997, SELECTED PROBLEMS SC

[7]

Du J., 1989, SIAM J. Discret. Math, V2, P473, DOI [10.1137/0402042, DOI 10.1137/0402042]

[8]

JANSEN K, 2000, INT S ALG COMP

[9] Scheduling one and two-processor tasks on two parallel processors [J].

Lee, CY ;

Cai, XQ .

IIE TRANSACTIONS, 1999, 31 (05) :445-455

[10]

Lenstra, 1977, ANN DISCRETE MATH, V1, P343, DOI DOI 10.1016/S0167-5060(08)70743-X

← 1 2 →