Multiprocessor scheduling with interprocessor communication delays

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

doi:10.1016/0167-6377(88)90080-6

Multiprocessor scheduling with interprocessor communication delays

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

^*Corresponding author for this work

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

59 Scopus citations

Abstract

We consider the problem of scheduling a set of n partially ordered tasks on m identical processors in order to minimize the makespan, where there is a communication delay between any pair of distinct processors. This problem is NP-hard. We provide a heuristic algorithm, call it Earliest Ready Task (ERT) algorithm, to solve the problem. Among all tasks whose parent tasks have been assigned, an ERT algorithm is one that always chooses one task that can be processed earliest. We show that the makespan M generated by ERT algorithm always satisfies M {slanted equal to or less-than} (2-1/m)M′ + C_comm, where M′ is the optimal makespan without considering communication delay and C_comm is the maximum communication delay in one chain. We will also provide an algorithm to find this chain. The time complexity of implementing the ERT algorithm is O(mn²).

Original language	English
Pages (from-to)	141-147
Number of pages	7
Journal	Operations Research Letters
Volume	7
Issue number	3
DOIs	https://doi.org/10.1016/0167-6377(88)90080-6
State	Published - 06 1988
Externally published	Yes

Keywords

interprocessor communication delay
multiprocessor scheduling
worst-case error bound

Access to Document

10.1016/0167-6377(88)90080-6

Cite this

@article{4341db4c8c1b4a76b363634c4e8aa93c,

title = "Multiprocessor scheduling with interprocessor communication delays",

abstract = "We consider the problem of scheduling a set of n partially ordered tasks on m identical processors in order to minimize the makespan, where there is a communication delay between any pair of distinct processors. This problem is NP-hard. We provide a heuristic algorithm, call it Earliest Ready Task (ERT) algorithm, to solve the problem. Among all tasks whose parent tasks have been assigned, an ERT algorithm is one that always chooses one task that can be processed earliest. We show that the makespan M generated by ERT algorithm always satisfies M {slanted equal to or less-than} (2-1/m)M′ + Ccomm, where M′ is the optimal makespan without considering communication delay and Ccomm is the maximum communication delay in one chain. We will also provide an algorithm to find this chain. The time complexity of implementing the ERT algorithm is O(mn2).",

keywords = "interprocessor communication delay, multiprocessor scheduling, worst-case error bound",

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

year = "1988",

month = jun,

doi = "10.1016/0167-6377(88)90080-6",

language = "英语",

volume = "7",

pages = "141--147",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Multiprocessor scheduling with interprocessor communication delays

AU - Lee, Chung Yee

AU - Hwang, Jing Jang

AU - Chow, Yuan Chieh

AU - Anger, Frank D.

PY - 1988/6

Y1 - 1988/6

N2 - We consider the problem of scheduling a set of n partially ordered tasks on m identical processors in order to minimize the makespan, where there is a communication delay between any pair of distinct processors. This problem is NP-hard. We provide a heuristic algorithm, call it Earliest Ready Task (ERT) algorithm, to solve the problem. Among all tasks whose parent tasks have been assigned, an ERT algorithm is one that always chooses one task that can be processed earliest. We show that the makespan M generated by ERT algorithm always satisfies M {slanted equal to or less-than} (2-1/m)M′ + Ccomm, where M′ is the optimal makespan without considering communication delay and Ccomm is the maximum communication delay in one chain. We will also provide an algorithm to find this chain. The time complexity of implementing the ERT algorithm is O(mn2).

AB - We consider the problem of scheduling a set of n partially ordered tasks on m identical processors in order to minimize the makespan, where there is a communication delay between any pair of distinct processors. This problem is NP-hard. We provide a heuristic algorithm, call it Earliest Ready Task (ERT) algorithm, to solve the problem. Among all tasks whose parent tasks have been assigned, an ERT algorithm is one that always chooses one task that can be processed earliest. We show that the makespan M generated by ERT algorithm always satisfies M {slanted equal to or less-than} (2-1/m)M′ + Ccomm, where M′ is the optimal makespan without considering communication delay and Ccomm is the maximum communication delay in one chain. We will also provide an algorithm to find this chain. The time complexity of implementing the ERT algorithm is O(mn2).

KW - interprocessor communication delay

KW - multiprocessor scheduling

KW - worst-case error bound

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

U2 - 10.1016/0167-6377(88)90080-6

DO - 10.1016/0167-6377(88)90080-6

M3 - 文章

AN - SCOPUS:0024034138

SN - 0167-6377

VL - 7

SP - 141

EP - 147

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Multiprocessor scheduling with interprocessor communication delays

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this