A big bucket time indexed mixed integer linear programming formulation for nonpreemptive single machine scheduling problems is presented in which the length of each period can be as large as the processing time of the shortest job. The model generalises the classical time indexed model to one in which at most two jobs can be processing in each period. The two models are equivalent in the case that the shortest job has unit processing time. For larger minimum processing times the big bucket model can have significantly fewer variables and nonzeros than the time indexed model at the expense of a greater number of constraints. Facet-inducing inequalities for the convex hull of the set of feasible partial schedules, that is, schedules in which not all jobs have to be started, are derived from facet-inducing inequalities for the time indexed model. A computational study using weighted tardiness instances reveals the big bucket model significantly outperforms the time indexed model on instances where the mean processing time of the jobs is large and the range of processing times is small, that is, the processing times are clustered rather than dispersed.
Citation
Report C-OPT 2013-002, Centre for Optimal Planning and Operations, University of Newcastle, Australia, February 2013