|
Article Excerpt
Professional tennis organizations, such as the United States Tennis Association (USTA), the Association of Tennis Professionals (ATP), the International Tennis Federation (ITF), and the Women's Tennis Association (WTA), host tennis tournaments throughout the world. At these tournaments, chief umpires assign and schedule line umpires for every match. For most tournaments, they perform this task manually, which can be cumbersome for large tournaments. For large tournaments, such as the US Open, they can use software developed to facilitate scheduling. Unfortunately, the software package currently available often creates suboptimal or infeasible schedules that must be manually adjusted. We developed a program based on optimization that automates the scheduling procedure. Our program consistently provides high-quality schedules in as little as 25 percent of the time taken with other methods.
Key words: recreation and sports; programming: integer.
History: This paper was refereed.
**********
Any respectable tennis fan should be able to tell you who won the 2003 US Open. However, do you think the fan remembers the chair umpire of the women's or men's championship match? Probably not, and tournament officials prefer this anonymity. In any sport, the umpire or referee is responsible for calling a fair contest in agreement with the rules of the sporting event. The umpires' crucial role is to accurately and consistently oversee the match without drawing unnecessary attention to themselves or the governing process. Behind the scenes, an intricate system of hierarchies, experience, and qualifications dictates the proper assignment of umpires to tennis matches.
Chief umpires must follow guidelines that complicate the scheduling process in terms of time and effort needed to assign umpires properly. For example, during large tennis tournaments, up to 18 matches may be played simultaneously. On each court, up to 10 umpires may be calling one match--one chair umpire and nine line umpires. Furthermore, different criteria must be used in selecting chair umpires (who are in charge of each match) and line umpires for each match. The selection of chair umpires is based primarily on nationality, player histories, and experience. The selection of line umpires is based on skill level and experience at a particular position. In addition, line umpires must be allocated to courts to ensure that a minimum number of male and female umpires are on each court at all times. Furthermore, because line umpires cannot stay on court for an entire day while matches are played, the chief umpires must schedule rotation shifts to allow them lunch and rest breaks. Finally, tournaments run anywhere from one to three weeks, with the matches throughout that period increasing in visibility. Because of this visibility, requirements can become stricter as the tournament goes on, making scheduling even more difficult.
Typically, chief umpires assign line umpires to positions during a tournament. To facilitate scheduling, the United States Tennis Association (USTA) developed a software package to automate umpire assignments. The scheduling algorithm used in this program is a greedy heuristic that sequentially assigns the best available umpires to the highest priority lines. First, it evaluates umpires based on their historical performance and assigns them a skill-rating number ranging from 1 to 7 (1 represents the highest skill level). Next, it assigns each court a priority index and the required lines on each court a minimum and maximum skill-rating number. The sequential-assignment algorithm starts at the court with the highest priority and the first position on that court. If that position has a minimum rating of 1, the algorithm searches for the first available umpire with a rating of 1 and assigns him or her to that position. If no 1s are available, the algorithm searches for umpires with a rating of 2. After assigning an umpire to that position, the algorithm moves to the next position and repeats the process. After scheduling the entire court, it moves to the court with the next highest priority index and repeats the search procedure using that court's requirements. It continues until it has fully assigned all courts.
This system has multiple pitfalls. First, the program was designed for use only at the US Open. Most tournaments use different scheduling criteria. Next, the algorithm's greedy nature prevents any form of looking ahead. Similar in nature to a seating heuristic, the system schedules blindly without considering the global solution and is concerned only with the local assignment of an umpire to a location. In other words, it makes individual assignments with no regard for their effect on the schedule as a whole, often assigning too many highly skilled umpires to early courts. No more umpires may be available to meet the skill requirements for later courts, leaving no feasible solution. Furthermore, even if it finds a feasible schedule, the system does not account for gender requirements. The chief umpire must review every schedule for gender feasibility and adjust schedules manually when they do not meet gender requirements.
In 2002, Jeff Smith, an industrial and systems engineering professor at Auburn University, was at the US Open during a rain delay. During this tournament, extensive rain delays completely changed the scheduling requirements, increasing the number of courts...
|
