Scheduling - A School's Heuristic Problem

Students learn about algorithms in Computer Science to solve complex problems in reasonable times. Some issues are too complex even for the best algorithms to perfectly solve, and those are known as heuristics. The example commonly used is the traveling salesman. While a little outdated, and I have updated the example to be the logistics of UPS delivering packages, the story goes like this. 

A traveling salesman arrives in a new town intending to get to each house in the most efficient path possible. They get a road map of all the homes they will visit and their hotel room and start mapping out paths. The math works out to show the following:

Let's nerd out for a moment. Each number of possible paths is the mathematical factorial of the number of homes on the path. So 3 homes means 3*2*1 = 6 paths. 7 homes means 7*6*5*4*3*2*1 = 5040 homes. Just 10 homes, and we are at 10 factorial or 3,682,800 pathways! How can one possibly solve for the best route with that many choices? It is too complex to be solved in a reasonable amount of time, so instead, the answer is to find a path that is practical enough.

Building a school's master schedule is a lot like this. My current high school has 1300 students choosing any variation of 5 to 8 classes for their schedule from a list of nearly 100 courses. I asked Google Sheets to find me the factorial of 1300, and it told me 170 is its maximum value for factorials. The number is too large for a spreadsheet to make sense of! The permutations of each child having 6 choices make 720 possible outcomes per child (6 factorial).

Once each child has chosen their courses, decisions must be made on what courses to run or not run and how many sections of each course we can run. We get a total number of teaching sections for the building, so we have to cut our sections into that total. Sometimes, we can run a section with fewer students; sometimes, we have to cut sections high to make it in our allotted staff. Then, we have to build the schedule. Teachers get assigned courses based on their certifications, qualifications, and, ideally, strengths and preferences.

When we start to lay out the courses during the day, we have 9 periods to fill. We want balance throughout the day of how many classes we run, and we know specific courses have to run at certain times based on staff or room availability. Everything else fits around until we have a schedule that meets the kids' needs and wants, the teacher's abilities, and honors all contractual stipulations for course load. Then, the next heuristic comes into play - we want every kid to get every course they want. 

We run what is called a conflict matrix to see, for each course, how many students who want the course will not be able to take it because it runs at the same time as another of their courses. For example, we may have one section of Percussion Studies and one section of Anatomy and Physiology. If a kid picks those two classes and we run them both during 3rd period, that kid has to decide which of those two high-interest courses they will take. So, we now have to determine if we will move one of those two classes, and if so, which one to which period. If we move Percussion to fourth period, we no longer conflict with Anatomy, but what else does that conflict with?

Each year's goal is to be 100% conflict-free, but this is nearly impossible. In fact, the smaller the school, the more likely the conflicts are to happen. Less kids means more singleton courses (classes that only run once per day), and less opportunities for students. Rather than finding the perfect 100%, we must settle for optimization and get as close to that as possible. 97% is a really high bar to achieve, which means that 3% make unwanted choices of courses to drop. 

I'm off for my second round of conflict matrix work now and hoping for almost 100%!