Name
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 headj and tailj , respectively.Between these two, j runs its parallel part parallelj. 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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1023/A:1018964732122 | Annals OR |
Keywords | Field | DocType |
Completion Time,Sequential Part,Parallel Processing,Strong Sense,Optimal Schedule | Fixed-priority pre-emptive scheduling,Preemption,Computer science,Scheduling (computing),Parallel processing,Parallel computing,Embarrassingly parallel,Schedule,Heuristics,Linear programming | Journal |
Volume | Issue | ISSN |
90 | 0 | 1572-9338 |
Citations | PageRank | References |
1 | 0.35 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maciej Drozdowski | 1 | 1 | 0.35 |
| Wieslaw Kubiak | 2 | 540 | 62.61 |