Constraint Satisfaction Timetabling Research Based on Course-Period-Template Selection and Conflict-Vector Detection

The University Course Timetabling Problem (UCTP) is a ubiquitous NP-Complete combination optimized problem. This paper addresses the problems existing in model formulation and conflict detection efficiency of the current algorithms and proposes a concise and general constraint formulation mechanism of university timetabling, which is based on course-period-template selection and conflict-vector detection. Through the aforesaid mechanism, a high-efficiency algorithm based on constraints satisfaction is suggested, using conflict-vector additive mixing and course-period-template satisfaction degree adjustment for constraint propagation. Meanwhile, min-conflicts truncation backtracking algorithm is used for eliminating conflicts. The presented algorithm supports automatic timetabling and human interactive timetabling as well. This algorithm has been tested and proved to perform with high efficiency in large scale course timetabling for universities.