Using column generation to solve an aircrew training timetabling problem

The 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.