Dancing links for optimal timetabling

Abstract

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