4
$\begingroup$

This is my basic setup: I have five time slots (A, B, C, D, E; each day has these five time slots) over 60 days that all need to be filled with n people each (n must remain a variable). However, each person has a different availability (ex. ABDE, BCDE, AE, BCD, etc.). I want this to be distributed equally so all workers get the same number of shifts, but some workers should be able to input in a number of shifts that they want to do.

I recognize that this is a subproblem of the nurse scheduling problem, and I have spend a few hours trying to grind through some academic papers on it. However, it gets very convoluted very quickly and I get lost somewhere in the mix, as I do not have a knowledge of these kinds of algorithms. This seems to be a simpler version with fewer constraints, so I was wondering what a simple yet effective algorithm would be to solve this problem and if you could provide details on it.

I have come up with a two crude algorithm ideas, and I don't know which of these (if any at all) would be the most effective:

  • First distribute work to the person with (1) the least number of shifts assigned so far and then (2) with the least number of availabilities.

  • Distribute all work days to those with the least number of availabilities, but fill a person's entire schedule before progressing on to the next person. Shifts get assigned by determining which time slot (A/B/C/D/E) has the least number of people working it.

The thing that I don't like about each of these algorithms is that it seems very easy to get stuck at any given point, and from there I really wouldn't know what to do.

Thanks.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ What happens to the constraint of equal distribution when workers select their desired number of shifts, are they distributed equally on the rest of the workers? Are all the constraints hard constraints? If yes, the problem can be modelled as a flow network, think of it as a maximum matching with nodes having capacities greater than 1. $\endgroup$
    – Amir Nasr
    Commented Jul 22, 2016 at 12:11

2 Answers 2

Reset to default
4
$\begingroup$

The simplest solution (in terms of saving you the time of understanding the literature) is probably going to be to use integer linear programming (ILP / MILP). You can formulate it as an ILP instance, then apply an off-the-shelf ILP solver.

Introduce zero-or-one variables $x_{i,j}$, with the goal that $x_{i,j}=1$ means that the $i$th person is assigned to $j$th time slot, and $x_{i,j}=0$ means that they're not assigned to that time slot. Now you can write down some linear inequalities/equations constraining these, e.g.,

$\sum_{i} x_{i,j} = n$ for each $i$ (each time slot needs to be filled with $n$ people)

$\sum_j x_{i,j} = c_i$ for each $i$, where $c_i = $ the number of shifts the $i$th worker should be assigned

Also if the $i$th worker isn't available for the $j$th slot, then add a constraint that $x_{i,j}=0$.

Also, $0 \le x_{i,j} \le 1$ (to force each $x_{i,j}$ to be zero or one).

The combination of all of these constraints gives you an integer linear program. Ask the ILP solver to find a feasible solution, and boom, you're done. This might not be the most efficient possible algorithm, but it will be simple to implement and play around with, and I expect that it'll give high-quality solutions and be fast enough for the size of problem you're likely to encounter in practice.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you potentially have a good working example of one that would be applicable for my situation? I have been looking but the summation constraint is difficult to find included in the solver. $\endgroup$
    – louie mcconnell
    Commented Aug 4, 2016 at 23:23
  • $\begingroup$ @louiemcconnell, every linear programming solver allows sums. $\sum_i x_{i,j}$ is another way of writing $x_{1,j} + x_{2,j} + \dots + x_{m,j}$. Every ILP solver will let you express inequalities/equalities containing sums like that (it's a linear sum of variables, which is where the word "linear" in linear programming comes from). $\endgroup$
    – D.W. ♦
    Commented Aug 5, 2016 at 0:32
1
$\begingroup$

Given my understanding of your problem, you should be able to model it as a Maximum Flow Problem for which some polynomial algorithm exists.

Each of your workers would be represented by a node and each of your (60*5) time slot would be represented by a node. An edge of capacity 1 would exist between a worker and a time slot if that worker has the possibility of working that time slot.

You would then introduce an edge of capacity n between each of your time slot nodes and your sink node.

You would introduce edges between the source nodes and the worker nodes having a capacity of number of slots that the worker wants to work (if this is specified) otherwise it would be the ceiled value of (60*5*n - number of shifts that all workers specified that they wanted to work)/(number of worked having not specified a number of shifts to work).

If your total flow has a value of 60*5*n you have a feasible solution to your problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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