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

^*此作品的通信作者

National Yang Ming Chiao Tung University

研究成果: 期刊稿件 › 文章 › 同行評審

438 引文斯高帕斯（Scopus）

摘要

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²).

原文	英語
頁（從 - 到）	244-257
頁數	14
期刊	SIAM Journal on Computing
卷	18
發行號	2
DOIs	https://doi.org/10.1137/0218016
出版狀態	已出版 - 1989
對外發佈	是

存取文件

10.1137/0218016

其它文件與鏈接

Link to publication in Scopus

引用此

@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

摘要

存取文件

其它文件與鏈接

指紋

引用此