Upper bound on the number of processors for scheduling with interprocessor communication delays

Aziz Moukrim

Mathematical Methods of Operations Research, 2000, vol. 52, issue 1, 99-113

Abstract: The problem of scheduling a task system with communication delays on multiprocessor systems is known to be NP-hard in its general form as well as many restricted cases even on an unlimited number of processors. In this paper, we study the problem of determining an upper bound on the minimum number of processors achieved by a schedule that minimizes the makespan for scheduling problems with communication delays. We prove that the minimum number of partitioning paths of the precedence graph is an upper bound on the minimum number of processors for UET-UCT (Unit Execution Time-Unit Communication Time) task systems. Then we propose an algorithm of O(n) (n designates the number of tasks) to compute an upper bound, which is valid independently of task processing times and communication delays, in the special case when the precedence graph is an out-tree or an in-tree. Copyright Springer-Verlag Berlin Heidelberg 2000

Keywords: Key words: scheduling; makespan; communication delays; minimum number of processors (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s001860000062 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:52:y:2000:i:1:p:99-113

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s001860000062

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().