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 as a linear program with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates binary student variables into integer variables denoting the number of students enrolled in a course. 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 show that the new formulation is significantly faster and can be made to be reasonably accurate.
","abstract_html":"<p>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 as a linear program with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates binary student variables into integer variables denoting the number of students enrolled in a course. 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 show that the new formulation is significantly faster and can be made to be reasonably accurate.</p>","abstract_has_math":false,"creators":["Bukenberger, Jesse Paul"],"institution":null,"degree_name":"MS in Industrial Engineering","degree_level":null,"degree_discipline":"Industrial and Manufacturing Engineering","degree_department":null,"school":null,"contributors":["Tali Freed"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-06-01T07:00:00Z","date_published":"2014-06-01T07:00:00Z","updated_at":"2026-07-24T01:31:28Z","subjects":["Operations Research","Integer Linear Programming","Scheduling","Couse Timetabling","Blocking","Industrial Engineering","Operational Research"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["10.15368/theses.2014.95"],"render_values":[{"text":"10.15368/theses.2014.95","href":"https://doi.org/10.15368/theses.2014.95","code":true}]}]},"links":{"outbound_url":"https://digitalcommons.calpoly.edu/theses/1250","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Tali Freed"]},{"key":"dc:creator","label":"Author","values":["Bukenberger, Jesse Paul"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2014-07-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial and Manufacturing Engineering"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Industrial Engineering"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Operations Research","Integer Linear Programming","Scheduling","Couse Timetabling","Blocking","Industrial Engineering","Operational Research"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.calpoly.edu/theses/1250","10.15368/theses.2014.95"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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 as a linear program with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates binary student variables into integer variables denoting the number of students enrolled in a course. 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 show that the new formulation is significantly faster and can be made to be reasonably accurate.
"]},{"key":"dc:title","label":"Title","values":["A Set Union Based Formulation for Course Scheduling and Timetabling"]}]}],"canonical_facts":{"dc:contributor":["Tali Freed"],"dc:creator":["Bukenberger, Jesse Paul"],"dc:date.available":["2014-07-01T07:00:00Z"],"dc:description.abstract":["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 as a linear program with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates binary student variables into integer variables denoting the number of students enrolled in a course. 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 show that the new formulation is significantly faster and can be made to be reasonably accurate.
"],"dc:identifier":["https://digitalcommons.calpoly.edu/theses/1250","10.15368/theses.2014.95"],"dc:subject":["Operations Research","Integer Linear Programming","Scheduling","Couse Timetabling","Blocking","Industrial Engineering","Operational Research"],"dc:title":["A Set Union Based Formulation for Course Scheduling and Timetabling"],"thesis:degree_discipline":["Industrial and Manufacturing Engineering"],"thesis:degree_name":["MS in Industrial Engineering"]},"updated_at":"2026-07-24T01:31:28Z"}