Incorporating dynamic constraint matching into vertex-based graph coloring approach for university course timetabling problem

摘要

University Course Timetabling Problem (UCTP) belongs to Constraint Satisfaction Problems (CSPs), which are the set of objects whose state must satisfy a number of constraints. The constraints, in this case, are related to characteristics and regulations of a particular university. Certainly, these will vary from one university to the other. A number of approaches have provided feasible and optimal solutions for UCTP. However, their solutions are still based certain university's constraints. Our approach has given another way to occupy various constraints for various universities. Dynamic Constraint Matching (DCM) consists of constraints logical formulation, collision matrix generation, and validation using the collision matrix. Our experiment, using 93 subjects offered in Faculty of Information Technology Tarumanagara University, has shown that all constraints, taken from the characteristics and regulations of the Faculty, can be formulated successfully. When DCM were integrated with Vertex Graph Coloring (VGC) as one of the guaranteed optimal solutions for UCTP, the approach results a course schedule that does not contain any hard or soft constraints violations. The processing time can be said fast, which is less than 1 minutes.