A simultaneous sequencing and allocation problem for military pilot training: integer programming approaches

Abstract In this paper, we study a unique, rich combinatorial optimization problem that arose from helicopter aircrew training for the Royal Australian Navy. Each pilot trainee (student) has to complete a syllabus. A syllabus is a sequence of courses (commonly known as subjects), and each course is associated with a pass rate. A pre-requisite structure exists amongst some courses. Each course has a number of repeated sessions, each spanning the same amount of time, but occupying a different set of (possibly overlapping) time slots. A feasible schedule is a sequence of course sessions such that each course in the syllabus is covered by exactly one session, and that all pre-requisite requirements are observed. The optimization problem is to simultaneously assemble course sessions to form feasible schedules, allocate students to these schedules with an objective to minimize the total time-span in completing the syllabus, while ensuring that the class size limits for each course session is not exceeded. The problem is different from the school or university time tabling family of problems due to the assembly component required. This paper is to serve as a pilot study: we derive a number of mixed-integer linear programming models and investigate their performance using test instances provided for us by our industry partner. For each of these models, we propose a number of solution strategies as topics for future research papers. From our numerical testing, it appears that the Column Generation-based approach is computationally the most promising method.