# Assigning Classes

Dave Cross dave at dave.org.uk
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
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 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.

Cheers,

Dave...

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

```