Minimizing schedule length subject to minimum flow time

The problem of scheduling n independent tasks on m ≥ 1 identical processors, with the objective of minimizing the schedule length under the constraint that it must have minimum flow time, is considered. For nonpreemptive scheduling, it is known that the problem is NP-hard. This paper shows that the problem is a lot easier for preemptive scheduling. Specifically, an O(n log n) time algorithm to find an optimal preemptive schedule is given. This algorithm generates schedules with at most m - 1 preemptions. It is also shown that an optimal nonpreemptive schedule can be almost twice as long as an optimal preemptive schedule. The results suggest that preemption is extremely beneficial in simultaneously minimizing the flow time and the schedule length.