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" [...]


  The main criterion for them is your ability to repay any Wisconsin Loans Online, they are not interested in your previous attempts, the current one is all that matters. In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.