Scheduling parallel tasks withsequential heads and tails

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