# Algorithm for assigning people to time slots based on preference

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?

• What should happen if everyone has given valid preferences, all first-coice preferences can be fulfilled, but this results in a uneven distribution (afternoon timeslots are nearly all filled to capacity, but there is plenty of room in morning timeslots)? Jan 1, 2018 at 21:10
• @BartvanIngenSchenau To be honest, I'm not really sure. I technically prioritized distributing the population evenly above first choice, but the potential to give everyone their first choice would probably outweigh that. I would probably then check to see whether the morning time slots can be eliminated entirely. So for example, if it's possible to move everyone out of a time slot while giving them their 2nd or 3rd choice and making the time slots as a whole more evenly distributed, that would be the best solution. Jan 1, 2018 at 22:07
• Will the number of preferences ever exceed the number of slots? Jan 1, 2018 at 22:59
• @InvertedLlama I'm not sure I understand what you're asking? Are you asking if there would ever be less than 3 slots? My intended use is scheduling things on a calendar, so it's unlikely there would ever be less than 3 slots. Jan 1, 2018 at 23:26
• @RobRose, It would be easier if we understood the full context of the problem. For example, do these "slots" represent an open-air public meeting or a site tour, or do they represent a group of appointments available for a consultation with a doctor? Jan 2, 2018 at 9:28