Scheduling chain-structured tasks to minimize makespan and mean flow time

AbstractWe 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