Assigning Classes

[Abigail]

On Mon, Sep 09, 2013 at 12:45:43PM +0000, Dave Cross wrote:
>
> I have offered to help a friend[1] solve what sounds like an interesting 
> problem.
>
> 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 
> it.
>
> 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.


Abigail