Dancing links for optimal timetabling
journal contribution
posted on 2018-01-01, 00:00 authored by V Nguyen, B Moran, A Novak, Vicky MakVicky Mak, Terry Caelli, B Hill, D Kirszenblat© 2018 Military Operations Research Society. All rights reserved. Algorithms for timetabling solutions typically involve sequential allocation of students to courses and resources as the algorithm unfolds. Most current solutions, to this end, commonly use some form of stochastic optimization. In this paper, we propose a novel paradigm for optimal timetabling that comprises two distinct phases. First, we enumerate all feasible course schedules, along with their costs, using a modified implementation of Knuth’s Dancing Links technique for the exact cover problem. To our knowledge, the only prior use of this implementation has been to solve games such as Sudoku and N-Queens. Once the list of all solutions that satisfy prerequisite and time-clash constraints is generated, the second phase applies a standard deterministic optimization to allocate students to these feasible schedules. This method has been applied to a real complex timetabling problem in the Royal Australian Navy helicopter aircrew training program. The results are compared, in terms of computational time, to an exhaustive best practice backtracking algorithm for generating a complete set of feasible schedules, as well as to a pure integer linear programming solution for generating schedules and allocating students to schedules.
History
Journal
Military Operations ResearchVolume
23Pagination
61-77Location
Alexandria, Va.Publisher DOI
ISSN
0275-5823eISSN
2163-2758Language
EnglishPublication classification
C Journal article, C1 Refereed article in a scholarly journalCopyright notice
2018, Military Operations Research SocietyIssue
2Publisher
MILITARY OPERATIONS RESEARCH SOCUsage metrics
Categories
Keywords
Licence
Exports
RefWorksRefWorks
BibTeXBibTeX
Ref. managerRef. manager
EndnoteEndnote
DataCiteDataCite
NLMNLM
DCDC