Article ID: | iaor20014035 |
Country: | Netherlands |
Volume: | 92 |
Start Page Number: | 349 |
End Page Number: | 361 |
Publication Date: | Nov 1999 |
Journal: | Annals of Operations Research |
Authors: | Tadei Roberto, Croce Federico Della, Asioli P.S. |
Keywords: | timetabling, scheduling |
A practical problem encountered by the management of a tennis club is the organization of a tennis tournament for the club members. The tournament participants are split into different series: in each series, every player plays once a week with a different opponent in a round robin tournament. All matches are subject to a time limit corresponding to one hour. All the series share the same pool of courts, whose weekly availability is predefined. In addition, the players have their own availability constraints. Given the courts and players availability, the objective is to schedule the tournament with no violation of the constraints or, more realistically, in order to maximize the number of feasible matches. This problem can be formulated as a maximum matching problem, with the additional constraint that each player must play just once a week. It can also be modeled as a maximum clique problem. A two-step heuristic procedure is proposed to solve the problem: first, the round robin tournaments of each series are generated, then the matches of each tournament are assigned to the available courts for every week by means of a local search procedure. The procedure has been successfully implemented and is currently used by the tennis club.