Football Fixture Scheduling: Another Project

Over the past nine months or so I have been working with a local company who provides an online service to schedule various types of sporting events. They contacted me after seeing my contact details on wikipedia (which was a nice way to be contacted).
The company need to produce double round robin tournaments but they have some factors which are not present in the major English leagues. For example

1. Teams might share pitches so those two teams cannot play at home on the same day.
2. There are a number of different leagues and the teams in different leagues might share pitches (see above) but the leagues play in different timeslots. That is, pitches are available in certain timeslots and teams can play in certain timeslots and these are not consistent across divisions.
3. We want to provide a good spread of games such that repeat fixtures (team i vs team j and team j vs team i) are as far apart as possible.

There followed a series of meetings (at 7:30am for reasons best known to ourselves), which discussed the problem so that we both fully understand the task at hand.

At the moment, I am trying to develop a constructive heuristic and then carry out some additional optimisation with simulated annealing.

It has proven to be a very interesting problem and there is still a lot that I want to do, but I have just about got a constructive heuristic that works (in that it produces a feasible solution).

My focus over the coming week or so (as I have some time to work on the problem) is the following.

1. Investigate if I can produce a more efficient constructive heuristic. At the moment, it takes many iterations to get a feasible solution and I’d like to do it much more quickly.
2. Run the local search optimisation (in this case simulated annealing) which will take the feasible solution from the constructive heusristic and try to improve on it. In addition, it will also attempt to spread out the repeat fixtures.
3. Once I have something that seems worthwhile I want to document the algorithm. This is for the purposes of a potential paper (the holy grail in our world!) and also to discuss the approach with the company.

So, the next couple of weeks should be very interesting (well, at least for me!).