Download slides here (gzipped PostScript file).
Why is it that the Pirates played six games against the Braves between April 7th and 16th, 1998? Who makes sure that the Texas Rangers don't have a road trip which takes them to Boston and then to Seattle? Why is it that Duke and N.C. Chapel Hill, the two top basketball teams in the ACC, just happened to meet in a dramatic last game of the 1998 season? These are just a few of the questions which Michael Trick considers as he applies optimization techniques to scheduling ACC basketball and Major League Baseball.
The algorithm Trick uses for sports scheduling has three main phases:
Choosing a pattern set involves choosing several strings of home games, away games and byes which will be used in scheduling the teams. No specific team is assigned to any pattern at this point. Next, the timetable dictates which patterns will play each other on which dates. As you might expect, this must be a matching between teams at home on a given date, and teams that are away on that same date. Lastly, choosing the schedule involves assigning specific teams to the pattern.
The algorithm is outlined on the first slide, and a small example with four teams appears on the second.
Trick's first experience with sports scheduling came from dealing with the ACC basketball schedule. Basketball is an important and profitable sport for the ACC which contains perennial powerhouses Duke and N.C. Chapel Hill as well as several other quality teams. The difference between a good schedule and a poor one can mean a large fluctuation in profits for one or more of the athletic departments involved.
So, what differentiates a good schedule from a poor one? There are many requirements, which are listed in slides three and four, but one of the most basic requirements is that every team should play every other team, with one game at each team's home court. Second, no team should be forced to play a long series of away games, or have a disproportionate number of away games on weekends. Several other constraints are due to the high quality of the Duke and Chapel Hill teams. No team should have to play those two opponants in succession, and it is preferable to have them play each other in the second half of the season.
Trick went on to explain how a successful 1997 schedule (his first year working on the problem with George Nemhauser of Georgia Tech.) prompted the ACC to add more constraints the following year. The TV networks started to ask for certain games, those likely to attract many viewers, to be played on certain dates. Certain teams in the league requested that they finish the season with games against traditional rivals (such as Duke vs. UNC), and there were other suggestions as to what made for a better schedule.
Apparently Trick and Nemhauser were up to the challenge, and the fifth slide shows the ACC's basketball schedule from the 1998 season. As you can see, it avoids many of the undesirable situations such as long strings of home and away games or games against the same opponent close together.
You might expect that the methods used in scheduling ACC basketball would be easily transferable to Major League Baseball, however there are a few difficulties. The ACC contains 9 teams, each of which plays sixteen games in a season, while MLB has two leagues of fifteen teams, playing about 160 games in a season. Even before the addition of inter-league play, the jump from nine teams to fifteen leads to a huge explosion in the number of possible schedules. The addition of inter-league games is just one more difficulty for anyone trying to schedule a MLB season. To address this problem, we need more than the three phase approach used in scheduling ACC basketball games.
The current schedulers of Major League Baseball use a strategy based on semi-repeaters, where team A visits team B one week and team B visits team A the following week. This provides a conveniant building block for putting together a schedule, but it is not very popular with fans who don't want to see all the games between two particular teams lumped together so closely. Since it is in the best interest of the MLB administration to keep fans happy and eager to attend games, they would prefer a method of scheduling that cut down on this phenomenon, as long as it didn't lead to worse performance in other areas.
What other areas does MLB look at in a schedule? You can find some of these constraints in slides six and seven, but just like the ACC, MLB wishes to avoid excessively long strings of home or away games. Teams would like to be playing their traditional rivals during the summer weekends so as to draw in a large number of fans, and the TV networks also have their preferences as to when certain games should occur. Since the MLB season goes on for many months, teams would like to cut down on the wear and tear due to travel so the proposed road trip to Boston and Seattle, in the introduction, is to be avoided unless absolutely necessary.
To account for the increased number of teams and large number of restrictions, Trick uses an integer program which has a variable for each possible road trip. In this manner, road trips such as Boston-Seattle can be discouraged while trips to neighboring teams, such as Boston-New York-Baltimore are encouraged. This strategy results in an integer program with approximately 2 million variables and 12,000 constraints, but by combining this with the technique of choosing home and away patterns, the number of variables can be reduced to about 10,000.
Trick explained that even a well-designed integer program doesn't guarentee a lock on the best schedule. In designing the 1998 schedule, he submitted a schedule based on two fifteen team leagues. Failing to anticipate the Brewers' shift to the National League meant that his schedule was not accepted for that season. Despite this temporary setback, Trick describes himself and his collaborator, Doug Bureman, as "the second best schedulers in baseball, and still improving".
Slide eight shows the first half of the Bureman/Trick schedule for 1997. You can see that there are some semi-repeaters, such as Montreal playing Los Angeles in two of the first three series, and lengthy road trips, such as Chicogo's trip in early May: San Francisco-Montreal-Philadelphia. However, no schedule is going to satisfy everybody all of the time and Bureman and Trick's certainly stacks up competitively against the current offerings.
Many of Trick's comments about the next step in sports scheduling can be found on the ninth slide, but a few of the interesting questions are: