Tag: integer programming

Physical distancing threw a wrench in college course scheduling, but optimization can help colleges respond

While physical (or ‘social’) distancing is an important public health intervention during COVID-19, physical distancing in classrooms poses some operational challenges for colleges that want to offer in-person learning. This article provides a non-technical summary of our recent journal article describing how mathematical optimization can be used to identify and respond to these challenges.

Physical distancing causes huge reductions in classroom capacity. This leads to a big mismatch in the “supply” and “demand” for classrooms

We showed that when physical distancing policies are in place to keep students at least 6-feet apart, classroom capacity drops to 10-30% of full capacity. This is visualized below for one of the largest classrooms on Georgia Tech’s campus. Without physical distancing requirements, this classroom can hold 305 students. However, the classroom can only hold 78 students when a physical distancing policy is enforced.

While classroom capacity dramatically drops, course enrollments stay the same. As a result, there becomes a big mismatch in the “supply” and “demand” for classrooms across campus.

When classroom capacity suddenly drops due to physical distancing, how can colleges respond to deliver a meaningful amount of in-person learning?

Offering courses in different “modes” is one way to respond to the sudden capacity reduction

One way to respond to these sudden classroom reductions is to change the “Mode” in which courses are delivered. For example, if a class has an enrollment of 300 students but the biggest classroom on campus can only hold 100 students with physical distancing, that class could simply be offered in “Remote” format. We considered several different options for course modes:

  • In-Person (with physically distancing)
    • All students attend every lecture and are physically distanced in the classroom.
  • Hybrid
    • Students alternate between attending in-person and virtually.
    • Students attending in-person are physically distanced in the classroom
    • Students are able to attend in person at least once per week.
  • Remote
    • The course is offered completely remotely using video conferencing software or recorded videos.
    • No classroom is needed for this course

Let’s consider what happens if we only change the modes of courses

Consider the example below that shows what happens if we only change the mode of courses to respond to classroom reductions.

Suppose that before physical distancing was needed, the schedule had three classes offered during the same Monday/Wednesday 10-11:30am timeslot:

  • Math 101: 10 students attend class in Room A with 12 seats
  • Span 201: 8 students attend class in Room B with 10 seats
  • Engl 405: 3 students attend class in Room C with 5 seats

After physical distancing, the classroom capacities drop dramatically:

  • Room A now only has 4 seats
  • Room B now only has 3 seats
  • Room C now only has 2 seats

What can campus planners do if they only change the course modes?

By just changing the modes alone, we see that:

  • Math 101 must be delivered in Remote mode
    • There are only 4 seats in Room A. 4 students could attend on Monday, another 4 could attend on Wednesday, but this leaves 2 students who did not attend that week. Thus, Room A is not big enough to offer Math 101 in Hybrid Split mode
  • Span 201 must be delivered in Remote mode
    • We see that Span 201 cannot be offered in Hybrid Split mode because Room B is not big enough to ensure students can attend this M/W class at least once per week.
  • Engl 405 can be offered in Hybrid Split mode
    • Room C is big enough to ensure that students can attend at least once per week. However, Room C is not big enough to allow students to attend every lecture.

However, this means that of the 21 students, only the 3 students in Engl 405 attend any in-person lecture with physical distancing, and each of those 3 students only attend that course 2/3 of the time.

Therefore, we are offering about (10*0% + 8*0% + 3*66.7%)/(21*100%) ~= 9.5% of In-Person instruction that we could have offered during regular times.

Re-assigning classrooms is another way to respond to the sudden capacity reduction

Notice that whenever a course is offered in “Remote” mode, that course’s classroom becomes available. This offers an opportunity to move a smaller class into a larger room so that it can be offered in “Hybrid” or “In-person” format. Consider one strategy that takes advantage of this:

  • Offering Math 101 in Remote mode opens up Room A.
    • Math 101 is too big to be held as “Hybrid Split” in any room. Therefore we move Math 101 to Remote
  • If we then move Span 201 to Room A, we can deliver Span 201 in Hybrid Split format and open up Room B.
    • Because Room A has 4 seats, the 8 students in Span 201 can rotate attend every other lecture.
  • Engl 405 can now be offered in Room B and be delivered “In-Person.
    • Because Room B is now available with 3 seats, the 3 students in Engl 405 can attend every lecture.

After making these mode changes and room re-assignments, we have that the 10 students in Math 101 don’t attend any in-person lectures, the 8 students in Span 201 attend 50% of the lectures, and the 3 students in Engl 405 attend 100% of the lectures.

Therefore, we are able to offer (10*0% + 8*50% + 3*100%)/(21*100%) ~= 33% of the In-Person instruction that we could have offered during regular times. This 33% is a dramatic improvement over the 9.5% if we did not rearrange rooms.

Mathematical optimization can be used to change course mode and room assignments in line with the goals of campus planners

Mathematical optimization describes a quantitative method to pick the “best” solution out of a set of alternative solutions that satisfy some requirements. We typically characterize what is meant by the “best” solution as the one that maximizes our objective function, and we describe the requirements of our solution using a set of constraints.

Decision variables

While we were deciding both course modes and room assignments, we chose to model the course mode as a byproduct of the room assignment. Therefore we considered binary decision variables, Xc,r, which takes on a value of 1 if course section c was assigned to classroom r and a value of 0 otherwise. If Xc,r = 1, then the course mode for course c was determined by the ratio of the enrollment of course section c and classroom r.

If course section c was assigned no room or a room that was too small to satisfy the Hybrid Split criterion, course section c would be offered in Remote mode.

Constraints

Given the relatively short timeframe to prepare for these decisions, we worked within the existing timetable. This led to the following set of constraints:

  • Each course section could only be assigned to at most one room (Remote sections were not assigned a room)
  • Each room could hold at most one course at a time. We had to be mindful of overlapping timeslots in the timetable.

Objectives

While the amount of in-person instruction might be one of the goals, discussions with campus planners unveiled some of the objectives:

  • Maximize Contact Hours: The total number of hours that students receive in-person instruction
  • Maximize Mode Preferences Satisfied: We considered that some courses may have preferred course modes:
    • Some sections preferred In-Person (e.g., chemistry lab)
    • Some sections preferred Remote (e.g., instructor’s health accommodations)
  • Maximize Plan Stability:
    • Minimize relocation distance:  The total distance that sections are moved from the original room assignments
    • Minimize assignment changes:  The total number of room assignment changes from the original assignments

We used an optimization model to maximize these objectives while satisfying the above constraints.

Our optimization model led to insights into the impacts of physical distancing and the benefits of re-assigning rooms.

We applied our mathematical model to data from the Georgia Institute of Technology. Doing so generated some of the following insights.

Contact hours dramatically reduced once capacity dropped by more than 50%

As capacity drops from 100% of original capacity down to about 50% of original capacity, the optimization model is able to maintain a high amount of in-person instruction. However, once capacity drops below 50% of original capacity, the amount of contact hours is dramatically reduced.

Using the optimization model can still achieve 68% of the maximum contact hours compared to only 48% if no rooms are reassigned (i.e., changing course modes only).

Using optimization leads to many more satisfied In-Person mode preferences compared to the strategy where no rooms are re-assigned

We also quantified trade-offs between different objectives and considered the implications of department-controlled classrooms. These details are found in our journal article.

Summary

While physical distancing is an important public health intervention during airborne pandemics, physical distancing dramatically reduces the effective capacity of classrooms. During the COVID-19 pandemic, this presented a unique problem to campus planners who hoped to deliver a meaningful amount of in-person instruction in a way that respected physical distancing.

Optimization can be used to re-assign classes to classrooms and classes to course delivery models (e.g., in-person, hybrid, remote) in a way that satisfies administrative preferences. When classroom capacities decrease to 20-25% of full capacity due to social distancing, optimally switching the rooms that classes are delivered in can produce 15.5% more in-person instruction hours compared to a strategy where no classes switch classrooms. The optimization model was used to inform a collaborative and iterative decision-making process at a college to evaluate re-opening plans for Fall 2020 during COVID-19.

Related Articles:

Github Code

https://github.com/COVID19-Campus-Recovery/Scheduling-Optimization