Friday, 11:00 - 11:25 h, Room: H 2033


Riley Clement
A big-bucket time-indexed formulation for nonpreemptive single machine scheduling problems

Coauthors: Natashia Lesley Boland, Hamish Alfred Waterer


Nonpreemptive single machine scheduling problems require a set of jobs to be scheduled on a single machine such that each job is processed exactly once without interruption and the machine processes at most one job at a time. The classical time-indexed (TI) formulation of this problem discretizes a planning horizon into periods of unit length. We
present a big-bucket time-indexed (TIBB) formulation in which the length of each period is no larger than the processing time of the shortest job. The two models are equivalent in the case that this job has unit processing time. When the minimum processing time is larger than the greatest common divisor of the problem input data the TIBB model has fewer periods than the TI model. We show how to adapt facet-defining inequalities for the TI model to the TIBB model and describe conditions under which they are facet-defining. Computational experiments compare the performance of the TIBB model to the TI model for both weighted completion time and weighted tardiness instances described in the literature.


Talk 2 of the invited session Fri.1.H 2033
"Integer programming approaches to job scheduling" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis Sale was obtained in Europe, Australia, New Zealand.