Constraint programming models for real-world examination scheduling

Educational timetabling consists of various scheduling problems, one of which is the examination scheduling problem. This problem requires assigning exams to rooms and timeslots in such a way that no students are required to write two exams at one time. In addition, other restrictions can be imposed so as to improve the quality of the schedule for the participants (i.e., students and faculty). We introduce a new general formulation of a student hardship, which, when minimized, constrains the maximum number of exams students write within a specified length of time. This definition of hardship is incorporated into a two-phase constraint programming model which has a timeslot assignment phase and a room assignment phase. Within the timeslot assignment model, a set of cuts are added to the model to assist in generating solutions that will lead to feasible room assignments by restricting the sizes of exams scheduled in a timeslot. The set of cuts is shown to be a necessary condition for a timeslot assignment solution to have a corresponding room assignment such that the exams can be assigned rooms based on size. If rooms are limited to only hosting one exam in a timeslot, then this set of cuts is shown to be sufficient. The room assignment model then uses such a solution to generate a complete exam schedule. We also provide a unified approach which combines the timeslot and room assignment models. The combined model ensures that a feasible solution is generated, but at a cost of the size and performance. The models presented in this thesis were used to generate the exam schedules for the University of British Columbia’s Okanagan campus in the 2021/2022 academic year. The optimized schedules were well received and exhibited historically low numbers of student hardships. We use these datasets in the experiments of this thesis, as well as international benchmark datasets, to illustrate the effectiveness of the cuts approach versus the unified approach and to position this model in the context of the work done by other researchers in this field.Science, Irving K. Barber Faculty of (Okanagan)Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)Graduat