Leiden University Student Repository

Ruijters, Anne (2025)

The High School Clustering Problem

Master thesis | Mathematics (MSc)

The High School Scheduling Problem (HSSP) is an optimization problem. Each lesson of subject groups must be assigned to a time slot in a schedule. Students and teachers attending these groups cannot be scheduled in the same timeslot twice. Our first step is clustering the subject groups which can be placed in the same timeslot. This thesis examines an existing branch and bound, and a backtracking method to solve the clustering problem. Moreover, it studies two new techniques to improve the algorithm. Both of these new approaches are based on hill climbing algorithms. Finally, these new techniques are tested on a real-life problem. This thesis finds that combining the old technique with hill climbing algorithms has a positive effect on creating an optimal cluster scheme.

Author

Ruijters, Anne

Faculty

Faculty of Science

Specialisation

Optimization

Supervisors

Kooy, N.J van der
Kanavetas, O.

ECTS Credits

36

Language

en