Set Union Based Formulation for Class Scheduling and Timetabling

摘要

The Course Timetabling Problem is a widely studied optimization problem where a number of sections are scheduled in concert with the assignment of students to sections in order to maximize the desirability of the resulting schedule for all stakeholders. This problem is commonly solved with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates student preference data with set union principles. Our solution method assumes decomposition of the general schedule into time blocks, and applies a unique set theory based, integer linear programming formulation that seeks to maximize the total number of students enrolled in their desired sections across the time blocks. Once the problem has been solved, the simpler problem of disaggregating the solution is resolved. This approach can be used to find exact solutions, given sufficient computing power, or simplified to quickly find solutions within calculable bounds of optimality. Case studies with a local elementary school and a local high school are included.