The Multiprocessor Scheduling of Precedence-Constrained Task Systems in the Presence of Interprocessor Communication Delays

Sanjoy K. Baruah
Additional contact information
Sanjoy K. Baruah: The University of Vermont, Burlington, Vermont

Operations Research, 1998, vol. 46, issue 1, 65-72

Abstract: The problem of scheduling precedence-constrained task systems characterized by interprocessor communication delays is addressed. It is assumed that task duplication is permitted. The target machine is a homogenous multiprocessor with an unbounded number of processors. The general problem is known to be NP-hard; however, when communication delays are small relative to task execution times, the C.P.M. based approach of Colin and Chrétienne (1991) yields an optimal schedule in polynomial time. Extensions to this method of Colin and Chrétienne are presented here, which allow for polynomial-time optimal schedule generation for certain categories of task systems with arbitrary precedence relations, processing times, and communication delays.

Keywords: Computers; task allocation on distributed memory processors; Production/scheduling; scheduling with interprocessor communication delays (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.1.65 (application/pdf)

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:inm:oropre:v:46:y:1998:i:1:p:65-72

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().