In this assignment, we consider the situation where a number of students need to be assigned to a number of courses. The students have different preferences for different courses. These preferences are given to you – the planner – and your job is to assign the students to the courses in a way that results in high utility, both for the students individually and in total.
Let C be the set of courses and let S be the set of students. Each student can only be assigned to each course once, but can be assigned to as many different courses as you want. Each course has a limit on the number of students that can be assigned to the course. This is called the capacity of the course. Every student has a utility (preference) for each course, and each student distributes a total of 100 utility points to the courses (possibly zero for some of the courses).
If a student is assigned to a course for which he has assigned positive utility, the student obtains that utility. The total utility obtained by a student is the sum of the utilities the student has for the courses he is assigned to, and the total utility of an assignment is the sum of the utilities of the students. High utility is preferred to low utility.
Example: Assume that a student has the following utility for each of ten courses:
If the student is assigned to courses 1, 5, and 8, he gets a total utility of 65. If the student is assigned to courses 3, 6, 7, and 10, he gets total utility of zero.
We use three measures to evaluate an assignment:
A. Total utility: The sum of all utilities of all the students.
B. Min. utility: The utility of the student with the smallest utility.
C. Number lost: The sum of the number of courses that each student wanted, but did not get.
We consider the following three strategies for assigning students to courses:
Strategy 1:
Repeat the following as long as there are courses with vacant capacity that are wanted by students who have not been assigned to that course:
I. Identify the highest utility (Umax) that any student has for any course with vacant capacity (which he/she is not already assigned to).
II. Let s be such a student and let j be such a course. I.e. student s has utility Umax for course j. If the student-course combination fulfilling this is not unique (if there is more than one choice), then select the course with highest vacant capacity. If it is still not unique, select the student with highest unsatisfied utility. If there is still more than one option, choose arbitrarily among those.
III. Assign student s to course j.
Strategy 2:
Initialize C and S to be the complete set of courses and students, respectively. Repeat the following as long as both S and C are non-empty:
I. Remove from C all courses that are not wanted by any student in S and courses that are filled to the capacity limit.
II. Remove from S all students that do not want any of the courses in C.
III. Select the student s in S with the smallest satisfied utility (which we define as the sum of utility of the courses the student has already been assigned to). If there is more than one student who fulfills this (i.e. the choice of student is not unique), let s be the one with least remaining opportunities for satisfaction (defined as the number of courses still in C for which the student has positive utility).
IV. Assign student s to the course still in C which he wants the most.
The whole process is repeated R times (where the number of repetitions, R, is dynamic and should be an input to the procedure), and the solution with the highest Total utility is remembered and is the final solution.
Strategy 3:
Repeat the following as long as there are courses with vacant capacity that are wanted by students who have not been assigned to that course:
I. Select randomly (uniformly distributed) a course j with vacant capacity (which is wanted by at least one student who has not been assigned to it).
II. Consider the students that want the course (and have not yet been assigned to it). Let the probability of selecting student k be proportional to the utility student k has for course j compared to the utility that the other students have for course j. Let student s be randomly chosen according to that probability distribution.
III. Assign student s to course j.
Example to explain step II in strategy 3: Assume that three students want the selected course, and their utility for the course is 5, 10, and 15, respectively. Then the probability of selecting student 1 should be 5/(5+10+15) = 5/30 = 1/6, the probability of selecting student 2 should be 10/(5+10+15) = 10/30 = 1/3, and finally, the probability of selecting student 3 should be 15/(5+10+15) = ½. Using a roulette wheel approach, let r be a random number between 0 and 1. Then, if 0 <= r < 0,1666, we select student 1. If 0,1666 <= r < 0,5, we select student 2, and finally if 0,5 <= r < 1, we select student 3. Data set format Each data set is located in a separate file. The file name (except the “.xlsx”) is the name of the data set. They all have the following format: Cells B1 and B2 give the number of students and courses respectively. Row 4 (starting in column B) states the capacity of the courses. The matrix starting in row 6 gives the utility each student (vertically) has assigned to each course (horizontally). The first column provides the student ID. In the below example, course 2 has capacity for 3 students. The first student (ID 0) has utility 16 for that course, whereas student ID 1 is not interested in that course (utility = 0). In this assignment, you are asked to: Create a user form where the user can select data set (is must be possible to select more than one at a time), planning strategy, and measure (it must be possible to select more than one measure). If strategy 2 is selected, the user should be allowed to choose the number of repetitions (R) – also in the user form. When pressing an OK button, your code should plan with the selected strategy for the selected data sets. The resulting assignment and the calculated measure should be displayed in separate sheets of the file with the code (not the data files). Please also make a simple option for removing all those sheets. (To prepare for a new run). The data files are located in a folder “Data”, which can be assumed to be a subfolder of the folder with the code. Your code must be dynamic in the sense that if more data files are added to the folder, it still works.