Solving the timetabling problem using constraint satisfaction programming

The timetabling problem is well known and much research has been done about it. It consists of dealing with a number of different factors, such as the number of lectures, subjects, classrooms, working time slots, and various other constraints. The problem consists of a set of subjects to be scheduled in timeslots, a set of rooms in which time can take place, a set of students who attend the subjects, and a set of subjects satisfied by rooms and required by timeslots. The heart of the problem is the constraints that exist as regulations within each resource and between resources. The problem exhibits the unwelcome nature of combinatorial explosion. There are various solution approaches to solve the timetabling problem. This research applies constraint satisfaction programming approach to address the problem. Constraint satisfaction programming is a paradigm in Artificial Intelligence, which has been used successfully to solve many scheduling problems. Constraint satisfaction problem (CSP) is defined by a set of variables, a domain of values for each variable, and a set of constraints between each pair of variables. A solution of a CSP is a consistent assignment of all variables to values in such a way that all the constraints are satisfied. Backtracking with arc consistency is the basic of the search algorithm for applying constraint propagation. Strategies of variable and value ordering play an important role in solution efficiency. This research focuses on developing a CSP model for a university timetabling problem. A sample case study problem is investigated and a constraint satisfaction programming approach is implemented using ILOG Scheduler and ILOG Solver. We have used various goals in ILOG to investigate the performance of the CSP approach. Our results have shown that enforcing tight constraint level and ranking the constraints by positioning the constraints at the beginning of the activities can lead to better result.