Constraint Satisfiability Algorithms for Interactive Student Scheduling

Abstract

A constraint satisfiability problem consists of a set of variables, their associated domains (i.e., the set of values the variable can take) and a set of constraints on these variables. A solution to the CSP is an instantiation (or labeling) of all the variables which does not violate any of the constraints. Since constraint satisfiability problems are, in general, NP-complete, it is of interest to compare the effectiveness and efficiency of heuristic algorithms as applied, in particular, to our application. Our research effort attempts to determine which algorithms perform best in solving the student scheduling problem (SSP) and under what conditions. We also investigate the probabilistic techniques of Nude! for finding a near optimal instantiation order for search algorithms, and develop our own modifications which can yield a significant improvement in efficiency for the SSP. Finally, we assign priorities to the constraints and investigate optimization algorithms for finding schedules which rank high with respect to the priorities. Experimental results have been collected and are reported here. Our system was developed for and used at Bar-IIan University during the registration period, being available for students to construct their timetables.