CARMA ANALYSIS AND NUMBER THEORY SEMINAR

Speaker: Dr Hamish Waterer (CARMA, University of Newcastle)
Title: A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems
Time & Date: 3:00 pm EST, Tuesday 17 September 2013
Venue: Room V205, Mathematics Building, Callaghan Campus, The University of Newcastle
Also available on the Access Grid network (venue: UNewcastle).

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.

This research is a joint work with Natashia Boland and Riley Clement.

This talk will be broadcast using Access Grid Technology from The University of Newcastle. To participate in this seminar, book your University's AGR or a university/APAC etc. AGR that you are otherwise able to use. A listing of Access Grid nodes is available at: http://www.accessgrid.org/nodes.

This seminar notice is available on the AMSI Website: Events > AGR Events

Seminar Convenors

• Liangjin Yao liangjinyao@gmail.com
• Matthew Tam matthew.tam@uon.edu.au

If you (and your colleagues) wish to participate, please:

1. book your own AGR (or university/APAC etc. AGR that you otherwise are able to use), and ask your AGR technical people to contact David Allingham David.Allingham@newcastle.edu.au (the AGR technical person at Newcastle University) in advance of the seminar.
2. Advise the seminar convenor: Julianne Turner (juliane.turner@newcastle.edu.au

Contact:

Ms Maaike Wienk
Access Grid Coordinator
Australian Mathematical Sciences Institute
Building 161, C/- The University of Melbourne, Victoria 3010 Australia
P: 03 8344 1776 | F: 03 9349 4106
E: agr@amsi.org.au | W: http://www.amsi.org.au/