Round-robin Tournament - Scheduling Algorithm

Scheduling Algorithm

If is the number of competitors, a pure round robin tournament requires games. If is even, then in each of rounds, games can be run in parallel, provided there exist sufficient resources (e.g. courts for a tennis tournament). If is odd, there will be rounds, each with games, and one competitor having no game in that round.

The standard algorithm for round-robins is to assign each competitor a number, and pair them off in the first round …

Round 1. (1 plays 14, 2 plays 13, ... ) 1 2 3 4 5 6 7 14 13 12 11 10 9 8

then fix one competitor (number one in this example) and rotate the others clockwise one position

Round 2. (1 plays 13, 14 plays 12, ... ) 1 14 2 3 4 5 6 13 12 11 10 9 8 7 Round 3. (1 plays 12, 13 plays 11, ... ) 1 13 14 2 3 4 5 12 11 10 9 8 7 6

until you end up almost back at the initial position

Round 13. (1 plays 2, 3 plays 14, ... ) 1 3 4 5 6 7 8 2 14 13 12 11 10 9

If there are an odd number of competitors, a dummy competitor can be added, whose scheduled opponent in a given round does not play and has a bye. The schedule can therefore be computed as though the dummy were an ordinary player, either fixed or rotating. Instead of rotating one position, any number relatively prime to will generate a complete schedule. The upper and lower rows can indicate home/away in sports, white/black in chess, etc.; to ensure fairness, this must alternate between rounds since competitor 1 is always on the first row. If, say, competitors 3 and 8 were unable to fulfil their fixture in the third round, it would need to be rescheduled outside the other rounds, since both competitors would already be facing other opponents in those rounds. More complex scheduling constraints may require more complex algorithms. This schedule is applied in chess and draughts tournaments of rapid games, where players physically move round a table.

Alternatively Berger tables, named after their inventor Johann Berger, are widely used in the planning of tournaments.

Round 1. 1-14 2-13 3-12 4-11 5-10 6-9 7-8 Round 2. 14-8 9-7 10-6 11-5 12-4 13-3 1-2 Round 3. 2-14 3-1 4-13 5-12 6-11 7-10 8-9 … Round 13. 7-14 8-6 9-5 10-4 11-3 12-2 13-1

This constitutes a schedule where player 14 has a fixed position, and all other players are rotated clockwise positions. This schedule alternates colours and is easily generated manually. To construct the next round, the last player, number 8 in the first round, moves to the head of the table, followed by player 9 against player 7, player 10 against 6, until player 1 against player 2.

This schedule can also be represented as a (n-1, n-1) table, expressing a round in which players meets each other. For example player 7 plays against player 11 in round 4. If a player meets itself, then this shows a bye or a game against player n. All games in a round constitutes a diagonal in the table.

Diagonal Scheme
× 02 03 04 05 06 07 08 09 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13
1 1 2 3 4 5 6 7 8 9 10 11 12 13
2 1 2 3 4 5 6 7 8 9 10 11 12 13
3 1 2 3 4 5 6 7 8 9 10 11 12 13
4 1 2 3 4 5 6 7 8 9 10 11 12 13
5 1 2 3 4 5 6 7 8 9 10 11 12 13
6 1 2 3 4 5 6 7 8 9 10 11 12 13
7 1 2 3 4 5 6 7 8 9 10 11 12 13
8 1 2 3 4 5 6 7 8 9 10 11 12 13
9 1 2 3 4 5 6 7 8 9 10 11 12 13
10 1 2 3 4 5 6 7 8 9 10 11 12 13
11 1 2 3 4 5 6 7 8 9 10 11 12 13
12 1 2 3 4 5 6 7 8 9 10 11 12 13
13 1 2 3 4 5 6 7 8 9 10 11 12 13
Round Robin Schedule
× 1 2 3 4 5 6 7 8 9 10 11 12 13
1 1 2 3 4 5 6 7 8 9 10 11 12 13
2 2 3 4 5 6 7 8 9 10 11 12 13 1
3 3 4 5 6 7 8 9 10 11 12 13 1 2
4 4 5 6 7 8 9 10 11 12 13 1 2 3
5 5 6 7 8 9 10 11 12 13 1 2 3 4
6 6 7 8 9 10 11 12 13 1 2 3 4 5
7 7 8 9 10 11 12 13 1 2 3 4 5 6
8 8 9 10 11 12 13 1 2 3 4 5 6 7
9 9 10 11 12 13 1 2 3 4 5 6 7 8
10 10 11 12 13 1 2 3 4 5 6 7 8 9
11 11 12 13 1 2 3 4 5 6 7 8 9 10
12 12 13 1 2 3 4 5 6 7 8 9 10 11
13 13 1 2 3 4 5 6 7 8 9 10 11 12

The above schedule can also be represented by a graph, as shown below:

Read more about this topic:  Round-robin Tournament

Other articles related to "scheduling algorithm, algorithm, scheduling algorithms, scheduling":

Resource Starvation
... Starvation is usually caused by an overly simplistic scheduling algorithm ... The scheduling algorithm, which is part of the kernel, is supposed to allocate resources equitably that is, the algorithm should allocate resources ... Modern scheduling algorithms normally contain code to guarantee that all processes will receive a minimum amount of each important resource (most often CPU time ...
WiMAX - Technical Information - MEDIA ACCESS CONTROL, MAC (data Link) Layer
... The WiMAX MAC uses a scheduling algorithm for which the subscriber station needs to compete only once for initial entry into the network ... to being stable under overload and over-subscription, the scheduling algorithm can also be more bandwidth efficient ... The scheduling algorithm also allows the base station to control Quality of Service (QoS) parameters by balancing the time-slot assignments among the application needs of the subscriber station ...
Scheduling Algorithms - Scheduling Disciplines - How To Choose A Scheduling Algorithm
... When designing an operating system, a programmer must consider which scheduling algorithm will perform best for the use the system is going to see ... There is no universal “best” scheduling algorithm, and many operating systems use extended or combinations of the scheduling algorithms above ... NT/XP/Vista uses a multilevel feedback queue, a combination of fixed priority preemptive scheduling, round-robin, and first in first out ...
Rate-monotonic Scheduling - Introduction
... and time-sharing schedulers fail to meet the scheduling needs otherwise ... Rate monotonic scheduling looks at a run modeling of all threads in the system and determines how much time is needed to meet the guarantees for the set ... meaning that if any static priority scheduling algorithm can meet all the deadlines, then the rate monotonic algorithm can too ...