9
$\begingroup$

I have a nurse-scheduling type of problem with a time span of a year and many employees.

Formulation

My main variables are: \begin{align}x_{e,t} &= \begin{cases}1 \text{ if employee } e \text{ is assigned to task } t \\ 0 \text{ otherwise} \end{cases}\\w_{e,d} &= \begin{cases}1 \text{ if employee } e \text{ is assigned to any task in day } d \\ 0 \text{ otherwise} \end{cases}\\v_{e,d} &= \begin{cases}1 \text{ if employee } e \text{ is on vacation on day } d \\ 0 \text{ otherwise} \end{cases}\end{align} Hired days: $$ H_{e} = \text{last work day}-\text{first work day} $$ Employee vacations: $$ V_{e} = \left\lceil\frac{H_{e}\cdot31}{366}\right\rceil $$

Details

  • I cannot divide the problem more in terms of time as there are some constraints and variables that need to be calculated yearly.
  • I have the following symmetry breaking constraint: $$ \sum_{t\in T}{x_{e,t}} \le \sum_{t\in T}{x_{e-1,t}}$$
  • I have divided the problem into cliques of related tasks and employees.
  • I can provide more details about my variables and constraints if needed.

Question

Is there a better way to formulate this problem?

Maybe I could add more symmetry breaking or redundant constraints that could speed up the solving (I'm using OR-Tools).

I also feel like I should assign group of tasks instead of individual tasks, is that a good idea?

Edit:

With this formulation I have around 159245 variables and 478303 constraints with 80 employees.

$\endgroup$
  • $\begingroup$ can you give us some insights how many variables and constraints you have? $\endgroup$ – JakobS Oct 18 '19 at 15:19
  • 1
    $\begingroup$ Info added, but I think that I will remove this question in favor of specific questions about how I implement some of the constraints. $\endgroup$ – Stradivari Oct 18 '19 at 15:25
  • $\begingroup$ Can you add a minimal working example for the code you have using or-tools? This would make it easier to give you hints what to improve. $\endgroup$ – JakobS Oct 18 '19 at 19:03
4
$\begingroup$

There are many approaches to formulate nurse scheduling model. In practice, MIPs and some heuristics have frequently been used. AFAIK, for large scale MIPs, column generation technique can be applied.

Some useful references are:

I hope, they would be useful.

$\endgroup$

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.