Creating a scheduling algorithm based on preferences

Question

Currently, we are attempting to build a matching application that matches students to alumni for an event. The event consists of multiple time-slots, in each of which each of the students can be assigned to one alumnus.

For each time-slot, the alumni have a maximum and a minimum number of students that should be assigned to them, and the students have a minimum number of time-slots in which they should be assigned to an alumnus. Students should also never be assigned twice to the same alumnus. Here's the real kicker though: the students can submit a ranked list of preferences for the event which contains a ranking of alumni they would like to talk to.

The algorithm has to create a schedule that contains a "fair" distribution of the students over the alumni and the time-slots.

We have already concluded that we will probably not be able to get an optimal solution, so we want to try to use Local Search to get somewhat of a "fair" schedule. However, to run Local Search we first need to create some random (but valid!) schedules with the capacities and constraints in mind. This "random fill" algorithm is where we run into some issues, since we can not figure out how to create a non-deterministic algorithm that, with the above constraints, creates even a random schedule.

We have tried converting the problem to a flow problem but the resulting graph is way too large to solve in a reasonable amount of time, and we have tried some sort of FCFS approach but there are always edge cases in which conflicts exist that require the algorithm to go into a recursive loop that could take such a long time that we might as well brute force the schedule.

While we cannot figure anything out ourselves, we feel like there must be some similar problem that can be solved with an algorithm that has already been found before. If anyone has any experience with a problem similar to this, we would love their help.

Answer 1

I would recommend a simple greedy approach. Whenever you are assigning a student, assign the student to their best slot. Where best is defined as follows:

1. If any desired alumnus has not reached a minimum in some time slot that the student is available, then the most desired such alumnus, in the available slot that is farthest from reaching a minimum.
2. If any desired alumnus has not reached a maximum in some time slot that the student is available, then the most desired such alumnus, in the available slot that is farthest from reaching a maximum.
3. If the student has not reached their minimum, all alumni in all available slots have hit a maximum, and any student in those slots has passed their minimum, then bump an assigned student. Choose to bump a student based on this student's preference minus that student's preference is as high as possible (ie it is easier to bump someone from their 5th slot than their 1st), and break ties by bumping the student who is farthest past their minimum.
4. No assignment this time.

Assign all students in random order, and try to assign them. Scramble them again, and repeat. Stop when there is a pass with no assignments at all.

This algorithm is not guaranteed to find a best solution, or find a solution. But within reasonable constraints, it is very likely find a decent solution in polynomial time.