4
$\begingroup$

I'm currently handling a project with a problem that is very similar to nurse scheduling problem in many respects. It is a part time workforce scheduling system whereby we need to determine which staff is most suitable to work on that a particular day in a course of 30 days. There are a few constraints:

Hard constraints

  • 10 staffs will be hired
  • only 5 staffs are required to work in a day
  • each staff could only work for a maximum of 20 days
  • in a month there will be some days where the staff has indicated that they could not work due to inavailability

Soft constraint

  • there will be also some days where the staff is less preferred to work on that day

I was suggested to use linear programming to build this project however I don't see how mathematics can be applied in this case. However, I could be wrong. In that case can anyone point me to the right direction as to what method or techniques should I be using to solve this case?

2 Answers 2

2

This could also be modeled as a max flow problem. Model a bipartite graph with the two disjoint sets $U$ (the staff) and $V$ (the days of the month). Connect now each staff node $u \in U$ with each day $v \in V$ he is willing to work with an edge with capacity 1.

Connect all $u \in U$ with the source with the capacity 20 (the maximal day a person is allowed to work) and all $v \in V$ with the sink with the capacity 5 (number of staff required for the day).

If you can solve this max flow problem with a maximum flow of $days * 5$ a solution for the problem exists. If not you might remove the soft constraints one by one (which means add edges between $U$ and $V$)

2

One way of formulating this as a linear program is to create one binary variable for each worker-day: $x_{i,j}$ represents worker $i$ working on day $j$, where we constrain $0\le x_{i,j} \le 1$ (eventually we will force $x_{i,j}$ to be either 0 or 1, but let us leave them as real numbers to start out.

The constraint that worker $i$ works at most 20 days is $\sum_j x_{i,j} \le 20$

and the constraint that there are at least 5 workers on day $j$ is $\sum_i x_{i,j} \ge 5$

we can force a worker to not work on a given day by setting $x_{i,j}=0$

The soft constraints can be handled as part of the objective Let $c_{i,j}$ be a measure of how little a worker wants to work that day, with $c_{i,j}=1$ being a normal day and $c_{i,j}=n$ being that worker $i$ would rather work $n$ normal days instead of just working that day. So our objective would be to minimize $\sum_{i,j}c_{i,j}x_{i,j}$.

Now it it possible, even probable, that after solving this not all the variables will be 0 or 1. The easiest thing to do is to constrain a variable that is close to 0 or 1 to 0 or 1 and resolve. In a problem this small a computer will get a solution in microseconds.