5

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)? – Bart van Ingen Schenau Jan 1 '18 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. – Rob Rose Jan 1 '18 at 22:07
  • Will the number of preferences ever exceed the number of slots? – Inverted Llama Jan 1 '18 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. – Rob Rose Jan 1 '18 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? – Steve Jan 2 '18 at 9:28
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.