Round Robin Tournament Scheduling

Algorithm for Court Balanced Round Robin

Ian Wakeling · 9 · 28748

Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
on: January 27, 2006, 04:59:56 AM
The question of for court balance in round robins has cropped up a lot.  Below is an algorithm that can produce court balance some of the time, also some recommended further reading for those interested.

Ian Wakeling.   Be sure to check out Ian's Excel file or Richard's page

In many different sports a round robin can be used to schedule n players (or teams) who meet weekly, fortnightly, or monthly at a central location where enough courts are available for playing each round.  Some examples would be tennis, squash, bocce, pool, curling etc.  In many, if not all, of these sports it is possible that a court has some unique characteristic specific to how it was constructed, or where it is situated.  One player or team who plays often on one court may gain an unfair advantage by learning to use its characteristics, perhaps its uneveness, to improve their chances of winning.  To avoid this problem, it is sensible to try to balance the number of times a player plays on each court in the course of the competition.

If n is odd follow Richard's cyclic algorithm for constructing the round robin for n+1 players. Player 1 is then assigned as the ghost player and any player partnered with the ghost is given a bye, then the schedule has a natural court balance with each team playing exactly twice at each court.

Example n=7.  First consider the cyclic schedule for 8 players.


          court
            1     2     3     4
round       
  1      ( 1 2 ) ( 3 8 ) ( 4 7 ) ( 5 6 )
  2      ( 1 8 ) ( 2 7 ) ( 3 6 ) ( 4 5 )
  3      ( 1 7 ) ( 8 6 ) ( 2 5 ) ( 3 4 )
  4      ( 1 6 ) ( 7 5 ) ( 8 4 ) ( 2 3 )
  5      ( 1 5 ) ( 6 4 ) ( 7 3 ) ( 8 2 )
  6      ( 1 4 ) ( 5 3 ) ( 6 2 ) ( 7 8 )
  7      ( 1 3 ) ( 4 2 ) ( 5 8 ) ( 6 7 )


The players highlighted in purple are given the bye at each round, so these matches with player 1 from the 8 player tournament are never played and court 1 is not needed.  Matches in courts 2, 3 and 4 all derive from the non-fixed positions in the cyclic algorithm, so it should be no surprise that each column contains all 7 players ( 2 to 8 ) exactly twice.  It only remains to map players 2 to 8, back to 1 to 7 to give the 7 player court balanced tournament schedule.

If n is even, and is a member of the infinite series 8,14,20,26,32,... [n=6i +2: i>=1] or a member of the series 6,12,18,24,30,36,... [n=6i : i>=1] then there is a simple modification to the cyclic algorithm that can give the necessary court balance.  In essence this is the method of Haselgrove and Leach (1977), see this article by Jeff Dinitz for a description of a similar algorithm.

(1)      Begin with the first round using the standard cyclic algorithm.
(2)      Generate subsequent rounds by rotating the players (n/2)-1 positions, rather than just a single position.
(3)      Stop when (n-1) rounds have been obtained. This gives exactly the same rounds as the cyclic algorithm but in a different order.
(4)      Number the rounds of the modified schedule as r=1...(n-1).  Now court balance may be obtained by making the following adjustments:
      for r=1...(n/2)-1, swap over pairs from courts 1 and r+1.
      for r=n/2...n-2, swap over pairs from courts 1 and n-r.
      for r=n-1, leave the round unchanged.

Example n=8. Since (8/2)-1=3, every third row from the cyclic schedule above is used in the construction of the reordered schedule below.  Note that after the seventh row the first row is considered to be next.  So r=1...7 below, corresponds with round=1,4,7,3,6,2,5 above.

        court
          1     2     3     4
r
1      ( 1 2 ) ( 3 8 ) ( 4 7 ) ( 5 6 )
2      ( 1 6 ) ( 7 5 ) ( 8 4 ) ( 2 3 )
3      ( 1 3 ) ( 4 2 ) ( 5 8 ) ( 6 7 )
4      ( 1 7 ) ( 8 6 ) ( 2 5 ) ( 3 4 )
5      ( 1 4 ) ( 5 3 ) ( 6 2 ) ( 7 8 )
6      ( 1 8 ) ( 2 7 ) ( 3 6 ) ( 4 5 )
7      ( 1 5 ) ( 6 4 ) ( 7 3 ) ( 8 2 )


Following step 4 in the modified algorithm identifies the matches in rounds 1 to 6 that are highlighted in red above.  Finally swap these matches over with the blue matches in the first column.


        court
          1     2     3     4
r
1      ( 3 8 ) ( 1 2 ) ( 4 7 ) ( 5 6 )
2      ( 8 4 ) ( 7 5 ) ( 1 6 ) ( 2 3 )
3      ( 6 7 ) ( 4 2 ) ( 5 8 ) ( 1 3 )
4      ( 3 4 ) ( 8 6 ) ( 2 5 ) ( 1 7 )
5      ( 6 2 ) ( 5 3 ) ( 1 4 ) ( 7 8 )
6      ( 2 7 ) ( 1 8 ) ( 3 6 ) ( 4 5 )
7      ( 1 5 ) ( 6 4 ) ( 7 3 ) ( 8 2 )


Before this is done player 1 plays all their matches on court 1, but afterwards they are distributed as evenly as possible. Remarkably, on any court the two underlined players play once, all other players play twice, so the best possible court balance has been found.

A court balanced tournament schedules is not possible for 4 players.  However schedules for the infinite series n=10,16,22,28,34,... [n=6i +4 : i>=1] do exist.  Their construction is much harder and involves some graduate level combinatorial mathematics, see Anderson (1997).

Further Reading

Anderson, I. 1997 "Combinatorial designs and tournaments", Clarenden Press Oxford.
Dinitz, J.H. "Designing Schedules for Leagues and Tournaments"
Haselgrove, J. and Leach, J. 1977 "A tournament design problem", Am. Math. Monthly, 84, 198-201
« Last Edit: May 23, 2018, 02:45:26 AM by Richard A. DeVenezia »


Fred

  • Newbie
  • *
    • Posts: 1
Reply #1 on: September 15, 2010, 05:41:00 AM
Hi,
Thanks for providing these details, they provide lots of information.

I am looking into how I can schedule a court balanced RoundRobin for slightly more complicated scenarios, say 10,12,14,16 or 18 (or maybe more) competitors on limited numbers of courts, (say 3 or 5).

At the bottom of your post you mention that these are possible and refer to Anderson, I. 1997 "Combinatorial designs and tournaments". I tried to get hold of a copy of this book but it is not held by any libraries in the area. I'm not sure my maths would stand up to it anyway, its a long time since I studied maths like that...

The paper "Designing Schedules for Leagues and Tournament" (J. Dinitz) does discuss this exact topic and even provides an example CBTD(10,3), but all he does is state they are possible, he doesn't go into details of the algorithm.

Further, I found a paper "Scheduling Court-Constrained Sports Tournaments" by Michael Trick.  He also talks about this subject referring to a Tournament Array TA(2n,c), gives an algorithm and a few examples.  His example for TA(8,[3,3,4,3,3,4,3,2,3]) appears to be perfect.  I thus followed this logic when there are always 3 slots and it just wasn't balanced.  I also tried it with 10 competitors (3 slots) and again it wasn't balanced.

Do you have any further details or could you explain a bit further how to cope with these court balanced RR?

Many thanks
Fred


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #2 on: September 16, 2010, 04:02:13 AM
Hi Fred,

Thanks for your message.  The book is not going to help with schedules where the number of courts are restricted, I referred to it as it gives enough detail to construct the full BTD when the number of players is 6i+4.  If you do want these schedules then I have made the constructions for you, just follow the link above for "Ian's Excel File".  At least the 10 player, 5 court BTD may be of some use.

I have not followed up the references on the combinatorics of CBTDs or TAs, but clearly if you are having problems then you need to refer back to the original Mendelsohn and Rodney paper.  When I have needed schedules like this I find that an exchange algorithm works fine and can produce superior schedules to the ones I have seen.  In particular I think it is essential that the distribution of the byes is considered.  For example, look at the plan for CBTD(10,3) that you refer to above; players 1, 2, & 3 have no byes in the first 6 rounds, while players 4 & 5 get 4 byes each.  This is so uneven that I think you might get complaints from the players if you used the schedule for a league.  It is possible to do much better:

(E J) (C H) (B G) 
(F I) (A D) (E H)
(B D) (F G) (C J)
(E I) (G H) (A B)
(C D) (A I) (F J)
------------------
(C E) (B J) (H I)
(A G) (D H) (E F)
(B C) (A J) (G I)
(A H) (B E) (D F)
(G J) (C F) (D I)
------------------
(B I) (D E) (C G)
(H J) (B F) (A E)
(D G) (I J) (A C)
(A F) (E G) (B H)
(F H) (C I) (D J)


Above the 10 players play exactly 3 times on each court and exactly 3 times in each block of 5 rounds.  There is also a minimal number of back-to-back games within the blocks of 5 rounds, I believe.

Some of the schedules you are looking for can be found directly by slicing up BTDs, for example just take the BTD for 12 players and form two rounds from each of the 11 rounds.  So games played on courts 4,5 & 6 in round 1 are played instead on courts 1,2 & 3 in round 2.

Let me know (on or off-line) if there are specific schedules that you are interested in finding.

Ian.
« Last Edit: May 23, 2018, 02:46:07 AM by Richard A. DeVenezia »


Bob_R

  • Newbie
  • *
    • Posts: 3
Reply #3 on: June 12, 2012, 08:12:50 AM
Round robin scheduling has been a problem since time began.  The real problem with scheduling sports is the number of permutations and combinations involved when trying to schedule teams, time slots, dates and locations.  The old method of always having a single team always playing in the same time slot or position is not the way to go.  It can, and does lead to disgruntled players, coaches, teams, and spectators.  The issue is the quality of the first position time slot.  If the time, location, and/or quality of the facility is desirable, then the team that's always scheduled there will be very happy.  This is where 'scheduling problems' usually begin because other teams will not share equal playing time at the desirable facility.  If the time and location is less than desirable (i.e., inconvenient time, long distance, poor quality of facility, etc.) the complaints will come from the team that is always scheduled to play there.

All of this is avoidable by creating true balanced schedules.  Most software companies are still working on the problem, but few have solved it.  Round robin scheduling must include the date, time, location, game number and home and visitor teams for each game on a schedule.  All of these things must be distributed and balanced as equally as possible to have a good schedule.  The old WHO, WHAT, WHERE, & WHEN is what I'm talking about.  

There are many different types of schedules that are different from the normal baseball, football, basketball types.  Tennis and golf come to mind with the many variations associated with those two sports. Lets simplify a little.  Tournament and league schedules are two different tasks.  

Lets talk about creating a schedule for a group of 12 ladies that come to play once a week.  Each week they want to play in a foursome and play with a different partner and have the opponents rotate as well.  This is a real easy schedule if you know how to do it.  The same logic applies to a mens golf or tennis group that play each week (foursomes) for 20 weeks.

I will post more info about scheduling if people are interested.  I have been at this since 1970 and developed software that really does the trick.

Bob R
« Last Edit: May 23, 2018, 02:46:29 AM by Richard A. DeVenezia »


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #4 on: June 13, 2012, 06:09:44 AM
Hi Bob,

Thanks for your message. Certainly I would be interested in reading further posts that discuss your approach to scheduling.

Your example of the 12 ladies is what I would call a whist design - there are some examples that you can find by following the 'schedules' link near the top of this page and they have the property of all partners once and all opponents twice. You say that WHERE is important, but can you arrange the 12 ladies on the three courts so that they play either 3 or 4 times on each court over the 11 weeks of the balanced whist schedule?  This is something that I don't have a solution to.  Can you software solve it? For 16 ladies and 15 rounds also?

Ian


Bob_R

  • Newbie
  • *
    • Posts: 3
Reply #5 on: June 13, 2012, 07:07:32 AM
Hi Ian,

Got your message.  If the there are an appropriate number of courts/time slots available to schedule (for the number of players or teams), I can schedule just about anything.  What I will do is create a schedule for your two examples based on the limited amount of information available.  I will save them as a PDF file and send it to you.  I have 3 appointments today, but will try to get at least one schedule to you this afternoon.

Bob R


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #6 on: June 13, 2012, 07:25:49 AM
Bob,

There is really no need to rush - this is for my academic interest only.  I was assuming the full amount of courts were available for everyone to play simultaneously, so time slots are not an issue.

Ian.


Mochi

  • Guest
Reply #7 on: November 25, 2012, 04:25:16 PM
Hi, Ian
  I am interested in tournament, however, I can't get a 10 balanced teams schedule. Could you help me to do a example?
Thanks


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #8 on: November 26, 2012, 02:10:15 AM
There is an example of the 10 team schedule here.  Otherwise you could use my Excel generator which you could find by following the first link in the first message above.
« Last Edit: November 26, 2012, 02:11:08 AM by Ian »