Séminaire du LIF
Jeudi 15 janvier à 14h - Luminy, Amphi 12
Hans-Juergen Bandelt
Université de Hambourg, Allemagne
Scheduling equal-length jobs within a tight planning horizon:
lifting grammar for facet-inducing inequalities
We study the 0/1-polytopes associated with the problem of scheduling n jobs on a single machine that require p consecutive units of processing time within a fixed planning horizon comprising T time units. The processing costs depend solely on the start times, and the aim is to minimize total costs. A polyhedral approach for this scheduling problem has previously been proposed by Crama and Spieksma under the additional hypothesis that the idling T - np of the machine lasts at least p (or more) time units. We consider the case of limited idling of p - 1 time units, for which new equations emerge. The structure of the facet-defining inequalities that are of set-packing type is more complex than in the case when the total idling is sufficiently large. Several classes of these and other inequalities can be generated via lifting procedures from the small polytopes for two or three jobs with processing time at most 4. These procedures can successively be combined, obeying certain rules ("lifting grammar").
This is a joint work with M. Hedde, O. Suhr, and S. De Vries.
Home page : http://www.math.uni-hamburg.de/home/bandelt/