For this project, we were asked to develop a web-application that would enable a school to automate the proces of planning their parent-teacher conferences. We were given a set of rules we needed to try a adhere to, like “Parents shouldn’t need to wait more than half an hour in total between different conferences.” And there were, of course, practical limitations we needed to account for, such as the number of available tables, the number of time-slots each evening and the annoying fact that teachers simply can’t be at to tables at once.
The assignment stated that we should use the Google App Engine platform, but we were free to choose the language. Because we already were familiar with Java, and the language Go was still in development, we chose to use Python.
We ended up building a system that allowed parents and guardians to pick what subjects needed to be discussed per child, and to order the available days according to preference as well as indicate if they had a preference to be planned early or late in the evening.
During the first part of this project, I focussed on the ingest of the available data into GAE’s datastore and on generating plausible parent-preferences to work on. The second part of the project I worked on the algorithm that generated the actual planning. The parents were first sorted by the number of conferences they requested. The parents with the most conferences were planned first, as they would be harder and harder to place as the schedule filled up. This would take into account their preference for day and time. All parents were planned with one empty time-slot between them. After a while all requested conferences would be planned, but there would be teachers planned at two or more tables at the same time, as shown in this PDF. The algorithm would then start reordering the planned conferences of each parent, until it found the order that resulted in the lowest number of conflicts. Ultimately, this would result in a planning that adhered to all the practical restrictions and most preferences, as shown in this PDF.