Concurrent Task Systems

Errol L. Lloyd
Additional contact information
Errol L. Lloyd: University of Pittsburgh, Pittsburgh, Pennsylvania

Operations Research, 1981, vol. 29, issue 1, 189-201

Abstract: We study minimum execution time scheduling of computer task systems where each task may require control of several processors during each step of its execution. Such a task system consists of: m identical processors, tasks T 1 , …, T n , and a partial order on those tasks which represents precedence constraints. Associated with each task T 1 is a positive integral execution time τ 1 and a degree of concurrency q 1 ∈ (C-script) where (C-script) ⊆ {1, …, m }. Task T 1 must execute for τ 1 , steps and for each of those τ 1 steps it requires q 1 processors. Minimum length schedules for systems in which all task execution times are equal (concurrent UET task systems) are studied. Three sets of results are given. First, we show that scheduling concurrent UET task systems is NP-complete even if there are only three processors and each task has a degree of concurrency of either 1 or 2. Secondly, given any concurrent UET task system let r be the maximum degree of concurrency of any task. We show that the ratio of the length of an arbitrary list schedule for that system compared to the length of an optimal schedule is bounded above by (2 m − r )/( m − r + 1). We also show that the ratio ⌊(2 m − r )/( m − r + 1 )⌋ is achievable. Finally, we give an algorithm which produces optimal schedules for concurrent UET task systems on two processors.

Date: 1981
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.29.1.189 (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:29:y:1981:i:1:p:189-201

Access Statistics for this article

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