**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**

**Abstract:**

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