contents
|
|
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.
References:
- M. Queyranne and A. S. Schulz,
Polyhedral approaches to machine scheduling, Preprint 408/1994,
Department of Mathematics, TU Berlin, to appear in Mathematical Programming B
- R. Müller and A. S. Schulz,
The interval order polytope of a digraph, in E. Balas and J. Clausen
(eds.), Integer Programming and Combinatorial Optimization, Springer Lecture
Notes in Computer Science 920 (1995), 50-64
- A. S. Schulz, Polytopes and Scheduling
(one-sided,
two-sided), PhD thesis,
Technical University of Berlin, Germany, 1996
|
top