Final Exam Scheduling – A Perfect Matching Problem
The Matching Problem
Cornell University has over 2,500 final exams and final deliveries to schedule over the Fall exam period, consisting of 8 days between December 8th – December 16th. Exams can occur at 9:00am, 12:00pm, 2:00pm, 4:30pm, and 7:00pm, for a sum of 5 exam slots per day per 9 days, or 5 * 9 = 45 slots. The university faces hard constraints such as the amount of testing rooms available every day. Additionally, they face soft constraints, such as keeping courses typically taken together on different days if possible.
In keeping the exams of similar classes on separate days, the University faces a unique challenge, as not accounting for this may result in a significant number of exam conflicts that could require rescheduling. For example, let’s say INFO 1200 and INFO 1300 are both courses with exams that students are likely to take together. They may try to avoid a potential exam conflict between these two courses by assigning weights based on the probability that a student taking INFO 1200 or INFO 1300 is in both classes. If there are 500 students taking INFO 1200, 600 students taking INFO 1300, and 300 students taking both courses, we can determine the probability that a student is taking both courses by dividing the number of students taking both courses by the total number of students in both courses. To avoid counting the 300 students in both classes twice, we subtract them from the total count of 1100, giving us an overall total number of students as 1100 – 300 = 800. As a result, the probability of a randomly selected student from these courses being in both courses is 300/800 = 0.375.
The probability can be assigned as a weight to INFO 1200 and INFO 1300 that encourages the University from assigning these two courses on the same day. In comparison, consider INFO 1200 and PHYS 1101, which are unlikely to have much crossover between the two courses. If INFO 1200 has 500 students and PHYS 1101 has 400 students, and there are 50 students in both courses, then we can calculate the probability as before. This results in a probability of 50/850 = 0.059. Using this probability as a weight, we can see that PHYS 1101 would be a much better option to schedule on the same day as INFO 1200.
As we can see, there are many challenges that must be faced in this perfect matching problem in order to make sure that buildings are not assigned to two courses finals on the same day and time, and that similar courses are not scheduled next to each other. We can set up a much more simple version of this to show what this process may look like for the university.
A Simplified Example
In our problem, we will have a total of 8 exams across 4 majors, and 2 days with 2 testing times each. There are 2 testing buildings, so it is possible for 2 exams to be scheduled at the same time as long as they are in separate buildings. However, we will add a hard constraint such that exams from the same major cannot be scheduled at the same time. For example, if there is a math exam on Monday at 2:00pm in Barton Hall, there cannot be a math test occurring at the same time in Statler Hall.
We have the following testing time slots:
- Monday 2:00 pm Barton Hall
- Monday 2:00 pm Statler Hall
- Monday 4:00 pm Barton Hall
- Monday 4:00 pm Statler Hall
- Tuesday 2:00 pm Barton Hall
- Tuesday 2:00 pm Statler Hall
- Tuesday 4:00 pm Barton Hall
- Tuesday 4:00 pm Statler Hall
We have the following exams:
- INFO 1200
- INFO 1300
- CS 2110
- CS 2800
- PHYS 1101
- MATH 1010
- MATH 1920
- CHIN 1101
To create a perfect matching, we can begin by assigning INFO exams and CS exams at the same times, since there are two of each and will be affected by our constraint:
- Monday 2:00 pm Barton Hall – INFO 1200
- Monday 2:00 pm Statler Hall – CS 2110
- Monday 4:00 pm Barton Hall
- Monday 4:00 pm Statler Hall
- Tuesday 2:00 pm Barton Hall – INFO 1300
- Tuesday 2:00 pm Statler Hall – CS 2800
- Tuesday 4:00 pm Barton Hall
- Tuesday 4:00 pm Statler Hall
This leaves the following exams:
- PHYS 1101
- MATH 1010
- MATH 1920
- CHIN 1101
Which we can apply in a similar manner:
- Monday 2:00 pm Barton Hall – INFO 1200
- Monday 2:00 pm Statler Hall – CS 2110
- Monday 4:00 pm Barton Hall – MATH 1010
- Monday 4:00 pm Statler Hall – PHYS 1101
- Tuesday 2:00 pm Barton Hall – INFO 1300
- Tuesday 2:00 pm Statler Hall – CS 2800
- Tuesday 4:00 pm Barton Hall – MATH 1920
- Tuesday 4:00 pm Statler Hall – CHIN 1101
As we can see, there is indeed a perfect matching with these exams, such that two exams from the same major are never occurring at the same time.
Conclusion
Universities face this challenge on a much greater scale, with numerous exams, days, time slots, and buildings. In order to improve the likelihood of a perfect matching, universities may apply a weight scale as mentioned above such that courses with final exams and a high likelihood of crossover are largely preferred to be placed at different times, but not required to be. This makes it easier to find a perfect matching when there are so many exams to schedule and so many crossover courses, as a hard constraint like ours would make it very unlikely to find a perfect matching. Weights would decrease the likelihood of conflicts and increase the likelihood of a perfect matching, but would not necessarily result in zero conflicts. This task of assigning exams across finals week shows a prime example of how perfect matching can hide behind the logistics of our lives, presenting unique challenges to those who discover them.
Sources
Cornell University Fall Final Exam Schedule https://registrar.cornell.edu/exams/fall-final-exam-schedule