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(nlogn) 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 sumultaneously minimizing the flow time and the schedule length.
