By Syl Kacapyr
As the coronavirus pandemic surged in the spring of 2020, Cornell University leaders faced a critical question as they contemplated an in-person fall semester: Would it even be possible?
It was a question that universities across the nation were grappling with as they tried to imagine what a safe, residential semester would require. Not only would Cornell need to establish a virus-testing protocol, but adhering to health guidelines meant students would have to sit at least 6 feet apart, drastically reducing the university’s classroom space. Exactly how much classroom space did Cornell have to work with, and could it accommodate any kind of course schedule?
It was the type of mathematical challenge fit for a logistics consulting firm, or perhaps a challenge better suited for a supercomputer given the looming deadline – just a matter of weeks – to determine the fate of the semester.
For its solution, Cornell turned to its own School of Operations Research and Information Engineering, where faculty and students live and breathe mathematical modeling, optimization, and analysis for data-driven decision making.
With the clock ticking, Cornell needed an exceptional and dependable plan to keep its community socially distanced and safe.
To identify options for the fall semester, Cornell assembled the Committee on Teaching Reactivation Options, comprised of faculty, students and staff, including David Shmoys, the Laibe/Acheson Professor of Business Management and Leadership Studies in the School of Operations Research and Information Engineering.
In thinking about how feasible it would be to host in-person classes, the committee knew it was only practical if every student in lectures would be sitting 6 feet apart, recalled Shmoys.
“If a student was in class and it was between their last negative COVID-19 test and a positive test, we didn't want to – from a health regulation standpoint – quarantine the entire class,” said Shmoys.
Determining how much classroom space the university had was a capacity planning exercise similar to what Shmoys would assign in one of his undergraduate courses. Except with so little known about coronavirus and the coming semester, it was far from a typical exercise.
“How many instructors would want to hold classes in person and what capacity would we have in order to do that? Which classrooms have fixed seating and which have movable seating? There were all kinds of issues coming into play and we were trying to understand what the limits really looked like,” said Shmoys, who added that another challenge was interpreting information about how the virus spreads, such as what 6 feet of social distancing really meant.
“Is it from the center of the seat to the center of the other seat? Is it from the edge of the seat to the edge of the seat? That one little change of phrase could make a 30% difference in terms of the number of seats that you can fit into an existing space,” said Shmoys. As it turns out, the Tompkins County Health Department clarified that proper social distancing measures from the center of one seat to the edge of the next.
Using an Excel spreadsheet, Shmoys began constructing a simple model with the help of undergraduate student Brian Liu ‘20, who assisted with data analyses and preparatory estimates. They determined that classrooms would hold roughly eight-to-10-times fewer students than before the pandemic, giving the university the answer it needed: Yes, an in-person semester did appear feasible, but only if course times and locations could be assigned appropriately.
By mid-June, the university had made its decision – the fall 2020 semester would be in-person, offering a variety of modalities, including online and hybrid approaches. Now, Cornell just needed a schedule.
As soon as Cornell confirmed its plan for a residential fall semester, Lisa Nishii, vice provost for undergraduate education, turned to Shmoys. “I hope you weren’t planning on doing anything this summer,” she remembers quipping before asking Shmoys to co-lead the university’s Course Roster and Scheduling Team.
“It felt like we were building a parallel university in six weeks,” said Nishii. “All our normal institutionalized practices, the systems, the workflows, all of that totally shattered and we had to start from scratch.”
Co-leading the scheduling team was the university registrar, Rhonda Kitch, who said being faced with building the entire university’s fall 2020 schedule was a daunting task.
“We knew developing the processes and tools needed to successfully build the roster and ultimately hold enrollment in the fall, or pre-enrollment for the spring, required optimization skillsets beyond the capacities within the Office of the University Registrar,” said Kitch.
Shmoys saw the challenge as a class of scheduling problems similar to what he and many faculty members had worked on before. So he assembled an all-star team of his colleagues to contribute to the design and implementation of the schedule, including Oktay Gunluk, professor of practice and former manager of the Mathematical Optimization and Algorithms Group at IBM Research; David Williamson, a professor specializing in optimization problems and scheduling; and Brenda Dietrich, the Geoffrion Family Professor of Practice and former vice president of IBM Research with decades of experience in applied optimization projects.
With the semester slated to begin September 4 and class registration needing to occur before that, the group had just a matter of weeks to build, from the ground up, a schedule that would keep students safe.
Armed with blueprints for 484 classrooms and spaces large enough to be scheduled with more than 10 students, the group divided the problem into two challenges: determine the times of the classes, and assign the classes to classrooms.
“We went multiple directions simultaneously, so that there were different groups that worked on different approaches,” said Shmoys. “There were many different ways to decompose the problem into smaller problems and we explored some of the most promising ones in parallel because we knew we had a hard deadline and the goal was to be sure that we had something that we could hand to the registrar.”
In a normal practitioner setting, the scheduling challenge would be solved with a draft solution that would then go back to the client for review. Perhaps three or more iterations of the solution would be presented before all of the kinks would be worked out. But the Cornell group didn’t have that luxury.
“We didn't have time to get things wrong,” said Shmoys. “We had one shot and that was it. We had to get it right.”
While the Office of the University Architect and one of the faculty groups began reviewing classroom blueprints, trying to determine each room’s new capacity, another group began working on building a schedule.
But how can a course be scheduled without knowing if a properly sized room will be available to host it? As a preliminary solution, the group categorized classrooms using a formula to determine how many students they thought each could hold – 16-20, 21-25 and 26-30, for example – hoping they had accurate enough estimates until better data was developed, according to Gunluk.
“The main approach we took was to model this using mixed integer programming,” said Gunluk, referring to a type of model in which some decision variables are not discrete. “And even in that case, you can build different kinds of integer programming models to deal with the same problem.”
Gunluk asked one of his Ph.D. students, Connor Lawless, if he had a couple extra hours to donate to the effort.
“I thought, ‘sure, maybe I'll read in some data, create a quick graph and get to learn more about scheduling problems,’” recalled Lawless. “Well, the model we were working on ended up being the winning one and from that point onward the project spiraled into being a 24/7 process for a month.”
There were many considerations—different options for class lengths, different combinations of days they could be scheduled on, and there was also the challenge of not crowding hallways by scheduling too many classes at the same time in the same building. To do this, the group began to model activity on campus as a function of time of day.
But the main challenge, as Lawless and others saw it, was that Cornell’s scheduling had been perfected in an iterative manner over the course of years, with many underlying assumptions baked into the schedule. For instance, almost every junior who takes ORIE 3300 is also taking ORIE 3500. The registrar learned not to schedule those classes together, but over time the reasoning for that separation was lost as the schedule was carried over from one semester to the next.
“There are all these idiosyncratic elements that go into making a schedule that most people, departments included, forget about until they look at a final schedule” said Lawless. “We would assign something like a math class in Schwartz Auditorium and call it a day. But then you’d get waves of complaints arguing that everything from the location to the color or length of a blackboard was all wrong.”
The Course Roster and Scheduling Team began hosting weekly town halls with academic departments to flesh out some of the class overlaps to avoid, but department representatives didn’t have a strong sense of elective courses in neighboring departments.
“There was this other piece to the project of just how do we use the data that we have to infer the kind of things that historical judgment has allowed us to settle into over time,” said Shmoys, who assigned undergraduate student Anders Wikum ‘21 to find a way to extract as much of that information as possible from previous semesters.
Wikum’s job was to “let the data speak” by finding annual trends in which students concurrently enrolled in two courses. Later, he also built a model for assigning office-hour rooms to departments.
As one group of engineers began homing in on a rough schedule, another was trying to develop a more precise list of how many students each classroom could actually hold. It was a tedious process going through each room, one by one, examining the dimensions of the walls and calculating how many desks could fit while meeting health guidelines.
“We had been working with the registrar and Professor Shmoys through the first hundred or so spaces to ensure we were maximizing the number of seats while strictly adhering to health department spacing guidelines, required exit pathways, adequate ventilation and sight-lines for AV,” said Margaret Carney, university architect. “We needed a way to automate the process.”
Shmoys thought it was an interesting problem he could introduce to his ENGRI 1101 course, which he was updating to include more real-world, computational experiences for students. So he assigned undergraduate student Qihan ‘Jody’ Zhu ’22 to build a class exercise around room capacity, together with operations research doctoral student Sander Aarts.
“It was basically just a maximum independent set at the core of the problem,” said Zhu, “If we could also figure out how to automatically recognize seats when given a floor plan, then one thing that we thought we could do better than the architect’s office was to speed up the process.”
So, Zhu coded a software program that could import classroom blueprints, read the floor plans, and use computer vision to help identify where seats could be placed.
“Jody came back after one week,” recalled Henry Robbins '22, “She found an automated way to identify every seat in a room. This allowed rooms to pack an additional two to three seats compared to the architect’s model. It was pretty incredible to see the tool be produced so quickly.”
.jpg)
Shmoys, impressed with what his students had created, approached Carney with the software and asked if she was interested in using it.
“When Professor Shmoys offered the assistance of his students and the software program they had invented, I thought he was joking,” said Carney. “Luckily, it was no joke, but it was magic, and a great collaboration between architects and engineers,” said Carney.
The university offered summer jobs to two prospective engineering students, Kyle Greenberg and Trey Hensel, working with staff at the architect’s office, going through each classroom and tweaking the software’s image recognition to work with different kinds of drawings. In the end, the software helped identify over 400 additional seats that could be used by the university.
“We just kept working on it and eventually got the results the university needed,” said Zhu. “Looking back, I’m really proud of the role I played, but at the time, it was all happening so quickly.”
With proposed course times and capacity determined, and with just days to spare, the groups could now merge their efforts into an initial schedule.
“We were lucky enough to pick a model for the problem that can be solved to optimality in a small amount of time, which means that we could optimally assign all classes to classrooms and times,” said Gunluk. “But when you're dealing with a large project like this, this is just the first stop.”
As knowledge of the coronavirus evolved, so did the schedule. So when health officials recommended placing 20 minutes between classes instead of 15, the group had to adjust their model. Then, it was recommended that every classroom be sanitized once in the middle of the day, in addition to a deep cleaning overnight. Once again, the model was fine tuned.
“This modeling is partially an art, it's not just math,” said Gunluk. “It is important to pick a model that can gracefully handle new information and constraints that come up later.”
With an initial schedule complete, hundreds of requests for changes began pouring in from the departments, effectively turning the group into a customer service unit. And with each request, accommodating the customer could mean the difference between students getting an in-person lecture and having to go virtual.
“I processed scheduling changes using Connor’s model,” said Robbins. “We managed them using a Google sheet and by the end, we processed over 250 schedule change requests.”
The group tirelessly worked on each request, figuring out how to rearrange classes and hardcoding it into their model.
“Someone would communicate changes back to the departments. Often, they were of the form ‘we rescheduled one of the two courses that previously conflicted” recalled Robbins. “Their response was usually ‘that doesn't work either.’ We processed these changes non-stop, every day for about a week.”
There was also the matter of scheduling evening prelim exams. With the capacity of classrooms limiting how many prelims could be given at one time, the unpopular, but necessary, decision of adding Sunday prelims was made.
It was all coming together, but in the last days of developing Cornell’s fall 2020 schedule, everything still felt uncertain to the team.
“David would come to our daily meetings and introduce another big hurdle,” said Robbins, “and we’d question, ‘Are we going to have a schedule? Are we not? Will we even have a semester? It was an interesting environment to work in, unlike anything I have worked in before.”
Nishii was also feeling the pressure. “I called the provost not that long before the start of the fall semester and I said, ‘I don't know if we can do it. I don't know if we have enough hours times humans to pull this off.’”
Requests were serviced, hurdles were jumped, and the model was updated again and again. It was all leading to a final effort to merge scheduling data with the registrar’s.
Because the decisions of departments, faculty, and teaching graduate students frequently changed as data was being collected through the summer, a systematic data integrity check was required to weed out any undetected errors in the schedule. It was a four-day effort for Shmoys and his team, but finally, the weary group of faculty, students and staff had a completed schedule.
“The work of the past months has been intense,” said Kitch, who commended all who collaborated across campus to build the fall schedule. “These individuals have spent hours meeting and collaborating days, nights and weekends to meet goals and milestones. I’ve joked I spent more time in meetings with David than with my own family.”
But even with the schedule finalized, the job wasn’t complete. As the semester got underway, issues developed in which the group would have to swing back into action.
“Because many of rooms that were being used were brand new to a class, you can have instances where an A/V configuration is almost unusable for a professor’s teaching style, or you have a discussion section that's all about conversational Spanish in a lecture hall that turns out to be way too large,” said Lawless. “So we handled those as they came in.”
As the semester progressed, it became clear that the schedule was working. And after students went home for winter break, the university declared fall 2020 a success. In a message emailed to the Cornell community, Vice Provost Nishii said there was no evidence of instances in which COVID-19 had spread in a classroom setting. And despite a drastic reduction in classroom space, about 60% of students received some form of in-person instruction.
“We were very concerned that first-year students would get the least amount of face-to-face time because they tend to be in larger intro classes, which are more likely to be online because we don't have the space,” said Nishii, “but as it turns out, they ended up faring quite well.”
Without Shmoys and the other faculty members from the School of Operations Research and Information Engineering, there may not have been an in-person fall semester, according to Nishii. She added that Shmoys’ students are especially deserving of recognition.
“They’re brilliant,” said Nishii. “I hope they understand just how much they're contributing to the functioning of the university. We couldn't have opened without a course roster.”
“These are incredible students,” added Shmoys. “To see them come together, commit and work incredibly hard, I mean, there were all-nighters that were done along the way to get things where they needed to be. They did it unflinchingly and they delivered.”
And yes, the group has already begun scheduling the spring semester and expect it to be even better than the fall because of lessons learned, mostly for the diversity of courses and majors that have specific needs.
“There are always new twists, but the group is up for the challenge,” said Shmoys. “It’s just so very satisfying to be the beneficiary of this talent, this deep-seeded love of Cornell, and this real sense of heart.”
Ph.D. student Lainie Eisner was drawn to Cornell specifically for its relationship with Hospital for Special Surgery in New York City. Read more about Investigating degenerative tendon disease and repair
Alex Cruz is a doctoral student in biomedical engineering from New Jersey. He studies tissue engineering approaches to calcific aortic valve disease under the guidance of Jonathan Butcher at Cornell. Read more about Using tissue engineering approaches to better understand cardiovascular disease
When Daniele Visioni was six months away from finishing his physics Ph.D. studies at Italy’s University of L’Aquila he took a long bus ride to Zurich, Switzerland to give a talk at an academic... Read more about Assessing the feasibility (and advisability) of using Sunlight Reflection Methods
