Fog Creek Software
Discussion Board




Creating automated scheduling systems

Hi all,

I'm working on a project to build a scheduling application for sports teams.  Part of the project is schedule manipulation (done throughout the year) -- changing which teams are playing against each other, and which location they are playing at.

The other big part of the project is a schedule generation tool that will create the initial schedule for the year.  The requirements are that the schedule generation tool will be fed a number of initial parameters, and then it should spit out the proposed schedule.

The initial parameters are rules such as:
- The number of teams, and their home location
- Which teams are in which division
- Travel restrictions on how far each team can travel during the regular season
- Restrictions around the number of times each team should play each other.
- Holidays in which no games should be played
- Specific days off in which certain teams should not be playing.
- Etc.

Our application will collect information for all these rules, and then the input the rules into the schedule generation tool which should then spit out a proposed schedule that meets all the restrictions defined.


Any recommendations as to how this could be implemented?  I'm assuming this problem has been solved before -- does anyone know about any off-the-shelf scheduling engines that we could integrate?

The rest of the application will be an ASP.NET web app, so ideally the scheduling generation tool would integrate well into this environment.  However, since the scheduling generation will occur once a year, a standalone system with clearly defined interfaces would work as well.

Thoughts?

Ed
Thursday, July 03, 2003

Ed,

I've done a little bit in this area, although my scheduling was limited to a golf league schedule.

One thing you might be missing in your parameters is how to handle conferences, and possibly if each division needs to play everyone in it's own division X number of times, and how to determine which out-of-division teams to play.

That being said, I've always wondered if there was a nice scheduling algorithm out there, I've searched briefly and couldn't find one readily available.

Jamie Hornstein
Thursday, July 03, 2003

I've done some work in this area as well... in my case it was for squash tournaments.

My feeling was that the rules could easily become so oddball and complicated that there was no hope of finding a generic scheduler that could cope.  Some issue with the characteristics of different venues for different matches, preferred times for or between matches, cancellations, etc. was always going to require that the organizer have a good tool for quickly hand configuring whatever the scheduling algorithm came up with anyhow.

My solution was to have the matches autogenerated according to certain criteria for the structure of the tournament and the player / team list, and then to have the organizer drag these matches from a pick list into the 'cells' of a special dynamically resized gridish control that represented the available court times.  The grid was built according to simple venue info, but court times could easily be blocked out with a mouse drag.  The pick list was sorted by match sequence, and could filter for a single event (eg. Men's A) or a single player or whatever.  This interface was slick enough that a couple of hundred matches could be 'semi-manually' scheduled in 15 minutes, and of course allowed for intelligent tradeoffs and changes at any time.

I went some distance down the path of packaging up the bits of the interface as 3 interoperating OCX controls, but never finished that part of things.

I might be able to find you some of my old stuff if you want to pursue a similiar approach.  My thing was a combination of VB6 & VC++6.

John Aitken
Thursday, July 03, 2003

While I have no experience of specifically scheduling - if it has to be completely automated - this would seem the kind of application which lends itself to calculating a fitness function for a "guess" and iteratively improving it.

Reason I say this:
1. It does not sound like there is one right answer, rather several good answers, and you want to converge on one of these.
2.  Additionally the criteria and relative importance for what is good or bad - you want them to control them (which would be possible in your fitness function).
3. Finally it sounds like there may be way too many variables to try every possible "guess" and find the best one. So you want to search the virtual space of possible answers, for good answers, without searching across the entire space.

Therefore - suggestion - Genetic Algorithm?

S. Tanna
Thursday, July 03, 2003

I read someone's PhD thesis on this subject recently - "Beck.Thesis.zip" at http://www.eil.utoronto.ca/profiles/chris/zip/

Christopher Wells
Thursday, July 03, 2003

I think the solution you're looking for could be Constraint Solving, specifically Finite Domain solving. It's a large topic, and there are many resources available. You don't say how many teams/rules/etc you have, but I'm certain this could help, especially since you don't seem to need real-time results.

I'm not sure what your monetary or time budgets are, but there may be libraries available that could be easily modified to fit your needs. If you are really looking to make an investment, then you could look into the ILOG Solver libraries, or possibly to the Mozart/Oz language. It has contraint capabilities built into it, but will require much time if you're not familiar.

One thing you haven't mentioned is optimization. Constraint solving can be used to find a large set of solutions, or can generate one solution, and then use optimization parameters that you provide to find better solutions.

For example, you may require that each team travel no more than 1000 miles in a season, but the first solution may have team 1 traveling three times as far as team 2. Optimization could be used to 'load balance' the solution.

Anyways, it's a large and complex topic, but very interesting.

Good luck.

ps. I just came across this...

http://mat.gsia.cmu.edu/sports/

Many links to do with sports scheduling.

It's a list maintained by Michael Trick whom I believe is still involved with the Operations Resource pages here...

http://www.informs.org/Resources

If you need anything related to Contrained Programming, the answer will likely be there.

Spam
Friday, July 04, 2003

*  Recent Topics

*  Fog Creek Home