A Fresh Set of Eyes on Course Scheduling

In 2021, I became the associate dean of undergraduate programs at the Leeds School of Business, University of Colorado Boulder. One of the things that attracted me to the job was my curiosity about how my OR/MS perspective would be useful in the role. I knew there was at least one such challenge that needed a fresh set of eyes, the creation of the school’s course schedule.

Creation of the course schedule happens behind the scenes, but it affects the day-to-day of all students, most faculty and a good portion of the staff. Scheduling is a classic category of optimization problem. I wondered what I could do to move closer to optimality for all those people.

I have been at Leeds for 17 years, and I noticed that the course schedule had become increasingly difficult to create. Around 2014, our school launched a handful of new master’s programs, but the only spots available for new courses were at 8 a.m. or 5 p.m. We could not launch a new program with that schedule! That dilemma planted the seed of interest I had in this problem.

The Old Way

I am sure our old way of creating the course schedule will sound familiar to anyone involved in creating schedules: roll it over. That is, use the previous spring or fall schedule as the starting point.

This way works great in a stable environment: few new courses, few new faculty, few changes in the expected enrollment in courses.

The old way has big advantages. Advantage 1: It minimizes the decision-making. The default was what we did last year, and the department chairs only had to attend to the deviations. Advantage 2: It preserved the implicit constraints and preferences. The quirky faculty member who wants to teach a class once a week Tuesdays at 3:30 p.m. in a specific room? By rolling over the schedule, we don’t have to revisit those preferences every semester.

The Pain Points

The roll-it-over plan works great in a stable environment. But guess what we do not have? A stable environment! We have had growth in our undergraduate and master’s programs. We have new courses, new programs and new faculty to serve the growth.

Yes, the old way memorializes solutions to earlier problems. But we experienced pain points, including:

• The old way didn’t attend to enrollment, just the number of sections. If a class had three sections but only 75 students, we could serve as many students, and more, with just two sections. We have 21 classrooms in our building, and they range in size from 35 to 175 seats.
• The old way reinforced what was done before. Some people were thus repeatedly making a compromise, such as the night-owl student taking the 8 a.m. class or the same instructor always teaching an outsized section because they were assigned to a larger classroom.
• And the big one: the old way didn’t allow for flexibility and change.

A New Way?

About five years ago, after some difficult semesters of packing in the new master’s courses into our building, I worked on a small team of faculty and staff that tried a different approach. We tried UniTime, an impressive scheduling optimization software developed by faculty at Purdue University (https://www.unitime.org/).

The software is incredible. It was clearly built by people who understand the problem. Everything we wanted to specify was available as a feature. For example, you can enter each faculty member’s preferences for how many classes in a row before a break. You can enter which course sets are taken concurrently by students and therefore should not have conflicts. You can have half-semester courses (like we do). The developers thought of everything!

UniTime is an elegant tool, and yet, this solution didn’t stick for us. With the way we were using the system, it didn’t communicate well with our campus registration system, our Student Information System (SIS). UniTime helped us optimize for an early draft of the schedule, but we balked at keeping two sets of books on the schedule, both UniTime and SIS. We have about 500 sections of courses in a semester, and from the initial draft to the final version, more than a third of them change. That’s not a complete diagnosis of our abandonment, but it’s part of the story.

My New Way

The old way, with deviations from the past, was a local search in a complex terrain. I didn’t have any illusions that I could find a global optimal solution – with 500 sections, 150 faculty members, 20 programs of study, we won’t find “the best.” But I did know that the accumulation of incremental changes reflected in last year’s schedule was imposing a lot of constraints. I was optimistic that with the potential for Pareto improvements from a clean slate, we could make many people better off without making some people worse off.

The system has three categories of preferences and constraints: rooms, people and programs.

• Some constraints on rooms are hard constraints: no double-booking. But post-pandemic, we have new ways of relaxing constraints because we can offer a remote section if needed.
• For people-related constraints and preferences, I solicited from department chairs whether each faculty member wants their teaching schedule as compact as possible or spread out and whether there are any idiosyncratic preferences.
• For programs, the structure of the requirements and electives generates the constraints. If two required classes for a program each have a single section, those obviously cannot be at the same time. But because students sign up for classes instead of being assigned to them, overlap in multiple sections can lead to seats in a course effectively being blocked.

Because the system is nearly fully constrained on the important dimension of rooms, the whole system is highly complex – that is, highly interconnected. Any one move has ripple effects. If we notice a conflict in two required classes for one of the master’s programs, for example, we might have to move around 10 other classes to resolve it and still respect people’s schedule preferences. That tight interconnectedness is why it is so important to drop any commitment to the previous year’s schedule.

Readers of this magazine will find my new way to create the schedule to be low tech. I did not write an optimization engine. I’m using optimization concepts –constraints versus preferences, local search on a rugged terrain, complexity and contingency planning – even if I am not mathematically optimizing. 

Instead of an optimization routine, I wrote utilities in Python code to help me visualize the schedule. I created views by room, person and course groupings. The graphic view helps me check drafts of the schedule. I can easily identify a violation of a hard constraint on a person or room. But the graphic view also helps me identify solutions to problems in the schedule. If a department chair asks me to consolidate an assistant professor’s classes into two days of the week, and the current draft has them across 4 days, I can visually scan the drafts of people’s schedules to find the possible swaps. 

The graphs also help in communication, which takes on new importance when people cannot assume the schedule will be the same as the year before. They make it easy for instructors to check their schedules. They also help communicate how full the building is and why everyone cannot have their first choice of times.

Reflections

As I write this, I am working on the third semester of scheduling for the school. This is an ongoing project, and each semester I’ve done a little better than the previous one. I hope we can continue to improve, striking just the right balance of systematic analysis and high-bandwidth communication.

I appreciate the schedule as an optimization problem, even if I have not formally modeled my objective function and constraints and run an optimization routine. Relaxing a constraint by convincing a chair to move someone out of “prime time” is a human solution, not a mathematical one, and a few decisions like that drastically increase the slack in our system.

Our highly constrained space makes the problem complex, in which every change has ripple effects. The schedule isn’t just complex; it is also high stakes. If we do it well, we help our undergraduate students graduate in four years, creating value for them, their families and society.