Facets of Scheduling

Participant: Andreas S. Schulz
Cooperation with: Maurice Queyranne, The University of British Columbia, Canada
Supported by: German National Science Foundation (DFG), grant Mo 446/3-1.

Project description:

The polyhedral approach is one of the foundations of mathematical programming. It applies in particular to combinatorial optimization, for which it has theoretically and computationally important implications. The polyhedral point of view often leads to a deep understanding of structural and algorithmic properties of combinatorial optimization problems. Until recently, however, there was only limited success in applying polyhedral approaches to scheduling.

In this research project, we exploit the polyhedral point of view for several scheduling problems. Thereby, we mainly aim for a unifying point of view which leads to deeper insights and more general results than have been known heretofore. The results obtained by this approach touch various fields: approximation algorithms are designed and analyzed by using appropriate linear programs; min-max theorems in polyhedral combinatorics are obtained from complete linear descriptions; and scheduling theory is enriched by establishing the underlying common polyhedral structures of seemingly different scheduling problems, giving a better understanding of those aspects that make them tractable.

Figure: The three-dimensional permutahedron: a simple scheduling polytope.

New insights especially result from establishing a rigorous relationship to supermodular polyhedra which reveals the real nature of many scheduling polyhedra.

In his 1990 paper on single machine scheduling problems (L.A. Wolsey, Formulating single machine scheduling problems with precedence constraints, in J.J. Gabszewicz et al. (eds.), Economic Decision-Making: Games, Econometrics and Optimisation, North-Holland, Amsterdam, 1990, pp. 473-484), Wolsey said that ``The ultimate goal of this research is to obtain strong lower bounds for problems simultaneously involving several machines with precedence constraints, deadlines and release dates.'' However, neither powerful polyhedral formulations for multiple machine problems nor a worst-case analysis of the quality of the LP relaxations were known at that time. Part of our work can be seen as a step in this direction. LP's for various multiple machine environments including precedence constraints and release dates are presented and, for the first time, analyzed.

A particularly promising model for resource-constrained scheduling is the interval order polytope of a digraph, which precisely captures the underlying order-theoretic structure of the problem and abstracts from the actual processing times of the jobs. Future work will include the algorithmic use of primal and dual bounds obtained from this approach to real-world problems.