Sports League Scheduling with GALib
Kyle and Liz
kyle_liz at radiks.net
Thu Feb 21 01:00:04 EST 2002
It is my experience with using GA's for scheduling (also known as time tabling) that it is up to you to design/program this "business rule" constraint into your specific objective function. The GA application that I am developing is for scheduling, and I have about 20 classes (C++)that make up the objective function logic for how I try to place events onto a Calendar object. My point of that statement is is that it may take some work.
Here is what I am doing: The way I would treat this constraint is just like any other constraint. I would design/program heuristic/customized logic for what means good and what means bad for your rules and then penalize/award accordingly. I use an order-based genome/string (this is THE key point to my design/solution to scheduling GA's) simply to represent the order in which the 'events' are attempted to be scheduled. This is effective because usually there are always events that are harder to schedule than others and you don't want to wait until the end to try to place them. So, with the genomes of the population all representing different orders of how/when to schedule the events, some score better than others against the constraints. As each genome is presented to the objective function you just take the events one at a time from the genome and try to schedule them where that event would most like to go (again, it's up to your customized definition of what you desire). If that spot on the calendar is full try the next most desirable spot, etc, etc. Then when that event is finally placed somewhere on the calendar (or maybe it isn't at all) you score it against all the constraint rules that you have designed/programmed and they each will contribute to the score of the genome (I add penalty points for not getting what I want). As I said, time tabling is a specific field of GA's and you should be able to find good material on it if you look around. I think some of the best work on it is done in the University of (Scotland?/England? sorry!) in Edinborough.
hope it helps,
software developer/industrial engineer
From: James Cavanaugh [SMTP:james.cavanaugh at snet.net]
Sent: Monday, February 11, 2002 10:53 PM
To: galib at mit.edu
Subject: Sports League Scheduling with GALib
<< File: ATT00001.txt; charset = Windows-1252 >> << File: ATT00002.html; charset = Windows-1252 >>
More information about the galib