TREE SCHEDULING WITH COMMUNICATION DELAYS

被引：8

作者：

CHRETIENNE, P

机构：

来源：

DISCRETE APPLIED MATHEMATICS | 1994年 / 49卷 / 1-3期

关键词：

D O I：

10.1016/0166-218X(94)90205-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper considers the problem of scheduling a tree-structured task system in a distributed environment with the goal of minimizing the makespan. Interprocessor communication delays are taken into account and task duplication is allowed. Furthermore, it is assumed that the number of processors is unlimited. It is shown that there is a polynomial-time algorithm for an outtree and that the intree case is NP-hard. In addition, a special case of intree is shown to be polynomially solvable.

引用

页码：129 / 141

页数：13

共 8 条

[1] CHRETIENNE P, 1989, EUROPEAN J OPER RES, V2, P225
[2] CHRETIENNE P, 1989, P INT WORKSHOP PARAL
[3] COLIN JY, 1991, OPER RES, V39
[4] GAREY MR, 1978, COMPUTES INTRACTABIL
[5] MULTIPROCESSOR SCHEDULING WITH INTERPROCESSOR COMMUNICATION DELAYS
LEE, CY
HWANG, JJ
CHOW, YC
ANGER, FD
[J]. OPERATIONS RESEARCH LETTERS, 1988, 7 (03) : 141 - 147
[6] LENSTRA JK, 1978, OPER RES, V26
[7] PAPADIMITRIOU CH, 1988, 20TH P ANN ACM S THE
[8] RAYWARDSMITH VJ, 1988, DISCRETE APPL MATH, V18, P55

← 1 →