An automated tool for optimal classroom seating assignment with social distancing constraints

ABSTRACT

Social distancing has become a necessity due to COVID-19, requiring schools to reduce classroom capacities to host in-person students. In doing so, schools seek to maximize the number of seats that can be used within a classroom, while ensuring that no pair of usable seats violates social distancing guidelines. We model this problem as a graph-theoretic maximum independent set problem and develop a user-friendly tool that solves real instances of the problem. We then use that tool to create optimal classroom seating plans for a major university. Our core model considers the case of a classroom with fixed seats. This problem can be expressed as a graph, identifying seats as nodes and inserting edges between seats that are closer than some prescribed threshold. A maximum independent set in this graph corresponds to an optimal seating plan. Our seat assignment tool allows any user to solve this problem by uploading an architect's drawing of a classroom. Then, computer vision aids the user by locating seats, and the tool finds and prints an optimal plan. Our tool also allows users to easily incorporate additional requirements, such as designated teacher spaces and the inclusion of movable chairs. Our tool helped automate the classroom planning process at Cornell University where its ease of use allowed it to be run on hundreds of classrooms. Compared to initial reduced-capacity classroom estimates determined by the Office of the University Architect, it helped identify over 400 additional seats that could be used. © 2021 IISE Annual Conference and Expo 2021. All rights reserved.