Round Robin Tournament Scheduling

Schedules - You must register to Post and Download => Mathematics => Topic started by: Rourke on July 02, 2020, 08:49:29 PM

Title: Partial Schedule Played, complete it
Post by: Rourke on July 02, 2020, 08:49:29 PM

Just stumbled on this board, thanks for putting it together! I've always had an interest in tournament scheduling, and have been able to put it into practice several times.

We've had a situation in our national league where due to coronavirus a big slab of the season went missing after a few rounds had been played. The original schedule was not a perfect double round-robin. The organisers want to complete it with a single round-robin, given the shortened time. They also have a few key matches that must be played on a certain date (Locked).

I managed to develop an algorithm that seems to work, something like simulated annealing. Sharing it here for feedback, and to see if anyone can point me to similar published work:

• For each remaining round, generate a random permutation of the teams that are not involved in a Locked match, and put them in pairs of teams
• Count how many times each team plays each other in the full fixture
• While there are team pair counts that are zero:
  
  • Randomly choose a pair A:B with count more than one (overplayed)
  • Randomly choose one of their non-Locked matches
  • Find another overplayed match in the same round; if there are none, choose any match X:Y in the round
  • Decide whether A:X & B:Y or A:Y & B:X would be the better replacement by testing the overplayed count; if equal, flip a coin
  • Make the swap
  • Update the team pair counts

This seems to steadily move the overplayed count down, with random walks where it gets larger for a while. I'm yet to see it fail, but that would assuredly happen if enough of the fixture was already Locked.

It also works if you want to allow byes, just by adding an extra round, running the algorithm, then removing some of the overplayed matches at the end.

You can then balance the home & away counts with a similar stochastic process.

Title: Re: Partial Schedule Played, complete it
Post by: Ian Wakeling on July 06, 2020, 08:29:54 AM

Thanks for posting your algorithm.  I don't have any specific literature to point to, but I know that the operations research people (I am not one of them) have studied these sorts of sports scheduling problems.  Common methods for finding solutions are constraint programming, integer programming and perhaps genetic algorithms.

It seems that your approach is working well, and I think this is because the random element prevents it becoming trapped at local optima.  There is probably an alternative approach where the matches are first fixed, and then the non-locked ones are moved around the schedule with the aim of having no repeated teams in a round.