5
$\begingroup$

I am in the process of building some software to generate fixtures for a chess league, which has a little twist which complicates matters. I would like to introduce a constraint whereby two consecutive teams from the same club are not allowed to play on the same night. e.g. Loughborough 1 is not allowed to play on the same night as Loughborough 2. This help teams share players, and therefore play more games.

The league has five divisions, with 8, 7, 8, 7, 7 teams respectively. The first half of the league is played over 10 weeks. This means that teams do not have to play each week.

A solution would be to brute force all the fixture combinations, for all the divisions. The problem with this approach is that there are way too many combinations!

I am wondering if there are any mathematical techniques that I could use to help me with this problem. I am not wanting to find a unique solution (a combination of fixtures, without violating the constraints). I would be happy with an algorithm which produced 10 violations of constraints in the season.

Any help or pointers would be greatly appreciated. Can anyone suggest any areas for me to research?

  • 0
    How often does such a combination happen randomly? If you're lucky, you might get by with simply trying a few combinations until it works.2011-04-14

2 Answers 2

1

Timetabling is something evolutionary strategy's can get solutions for pretty quickly with all kinds of limitations. Edinburgh university schedules all its courses/classes using an some ES software.

could probably use a basic genetic algorithm to get a good solution. Even better is with a GA you dont get A solution you get a population of solutions to pick the one you like best from!

1

Why don't you constrain the generative process?

For each match-up: randomly select a valid pair of teams.

"Valid" pair meaning: teams which currently have less than 8 match-ups, and which are not adjacent in the same division. (Can also add, for instance, teams which have not played against each other yet.)

Cheers