Introduction to the Special Issue on Analytics in Sports, Part II: Sports Scheduling Applications

This second issue of the Interfaces double issue on analytics in sports focuses on sports scheduling. Although work in the arena of sports scheduling traces back over 40 years, the number of papers investigating sports scheduling has increased significantly in recent years (Kendall et al. 2010). As this issue of Interfaces demonstrates, the increase in scientific interest is being coupled with the increased practitioner adoption of operations research (OR) technology to schedule leagues ranging from youth to professional sports.

Historically, sports leagues have crafted their schedules manually using trial-and-error methods guided by experience and intuition. In 1981, Major League Baseball (MLB) hired Henry and Holly Stephenson to create the MLB schedule. This husband-and-wife team used a combination of computer programming and manual intervention to create the MLB schedules from the 1982 to the 2004 seasons. Sports Scheduling Group won the 2005 MLB bid with a schedule constructed via a combination of OR techniques assembled by prominent operations researchers Michael Trick, George Nemhauser, and Kelly Easton.

OR also plays a prominent role in the scheduling for the other major sports leagues around the world. In the United States, OR is used to develop schedules for all major sports leagues. Optimal Planning Solutions partners with Dash Optimization to schedule the National Football League and Major League Soccer. Another partner of Dash Optimization, Bortz Media and Sports Group, schedules the National Basketball Association and the National Hockey League. The growing use of algorithmic approaches to sports scheduling is motivated by (1) advances in algorithms and computing power and (2) the ever-increasing complexity of league divisions, playoff structures, and conflicting demands from constituent teams and other stakeholders.

This special issue of Interfaces presents papers that are diverse in both the sport considered and the methodology used to solve the specific scheduling problem. The sports discussed include volleyball, Canadian football, softball, and soccer. The articles originate from five countries (Argentina, Brazil, Chile, Canada, and the United States), illustrating the international scope of sports scheduling applications. The solution methodologies employed to solve sports scheduling problems include integer programming, constraint programming, decomposition approaches, local search heuristics, and combinations thereof.

A common theme among these sports scheduling applications is the interactive nature of the process. The typical process of developing sports schedules in practice is iterative and consists of determining how to mathematically formulate the objectives and requirements expressed by the stakeholders, devising a solution approach to obtain one or more schedules, conducting several rounds of presenting the schedule(s) to stakeholders for feedback, and incorporating feedback in the form of new constraints or objectives to generate new schedules. The adopters of OR-based scheduling methods have praised their effectiveness for three primary reasons: (1) the process of generating schedules is more transparent; (2) the incorporation of requests from all stakeholders in the schedule is viewed as fairer; and (3) alternative schedules for various scenarios can be generated quickly.

Papers in Part II of This Special Issue

In “Scheduling Major League Baseball Umpires and the Traveling Umpire Problem,” Trick et al. (2012) define a new scheduling problem, which they call the umpire scheduling problem, and provide a test bed of data sets for this new problem. In the umpire scheduling problem, four-man umpire crews are assigned to a predetermined schedule of games subject to a collection of hard and soft constraints reflecting physical impossibilities, union rules, and umpire preferences. A unique aspect is that umpires have no home base because MLB wants to prevent them from umpiring the same team too many times. The objective of the corresponding integer program is to minimize total miles traveled by umpires with the consideration that each umpire crew's schedule should be balanced with respect to miles traveled, games umpired, and days off. Instance sizes render exact approaches impractical; therefore, the authors generate an initial solution with a greedy matching heuristic and use simulated annealing to obtain good solutions, which MLB has implemented since 2006.

“An Application of the Traveling Tournament Problem: The Argentine Volleyball League” represents, to our knowledge, the first published application of the traveling tournament problem to a real-world sports league. Bonomo et al. (2012) use a decomposition approach to couple the teams into traveling pairs and then schedule the corresponding pairs. The coupling of teams is motivated by practice (it halves the size of the problem) and is prevalent in other sports leagues worldwide. For the coupling stage, the authors demonstrate why a simple matching does not suffice; they then formulate an objective that facilitates the minimization of travel distance in the subsequent scheduling phase. They use a combination of integer programming techniques and tabu search to solve the two subproblems. This approach has been used to create the league schedules since the 2007–2008 season.

In “Scheduling the Brazilian Soccer Tournament: Solution Approach and Practice,” Ribeiro and Urrutia (2012) describe their experience working with the Brazilian Football Confederation to schedule its annual soccer tournaments in 2009 and 2010. Subject to numerous constraints enforcing equity among teams, the authors formulate an integer program to obtain a schedule that essentially maximizes the gate attendances and television audiences of league games. The authors apply a three-phase solution approach that consists of (1) generating all feasible patterns of home and away games, (2) assigning the home-away patterns to teams, and (3) solving a simplified integer program to schedule the games according to the home-away patterns assigned to the teams. The authors state that the ability of their approach to quickly generate alternative schedules was a factor in gaining acceptance from the league. These alternative schedules can then be evaluated with respect to secondary goals not explicitly considered in the mathematical model. Using the authors' computer-based approach will apparently continue to be essential in light of the difficulties that arise from season-to-season differences; for example, promotion and relegation between the upper and lower leagues cause geographical constraints to vary, and the World Cup interrupts the season every fourth year.

In “Operations Research Techniques for Scheduling Chile's Second Division Soccer League,” Durán et al. (2012) continue their previous work in sports scheduling by considering the unique challenges presented by Chile's Second Division soccer league. The authors provided schedules for the Asociación Nacional de Fútbol Profesional from 2007 to 2011; during this period, the Second Division requested various scheduling formats as it experimented with tournament structures to improve public sentiment and economic viability. An additional complication is that the league grew from 11 teams in 2007 to 14 teams in 2011. The authors develop a two-stage solution framework with sufficient flexibility to provide schedules subject to the numerous modifications made year to year to the league format and other requirements. In the first stage, an integer program is solved to generate the home-and-away patterns for each team. In the second stage, an integer program is solved to schedule the match-date assignments. Because Chile stretches 4,300 kilometers from north to south, geographical considerations are important. The authors geographically cluster teams and then constrain road trips based on these clusters. As a result, teams in the far north and south save an estimated 13 percent of their monthly payrolls because of the improved scheduling. In addition, the league also observed a 10 percent increase in its average match attendance after implementing the authors' schedules; at least part of this increase is believed to be attributable to the improved timing of key match-ups.

In “A Decision Support System for Scheduling the Canadian Football League,” Kostuk and Willoughby (2012) work with the eight-team Canadian Football League (CFL) to create each team's 18-game schedule via an integer programming approach. To handle the vaguely defined requirements, the authors prioritize constraints into categories of importance (ranging from fundamental scheduling “must haves” to constituent preferences that would be nice to have) and introduce them sequentially so they can pinpoint which requirements are causing conflicts. Each time a conflict arose, the authors presented the trade-offs and allowed the decision makers to determine how to adjust their requirements to achieve resolution. Additionally, the authors addressed the multiple objectives stated by league management by optimizing a criterion, adding a constraint to keep that criterion at its optimal level, and then optimizing a different criterion. They generated 22 final schedules, one of which was selected as the official 2010 CFL schedule.

In “Scheduling Softball Series in the Rocky Mountain Athletic Conference,” one of the primary goals was to obtain a schedule that is equitable to the participating student athletes. Saur et al. (2012) develop an integer program that allowed the league organizers to abandon the heuristic pairing of sister schools that was previously used to ease the manual construction of schedules. By eliminating the sister-school weekday games, the authors develop a schedule that is more palatable to the student athletes and more amenable to the academic pressures that they face. Furthermore, the authors prohibit back-to-back long road trips by categorizing potential away games as either far or close. To account for several other problem-specific constraints (such as pod play in which four teams meet at a single location, and the desire to avoid early-season matches that are more likely to be disrupted because of poor weather conditions), the authors' integer program minimizes the number of times a team plays a back-to-back home (or away) series, commonly referred to as a break in the academic literature. The authors cite their ability to generate schedules for various scenarios (they proposed 36-, 40-, and 44-game schedules) in a transparent, objective manner as key to their acceptance as official scheduler for the 2011 softball season.

“Softball Scheduling as Easy as 1-2-3 (Strikes You're Out)” illustrates the far reach of OR in scheduling a recreational youth softball league. The size of the girls' fast-pitch softball league under consideration grew from 29 teams on eight fields to 74 teams on 12 fields over the past seven years, overwhelming the manual methods of scheduling. In addition to typical scheduling requirements, this youth league also faced unique constraints such as coaches staffing multiple teams. Grabau (2012) models this scheduling problem as an integer program with 144,636 binary variables and 6,137 constraints. Lacking a hard measure of success beyond minimizing parent complaints, the author's objective is to obtain a feasible solution, which is achieved within two hours using ILOG software. This article and the others in this issue establish how sports scheduling is a fertile area for successful OR practice.