Scheduling parallel tasks with sequential heads and tails

This paper considers scheduling of parallel tasks in a multiprogrammed, mul tiprocessor system. The problem of preemptive scheduling of n tasks on m pr ocessors to minimize makespan is studied. Task j starts and finishes with s equential parts head(j) and tail(j) , respectively. Between these two, j ru ns its parallel part parallel(j). The sequential parts have to be executed by one processor at a time. The parallel part can be executed by more than one processor at a time. It is shown that this problem is NP-hard in the st rong sense even if there are fewer tasks than processors. A linear program is presented to find an optimal schedule for a given sequence of completion times of heads and start times of tails. If the optimal schedule for tasks longer than the mth longest task is given, an efficient, polynomial-time m erging algorithm is proposed to obtain an optimal schedule for all n tasks. The algorithm builds an optimal schedule with at most m - 1 tasks running their parallel parts on more than one processor at a time, the remaining ta sks run their parallel parts as if they were sequential. Therefore, there a lways exist optimal schedules with only a few tasks exploiting the parallel processing capability of a parallel system. Finally, polynomially solvable cases are discussed, and the worst-case performance of three heuristics fo r the problem is analyzed.