SCHEDULING CHAIN-STRUCTURED TASKS TO MINIMIZE MAKESPAN AND MEAN FLOW TIME

We consider the problem of scheduling a set of chains onm 〉 1 identical processors with the objectives of minimizing the makespan and the mean flow time. We show that finding a nonpreemptive schedule with the minimum makespan is strongly NP-hard for each fixedm 〉 1, answering the open question of whether this problem is strongly NP-hard for trees. We also show that finding a nonpreemptive schedule with the minimum mean flow time is strongly NP-hard for each fixedm 〉 1, improving the known strong NP-hardness results for in-trees and out-trees. Finally, we generalize the result of McNaughton, showing that preemption cannot reduce the mean weighted flow time for a set of chains. The last two results together imply that finding a preemptive schedule with the minimum mean flow time is also strongly NP-hard for each fixedm 〉 1, answering another open question on the complexity of this problem for trees. © 1991, Academic Press, Inc.. All rights reserved.