Scheduling parallel tasks withsequential heads and tails

M. Drozdowski and W. Kubiak

Annals of Operations Research, 1999, vol. 90, issue 0, 246 pages

Abstract: This paper considers scheduling of parallel tasks in a multiprogrammed, multiprocessorsystem. The problem of preemptive scheduling of n tasks on m processors to minimizemakespan is studied. Task j starts and finishes with sequential parts head j and tail j , respectively.Between these two, j runs its parallel part parallel j . The sequential parts have to beexecuted by one processor at a time. The parallel part can be executed by more than oneprocessor at a time. It is shown that this problem is NP‐hard in the strong sense even if thereare fewer tasks than processors. A linear program is presented to find an optimal schedulefor a given sequence of completion times of heads and start times of tails. If the optimalschedule for tasks longer than the mth longest task is given, an efficient, polynomial‐timemerging algorithm is proposed to obtain an optimal schedule for all n tasks. The algorithmbuilds an optimal schedule with at most m ‐ 1 tasks running their parallel parts on morethan one processor at a time, the remaining tasks run their parallel parts as if they weresequential. Therefore, there always exist optimal schedules with only a few tasks exploitingthe parallel processing capability of a parallel system. Finally, polynomially solvable casesare discussed, and the worst‐case performance of three heuristics for the problem is analyzed. 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:1018964732122 (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:90:y:1999:i:0:p:221-246:10.1023/a:1018964732122

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

DOI: 10.1023/A:1018964732122

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