Title: Scheduling aircraft landings optimally
Speaker: Mohan Krishnamoorthy, CEO, IITB-Monash Research Academy
Time and date: 3:30 p.m. on Friday, March 18, 2011
Venue: Room 201, Mechanical Engineering Building
Abstract:
In this talk we introduce the problem of scheduling aircraft landings at a busy airport. The problem of scheduling aircraft landings on one or more runways is an interesting problem that is similar to a machine job scheduling problem with sequence-dependent processing times and with earliness and tardiness penalties. The aim is to optimally land a set of planes in the "horizon" of the air traffic controller (ATC) on one or several runways in such a way that separation criteria between all pairs of planes (not just successive landings) are satisfied. Although the talk specifically deals with "landings", it is also possible to easily integrate "take-offs" into the formulation too. The separation criteria is important since each landing (or take-off) creates a 'wake',which means a specific plane type can only land after a certain (separation time) duration in order to not be affected by the turbulence. Each plane has an allowable time window as well as a target time. There are costs associated with landing either earlier or later than this target landing time. In this talk, we first present an integer programming formulation of the problem. We review the literature on the problem before providing initial results. We then tighten the formulation by introducing additional constraints. We then develop a specialized revised simplex algorithm which evaluates the landing times very rapidly, based on some partial ordering information. We also develop a problem space search (PSS) heuristic as well as a branch-and-bound method for both single and multiple-runway problems. The effectiveness of our algorithms is tested using some standard test problems from the literature.
Speaker Bio:
Mohan Krishnamoorthy is the inaugural CEO of The IITB-Monash Research Academy in Mumbai, India. Prior to this, Professor Krishnamoorthy was Associate Dean Research, Faculty of Engineering, Monash University, Melbourne, Australia. Prior to joining Monash University, Mohan Krishnamoorthy worked as a researcher, group leader and program leader at CSIRO, Australia from 1992 till 1998. After securing his PhD from Imperial College London, in 1990, Professor Krishnamoorthy taught Operations Research at the University of Kent, Canterbury from 1991 to 1992. He also has a Masters in Management Science from Imperial College,
London and a Masters in Operations Research from Delhi University, India. His interests lie mainly in the design, development, analysis and computational testing of (exact, heuristic and novel solution) algorithms for graph, network and combinatorial optimization problems. He has over 50 international refereed journal publications and nearly 70 conference publications to his name. At CSIRO, Mohan developed an OR Group that worked on developing research-backed solutions for clients in
industries such as logistics, airlines, diary, wine, mining, travel and shipping. He has worked on problems such as the travelling salesman problem, degree constrained minimum spanning tree, hub location problem, aircraft landing problem, multi-processor task scheduling problem, rostering problems and personnel task scheduling problem.