Assigning Classes

[Abigail]

On Tue, Sep 10, 2013 at 08:29:05AM +0000, Dave Cross wrote:
> Quoting Dave Cross <dave at dave.org.uk>:
>
>> I have offered to help a friend[1] solve what sounds like an  
>> interesting problem.
>
> [ snip ]
>
> Thanks for all the suggestions.
>
> It turned out that I only had two or three hours to do this, so I didn't 
> have time to research any of the algorithms that you mentioned. So I took 
> a very basic approach that got me close enough to a solution.
>
> * Iterate across the list of students in random order
> * For each student find their favourite course that still has places available
> * Allocate the student to that course.
> * Repeat to choose the second course.
>
> This has many problems. It doesn't, for example, ensure that each course 
> has students allocated to it.
>
> But we had 387 students, leading to 774 course allocations. And my  
> algorithm allocated 722 of those places, leaving the staff with about 50 
> to allocate manually. Although it's not a complete solution, it's enough 
> of an improvement on the old (manual) process that they are really happy.
>
> I'll carry on working on the program to have it complete for next year's 
> courses.


There's also the lazy solution: randomly assign students to classes.
Tell them they're allowed to make any change they want, provided
that: 1) it gets a buy-in from any student involved in the change,
and 2) no class exceeds the max capacity and no class has just one
student.

That won't reach the optimal solution, but it will reach a solution
that's close enough to an optimum that the trouble getting another change
is more than the gain it will give. 



Abigail