1
$\begingroup$

I'm trying to build a scheduling app for a friend, but am stuck on how to sort the employees.

I have three holidays each with their own employee_need:

thanks_giving: 2

christmas: 3

new_years_eve: 2

I have employees who have a predetermined number of days they will work. The sum of the employee’s predetermined work days will always add up to the sum of the three holiday’s employee_need. They also have ranked the holidays by preference, which should guide the scheduling process. The data looks something like this:

Polly:

days_to_work: 1

preferences: [christmas, new_years_eve, thanks_giving]

Stan:

days_to_work: 2

preferences: [thanks_giving, christmas, new_years_eve]

etcetera.

Right now my process of sorting is to

  1. Fill each holiday with a list of all employees.

  2. Loop through the employees, starting with those who have the most days off.

  3. Loop through the employee's preferences and pull them from the one they most desire to have off that also has room for them to be taken off

  4. Continue looping until the days are properly scheduled. If there is room to remove them from that day, I do so, until they are working the number of days they are supposed to.

The algorithm works a decent amount of time, but I really need it to work all the time.

Is anyone familiar with this kind of problem, and can point me toward a better methodology?

$\endgroup$
3
  • $\begingroup$ This seems like a problem that must have been tackled before. Have you finding relevant work on the internet using a search engine? $\endgroup$ – Yuval Filmus Jan 14 at 11:58
  • $\begingroup$ For example, Google OR-Tools also handle some scheduling problems: developers.google.com/optimization/scheduling $\endgroup$ – Yuval Filmus Jan 14 at 11:59
  • $\begingroup$ I found the nurse scheduling problem early on in my research, and I had trouble adapting it to my use case. Perhaps now that I've spent more time on the problem it'll shed some more light. I'll take a look at it again. Thanks! $\endgroup$ – Eojo Jan 14 at 17:39
1
$\begingroup$

This looks a lot like the stable marriage problem, itself related to the problem of matching in biparftite graphs. There are very efficient algorithms to solve both problems.

$\endgroup$
1
  • $\begingroup$ I found the stable roommate problem through your link, which seems a little closer. However, they both relate to inner pairing. I'll see if I can make it work for my user case. Thanks! $\endgroup$ – Eojo Jan 15 at 3:28
0
$\begingroup$

A standard approach is to use integer linear programming. You have a zero-or-one integer variable $x_{e,t}$, with the intended meaning that $x_{e,t}=1$ if employee $e$ is scheduled on timeslot $t$. Then each of your constraints can be expressed as a bunch of linear inequalities.

Scheduling problems are widely studied in operations research, so you could also look at standard tools for operation research problems (e.g., OR-Tools, as Yuval Filmus mentions).

$\endgroup$
1
  • $\begingroup$ I've been looking for or-tools that can be used with Ruby. I've found a couple gems, but they weren't flexible enough to fit my needs. I'll post back if I find anything. $\endgroup$ – Eojo Jan 15 at 3:33

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.