On the minimum number of processors for scheduling problems with communicationdelays

A. Moukrim

Annals of Operations Research, 1999, vol. 86, issue 0, 455-472

Abstract: Scheduling problems with interprocessor communication delays are recent problemsarising with the development of new message‐passing architectures whose number of processorsis increasing more and more. The scheduling problem with communication delays isNP‐complete even on an unlimited number of processors, and most of the restrictions whichare known to make the problem easy suppose that the number of processors is unlimited.The aim of this paper is to estimate the minimum number of processors required to realizea schedule that minimizes the makespan for problems with communication delays. Contraryto problems without communication costs, we show that the minimum number of partitioningpaths of tasks is not an upper bound. Then we propose two upper bounds b and b whichare valid independent of task processing times and communication costs. We show thatb can be calculated in O(n 2 ) if n designates the number of tasks. Then we give an algorithmfor determining b in the special case when the precedence graph is an in‐tree or anout-tree. A specific study of SCT task systems (Small Communication Time) shows that theachromatic number of the cocomparability graph is an upper bound on the minimum numberof processors. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018931508072 (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:annopr:v:86:y:1999:i:0:p:455-472:10.1023/a:1018931508072

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

DOI: 10.1023/A:1018931508072

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().