Multiprocessor scheduling with interprocessor communication delays

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

*此作品的通信作者

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

59 引文 斯高帕斯(Scopus)

摘要

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

原文英語
頁(從 - 到)141-147
頁數7
期刊Operations Research Letters
7
發行號3
DOIs
出版狀態已出版 - 06 1988
對外發佈

指紋

深入研究「Multiprocessor scheduling with interprocessor communication delays」主題。共同形成了獨特的指紋。

引用此