Optimization Online


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

Natashia Boland (natashia.boland***at***newcastle.edu.au)
Riley Clement (riley.clement***at***uon.edu.au)
Hamish Waterer (hamish.waterer***at***newcastle.edu.au)

Abstract: 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.

Keywords: single machine scheduling, time indexed, big bucket, mixed integer linear programming

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Report C-OPT 2013-002, Centre for Optimal Planning and Operations, University of Newcastle, Australia, February 2013

Download: [PDF]

Entry Submitted: 02/13/2013
Entry Accepted: 02/13/2013
Entry Last Modified: 09/12/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society