Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

comment on

( [id://3333] : superdoc . print w/replies, xml ) Need Help??
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.

In reply to Looking for help with AI::Genetic and classroom scheduling by merlyn

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.