Chapter 17, Problem 1.2ASC

Scheduling Major League Baseball Umpires

It used to be that major league baseball (MLB) umpires were scheduled on an Excel spreadsheet. The task took several weeks and had to be revised often. Now they use a scheduling system developed by researchers at the University of Miami, Carnegie Mellon, and Michigan State University. A variant of the classic Traveling Salesman problem, umpires, as shown in the photo, are assigned to crews that must visit all ballparks at least once during the year. Of course, there are many more constraints.

Perspectives/Jeff Smith/Shutterstock

MLB teams play 2430 games in a two- to four-game series during a six-month season. Each game requires a crew of four umpires. There are currently 70 umpires on MLB staff, and 22 AAA umpires who may be called up as needed to fill in for games. A typical umpire will handle 142 games a year. Unlike football referees, umpires are full-time employees of MLB. Umpires are normally assigned to crews, but the content of these crews can change during the year. Constraints to umpire crew scheduling include mandated vacations, overexposure to individual teams, prohibition to refereeing at home, and minimizing coast-to-coast travel. Examples of MLB rules used to enforce these constraints are:

• Crews should travel to all 30 ballparks at least once during a season.
• Crews should not umpire the same team’s series of games more than once every 18 days.
• Crews must not travel from the West Coast to the East Coast without an intermediate day off.
• Crews must not umpire consecutive series more than 1700 miles apart without an intermediate day off.
• Crews must not travel more than 300 miles preceding a series whose first game is a day game.
• Crews should not work more than 21 days without a day off.
• Crews should see each team at home and on the road at least once.
• Crews should have balanced schedules (i.e., travel approximately the same number of miles, umpire the same number of games, and have the same number of days off).

Real-life scheduling problems, like umpire scheduling, can be quite complex. The general solution approach is similar to the assignment method of linear programming described in this chapter. There is an objective function of minimizing distance traveled subject to a number of constraints, as listed earlier. The variables are (0,1) meaning an umpire is either assigned to a game slot (i.e., 1), or not (i.e., 0), and the game slots are numerous (2430 × 4 = 9720). While this can be solved as an integer linear programming (LP) problem, the length of time to do so and the inability to relax constraints make it difficult to find a feasible solution.

Academics use heuristics, or rules of thumb, to solve these types of problems. Heuristics do not necessarily satisfy all constraints and do not guarantee an optimal solution, but they can give satisficing or “good enough” solutions. The heuristics are evaluated against performance metrics, previous solutions, and “optimal” solutions (from mathematical programming such as LP). The heuristics are usually improved on with use until users accept them. Many are then coded into software and sold as scheduling systems for particular applications.

Approximate the number of possible solutions for this problem. With computer systems able to process huge amounts of data quickly, would it be possible to enumerate all possible schedules and choose the best? Investigate.