Constraint programming models for real-world examination scheduling
department or school: Science, Irving K. Barber Faculty of (Okanagan)
department or school: Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
data provider: DSpace
degree campus: UBCO
creator: Hamilton, Stephanie
issued: 2022-08-26T13:53:00Z
issued: 2022
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: 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 m…
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/82540
note: Constraint Programming Models ForReal-World Examination SchedulingbyStephanie HamiltonB.Sc. Hons., The University of British Columbia, 2020A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)August 2022© Stephanie Hamilton, 2022The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Constraint Programming Models For Real-World Examina-tion Schedulingsubmitted by Stephanie Hamilton in partial fulfilment of the require-ments of the degree of Master of ScienceDr. Donovan Hare, I. K. Barber Faculty of ScienceSupervisorDr. Yong Gao, I. K. Barber Faculty of ScienceSupervisory Committee MemberDr. Shawn Wang, I. K. Barber Faculty of ScienceSupervisory Committee MemberDr. Amir Ardestani-Jaafari, Faculty of ManagementExternal ExamineriiAbstractEducational timetabling consists of various scheduling problems, one ofwhich is the examination scheduling problem. This problem requires as-signing exams to rooms and timeslots in such a way that no students arerequired to write two exams at one time. In addition, other restrictionscan be imposed so as to improve the quality of the schedule for the partici-pants (i.e., students and faculty). We introduce a new general formulationof a student hardship, which, when minimized, constrains the maximumnumber of exams students write within a specified length of time. This defi-nition of hardship is incorporated into a two-phase constraint programmingmodel which has a timeslot assignment phase and a room assignment phase.Within the timeslot assignment model, a set of cuts are added to the modelto assist in generating solutions that will lead to feasible room assignmentsby restricting the sizes of exams scheduled in a timeslot. The set of cutsis shown to be a necessary condition for a timeslot assignment solution tohave …
has type: Thesis/Dissertation
date issued: 2022-09
is shown at: 10.14288/1.0417561
language: eng
degree discipline: Mathematics
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
contributor: Hare, Donovan
type: Text
identifier URI: http://hdl.handle.net/2429/82540