4
$\begingroup$

I am trying to implement an employee (nurse) scheduling problem and seek some advice on how to implement a specific constraint.The problem is as follows: There is a set of employees and days (both labeled by integer numbers). Each employee can be assigned a day shift D[(i, j)] , nightshift N[(i, j)] or a day off V[(i, j)]. These are my decision variables:

D = LpVariable.dicts(name="Dagdienst", indexs=[(i, j) for i in employees for j in days], cat='Binary')
N = LpVariable.dicts(name="Nachtdienst", indexs=[(i, j) for i in employees for j in days], cat='Binary')
V = LpVariable.dicts(name="Vrij", indexs=[(i, j) for i in employees for j in days], cat='Binary')

An example constraint to enforce either a dayshift, nightshift or day-off for each day and each employee is the following.

for i in employees:
    for j in days:
        m += D[(i, j)] + N[(i, j)] + V[(i, j)] == 1

To give you some idea what I'm working with, two other constraints are the following:

for i in employees:
    for j in range(1, len(days)-1):
        m += N[(i, j)] + D[(i, (j + 1))] <= 1
        m += N[(i, j)] + D[(i, (j + 2))] <= 1

max_consecutive_days = 4
for i in employees:
    for j in range(1, (len(days)+1 - max_consecutive_days)):
        m += D[(i, j)] + D[(i, j + 1)] + D[(i, j + 2)] + D[(i, j + 3)]+ D[(i, j + 4)] <= max_consecutive_days

Now I want to model two additional constraints. The first one should be fairly simple I hope. If an employee works on saturday (6th day of the week), he/she must also work on sunday (7th day of the week). The idea is that one either works all weekend, or is free all weekend. I tried the following:

for i in employees:
    m += N[(i, 6)] - N[(i, 7)] >= 0
    m += N[(i, 7)] - N[(i, 6)] >= 0

But these constraints turn out to be non-binding of course because when N[(i, 6)] = 0 and N[(i, 7)] = 0 the constraints are also satisfied. First question: how do I rewrite these constraints?

Then, on top of that I also want to implement a way to make sure that employees can only work odd or even weekends but don't really know where to start. I assume I must introduce two extra decision variables "works even-weekends" and "works odd-weekends" and set some constraints to enforce these. So the second question is: how could I implement this?

Ideally I'd rather be able to help myself with these kind of questions so reading materials (specific chapters/sections would be nice) are very welcome as well!

$\endgroup$
5
$\begingroup$

The rule "works on Saturday implies works on Sunday" can be expressed as $$(D_{i,6} \lor N_{i,6}) \implies (D_{i,7} \lor N_{i,7}),$$ which can be rewritten in conjunctive normal form as follows: \begin{equation} \neg (D_{i,6} \lor N_{i,6}) \lor (D_{i,7} \lor N_{i,7}) \\ (\neg D_{i,6} \land \neg N_{i,6}) \lor (D_{i,7} \lor N_{i,7}) \\ (\neg D_{i,6} \lor D_{i,7} \lor N_{i,7}) \land (\neg N_{i,6} \lor D_{i,7} \lor N_{i,7}), \end{equation} yielding linear constraints $$(1- D_{i,6} + D_{i,7} + N_{i,7}) \ge 1) \land (1- N_{i,6} + D_{i,7} + N_{i,7} \ge 1),$$ equivalently $$(D_{i,6} \le D_{i,7} + N_{i,7}) \land (N_{i,6} \le D_{i,7} + N_{i,7}).$$ Because $D_{i,6}+N_{i,6} \le 1$, you can strengthen these as a single constraint $$D_{i,6} + N_{i,6} \le D_{i,7} + N_{i,7}. \tag1$$

More simply, you can rewrite $$\neg V_{i,6} \implies \neg V_{i,7}$$ in conjunctive normal form as $$V_{i,6} \lor \neg V_{i,7},$$ yielding linear constraint $$V_{i,6} + 1 - V_{i,7} \ge 1,$$ equivalently, $$V_{i,6} \ge V_{i,7},$$ which is just the complement of $(1)$.

Your description sounds like you might also want the converse that working Sunday implies working Saturday. If so, that is $$V_{i,7} \ge V_{i,6},$$ so if you want both implications, just impose $$V_{i,6} = V_{i,7}.$$

For your second question, I think you just want some conflict constraints of the form $\text{Odd}_i + \text{Even}_i \le 1,$ together with \begin{align} 1 - V_{i,j} &\le \text{Odd}_i &&\text{for $j$ in odd weekend}\\ 1 - V_{i,j} &\le \text{Even}_i &&\text{for $j$ in even weekend} \end{align}

| improve this answer | |
$\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.