Final Exam Scheduling and Bipartite Graph Matching
In March of 2005, two operations research professors at Cornell (Bob Bland and David Shmoys) developed a new method for determining final exam schedules that reduced the number of students scheduled for three exams in a 24-hour period by a whopping 85% from what the average had been in the past three spring semesters. Their solution also reduced the number of students with three exams in one day by about 75% and those with back-to-back exams by ~65%.
In the past, students had complained about their stress and unhappiness when faced with such crammed exam schedules. Some students would have three exams in one day or back-to-back finals with only 30 minutes in between them. This is mentally exhausting and draining, so many students had to ask their professors to schedule a make-up exam for them. This made logistics and negotiations difficult for professors (especially of large classes) who were trying to arrange make-up times that would meet the needs of all their students. As such, the university reached out to Bland and Shmoys asking if they could use their expertise in operations research to mitigate this problem.
Interestingly enough, the problem of matching courses with exam times can be modeled as a bipartite graph. In class, we learned that in a bipartite graph, the nodes are divided into two categories and each edge connects a node in one category to a note in the other category. In this case, the two categories are courses and exam times. Here, bipartite graphs are useful for modeling the matching between each course to an exam time (multiple courses can be assigned to a specific exam time) under a set of constraints. The constraints here are minimizing the total number of “crammed” schedules for students.
In their solution, there were only 51 students who pre-registered for their courses (the new method uses pre-enrollment data) that had three exams in a 24-hour period, down from 341 students. Though these numbers were from the Spring ’05 semester, the university is still using this method for final exam scheduling.
On a related note, I think it would be interesting to see if this same technique is used for matching final exams with rooms. The ideal solution would be a perfect matching where each final exam is matched with a unique room number. For this problem, the constraint would be making sure that the assigned room number has enough capacity to hold all the students taking the exam.
Shout out to the ORIE department for making our lives more stress-free!
http://www.news.cornell.edu/chronicle/05/3.3.05/exam_sked.html
-av272