Scheduling multiprocessor tasks for mean flow time criterion

Multiprocessor tasks are executed by more than one processor at the same moment of time. This work considers the problem of scheduling unit execution-time and preemptable multiprocessor tasks on m parallel identical processors to minimize mean flow time and mean weighted flow time. We analyze complexity status of the problem. When tasks have unit execution time and the number of processors is arbitrary the problem is shown to be computationally hard. Constructing an optimal preemptive schedule is also computationally hard in general. Polynomial algorithms are presented for scheduling unit execution time tasks when the number of processors is fixed, or the numbers of simultaneously required processors are powers of 2. The case of preemptable tasks requiring either 1 or m processors simultaneously is solvable in low-order polynomial time.