Publication Date
2021
Document Type
Dissertation
Committee Members
Subhashini Ganapathy, Ph.D. (Committee Chair); Pratik Parikh, Ph.D. (Committee Co-Chair); Xinhui Zhang, Ph.D. (Committee Co-Chair); George Polak, Ph.D. (Committee Member); Thomas Wischgoll, Ph.D. (Committee Member)
Degree Name
Doctor of Philosophy (PhD)
Abstract
The course scheduling problem (CSP), more commonly referred to as the university timetabling problem, belongs to the larger family of general scheduling problems, where the aim is to assign students, faculties, exams, or lectures to a limited number of rooms over time in accordance under real-world constraints. Such problems are known to be NP-complete and have been the subject of study for the optimization society for many decades. This research extends the classical CSP to the CSP with Room Considerations (CSP-R) by incorporating two room-related considerations; cohort-to-room preference and topic-to-room preference. While the former refers to students in each cohort staying in the same room (each cohort has one main room) for most of the week to reduce students’ travel distance, the latter ensures topics will be assigned to preferred rooms. Essentially, students in each cohort are preferred to stay in their main room for the lectures that they have in common, but can go to different rooms for other lectures while satisfying other constraints and preferences. Further, we incorporate complex rules and preferences (proposed by the educational institutions we were working with), some of which have never been studied in the literature, so as to construct “good” schedules. We first propose a mixed integer optimization model for the CSP-R problem and then propose a nested simulated annealing-based algorithm to solve real-world instances. The algorithm elegantly models preferences that complement the course scheduling literature, utilizes several neighborhood operators for different aspects of the problems, and contains several enhancements such as probability selection and candidate listing to guide the search process in the simulated annealing algorithm. The algorithm uses one Outer SA to control cooling parameters and keep track of the best solution found at the end of each iteration and uses two Inner SAs to solve a decomposed portion of the original problem. This design has enabled the algorithm to efficiently and effectively solve these complicated school scheduling problems. Testing this algorithm on small and large problems instances (up to 450 students, 10 cohorts, 16 groups and 10 rooms) suggest that high quality solutions can be obtained in under 4 hours. We expect our approach to provide a viable optimization-based solution approach to this challenging to a broad range of educational institutions (high school, community colleges, and universities) globally.
Page Count
93
Department or Program
Ph.D. in Engineering
Year Degree Awarded
2021
Copyright
Copyright 2021, all rights reserved. My ETD will be available under the "Fair Use" terms of copyright law.
