Algorithm for assigning people to time slots based on preference

algorithms

I'm attempting to figure out if an algorithm currently exists to accomplish what I'm trying to accomplish.

I have a series of time slots over the course of a week where I wish to assign a roughly equal number of people to each time slot during the week. Unlike this question, the time slots are provided as just ranges of hours, and members of the population only need to be pigeon holed in a roughly equally distributed way.

Most of the population has provided a 1st, 2nd and 3rd choice for their desired time slot. People who list a time slot as multiple preferences are considered improperly filled out and the preference will only be considered once and their remaining preferences will be considered as having no preference.

Additionally some of the population may not provide an answer or may say they have no preference. They will still need to be assigned a time slot, but can be assigned whatever time slot is necessary to satisfy the algorithm.

However, the time slots themselves have no preference over who goes where, other than that they want people to be roughly evenly distributed, meaning this is not just a case of the stable-marriage/hospital-resident problem. It further differs from the stable marriage problem in that members of the population do not have a preference for every time slot, which seems to be required for that algorithm to operate.

The objective of the algorithm is as follows (in order of importance):

  1. Ensure that everyone is assigned a time slot.
  2. Ensure that everyone who provides a separate 1st, 2nd and 3rd choice is assigned to at least one of them.
  3. Distribute the population so that they are roughly equal among time slots.
  4. If it would make the population more evenly distributed, eliminate time slots by moving people out of them.
  5. Maximize the number of people who get their 1st choice.
  6. Maximize the number of people who get their 2nd choice.
  7. Maximize the number of people who get their 3rd choice.
  8. Minimize the resources and run-time required for the algorithm.

In my research, I've also found that the stable-marriage problem can have different outcomes depending on which side goes first in their proposals. I hope that the starting state would not affect the outcome of the algorithm, but if necessary I can simply run it many times and take the best result. I would also like to avoid assigning arbitrary constants to preferences unless absolutely necessary.

This is a fairly complex problem so I'm not expecting to get a complete algorithm from here unless one already exists for solving this exact problem. My question is mostly regarding whether there are similar algorithms or areas of study that I should start from. Can anyone help point me in the right direction?

Additionally, am I dismissing the SMP as a starting point incorrectly?

Best Answer

It seems like you should do the following:

  1. give everybody their first choice time-slot.
  2. If the distribution is "roughly equal among time slots" (whatever that means) then you are done.

If they are not roughly equal then you will have to move one or more people from their first to their second choice. It would probably be best to focus on the most requested time slot although you could pick people randomly instead.

If they are still not roughly equal even after everybody is set to their second request, then start giving people their third request.

The above will not work if you are actually trying to distribute people evenly among a set of time slots. In that case then give everybody their first choice. Then any time slot that has too many people, find the individual in the slot who's second choice is the least popular and move him/her there instead. If everybody in the slot already is at their second choice, then find the individual who's 3rd choice is the least popular and move him/her.

Related Topic