CARMA/OANT AGR Seminar: A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems

Host Institution:

University of Newcastle (CARMA)

Title of Seminar:

A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems

Speaker's Name:

Dr Hamish Waterer

Speaker's Institution:

CARMA, University of Newcastle

Time and Date:

Tuesday 17 September 2013, 3.00pm (AEST)

Seminar Abstract:

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.

Seminar Contact:

This email address is being protected from spambots. You need JavaScript enabled to view it.
This email address is being protected from spambots. You need JavaScript enabled to view it.

AGR Support:

This email address is being protected from spambots. You need JavaScript enabled to view it.