OR-Tools Nurse scheduling shift_scheduling_sat.py questions/problems

Question

I am trying to use Google's OR-Tools or more specifically the example shift_scheduling_sat.py which was more comprehensive and is closer to the features that I want. The problem I need to be done is still the same (distribution of workers into set shifts) and I am just having trouble adding the things I want. For example, I want to set the number of workers in a single shift to be only one, as with the simpler example shown in their guide, which is done by:

for d in all_days:
    for s in all_shifts:
        model.Add(sum(shifts[(n, d, s)] for n in all_nurses) == 1)

Which I could maybe do, but the example itself has a method wherein I can set the number of workers in a given workday:

weekly_cover_demands = [
    (2, 3, 1),  # Monday
    (2, 3, 1),  # Tuesday
    (2, 2, 2),  # Wednesday
    (2, 3, 1),  # Thursday
    (2, 2, 2),  # Friday
    (1, 2, 3),  # Saturday
    (1, 3, 1),  # Sunday
]

So I tried setting all of their values to: (1,1,1) indicating that only one worker should be selected for the specified shift and to comment out the line indicating the constraint on the number of rest per week a worker should have:

# Weekly sum constraints on shifts days:
#     (shift, hard_min, soft_min, min_penalty,
#             soft_max, hard_max, max_penalty)
weekly_sum_constraints = [
    # Constraints on rests per week.
    # removing constraints on rests
    #(0, 1, 2, 7, 2, 3, 4),
    # At least one night-shift per week (penalized). At most 4 (hard).
    (3, 0, 1, 3, 4, 4, 0),
]

The solution, however, took some time so I had to add the solver.parameters.max_time_in_seconds variable to limit the time involved searching for the solution, which should theoretically be easy. The result is as follows:

          M T W T F S S M T W T F S S M T W T F S S 
worker 0: O M O M O O N N O M O O M O O N N O O A O
worker 1: O M N N O O M O O A O N N O O M O O A O O
worker 2: M A O O A O O A O O A O O N N O O A O O A
worker 3: M A O A O O A O O M O O A O O A O O M O O
worker 4: A A O O N N O O A O O A O O A O O N N O O
worker 5: A O M O O M O O N N N O O M O O M O O M O
worker 6: O O A A O A O O M O O M O O M O O M O O M
worker 7: N N O O M O O M O O M O O A O O A O O N N

With the first two days having two workers in several shifts and the rest being correct (O being a 'day-off'). Why did it didn't work in the first two days and not the rest of the days?

I feel like the simpler example would be the one on their guide page but it is lacking for my needs. I still have lots of problems and questions about this such as;

How does one go about making their own constraint? I could somewhat understand the simpler guide example but I am still going through this one, would love to have an explanation of how they used model.Add, model.Minimize and how to use model.Maximize
On earlier examples it shows the problems in an algebraic format of finding for values for x and y etc etc, which I could understand a bit, but how would I go about implementing a system that say for example make the nurse preferably take the same shift as he did the previous time up to an arbitrary maximum limit. Like maybe create a pattern of some sort to evaluate if it fits it.
What does the penalty score mean and evaluate to? for example in the list: weekly_sum_constraints there is talk of having at list one night-shift per week "penalized" with the value of 3 and a "hard" penalty of 0 (which I assume is a solid rule that could not be broken), what does the value 3 and 0 mean and how are these values chosen?

Thanks for the help, I've been googling up 'constraint programming' trying to understand this but they were no specifically for this library, but I am still searching.

Laurent Perron Laurent Perron · Accepted Answer · 2020-10-05T15:31:23

There are no silver bullet answers.

read the code. There are no constraints, just modeling. The constraints of the model are linear equations, and Boolean constraints (and, or, implication).
if you want a specific list of allowed patterns or forbidden ones, you can look at the allowed assignment (forbidden assignment) constraint. See the doc entry. This constraint is used in this example.
Look at the penalized version of on soft constraints. It always results in creating a Boolean variable that is true if the penalty should be applied. Then the term bool_var * weight is added to the linear expression in the minimize part.

OR-Tools Nurse scheduling shift_scheduling_sat.py questions/problems

1 Answers