Assigning Classes

Dave Cross dave at
Mon Sep 9 13:45:43 BST 2013

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  

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 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.

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.

Any ideas would be much appreciated.



[1] And those of you who know that my wife is a teacher might well  
draw conclusions about who that friend is :-)

More information about the mailing list