Programme - Speakers

Plenary speaker: Dr. Jeffrey H. Kingston

Biography

Dr. Jeffrey H. Kingston is a former Associate Professor and current Honorary Associate of the School of Information Technologies at the University of Sydney, Australia. His research interests lie in the general areas of Algorithms and Complexity, with long term projects under way in high school timetabling and document formatting. Dr. Kingston is a founding member of the PATAT conference series steering committee, and one of the select few who have attended every PATAT conference since the series began in 1995.

Talk Title - Timetable construction: the algorithms and complexity perspective

Ideas developed under the general headings of Algorithms and Complexity have been applied to timetable construction since the early days. This talk is a series of practical examples which will, it is hoped, stimulate researchers to use these ideas in their own timetabling research work.

The examples will include relaxations, phased approaches, very large-scale neighbourhood searches, bipartite matchings, ejection chains, and NP-completeness analyses.

Plenary speaker: Dr. George White

Biography

George White received a bachelor's degree in Engineering Physics, B.A.Sc, at the University of Toronto, a master's degree at the University of Alberta in Calgary and the Ph.D. at the University of Calgary. He has been fortunate enough to have worked and studied at University College, Dublin, l'institut national de recherche en informatique et en automatique, INRIA, in Rocquencourt, France and the University of Colorado in Boulder, CO, U.S.A. At present he is Adjunct Professor at the University of Ottawa in Canada.

Talk Title - Estimating the limiting value of optimality for very large NP problems

The search for better timetables, schedules, resource allocation, etc., in large scale data sets often requires approximation methods. These methods can often yield solutions are "very good", although it is generally impossible to say just how good these solutions are. Not only do we not know what the best solutions are, we also don't know how far they are away from the optimum solution - they may be very close but they may also be quite far away. This paper describes a method of using historical data to estimate the limiting optimality of the solution to a problem if the problem arises from a situation taken from the real world. Knowledge of the limiting optimality can provide guidance in estimating just how far a trial solution lies from the "best solution" and just how good the solution may be.

Plenary speaker: Prof. Graham Kendall

Biography

Graham Kendall is the Dunford Professor of Computer Science and a member of the Automated Scheduling, Optimisation and Planning Research Group, School of Computer Science, University of Nottingham, Nottingham, U.K. He is the Deputy Head of the group, which has 9 members of academic staff, about 15 Research Associates/Fellows and about 40 PhD students.

His research interests include scheduling, optimisation, evolutionary and adaptive learning, heuristics and meta/hyper-heuristics. He has a particular interest in solving real world problems.

Talk Title - Scheduling Football (Soccer) Fixtures: Progress Made to Date and Future Challenges

This talk will present two different sports scheduling problems, the progress we have made to date and some of the challenges that remain. The first problem considers the scheduling of fixtures over a holiday period. Various constraints have to be respected with the overall objective being to minimise the distance travelled by the supporters. This project has also opened up new research opportunities that were not apparent at the start of this work, such as the use of geocoding for data collection. The second problem was introduced to us by a local company that produces commercial software to generate sports league schedules. This problem is totally different to the first problem with respect to the objective function and the hard constraints that have to be respected, even though we are still trying to generate feasible football (soccer) schedules.

Plenary speaker: Prof. David Ryan

Biography

David Ryan holds the Chair in Operations Research in the Department of Engineering Science and is Deputy Dean of the Faculty of Engineering at the University of Auckland. He has a strong interest in the development of optimisation based methods to solve real world resource scheduling problems. In particular he has made significant contributions to the formulation and solution of crew scheduling problems arising in the rail and airline industries.

Talk Title - An Optimisation-based Approach to the Train Driver Recovery Problem

In this talk I will describe the PhD research work of Natalia Rezanova who completed her PhD at the Danish Technical University in 2009. Natalia first developed an optimization-based solution method for solving the Train Driver Recovery Problem (TDRP) and then an initial prototype for a decision support system for the train driver dispatchers. When unforeseen disruption occurs in daily railway operations, some of the original driver duties become infeasible and this requires real-time rescheduling to generate new feasible recovery duties. The solution framework attempts to minimize the amount of disruption to the original duties. This is achieved by solving restricted TDRP instances with a rolling time horizon. We formulate the TDRP as a set partitioning model, where variables represent train driver recovery duties and show why the proposed model and solution method is particularly suitable for solving in real-time. Recovery duties are generated as resource constrained shortest paths in duty networks, and the set partitioning problem is solved with a linear programming based branch-and-price algorithm. Dynamic column generation and recovery neighbourhood expansion at each node of the branch-and-price tree together with a constraint branching strategy contribute to the solution method. Real-life operational data was provided by DSB S-tog A/S (the suburban rail operator in Copenhagen) in order to test the implemented solution method. Based on the computational experiments, we conclude that the proposed approach is indeed applicable for implementation in a decision support system for train driver dispatchers in practice.