Optimizing High School Course Scheduling with Multi-Objective Simulated Annealing
Abstract
An international division of a high school in Beijing faces a complex course scheduling problem involving 237 students and 53 courses with multiple constraints. Manual scheduling is time-consuming and labor-intensive, and it often leads to a relatively low average course preference fulfillment rate, with many students unable to obtain their desired course combinations. This study employs Multi-Objective Simulated Annealing (MOSA) to address this challenge. Drawing upon the complexity analysis of timetabling problems from Even, Itai, and Shamir (1976), this complex course scheduling problem is formulated as a mixed-integer programming model incorporating 6 types of hard constraints and 5 types of soft objectives. An improved simulated annealing algorithm is applied, integrating temperature-sensitive neighborhood operation strategies and an intelligent initialization method to find feasible solutions. Using real course scheduling data for the Fall 2025 semester from the high school, our optimized timetable achieves a 92.8% course preference fulfillment rate, significantly surpassing the results obtained through traditional manual scheduling.
