Polynomial-time Approximation Algorithms for Preemptive Resource Constrained Scheduling and Fractional Graph Coloring.
by
Klaus Jansen
Universität Kiel
Coauthors: Lorant Porkolab, Imperial College London

We study resource constrained scheduling problems where the objective is to compute feasible preemptive schedules minimizing the makespan and using no more resources than what are available. We present approximation algorithms along with some inapproximibility results showing how the approximability of the problem changes in terms of the number of resources. All the results are based on linear programming formulations (though with exponentially many variables) that are called fractional covering problems. Furthermore we show some interesting connections between resource constrained scheduling and (multi - dimensional, multiple-choice, and cardinality constrained) variants of the classical knapsack problem. Finally we present applications of the above results in fractional graph coloring and multiprocessor task scheduling.

Date received: March 26, 2001