MULTIPROCESSOR SCHEDULING WITH COMMUNICATION DELAYS

被引：91

作者：

VELTMAN, B ^{[1
]}

LAGEWEG, BJ ^{[1
]}

LENSTRA, JK ^{[1
]}

机构：

[1] EINDHOVEN UNIV TECHNOL,DEPT MATH & COMP SCI,POB 513,5600 MB EINDHOVEN,NETHERLANDS

来源：

PARALLEL COMPUTING | 1990年 / 16卷 / 2-3期

关键词：

SCHEDULING; PARALLEL PROCESSORS; COMMUNICATION DELAYS; ALGORITHMS; COMPLEXITY;

D O I：

10.1016/0167-8191(90)90056-F

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper adresses certain types of scheduling problems that arise when a parallel computation is to be executed on a multiprocessor. We define a model that allows for communication delays between precedence-related tasks, and propose a classification of various submodels. We also review complexity results and optimization and approximation algorithm that have been presented in the literature.

引用

页码：173 / 182

页数：10

共 22 条

[1]

BLAZEWICZ J, 1986, IEEE T COMPUT, V35, P389

[2] SCHEDULING INDEPENDENT 2-PROCESSOR TASKS TO MINIMIZE SCHEDULE LENGTH [J].

BLAZEWICZ, J ;

WEGLARZ, J ;

DRABOWSKI, M .

INFORMATION PROCESSING LETTERS, 1984, 18 (05) :267-273

[3]

BOKHARI SH, 1981, IEEE T COMPUT, V30, P207, DOI 10.1109/TC.1981.1675756

[4]

Bozoki G., 1970, AIIE T, V2, P246

[5] PREEMPTIVE SCHEDULING OF INDEPENDENT JOBS ON A HYPERCUBE [J].

CHEN, GI ;

LAI, TH .

INFORMATION PROCESSING LETTERS, 1988, 28 (04) :201-206

[6]

CHEN GI, 1988, P C THEORETICAL ASPE, P273

[7]

CHRETIENNE P, 1989, EUROPEAN J OPER RES, V43, P255

[8]

COLIN JY, 1990, IN PRESS OPER RES

[9]

Du J., 1989, SIAM J DISCRETE MATH, V2, P473, DOI DOI 10.1137/0402042

[10]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

← 1 2 3 →