Round Robin Tournament Scheduling
Schedules - You must register to Post and Download => Requests => Topic started by: homegun on August 19, 2013, 01:09:40 PM
-
I have been playing in racquetball leagues for years, and scheduling singles and doubles leagues is easy. This year I decided to start a new league playing cutthroat (three players in a match). I will be the captain and scheduler, and I'm finding that I am over my head trying to come up with a reasonable scheme for building the schedule. I'm hoping to find some good advice here on how to proceed. I have read some of the posts involving triples in various other situations, but I'm still at a loss for my application.
Some specifics:
- We will have "N" players - I am assuming anywhere from 6 to 15, could be anything in between.
- We will have 11 weeks of "regular season" play before the playoffs.
- We will have at most 4 courts available.
- If we have a number of players not divisible by three, or more than four courts can handle, there will be BYEs each week. BYE players can also be used to fill in if a player is unable to play in a particular week.
My objectives for the schedule:
- Mix it up as much as possible, with the least amount of duplication on the courts. That is, I want everyone to play on the same court with everyone else to the maximum extent, and I want to avoid having Player "A" on the same court with Player "B" more than once or twice unless the schedule scheme requires it.
- Make sure each player plays relatively the same number of matches during the 11 week season. I want to avoid a situation where some players play 11 matches and some play 8.
I'm not asking for someone to build a schedule for me, but looking for advice on a general approach that I could perhaps code up to use when I know the exact number of players that will be in the league.
Thanks in advance for any replies,
Eric
-
Eric,
Generally these sorts of problems are too large to attempt to evaluate all possible schedules and pick the best, so an optimisation approach is required. You could perhaps try an iterative improvement approach as follows:
First plan out the number of games, so for 10 players there would be 3 games per week giving 99 (11 x 3 x 3) slots in which to schedule players. Next decide who is going to play how often, for example player 1 could play 9 times, while players 2 to 10 could play 10 times each. Fill a schedule at random so the players play this many times each. Now look to make swaps of two players from different games to improve the schedule a little, and keep making such swaps until the schedule can no longer be improved. The hard part is to define a criterion to measure how good a schedule is, and so decide which swaps are good to make, by evaluating it before and after. The criterion needs to measure the balance of the schedule in terms of the number of times each player plays with each other and it also needs to penalise having the same player twice in one week, as clearly that is impossible. For the player balance you could use the frequency matrix that counts the number of times each player occurs together in the same game as each other player; the lower the sum of squares of the elements in this matrix, the better the balance should be. There are complications, you may want to restart many times with new random schedules as each run is only likely to find a local optimum, alternatively you need a strategy to avoid getting stuck at a local optimum by making the algorithm move away and also stopping it from going back.
There are other approaches possible, for example there are constraint programming languages which you might be able to use to solve the problem.
Ian.
-
With the help of a friend (and fellow racquetball player), I managed to develop a tool that produces a very good schedule for a cutthroat (3 player) league. The parameters are:
- Number of iterations of the model to run
- Number of players in the league
- Number of weeks in the season
- Available racquetball courts
The model uses simulated annealing (the Metropolis algorithm) to "relax" the schedule to a near-optimum state. Things that are optimized are:
- How many BYEs each player has in the season
- Spacing between BYEs for a player (avoid two BYEs in a row for example)
- How many times each player is on the court with another player (each player plays all other players the same number of times)
The last optimization costs a lot of CPU time because it involves a triple loop - number of players*number of players*weeks in the season.
I built the tool in Excel 2007, using VBA as the programming language and Excel to display the results. I have attached the latest version for anyone who would like to use it or just explore how it works.
Eric
-
Wow! That's a very nice spread sheet, thank you so much for sharing it.
I have a few comments and suggestions if you are thinking of developing the tool further.
The Court Assignment by Player table counts the courts from court 0, while the tables on either side count from court 1, it would be great if this were consistent.
I believe that the cell formulas in the player-by-player concurrence table are twice as long as they need to be. The players are always listed in columns C,D and E in increasing order, so the 1st, 2nd and 4th COUNTIFS are not needed.
If I choose 11 players, 6 weeks and 3 courts, then approximately half the time I run the macro, I will get a schedule where one of the players has 6 games and no byes, while 2 other players have 4 games and 2 byes. I wonder if you can give different weights to the different aspects of the criterion being optimised? For me absolute priority should be given to the number of byes, so it never returns a schedule where one player has two more matches than another.
Golfers often come to this message board with scheduling questions, and they nearly always want to play in foursomes, so I wonder if there is any possibility of extending the spread sheet to handle 3 or 4 players in a game?
Thanks once again to you and your friend for posting this file.
Ian.
-
Ian,
Thanks for the reply. Just wanted to let you know that I am working on a revision that incorporates some of your suggestions, but my time is limited right now so it might be a few days. It should be relatively easy to extend the tool to four players (or N players, for that matter). However, I'll have to study the convergence of the annealing process a little better to understand how to set various parameters.
As to your specific situation, I did not see the zero bye condition show up nearly as often as you did. I see it about one in ten times, which isn't bad. I will be studying all the parameters of the simulation to see how they impact the solution, so maybe I can improve that. The good news is that if you get a bad result on one run, it's very easy to run the simulation again to get a different and hopefully better answer.
Look for something later this week.
Eric