An efficient and exact algorithm for military timetabling and trainee assignment problems. (July 2022)

• Record Type: Journal Article
• Authors: Nguyen, Vivian; Mak-Hau, Vicky; Moran, Bill; Novak, Ana
• Is Part Of: Computers & industrial engineering. Volume 169(2022)
• Publication Date: 2022-07
• Subjects: Scheduling -- Timetabling -- Dancing Links -- Assignment; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108192
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Unique nature of military timetabling necessitates cost-effective solutions. Integration of Dancing Links with A* search for optimal timetabling. Scheduling problem solved using DLX as a min-cost covering problem. Assignment of trainees to min-cost schedules using A* search algorithm. Computational results are compared against a number of MILP formulations. Abstract: We present an efficient and exact algorithm for timetabling military training — a novel integration of Knuth's efficient Dancing Links indexing scheme with A ∗ search that allows us to simultaneously schedule and optimally assign military trainees to classes while respecting domain constraints. We show that our Simultaneous Sequencing and Assignment Solver (SSAS) is able to handle cohort sizes appropriate to the requirements of the Australian Defence Force under a complex prerequisite structure for the courses. Comparisons using real-life parameters with the best known integer programming approach (a column generation-based heuristic) has showed a significant computational benefit from using SSAS. We further tested our method on larger problem instances that might arise in larger training schools. Our SSAS was able to optimally solve such larger-scale problems or prove the problem infeasible in a reasonable computation time.