A Constraint Logic Programming Based Approach to the International Timetabling Competition
Patrick Pleass, Mark G. Wallace, Mauro Bampo · 2006
This paper outlines the modeling, implementation and refinement of a solution to the International Timetabling Competition using Constrai nt Logic Programming methods. This is primarily carried out within the ECLiPSe const raint programming framework using lib(ic), the hybrid integer/real interval ari thmetic constraint solver library. The International Timetabling Competition, organized by the Metaheuristic Net-work and sponsored by PATAT (Practice and Theory of Automated Timetabling) was held in 2003. The competition presented a reduced un iversity course timetabling problem and associated problem datasets designed by Ben Paechter. The aim of the competition problem was to deliver feasible timetab les, in a set execution time that meets all hard constraints and minimized occurrence s of soft constraints. Although this competition has already been held and winners announced [1,2,3,4], the outcome has provided researchers with a number of independently verified solu-tions and performance measures using a variety of d ifferent approaches. Further to this the Center for Emergent Computing at Napier Uni versity have posted new Harder Instances for the University Course Timetab ling Problem [5] that can further challenge heuristic development in this field. The aim of this research is to provide a solution to the timetabling problem using as much as possible the ECLiPSe framework and minimal use of external custom-built metaheuristics and solvers. The performance o f this approach is then compared to the competition results and differences analyzed and discussed. This approach in-troduces a number of design challenges in providing acceptable performance within ECLiPSe as opposed to a custom built heuristic. These challenges are outlined and discussed. The approach followed consists of the following stag es: Modeling the problem data Data from the input file format specified by the co mpetition is loaded into the constraint engine as a set of atomic facts such as: timeslot(timeslot_id) student(student_id,[classes]),