Consecutive days of works

Question

I'm trying to make a scheduler with or-tool. I'm currently stuck with the following problem. I want the employees to work at least n consecutive days.

I tried this :

for n in all_nurses:
    for d in all_days:
        if sum([shifts[(n, d, 0)], shifts[(n, d, 1)], shifts[(n, (d), 2)]]) == 1: # if employee works this day, then he should works the 2 days after too
            model.Add(sum([shifts[(n, d+1, 0)], shifts[(n, (d+1), 1)], shifts[(n, (d+1), 2)]]) == 1)
            model.Add(sum([shifts[(n, d+2, 0)], shifts[(n, (d+2), 1)], shifts[(n, (d+2), 2)]]) == 1)

It works with 3 employees, but if I add more employees (10), the model doesn't find any solutions.

Would you have an idea ?

EDIT : I tried to implement the example on https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/examples/python/shift_scheduling_sat.py#L61 But I failed .. Here is my attempt :

for n in all_nurses:
    works = [sum(shifts[n, d, s] for s in all_shifts) for d in all_days]
    print (works)
    for length in range(3, 4):
        for start in range(len(works) - length - 1):
            model.AddBoolOr(negated_bounded_span(works, start, length))
    for start in range(len(works) - 5 - 1):
        model.AddBoolOr([works[i].Not() for i in range(start, start + hard_max + 1)])

I get the error :

AttributeError: '_SumArray' object has no attribute 'Not'

I'm forced to make the sum of the shifts of the day, since I need consecutive days of work, but not in a specific shift.

Also, if someone has a good explanation on how works the method here : https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/examples/python Because I really don't get it how AddBoolOr insure that we have a sequence of true consecutive booleans

EDIT 2 :

I succeeded to implement the solution on the github. But, I still have a problem. I created a mirror of my days/shifts like this :

shifts = {}
mirrors = {}
for n in all_nurses:
    for d in all_days:
        mirrors[(n,d)] = model.NewBoolVar('mirror_n%id%i' % (n, d))
        for s in all_shifts:
            shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d,
                                                                      s))    


#Creation du mirroir
for n in all_nurses:
    for d in all_days:
        model.Add(sum(shifts[(n, d, s)] for s in all_shifts) == mirrors[(n,d)])

Such that for nurse 1 : 0010 0100 0010 1000 0000 0000 0000 Mirror would be : 1 1 1 1 0 0 0

Then I applied the method to have consecutive days of works on my mirror since he is linked to my principal table.

for n in all_nurses:
    works = [mirrors[n,d] for d in range(num_days)]
    for length in range(1, 3):
        for start in range(len(works) - length - 1):
            model.AddBoolOr(negated_bounded_span(works, start, length))
    for start in range(len(works) - 5 - 1):
        model.AddBoolOr([works[i].Not() for i in range(start, start + 5 + 1)])

Now, I would expect the result to not have any period of work not comprised between 3 and 5. But still, when I print the solution, for one nurse, I got the following result :

0010 0010 0010 0010 0010 0000 0000 0000 0001 0000

And for the mirror it is :

1111100010

This should not be possible, since a period of work is comprised between 3 and 5.

Would you have an idea ? Thanks!

Your further edit would be better asked as a new question. You can link to this one for background. — CrazyChucky

Laurent Perron Laurent Perron · Accepted Answer · 2019-04-16T01:08:58

This is implemented as a soft version in shift_scheduling_sat.py

See: https://github.com/google/or-tools/blob/39f44709bba203f5ff3bc18fab8098739f189a6d/examples/python/shift_scheduling_sat.py#L61

in

    # Forbid sequences that are too short.
    for length in range(1, hard_min):
        for start in range(len(works) - length - 1):
            model.AddBoolOr(negated_bounded_span(works, start, length))

Consecutive days of works

1 Answers