We are a bunch of nerds who once decided to volunteer to host a soccer tournament for our township's soccer club where our kids play.
About 200 teams played about 400 games over one weekend.
It was a lot of fun, and quite a time commitment. Surprisingly the most challenging aspect of it was to create a schedule that worked for all participating teams.
Teams had all kinds of constraints. Most notably
- Minimum time between games: Teams don't like to play back to back games (obviously).
- Maximum time between games: Many teams traveled an hour or more to attend the tournament. They don't want to sit around waiting for their next game for too long either
- Coaching conflicts: A single person sometimes coaches multiple teams. The coach needs to have the opportunity to be with their team for each game
- Late start or early end: Some teams had other commitments (like kids taking SATs) due to which they couldn't start before 12pm or others had to leave by 4pm
We were using a popular scheduling software (GotSport / GotSoccer) and even though it was great at highlighting conflicts, we still had to keep moving games around manually on a grid to find a time slot that worked.
If you have ever done that before, you know what I am talking about. Your head starts to spin after looking at that screen for a few hours. You do that for a few days, you don't want to try it again.
Our immediate thought was that there has to be a better way.
A tough problem to solve
After the event, we reached out to our great team of engineers to find a solution. Early on in the discussions, it became clear to us that it is mathematically a very hard problem to solve.
For example take a tournament with just 100 games in a day, that need to be played across 10 fields.
If you use brute force to enumerate all the theoretically possible options, and pick the best one, the number of options you would have to evaluate would be roughly 1090
(1 followed by 90 zeros).
We created a simple program that did exactly that. Using a low level programming language (C++) on a fast operating system (Linux) we were able to evaluate about 20,000 to 30,000 options per second.
To give you a sense of how complex the problem is, imagine this.
Google is rumored to have a couple of million processors worth of computing power. Let's say the number is 10 million. Let's also say that Google's processors are really powerful and can evaluate 1 million schedule configurations per second.
If all of Google's computing power was trying to solve our problem with brute force, it would take roughly 1077
seconds. That is a gazillion times more than the age of the universe - which is roughly 1020
Needless to say, brute force is not the way to go.
A better idea
We have to be honest. It took us a while to figure it out. But we did. We came up with a series of clever heuristics - thumb rules that allowed us to focus on those few million roads that are most likely to lead us to the promised land.
My friends, that is how Avery was born.
Avery still needs up to an hour to run, but in a majority of cases it does find a good schedule1
Even when it doesn't, it creates a partial schedule that's much better than what we have seen anywhere else.
Once you try Avery, we have no doubt you would agree.
1) Even though Avery uses a lot of soccer language (like fields), it can handle tournaments for any sport. Say basketball, lacrosse, baseball, hockey, football, ping pong, badminton or anything else you can think of