Mathematical Optimization to Support Safe Back-to-School

Public and private schools are struggling to figure out how to bring face-to-face instruction to students during this pandemic. Health risks to students and teachers, parents struggling with child-care options and/or support for virtual learning, and schools’ capacities and budget limitations make this problem a severe logistical challenge. Schools need to abide by CDC social distancing regulations as well as by each individual state’s guidance to minimize exposure and risk. In North Carolina, three different plans were considered by the state government: 

• Plan A: All students back to school with minimal social distancing 
• Plan B: Schools must limit the number of students and staff to ensure 6ft of separation when stationary 
• Plan C: Remote-only learning 

In July 2020, Governor Cooper announced guidance for all schools to operate under plans B or C. On September 17th, he issued a statement allowing elementary schools to open under plan A, reiterating that Plan A might not be right for all schools and each district will be in control of their come-back.

SAS and Operations Research 

Most school districts are considering Plan B, which presents specific challenges to school administrators. One of those is to find the best possible schedule for groups of students assigned to classrooms and matching teachers to those groups such that state and federal mandates are respected. Given the number of possible combinations of schedules, this is not a trivial problem to solve. Fortunately, operations research is the best analytical tool to support decision makers with data insights and scenario recommendations for this case. 

Historically, SAS® has been deeply committed to education endeavors. Recently, SAS created a COVID-19 Incident Command System in order to support our customers and community. As passionate operations research practitioners, we jumped in to provide analytical insights to our local school districts, with the hope these insights would aid them in their decision process. Furthermore, SAS has partnered with Durham Public Schools to develop the optimization engine described in this article as part of our Data4Good efforts. 

It is important to emphasize that it is not our intent to replace the human influence on the selection of final choice or overlook the complexity of this multifaceted and controversial decision process. School administrators are focused on evaluating many more qualitative and quantitative factors than the ones mathematically considered in this application. However, we do believe that some analytical insights might aid them in this difficult process.  

Considered Scenarios 

Given the limited capacity of each school, many school administrators are evaluating different scenarios (all under plan B) as described below. 

Monthly rotation. Students would come to school for one 1-2 weeks every 2-4 weeks and do remote learning for the rest of the time. For example, 1st grade might be scheduled to come on the third and fourth week of each month. 

Weekly rotation. Students would come to school 1-2 days per week, every week. For example, 3rd grade might be scheduled to come to school on Tuesdays and Thursdays.

Daily Blocks. Students would come to school every day, but for a predefined block of time only, allowing for deep facilities cleaning in between time blocks. For example, 5th grade might be scheduled to come 8-10am.

Problem Formulation

This implementation was developed as a mathematical optimization model to recommend a schedule that maximizes the amount of face-to-face instruction while respecting the state and federal guidelines, schools’ capacities, and logistical constraints. We will describe the main optimization elements below in layman’s terms (here is the math stuff for nerds like us: https://blogs.sas.com/content/operations/2020/10/26/backtoschooloptimization/).

• Controllable decisions (or decision variables): We allowed our analytical engine to decide how many students per group to place in each classroom in each time block. The time block can be configured as a couple of hours, a day, or a week (to match the rotations). The engine also decides/suggests which teachers to assign to each group of students.
• Goal (or objective function): The engine then attempts to find the best allocation of students to maximize the face-to-face instruction time while complying with all the regulations and balancing differences in grades assignments.
• Rules (or constraints): Student allocation is only allowed if a) reduced classroom capacity (as per CDC) is not exceeded, b) all students within one grade have the same number of instruction hours, and c) a cleaning and transportation break is included for daily block programming.

We code this formulation using SAS Optimization’s OPTMODEL language, which is an intuitive way to write mathematical formulations for optimization problems. We then solve the problem calling SAS MILP solver, which uses an adjusted Branch-and-Bound Algorithm and created dashboards for deep solution analysis with SAS Visual Analytics.

Results Discussion

To begin analyzing solutions and options, we wanted to see the comparison of relevant KPIs such as average weekly instructional hours (face-to-face) per student, average room utilization and teacher workload. SAS ran the optimization engine described above for the three scenarios (monthly, weekly and daily rotation) and for different capacity settings (measured as minimum square footage per student). Below you can see the results of these optimization runs. Note: These results have been fully anonymized and do not represent any specific school or school district.

We can observe above how in most capacity settings, the weekly rotation outperforms the other scenarios, meaning we are able to deliver more in-person instructional hours while satisfying capacity constraints and utilizing better the limited room availability. If we focus on a scenario including a weekly rotation and a maximum of 12 students per room (diagram below), most school can only accommodate 12 average weekly face-to-face instructional hours while a few can do as high as 32. The number of required teachers to generate this schedule though has a wider distribution across all schools, varying from 17 to 40.

If a given school decided to operationalize this (or any) scenario, SAS is then able to recommend detailed student schedule and classroom assignments.

Further work

We have incorporated many rules, KPIs, and functionalities into this optimization engine. We are eager to partner with school organizations to share these insights and potentially aid their decision planning during these trying times. Our deep admiration goes to all school administrators working day and night to balance hard decisions in order to support one of the most relevant pillars in our society: education.

Demo

For more details, please also watch a short (5min) video of the demo for this solution.

Project credits

This project is the result of lots of work from our awesome team (in alphabetical order): Matthew Fletcher (SAS), Lee Ellen Harmer (SAS), Matthew Palmer (Durham Public Schools), Subramanian Pazhani (SAS) and Natalia Summerville (SAS).