In retrospect, I think that finding mathematics/computer science was really no coincidence. I think they appealed to me because of my overall need to solve problems. Now, part of what makes moving into administration neat is that I get to see the problems of the institution as they truly exist and not as I discover them or am told about them. One problem that was becoming clear was that we had a suboptimal manner of putting classes to classrooms. I wanted to find a routine for optimized classroom scheduling at LaGrange College.
Optimized Classroom Scheduling at LaGrange College
As a very simple version of this problem, there are really only two criteria:
- I do not want to double-book a professor in two different classes during the same scheduling window.
- Classes with a maximum enrollment of m cannot be assigned to a room with number of seats n where n<m.
I wrote a couple of pieces of code to accomplish this task. The first is inspired by the genetic algorithm and was an integer-based metaheuristic search. The second was a piece of code that assigned the random integers as indices for both the teacher and classroom scheduling processes.
For example, for the Callway J. Cason Science Building (SCI), there are 9 rooms in which courses can be taught and 10 periods (six on MWF and four on TR). Therefore we have 90 scheduling opportunities. But, when labs and any other specialty courses are removed, there are 43 courses which must be taught. (Department chairs can schedule labs in the specialty spaces.) The algorithm first checks to see if classes (based upon max enrollment) can fit in their classrooms; if not, a penalty occurs. Then the algorithm checks to see if an instructor has been double booked in a particular period; if so, then a penalty occurs. The task is to eliminate all possible penalties. For the science building, this can be done, in under a second.
For the entire campus, I’ve not yet had success but believe that the answer lies in how the “population” (ala. the genetic algorithm) is spawned. So far, in under 30 minutes, the algorithm can regularly reduce to 14 errors all associated with overfilling the room. So far, the algorithm produces no over-bookings for the instructor.
I was recently invited to Berry College by Ron Taylor (a good mathematician and all-around nice guy) and was given the opportunity to talk about this. Here’s my talk (less some really cool runs of code that I demo’d on the spot).
If you’ve never been to that campus, you should–it’s truly amazing. Here’s the flier that Ron prepared for me.
I’ve got a piece of code that is working for smaller cases but that needs some fine-tuning for larger cases. I got to share this research with peers and students at Berry College. Also, there’s no doubt that the deadline of a talk helped me to rush the research.
Finally, I’d like to share the following things to all problem solvers:
- There is always low-hanging fruit to be obtained. You may not recognize it at first but it’s there.
- It is okay to fail. Failure is just a springboard for the next success.
- As problem solvers, we just report the news–we don’t make it.
If you have any questions or comments, please feel free to leave them below. If you enjoyed what you read, please subscribe to the blog or any of my social media accounts. Finally, feel free to share this link through social media.