SMS scnews item created by Andrew Mathas at Tue 27 Aug 2013 1625
Type: Seminar
Distribution: World
Expiry: 17 Sep 2013
Calendar1: 17 Sep 2013 1500-1600
CalLoc1: AGR Seminar
CalTitle1: AGR Seminar: A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems
Auth: mathas@gdh-47.on.site.uni-stuttgart.net in SMS-auth

AGR Seminar

A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems

Dr Hamish Waterer (CARMA, University of Newcastle)

Host venue
University of Newcastle (CARMA)

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 convenor

Seminar Convenors Liangjin Yao liangjinyao@gmail.com Matthew Tam matthew.tam@uon.edu.au AGR Technical support David Allingham David.Allingham@newcastle.edu.au This notice will be available shortly on the AMSI website (www.amsi.org.au):

--

If you would like to attend this seminar in our access grid room then please check to see if the grid is already booked at this time and send an email to accessgridroom@maths.usyd.edu.au to let the CSOs know that you would like to attend.


If you are registered you may mark the scnews item as read.
School members may try to .