- CARMA OANT SEMINAR
- Speaker: Dr Hamish Waterer, School of Mathematical and Physical Sciences, The University of Newcastle
- Title: A Bucket-Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems
- Location: Room V205, Mathematics Building (Callaghan Campus) The University of Newcastle
- Access Grid Venue: CARMA [ENQUIRIES]
- Time and Date: 3:00 pm, Tue, 17th Sep 2013
An exact bucket indexed (BI) mixed integer linear programming formulation for nonpreemptive single machine scheduling problems is presented that is a result of an ongoing investigation into strategies to model time in planning applications with greater efficacy. The BI model is a generalisation of the classical time indexed (TI) model to one in which at most two jobs can be processing in each time period. The planning horizon is divided into periods of equal length, but unlike the TI model, the length of a period is a parameter of the model and can be chosen to be as long as the processing time of the shortest job. The two models are equivalent if the problem data are integer and a period is of unit length, but when longer periods are used in the BI model, it can have significantly fewer variables and nonzeros than the TI model at the expense of a greater number of constraints. A computational study using weighted tardiness instances reveals the BI model significantly outperforms the TI 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.
Joint work with Natashia Boland and Riley Clement.
- [Permanent link]