Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Course assignment algorithm

Tags:

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

  1. the number of people assigned one course out of their preference is maximized
  2. 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:

  1. For courses which have less first preferences than maximum numbers of people attending, assign all those persons to the course
  2. For other courses: Put random people into the course which have selected this course as first choice until the course is full
  3. For courses which have less second preferences than free spaces, assign all those persons to the course
  4. For other courses: Put random people into the course which have selected this course as second choice until the course is full
  5. 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?