Abstract of Paper

Preemptive Scheduling with Dedicated Processors: Applications of Fractional Graph Coloring
by Klaus Jansen, Lorant Porkolab

Abstract:

We study the problem of scheduling independent multiprocessor tasks, where
for each task in addition to the processing time(s) there is a prespecified
dedicated subset (or a family of alternative subsets) of processors which
are required to process the task simultaneously. Focusing on problems where
all required (alternative) subsets of processors have the same fixed
cardinality, we present complexity results for computing preemptive
schedules with minimum makespan closing the gap between computationally
tractable and intractable instances. In particular, we show that for the
dedicated version of the problem, optimal preemptive schedules of
bi-processor tasks (i.e. tasks whose dedicated processor sets are all of
cardinality two) can be computed in polynomial time. We give various
extensions of this result including one to maximum lateness minimization
with release times and due dates. All these results are based on a nice
relation between preemptive scheduling and fractional coloring of graphs. In
contrast to the positive results, we also prove that the problems of
computing optimal preemptive schedules for three-processor tasks or for
bi-processor tasks with (possible several) alternative modes are strongly
NP-hard.