I need to assign n people to m courses, where each person specified their first and second preference and each course has a maximum number of persons attending. Each person can only attend one course. The algorithm should find one solution where the number of people assigned one course out of their preference is maximized the number of people assigned their first choice is maximized (taking into account 1 which is of higher priority). I guessed that this is not an uncommon problem but a search returned nothing too useful, therefore I decided to roll my own. This is what I came up so far: For courses which have less first preferences than maximum numbers of people attending, assign all those persons to the course For other courses: Put random people into the course which have selected this course as first choice until the course is full For courses which have less second preferences than free spaces, assign all those persons to the course For other courses: Put random people into the course which have selected this course as second choice until the course is full For each person without a course: At their first (then second) preference look out for a person which has chosen another course where spots are still free (if more than one is found take the one which has chosen the course with most free spots), move this person to their second choice and assign the missing person I still don't think this algorithm will find the optimal solution to the problem due to the last step. Any ideas how to make this one better? Are there other algorithm which solve this problem?

Reputation: 1270

Course assignment algorithm

I need to assign n people to m courses, where each person specified their first and second preference and each course has a maximum number of persons attending. Each person can only attend one course. The algorithm should find one solution where

the number of people assigned one course out of their preference is maximized
the number of people assigned their first choice is maximized (taking into account 1 which is of higher priority).

I guessed that this is not an uncommon problem but a search returned nothing too useful, therefore I decided to roll my own. This is what I came up so far:

For courses which have less first preferences than maximum numbers of people attending, assign all those persons to the course
For other courses: Put random people into the course which have selected this course as first choice until the course is full
For courses which have less second preferences than free spaces, assign all those persons to the course
For other courses: Put random people into the course which have selected this course as second choice until the course is full
For each person without a course: At their first (then second) preference look out for a person which has chosen another course where spots are still free (if more than one is found take the one which has chosen the course with most free spots), move this person to their second choice and assign the missing person

I still don't think this algorithm will find the optimal solution to the problem due to the last step. Any ideas how to make this one better? Are there other algorithm which solve this problem?

Upvotes: 12

Answers (4)

Jacob

Reputation: 34601

This is similar to the stable marriage problem.

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

Update:

Taking @bdares comments into account, and the fact that the courses have a finite capacity it would be hard to cast the problem as stable matching.

I would solve this as a linear program with the objective function based on the number of people who get their first choice and the course size as a constraint.

Upvotes: 2

yasouser

Reputation: 5177

Sounds like a linear bottleneck assignment problem. While you in the wiki page, check out the link provided in the reference section.

Upvotes: 1

user684934

Reputation:

Place everyone in their first choice course if possible.

If there is anyone who didn't get it, place them in their second choice.

Now, we might get some who didn't get any of their choices. (the "losers".)

Find a person who got his first choice course, which is also the second choice of the "loser". This guy will be reassigned to his second choice, while the "loser" takes his slot. If there is no such person, then your problem is unsolvable.

Note that this maximizes the number of people who got their first choice:

If you got your second choice, then it means either:

someone else already got your first choice as his first choice
someone else got your first choice as his second choice, but only because his first choice was taken as someone else's second choice, and whose first choice was filled with first choice students.

(Possibly that last bit is a bit hard to follow, so here's a rewording:)

For person X with first choice A and second choice B:

If X got choice B, then:

Y took X's slot in A, and Y's first choice is A.
Y took X's slot in A, and Y's second choice is A. Y's first choice is C, but C's slots are all filled with other students whose first choice is C as well.

Upvotes: 6

Greedy

Reputation: 56

The first problem can be modeled as a maximum cardinality bipartite matching problem. The second problem can be modeled as a weighted bipartite matching problem (also known as the assignment problem).

Upvotes: 0

Course assignment algorithm

Answers (4)

Update:

Related Questions