A comparison of heuristics for scheduling multiprocessor tasks on three dedicated processors

被引：4

作者：

Amoura, AK

Bampis, E

Manoussakis, Y

Tuza, Z

机构：

[1] Univ Paris Sud, LRI, F-91405 Orsay, France

[2] Univ Evry, LaMI, F-91025 Evry, France

[3] Hungarian Acad Sci, Inst Comp & Automat, H-1111 Budapest, Hungary

来源：

PARALLEL COMPUTING | 1999年 / 25卷 / 01期

基金：

匈牙利科学研究基金会;

关键词：

scheduling; multiprocessor tasks; dedicated processors;

D O I：

10.1016/S0167-8191(98)00102-1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problem of scheduling a set of independent multiprocessor tasks on three dedicated processors in order to minimize the makespan. We propose a new heuristic, called Divide Uniprocessor Tasks (DUT), and we provide simulation results comparing the effectiveness of DUT with previously known heuristics. (C) 1999 Published by Elsevier Science B.V. All rights reserved.

引用

页码：49 / 61

页数：13

共 10 条

[1]

BIANCO L, 1994, NAV RES LOG, V41, P959, DOI 10.1002/1520-6750(199412)41:7<959::AID-NAV3220410708>3.0.CO

[2]

2-K

[3]

BLAZEWICZ J, 1992, INFORM PROCESS LETT, V41, P275, DOI 10.1016/0020-0190(92)90172-R

[4] SCHEDULING MULTIPROCESSOR TASKS ON 3 DEDICATED PROCESSORS INFORMATION-PROCESSING LETTERS (VOL 41, PG 275, 1992) [J].

BLAZEWICZ, J ;

DELLOLMO, P ;

DROZDOWSKI, M ;

SPERANZA, MG .

INFORMATION PROCESSING LETTERS, 1994, 49 (05) :269-270

[5]

Bozoki G., 1970, AIIE T, V2, P246, DOI [10.1080/05695557008974759, DOI 10.1080/05695557008974759]

[6] AN APPROXIMATION ALGORITHM FOR SCHEDULING ON 3 DEDICATED MACHINES [J].

GOEMANS, MX .

DISCRETE APPLIED MATHEMATICS, 1995, 61 (01) :49-59

[7]

Graham R. L., 1979, Discrete Optimisation, P287

[8] COMPLEXITY OF SCHEDULING MULTIPROCESSOR TASKS WITH PRESPECIFIED PROCESSOR ALLOCATIONS [J].

HOOGEVEEN, JA ;

VANDEVELDE, SL ;

VELTMAN, B .

DISCRETE APPLIED MATHEMATICS, 1994, 55 (03) :259-272

[9] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS [J].

JOHNSON, DS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) :256-278

[10]

[No title captured]

← 1 →