Scheduling precedence graphs in systems with interprocessor communication times

Jing Jang Hwang; Yuan Chieh Chow; Frank D. Anger; Chung Yee Lee

doi:10.1137/0218016

Scheduling precedence graphs in systems with interprocessor communication times

Jing Jang Hwang^*, Yuan Chieh Chow, Frank D. Anger, Chung Yee Lee

^*Corresponding author for this work

National Yang Ming Chiao Tung University

Research output: Contribution to journal › Journal Article › peer-review

438 Scopus citations

Abstract

The problem of nonpreemptively scheduling a set of m partially ordered tasks on n identical processors subject to interprocessor communication delays is studied in an effort to minimize the makespan. A new heuristic, called earliest task first (ETF), is designed and analyzed. An algorithm is also provided to calculate the communication requirements over some immediate predecessor-immediate successor pairs along one chain. The time complexity of Algorithm ETF is O(nm²).

Original language	English
Pages (from-to)	244-257
Number of pages	14
Journal	SIAM Journal on Computing
Volume	18
Issue number	2
DOIs	https://doi.org/10.1137/0218016
State	Published - 1989
Externally published	Yes

Access to Document

10.1137/0218016

Cite this

@article{1844e6eefcb2414eb55ab3d82781c430,

title = "Scheduling precedence graphs in systems with interprocessor communication times",

abstract = "The problem of nonpreemptively scheduling a set of m partially ordered tasks on n identical processors subject to interprocessor communication delays is studied in an effort to minimize the makespan. A new heuristic, called earliest task first (ETF), is designed and analyzed. An algorithm is also provided to calculate the communication requirements over some immediate predecessor-immediate successor pairs along one chain. The time complexity of Algorithm ETF is O(nm2).",

author = "Hwang, {Jing Jang} and Chow, {Yuan Chieh} and Anger, {Frank D.} and Lee, {Chung Yee}",

year = "1989",

doi = "10.1137/0218016",

language = "英语",

volume = "18",

pages = "244--257",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Scheduling precedence graphs in systems with interprocessor communication times

AU - Hwang, Jing Jang

AU - Chow, Yuan Chieh

AU - Anger, Frank D.

AU - Lee, Chung Yee

PY - 1989

Y1 - 1989

N2 - The problem of nonpreemptively scheduling a set of m partially ordered tasks on n identical processors subject to interprocessor communication delays is studied in an effort to minimize the makespan. A new heuristic, called earliest task first (ETF), is designed and analyzed. An algorithm is also provided to calculate the communication requirements over some immediate predecessor-immediate successor pairs along one chain. The time complexity of Algorithm ETF is O(nm2).

AB - The problem of nonpreemptively scheduling a set of m partially ordered tasks on n identical processors subject to interprocessor communication delays is studied in an effort to minimize the makespan. A new heuristic, called earliest task first (ETF), is designed and analyzed. An algorithm is also provided to calculate the communication requirements over some immediate predecessor-immediate successor pairs along one chain. The time complexity of Algorithm ETF is O(nm2).

UR - http://www.scopus.com/inward/record.url?scp=0024647955&partnerID=8YFLogxK

U2 - 10.1137/0218016

DO - 10.1137/0218016

M3 - 文章

AN - SCOPUS:0024647955

SN - 0097-5397

VL - 18

SP - 244

EP - 257

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -

Scheduling precedence graphs in systems with interprocessor communication times

Abstract

Access to Document

Other files and links

Fingerprint

Cite this