Article

How Computer Scheduling Saved Millions of Dollars

November 14, 2012 ...

Digital Transformation

Six divisions. 14 sports. 250 schools. 5,400 teams. High Schools within a state-wide High School Sports Association play some 40,000 team sport games annually.

But who should play who? And what is the optimal schedule for all these schools, teams, and games?

High school sports are fun for both students and spectators, but crisscrossing the state in search of the championship has a cost. The costs are not limited to…

Gasoline for gas-chugging school buses
Bus Driver’s time
Parent’s, Friend’s, and Fan’s driving time
Players and Coaches driving time
Coaches time spent negotiating schedules
Time of Players, Parent’s, Coaches, and Fans

The Problem

Now consider that every year the 250 state High Schools play around 40,000 games in 14 sports.

Not only are there expenses for the maintenance, gasoline, and drivers but we must consider the time spent coordinating as well. Scheduling these games has traditionally been a manual process, which coaches calling each and trying to work out when their teams might be able to meet up for a match. Inefficiencies in the scheduling process also resulted in students and staff spending unnecessary time traveling to distant away games, incurring both financial expense and educational expense as students missed class to travel to games.

Oftentimes in order to travel to a distant away game students must miss valuable classroom instruction time, sleep, or extra homework time.

The Computer Scheduling project was to automate the game scheduling process to ease schedule creation with the additional goal of minimizing the amount of time that students spend traveling to their away games.

The Solution

Here’s how we did it.

First we used the Google Maps API to find the location of each AIA member school, and then the MapQuest Directions Web Service to calculate the drive time from every school to every other school in the state.

We split the schedule generation process in to two parts–first we determined the matchups (which schools should play which other schools), and then we assigned those matchups to specific dates. This allowed the schools to add in a few games of their own choosing before determining the game dates for all games at once.

To generate the matchups we had a number of rules which needed to be followed. Each sport has a certain number of games they must play, for example, with an equal number of home games and away games. There is also a limit on how many times each school may play each other school, which may very between schools depending on geography. Additionally, certain schools may not play certain other schools, while certain schools must play other certain other schools.

Our objective function was to minimize the sum of the squared travel times required for each school to travel to each of their away games, subject to the given constraints.

Schools are grouped in to divisions based on the size of their student population; schools may play schools at most one division above or below their own, but we would prefer them to play within their own division if possible. We encouraged this by adding a distance “penalty” for scheduling a matchup with a school in a different division.

We had similar constraints when it came time to assign the games to dates. Each sport has a season start and end date, with certain days of the week games can be played on (often with a preference for games to be scheduled on one weekday over another). We must respect national, state, district, and school holidays, can’t schedule certain teams to play at home on the same dates (as they share a field), schedule the Boy’s team and Girl’s teams together where possible (to further minimize travel), and ensure that the games are evenly spread throughout the season without scheduling too many consecutive home or away games in a row.

These are classic examples of Linear programming optimization problems. To model the problem we used Pyomo (Python Optimization Modeling Objects), a modeling framework developed by Sandia National Labratories, which allowed us to use multiple different solvers to do the heavy lifting. We started with GLPK (GNU Linear Programming Kit), then moved to CBC (COIN-OR Branch and Cut, originally developed by IBM Research), and finally to Gurobi, a commercial solver. We used Amazon’s EC2 (Elastic Compute Cloud) to run as many as 10 optimizations in parallel and to lease licenses to the Gurobi solver on a per-hour basis.

After we generated the game matchups the schools were given a period of time to schedule a limited number of games on their own. These games added non-optimal additional travel time (since the close games were scheduled automatically), but we still saw large reductions in travel time. Some sports saw the overall travel time of all schools reduce by over 36%. Statewide, across 14 varsity sports total travel time was reduced by over 20%, saving over 132 days worth of travel time. With an average of 20 students per team that’s over 7 years of combined saved student time–and that’s just for the Varsity teams.

Game Matchups

The math for the matchup problem:

Consider n schools S = {S1, S2, S3, …, Sn}

Let D be the matrix of distances between schools, such that Dij is the amount of time required to travel from school i to school j.

Let P be the matrix of distance “penalties” between schools imposed when one school plays a school in a different division, such that Pij is the penalty added to the travel time of school i when it schedules a game against school j. This would be zero for schools in the same division.

Let M be the matrix of the maximum number of time each school may play each other school, such that Mij is the maximum number of games school i may schedule at school j. In this application we restricted most schools to playing each other a maximum of one or two times depending on the sport, with the exception of one remote region where the schools there could play each other in additional games to avoid excess travel. Mii=0 to prevent schools from playing against themselves.

Let F be the matrix of the minimum number of time each school must play each other school, such that Fij is the minimum number of games school i must schedule at school j. This allows us to force games between certain schools and prevents negative game counts.

We need to find G, a matrix of games such that Gij is the the number of times school i (the away team) will play a game at school j (the home team).

Given this we can state our problem as:

minimize ∑i,j ∈ S DijGij + Pij

Such that all of the following conditions hold true:

Gij ∈ ℤ
Gij ≤ Mij
Gij ≥ Fij

Gj = h where h is the number of home games each school must have
Gi = a where a is the number of away games each school must have
– 1 ≤ Gij – Gji ≥ 1 ∀i, j ∈ S
(schools must have a roughly equal number of home and away games against each other)