abigail at abigail.be
Mon Sep 9 16:17:03 BST 2013
On Mon, Sep 09, 2013 at 12:45:43PM +0000, Dave Cross wrote:
> I have offered to help a friend solve what sounds like an interesting
> She has a list of courses that are offered. Some of these courses have a
> maximum class size and others are effectively infinite (I don't believe
> that second part, but hey!) There are about thirty of these courses.
> She also has a list of students who have decided which courses they are
> interested in doing. For each student, we have their five favourite
> choices - ranked from 1 to 5.
The point is, every student gets to follow just one course?
> The problem is, of course, to find the optimum arrangement of students
> to courses so that each student is doing the course as close to their
> first choice as possible.
That's ill defined. What is "as close to their first choice as possible"?
Say there are two solutions that differ only in the following:
Solution A) has student 1 get to their first pick, and student 2 to their
fourth pick. Solution B) has student 1 and student 2 doing their second pick.
Is any of those solutions to be preferred? If so, why? Is a first-first-fifth
solution to be preferred over a second-third-third? Over a third-third-third?
> There are, however, a couple of extra constraints.
> 1/ Each course much be run with at least two students. So if there is a
> course that has no students choosing it, two students must be assigned to
> 2/ Each student actually does two courses. So if someone is forced into a
> course because of rule 1 above, we can sweeten the pill slightly by
> guaranteeing (insofar as we can) that they get their first choice for
> their other course.
> I'm sure that most of this must be a previously solved problem. But I'm
> not sure where to start looking.
I don't think this would be an NP-complete problem (although it probably
is if the number of courses each student is taken isn't fixed), but
I'd think it's still computational heavy. I doubt a greedy algorithm is
going to work.
However, it sounds like a problem that will have a fast and relative
simple solution using heuristics that will give a close to perfect answer
in all but a few cases.
More information about the london.pm