A more "balanced" balanced schedule

[boot]

Hi,

I am responsible for scheduling a mixed curling league. We have 26 teams sharing 3 sheets of ice, with 2 draws on Friday, 2 on Saturday and 1 on Sunday. I separated the teams into 2 divisions: top 12 and bottom 14. I then used your rounds.php table to generate a balanced round robin schedule for each division as follows:

Div 1, 12 teams, 11 games, 6 sheets (3 sheets Friday, 2 sheets Saturday, 1 sheet Sunday)
Div 2, 14 teams, 13 games, 7 sheets (3 sheets Friday, 3 sheets Saturday, 1 sheet Sunday)

I am getting complaints from some teams that they are playing too many Fridays, or Saturdays in a row. They'd rather play alternating days each week then a balanced schedule of sheets. I'm being asked for a more balanced schedule.

I'm hoping there is something that can be done to randomize the draws, so that we can maintain the balanced sheets while getting a better alternation between play days.

I'm a software programmer (have been for 30+ years) so I don't mind getting under the hood if that's what it takes. I'm not very good with the math end of it, but I've got teenage kids who know everything about everything, so hopefully I'm covered there as well.

Any suggestions would be welcome.

Thanks,

Brian.

[Ian Wakeling]

Hi Brian,

I can't think of an off the shelf solution, so a computer algorithm to maximise the number of changes of day may be your best option.  What I would do would be start with the standard schedule, I am thinking of 12 teams here, then define matches 1-3 as Friday, matches 4-5 as Saturday and match 6 as Sunday.  Now construct an iterative improvement algorithm that considers all possible swaps of one match for another match, within the same round and between days.  At each stage pick one swap that improves the number of day changes the most.  Eventually no improvement will be possible and a local optimum will have been found; one way out is to make a few random swaps to open up a new line of search.  However, this is harder than it sounds as the algorithm may easily end up back at the same local optimum, but done well the search is constantly exploring solutions that are close to optimal.  The easier alternative would be to restart the search using a different standard schedule and repeat many times, finally picking the best among the many local optima found.   To get different starting schedules you could take some of the code from my Excel generator file here.

While this will probably give a workable solution, it does ignore the balance across the days, so while most teams will play different days in consecutive weeks, some teams may play more times on a Sunday than others.  The day balance could be included as an extra part of the criterion you are optimising but I think it would be much harder to get to work.

Hope that helps.  If you do follow my suggestion the let us know how it turns out.

Ian

[boot]

Thank you Ian for taking the time to reply.

Your suggestion for iterative improvement makes a lot of sense. With only 14 teams and 91 games to contend with, [highlight]a brute force approach is probably doable as well[/highlight]. I'll post back here in a few days (weeks?) with whatever I've come up with. Or perhaps sooner with more questions.

Thanks again,

Brian.

[highlight]Yikes![/highlight]

  14 ! = 87,178,291,200
  91 ! = 1.35200153 × 10¹⁴⁰

Back to the drawing board...