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.
