A New Approach to The University Course Timetabling Problem based on Clustering Algorithms & Fuzzy Multi-Criteria Decision Making

The UCTTP problem is a hybrid optimization problem that belongs to the NP-hard class, hence determining the optimal or analytical solution of this problem is challenging. This problem, which occurs at the beginning of the university semester, involves allocating events (courses, faculty, and students) to a number of time slot and specific number of rooms. The UCTTP problem must satisfy both hard and soft constraints so that feasible time tables are obtained after complete and correct satisfaction of all hard constraints. Satisfaction of soft constraints is merely for the quality improvement of the produced feasible time tables and unlike hard constraint their satisfaction is not mandatory. Another important issue associated with this problem is the multiplicity and variety of constraints (hard and soft) that are completely case dependent. The soft constraints considered by each solution (schedule) are evaluated by the penalty function, which is obtained by a summation operator. In this operator, a weight is assigned to each soft constraint, and according to these weights, a penalty function is obtained, the output of the penalty function is used in the objective function which yields final solutions. After obtaining all the final solutions, the schedule tables that have no collisions, that is, satisfy all the strict constraints, and secondly, have a higher value in terms of the value of the objective function are selected. According to the simulation results, it can be said that in using clustering algorithms, the efficiency of fuzzy C-clustering algorithm in minimizing resource loss (surplus) and descending satisfaction of soft constraints of common lecturers of faculties is higher than funnel clustering algorithm and the K-mean. The optimal ratio of the number of applied penalties for the violations of lecturers’ soft constraints and the percentage of violations of lecturers among the fuzzy multi-criteria decision comparison algorithms, local search and genetics, as well as the combination of these algorithms are related to the combination of two comparison algorithms (i.e. fuzzy multi-criteria decision making and local search).Discussion and We observed that with regards to the percentage of satisfaction of soft constraints of common lecturers, the combination of local search algorithms with C-fuzzy clustering shows the best performance and f fuzzy multi-criteria decision comparison algorithm has the worst performance.