File(s) under permanent embargo
Using column generation to solve an aircrew training timetabling problem
conference contribution
posted on 2017-01-01, 00:00 authored by David Kirszenblat, Brendan Hill, Vicky MakVicky Mak, Bill Moran, Vivian Nguyen, Ana NovakThe Training Authority Aviation (TA-Avn) is an organisation within the Royal Australian Navy
(RAN) responsible for managing aviation-specific training for all RAN personnel, who are to be employed in
an aviation-related job category. In a temporal sense, the bulk of aircrew training consists of a sequence of
major, structured courses and a number of mandatory short courses for which the prerequisite requirements are
less strict. Both short and long courses are run repeatedly throughout a year with a fixed number of repetitions
and are subject to high and extremely variable course pass rates. It is important to have an ability to quickly
and easily regenerate a new timetable at short notice, potentially on a weekly basis depending on whether
students have to repeat failed short courses.
In previous work we explored a number of approaches including a stochastic approach to optimisation. In
this paper, we adopt a different methodology, using more conventional integer linear programming techniques,
specifically, column generation. The problem of designing feasible schedules is formulated as a network flow
problem that encompasses covering and prerequisite constraints. Then column generation is applied in order
to improve the tractability of this large scale integer linear program. Here, the original problem is decomposed
into a master and subproblem. The master problem is initialised with a set of dummy schedules to which
we allocate the aircrew student population, whilst respecting class capacity limitations. The master problem
then requests solutions from the subproblem that offer some promise of minimising the overall time spent in
training. This process iterates between the master and subproblems until the solution of the master problem
cannot be further improved and we have thus reached an optimal allocation of students to feasible schedules.
Experimental results are compared with those of an ILP approach that assigns feasible schedules to labelled
students.
(RAN) responsible for managing aviation-specific training for all RAN personnel, who are to be employed in
an aviation-related job category. In a temporal sense, the bulk of aircrew training consists of a sequence of
major, structured courses and a number of mandatory short courses for which the prerequisite requirements are
less strict. Both short and long courses are run repeatedly throughout a year with a fixed number of repetitions
and are subject to high and extremely variable course pass rates. It is important to have an ability to quickly
and easily regenerate a new timetable at short notice, potentially on a weekly basis depending on whether
students have to repeat failed short courses.
In previous work we explored a number of approaches including a stochastic approach to optimisation. In
this paper, we adopt a different methodology, using more conventional integer linear programming techniques,
specifically, column generation. The problem of designing feasible schedules is formulated as a network flow
problem that encompasses covering and prerequisite constraints. Then column generation is applied in order
to improve the tractability of this large scale integer linear program. Here, the original problem is decomposed
into a master and subproblem. The master problem is initialised with a set of dummy schedules to which
we allocate the aircrew student population, whilst respecting class capacity limitations. The master problem
then requests solutions from the subproblem that offer some promise of minimising the overall time spent in
training. This process iterates between the master and subproblems until the solution of the master problem
cannot be further improved and we have thus reached an optimal allocation of students to feasible schedules.
Experimental results are compared with those of an ILP approach that assigns feasible schedules to labelled
students.
