http://qs1969.pair.com?node_id=432801

merlyn has asked for the wisdom of the Perl Monks concerning the following question:

I'm trying to help "Captain Neil" out with scheduling the future geekcruises. I figure I can use AI::Genetic with it, but if someone has a better module, I'll use that instead. (If I can get this to work in time, we'll actually use it live for Perl Whirl 05, and I can give a talk about how it worked...)

The problem is that essentially a schedule consists of time slots with various rooms within the slots, and instructors (and hopefully students) to fill the rooms. The obvious constraints apply: rooms can't hold two things at once, and instructors can't be in two places at once. There's also some "better than others" solutions, like having the first and second place class requested by attendees both be available and in different time slots, and possibly some ordering of classes based on "part 1" "part 2" information. And, if I can get past all that, there's actually different classroom sizes that can bias the result as well.

So, where I'm stuck is how to best represent a particular schedule. Should the genes represent the timeslots for each classroom, with the values being the class for that slot? Or should they represent the classes, with the values representing the timeslot-classroom identification? Both of them seem to have advantages for mutation and crossover, but with the cross-constraints, it seems like nearly any crossover is going to generate a schedule that immediately gets stillborn as an impossible deal.

Does anyone have any experience with setting up this sort of thing?

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.


update: It was asked in the CB about why I just don't search the entire solution set. I have 2.5 sea days on a typical cruise, which translates into 5 to 8 timeslots, with 2 to 4 classrooms available. Then there's evening slots for the larger events, usually on 3 or 4 nights. This means I have a potential 25 or so time-places to schedule (crossing time against place). Now, add to this that we're drawing from an offered class list of about 40 items or so (many of which will not be offered), and 150 to 300 attendees all giving "first choice" and "second choice" classes. It'd take "a while" to do this all by exhaustive search, I suspect. I'm trying to shortcut that a bit.