Final Exam Scheduling and Classroom Assignment Using Simulated Annealing

[摘要] Many universities schedule their exams manually. This requires a lot of time and results to many unsatisfied constraints such as conflicts and unfairness in schedules. This paper presents an algorithm to automate the exam scheduling at the University of the Philippines Los Ban ̃os. It does not only aim to minimize the number of conflicts and unfair- ness in schedules, but it is also designed for the users of the system to easily add constraints. In this work, a modified weighted-graph coloring problem was formulated and the Simulated Annealing (SA) heuristic was adapted to solve it. Different parameters for SA was observed based on the value of the objective function. After the schedule has been pro- duced, classrooms were assigned to the courses. In classroom assignment, parameters such as distance between rooms in a department, distance between departments, and number of rooms and capacities can easily be adjusted. Results showed that SA produces schedules with smaller number of conflicts and unfairness compared to the manually-prepared schedule. Results also showed that the value of the objective function was decreased by 24% after applying the parameters used in this work. In classroom assignment, both the soft and hard constraints considered in this work were satisfied.

[学科分类] 计算机科学（综合）

[关键词] Algorithms;Experimentation;Performance;Verification