room/timeslot schedule optimization

People can chose up to 5 of 25 lectures in advance. All these lectures are given on one day in five rooms at five time slots. Each (preferred) lecture a listener can attend to makes her a bit happier, each lecture he chose but can't attend to (because another preferred lecture is in the same time slot) makes him a bit unhappier. The list of preferred lectures is not weighted (at least the registrants have not been told to order their preferences, but if it makes things easier I could assume that the first choice has the highest priority and so on, that information is available).
Is there a way to maximize the overall happiness or an approximation without trying every single possible schedule? I've found an empty stub for the hospitals/residents problem on wikipedia which pretty much sounds like a similar problem(?)

The hospitals/residents problem — also known as the college admissions problem — differs from the stable marriage problem in that the "women" can accept "proposals" from more than one "man" (e.g., a hospital can take multiple residents, or a college can take an incoming class of more than one student). Algorithms to solve the hospitals/residents problem can be hospital-oriented (female-optimal) or resident-oriented (male-optimal).

The question does not limit the number of rooms. Without that restriction, 14 lectures could be in Slot A and only 3 lectures in Slot B to facilitate maximizing the attendees enjoyment.

jmucchiello 2009-04-02 13:23:00

"People can chose up to 5 of 25 lectures." Therefore there's noneed for them to always miss 4 lectures. All their preferred 5 lectures are in different time slots and they are perfectly happy. All their preferred lectures are in one time slot and they are very sad and won't attend at all.

chendral 2009-04-02 13:24:04

"The question does not limit the number of rooms. Without that restriction," Wrong. "All these lectures are given on one day in five rooms" There are only five rooms. 5 rooms, 5 time slots, 25 lectures, all rooms occupied at any given time slots (maybe unless no one wants this lecture, ignore that)

chendral 2009-04-02 13:27:17

@chendral: OK, gotcha. That portion of it wasn't clear (to me, which may mean nothing!) in the question. They aren't made "sad" by the fact that a lecture is taking place that they aren't in, they're "sad" if one of their PREFERRED lectures is going on and they can't attend.

Adam Robinson 2009-04-02 13:33:49

fixed (hopefully) ;)

chendral 2009-04-02 13:49:24

bit vague but I will give it a +1 as soon as possible (15 rep, let me see if I can answer any question here). I'm still hoping for a more "direct" approach (or proof that there isn't such a thing). I mean conference schedules... is it such an uncommon problem? ;-)

chendral 2009-04-02 14:21:29

No, it isn't an uncommon problem, but schedule generation is an 'NP hard' problem (meaning polynomial time...really long). While you could take an heuristic approach, this can quickly get away from you as it's basically brute force. A genetic algorithm would probably work best for you, as Grant says

Adam Robinson 2009-04-02 14:52:47

So then, it *is* np-hard and there's only the choice between (good) approximations or brute-force...

chendral 2009-04-02 15:01:55

Correct. Your only options are guesses, so it's just a matter at using an algorithm that guesses correctly with as few iterations as possible :)

Adam Robinson 2009-04-03 20:57:49

ansaurus

tags:

views:

answers:

room/timeslot schedule optimization

related questions