DRMacIver's Notebook
Notes on the design of a conference scheduler
Notes on the design of a conference scheduler
NB: This post is unfinished but it accidentally got added to the index and people keep asking about it, so I decided to publish it as is.
One of my lesser known but surprisingly impactful contributions to the world is the talk Easy solutions to hard problems, which is about mixed integer linear programming (MILP) and in particular about how to use integer linear programming to schedule conferences. Off the back of this, several conferences, including Electromagnetic field have scheduled their conferences using MILP.
I now think that was a mistake. Sorry.
There are roughly three problems with this approach:
- It’s actually really slow. Not as slow as scheduling it by hand maybe, but the EMF scheduler apparently takes most of a day to run.
- It gives totally opaque error messages when things go wrong.
- Every time I’ve attended a conference scheduled this way I’m left with a vague sense that the schedule is just not very good. It’s a bit all over the place in a way that I feel like a human scheduler would have done better.
Set against this, you really do want a computer in the loop because scheduling things by hand is such a nightmare that this is still preferable for the organisers despite the trade off.
Anyway I was thinking about this recently and realised that there’s probably a nicer way to do this.
The basic design is to follow the model from Can a machine design? for human-machine collaboration, which is that it is the job of a computer to propose solutions and for the human to correct them. So instead of designing a scheduler we are effectively designing a schedule editor. The computer proposes an initial schedule, which is expected to not be especially good, and then maintains the schedule and all its constraints as the human makes edits to it.
This solves the problem of the schedule missing the human touch, because the human can make changes until they’re happy with the schedule, and it’s the job of the computer to make those changes work.
The UI I’m imagining this is essentially a version of the schedule, in which a user can drag things around and have everything reorder itself to make it work.
The basic operations I’m imagining are:
- Lock a talk into the slot it’s currently scheduled in, so it will not be moved in future.
- Move a talk into a new slot, replacing the talk that’s currently there. This will either succeed, or the software will say that it’s forbidden (because the talk is not allowed into that slot because of e.g. constraints on when the speaker can manage), or that it has to unlock the following talks in order to make it work (with an explanation of why).
Many more operations are implementable (e.g. you could easily implement a “Move this talk somewhere else, I don’t care where as long as it fits the requirement” operation), these are just the obvious basics.
Implementing the UI for this should be relatively straightforward for anyone who is actually good at UI. I’m not, and I’m not invested enough in this problem to want to pick up the relevant skills. If you’re interested in this problem and already good at UI, feel free to drop me a line and talk about collaborating on this, because I pretty much know how all the algorithmic details should work!
Implementation
These operations are relatively easy to implement, and the basic algorithmic toolkit for this is to use Hall’s marriage theorem. Hall’s marriage theorem says that if you have some set of items (talks) you want to put into boxes (slots in the schedule), and each item can only go in some boxes (each talk can only be scheduled in certain slots), and each box can only hold one item (each slot can only have one talk), then either you can find an assignment that works, or you can find some set of items which is strictly larger than the number of boxes that are allowed to hold those items. e.g. there are three slots but four talks that all have to go in one of those three slots.
Hall’s marriage theorem is relatively easy to implement an efficient algorithm for if you have access to an implementation of the Hopcroft-Karp algorithm (and fortunately scipy has just such an implementation). You use this to find the largest possible assignment of items to boxes. If this assigns every item to a box, great you’re done. If not, you can use the unassigned items to construct a Hall violator - a set of items that cannot possibly be put into distinct boxes because there aren’t enough boxes.
As a side note, one nice thing about this algorithm is that it has the opposite efficiency characteristics to using MILP for this: The more constrained your problem gets, the faster it runs. As a result, it should (I think) be viable to use it the way I need to use it for this design, because we’ll mostly want to run it with quite constrained problems.
(You can also use MILP to solve the maximum matching problem and it may under some circumstances me more efficient to do that. This is something that would require experimentation. Certainly using a MILP gets you more flexibility than using Hall’s theorem, because it lets you handle things like “these two talks shouldn’t clash” natively)
Anyway, it’s easy enough to use Hall’s marriage theorem for the initial schedule: You just run it on your constraints, and it either gives you a schedule or tells you that you e.g. have too many talks that have to go into a particular day.
Here’s how to use it to power what should be a pretty good schedule editor:
You always have a current schedule that you are working on. In response to requests from the user, the scheduler makes (ideally small) edits to the schedule by rearranging sets of talks.
Each talk has an epoch, which is the last time it was moved. The goal is to have the schedule converge to stability, so we always prefer to move talks that are from a more recent epoch. Initially, all talks are given a random distinct epoch. A talk may also be locked (as marked by the user), in which case it will not be moved without the user asking. We will also sometimes temporarily lock talks as part of a rescheduling.
When a user moves a talk to a new slot, the following happens:
First, check if the talk is allowed in its new slot (i.e. it satisfies the constraints as to which rooms, times, etc the talk is allowed in). If not, complain to the user and don’t move it.
Second, if the talk that is already there is allowed in the slot you’re moving out of, swap the two. Similarly if the slot is empty because you don’t have a full schedule, just move the talk there.
Finally, if