Scheduling Single Round Robin Tournaments with Fixed Venues

Scheduling Single Round Robin Tournaments with Fixed Venues,Rafael A. Melo,Sebastian Urrutia,Celso C. Ribeiro

Scheduling Single Round Robin Tournaments with Fixed Venues   (Citations: 2)
BibTex | RIS | RefWorks Download
Sports scheduling is a very attractive application area due to the importance of the problems in practice and to their interesting mathematical structure. We introduce a new problem with practical applications, consisting in scheduling a compact single round-robin tournament with fixed venue assignments for each game. Two integer programming formulations are proposed and compared. Comparative numerical results are presented. 1 Problem statement The field of sports scheduling has been attracting the attention of an increasing number of re- searchers in multidisciplinary areas such as operations research, scheduling theory, constraint pro- gramming, graph theory, combinatorial optimization, and applied mathematics. Particular im- portance is given to round robin scheduling problems in which each team is associated with a particular venue, due to their relevance in practice and to their interesting mathematical structure. The diculty of the problems in the field leads to the use of a number of approaches, includ- ing integer programming (10, 15), constraint programming (6), hybrid methods (3), and heuristic techniques (1, 14). We refer to (4, 11) for literature surveys. In round robin tournaments, every team face each other a fixed number of times in a given number of rounds. Every team face each other exactly once in a single round robin (SRR) and twice in a double round robin (DRR). If the number of rounds is minimum and every team plays exactly one game in every round, then the tournament is said to be compact. Each team has its own venue at its home city. Each game is played at the venue of one of the two teams in confrontation. The team that plays at its own venue is called the home team and is said to play a home game, while the other is called the away team and is said to play an away game. A schedule must not only determine in which round each game will be played, but also at which venue. The problem of scheduling round robin tournaments is often divided into two subproblems. The construction of the timetable consists in determining the round in which each game will be played. The home-away pattern (HAP) set determines in which condition (home or away) each team plays in each round. The timetable and the home-away pattern set determine the tournament schedule. Some round robin scheduling problems consider both the construction of the timetable and of the home-away pattern set. As an example, the traveling tournament problem (TTP) (5) calls for a schedule minimizing the total distance traveled by the teams. However, either the timetable or the HAP set of the schedule may be fixed and known before- hand in some situations. In the first case, the timetable is given and the problem consists in finding
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Successful algorithms for sports scheduling include tabu search [12]-[14], simulated annealing [15]-[17], graph coloring and branch and bound [18], constrained programming [19]-[22], integer linear programming [23]- [25] and hybrid integer/constrained programming [8],[26]...

    Jari Kyngäset al. Scheduling the finnish major ice hockey league

Sort by: