3141 Words

Reading time 15 min

0 google-or-tools 26 code 6 cp_sat

More Automaton Fun

After the success of my experiment at splitting up the DFA documented in my last post, I now want to try more difficult constraints. Specifically, I was wondering about how to implement a constraint that gives everybody at least one two-day “weekend” every two weeks or so.

Two days off in a row

Back when I used to work at a hardware store between sophomore and junior year, I hated the fact that I didn’t have two days off in a row. We were all hourly workers, and while we all got between 30 and 40 hours per week, it was pretty rare that anybody would get two days off back to back without putting in a request. More recently, my daughter was working at PaperSource in Manhattan only 20hrs per week, and she would sometimes get scheduled five days in a row for 2 hours each. Given the commute time from Brooklyn, that was a terrible situation. That isn’t relevant to this case, but the rule to make that not happen is similar.

So what if the scheduler (corporate overlord) was benevolent and wanted to assign two days off in a row every two weeks. I’m pretty sure I could do it with the usual combination of conditional constraints and counting up shifts, but I want to do it with a DFA.

Modify an existing DFA to get what I want

I actually figured this out while sitting and knitting a scarf. I just played with ideas in my head and I think I hit on the solution. But as I type this, I haven’t yet actually tried the solution, so maybe it won’t work.

For this blog, I am going to repeat my thought process, which started with the idea of the “one off shift after at most three days of work” DFA. This is reproduced below.

finite_state_machine Off Off Off->Off off ~Off-S1 ~Off-S1 Off->~Off-S1 not off ~Off-S1->Off off ~Off-S2 ~Off-S2 ~Off-S1->~Off-S2 not off ~Off-S2->Off off ~Off-S3 ~Off-S3 ~Off-S2->~Off-S3 not off ~Off-S3->Off off

The reason why this works is that various nodes are designed to track state. “~Off-S3” is by definition the third shift in a row that is not an off shift. There is no way to get to that node without first passing through exactly two other non-off shift nodes.

So my first thought was to create a double off shift sequence, and link it up somehow to the existing shifts.

finite_state_machine Off Off ~Off-S1 ~Off-S1 Off->~Off-S1 not off ~Off-S1->Off off ~Off-S2 ~Off-S2 ~Off-S1->~Off-S2 not off Two Day Off 1 Two Day Off 1 ~Off-S1->Two Day Off 1 off ~Off-S2->Off off ~Off-S3 ~Off-S3 ~Off-S2->~Off-S3 not off ~Off-S2->Two Day Off 1 off ~Off-S3->Off off ~Off-S3->Two Day Off 1 off Two Day Off 2 Two Day Off 2 Two Day Off 1->Two Day Off 2 off Two Day Off 2->Two Day Off 2 off

This is not a complete DFA because it is clearly never going to work. There is an obvious problem in that I can’t transition to two different places with the identical assignment of “off”. It makes no sense that “off” shift assigned after, say “~Off-S2” would lead to both the root “off” node as well as the start of the potential two day off sequence. What I want to do is to let the solver decide when to slot in the two off days, but this isn’t going to cut it.

Then I hit on the idea of just one node for the two day off sequence, and that node (and only that node) can transition to the starting of the non-off nodes. Suppose the rule is two days off in a row every seven days. Then I want a DFA that looks something like this:

finite_state_machine ~Off-S1 ~Off-S1 ~Off-S2 ~Off-S2 ~Off-S1->~Off-S2 on Off-S2 Off-S2 ~Off-S1->Off-S2 off ~Off-S3 ~Off-S3 ~Off-S2->~Off-S3 on Off-S3 Off-S3 ~Off-S2->Off-S3 off ~Off-S4 ~Off-S4 ~Off-S3->~Off-S4 on Off-S4 Off-S4 ~Off-S3->Off-S4 off ~Off-S5 ~Off-S5 ~Off-S4->~Off-S5 on Off-S5 Off-S5 ~Off-S4->Off-S5 off Off-S6 Off-S6 ~Off-S5->Off-S6 on Two Day Off Two Day Off Off-S2->Two Day Off off Off-S3->Two Day Off off Off-S4->Two Day Off off Off-S5->Two Day Off off Off-S6->Two Day Off off Two Day Off->~Off-S1 on Two Day Off->Two Day Off off

That is close, but I forgot to transition from all the one-day-off nodes back to the following not off node. Adding those in:

finite_state_machine ~Off-S1 ~Off-S1 ~Off-S2 ~Off-S2 ~Off-S1->~Off-S2 on Off-S2 Off-S2 ~Off-S1->Off-S2 off ~Off-S3 ~Off-S3 ~Off-S2->~Off-S3 on Off-S3 Off-S3 ~Off-S2->Off-S3 off ~Off-S4 ~Off-S4 ~Off-S3->~Off-S4 on Off-S4 Off-S4 ~Off-S3->Off-S4 off ~Off-S5 ~Off-S5 ~Off-S4->~Off-S5 on Off-S5 Off-S5 ~Off-S4->Off-S5 off Off-S6 Off-S6 ~Off-S5->Off-S6 on Off-S2->~Off-S3 on Two Day Off Two Day Off Off-S2->Two Day Off off Off-S3->~Off-S4 on Off-S3->Two Day Off off Off-S4->~Off-S5 on Off-S4->Two Day Off off Off-S5->Two Day Off off Off-S6->Two Day Off off Two Day Off->~Off-S1 on Two Day Off->Two Day Off off

(Incidentally, I just learned how to turn off the default size of the generated SVG for these graphs, and also how to tell Graphviz to keep nodes on the same rank. That is the side effect of writing blog posts—I learn about new things like Quarto and remember things I’d forgotten like Graphviz!)

Code up the new constraint

I don’t expect that the existing problem will have any valid assignments if I just add in this new constraint, but I’m going to do it anyway. Worst case scenario it won’t find any solutions, but I can just add nurses until I get a good solution.

Everything is the same as my previous two posts, so I am just going to add the code for what has changed. Here, I translate the DFA graph into a list of states and transitions.

# Automaton 3: At least two days off in a row every 7 days,
# so no more than 5 days working in 7
states: dict[str, int] = {
    "on1": 1,
    "on2": 2,
    "on3": 3,
    "on4": 4,
    "on5": 5,
    "off2": 6,
    "off3": 7,
    "off4": 8,
    "off5": 9,
    "off6": 10,
    "TwoDayOff": 11,
}
assignments: dict[str, int] = {
    "off": 0,
    "on": 1,
}
transitions_constraint: list[tuple[int, int, int]] = [
    (states["on1"],  assignments["on"],  states["on2"]),
    (states["on1"], assignments["off"], states["off2"]),
    (states["on2"],  assignments["on"],  states["on3"]),
    (states["on2"], assignments["off"], states["off3"]),
    (states["on3"],  assignments["on"],  states["on4"]),
    (states["on3"], assignments["off"], states["off4"]),
    (states["on4"],  assignments["on"],  states["on5"]),
    (states["on4"], assignments["off"], states["off5"]),

    (states["on5"], assignments["off"], states["off6"]),

    (states["off2"],  assignments["on"],  states["on3"]),
    (states["off2"],  assignments["off"],  states["TwoDayOff"]),
    (states["off3"],  assignments["on"],  states["on4"]),
    (states["off3"],  assignments["off"],  states["TwoDayOff"]),
    (states["off4"],  assignments["on"],  states["on5"]),
    (states["off4"],  assignments["off"],  states["TwoDayOff"]),

    (states["off5"],  assignments["off"],  states["TwoDayOff"]),

    (states["off6"],  assignments["off"],  states["TwoDayOff"]),

    (states["TwoDayOff"],  assignments["off"],  states["TwoDayOff"]),
    (states["TwoDayOff"],  assignments["on"],  states["on1"]),

]
initial_state = states["TwoDayOff"]
accepting_states = list(states.values())

If I had to do this for a real problem, I would probably create a dummy initial node that can transition to any of the “On” shifts. The above will work, but the first shift will either be the day one shift, or an off shift. In a real world problem I’d want more flavors there I think.

Running it

As I expected, it did not work:

$ python src/call_scheduler/test_twodaysoff.py
No solution!

NumSolutions: 0
NumConflicts: 31276
NumBranches: 164358
WallTime: 4.730050411000001

Just to make sure that this constraint was coded up correctly, I turned off the other two automaton constraints. In that case the solver found solutions, and visually inspecting them you can see that everybody has two off days in a row at least every 7 days.

$ python src/call_scheduler/test_twodaysoff.py
Nurse0:  o n o o o d n o o o n d d d  day_stat: [('o', 7), ('n', 3), ('d', 4)] total: 7 workdays
Nurse1:  d o o d n n d o o o o o d d  day_stat: [('d', 5), ('o', 7), ('n', 2)] total: 7 workdays
Nurse2:  o o d o o d d d d d o o n n  day_stat: [('o', 6), ('d', 6), ('n', 2)] total: 8 workdays
Nurse3:  n n n n d o o n d n d d o o  day_stat: [('n', 6), ('d', 4), ('o', 4)] total: 10 workdays
Nurse4:  d d d d d o o d d d d n o o  day_stat: [('d', 9), ('o', 4), ('n', 1)] total: 10 workdays
Nurse5:  n d d d d o o n n n n n o o  day_stat: [('n', 6), ('d', 4), ('o', 4)] total: 10 workdays
Nurse6:  d d n n n o o d n d d d o o  day_stat: [('d', 6), ('n', 4), ('o', 4)] total: 10 workdays

Statistics per day:
Day 0:  3 2 2
Day 1:  3 2 2
Day 2:  3 2 2
Day 3:  3 2 2
Day 4:  3 2 2
Day 5:  2 1 4
Day 6:  2 1 4
Day 7:  3 2 2
Day 8:  3 2 2
Day 9:  3 2 2
Day10:  3 2 2
Day11:  3 2 2
Day12:  2 1 4
Day13:  2 1 4

Nurse0:  n o o n o d n o o o n o d d  day_stat: [('n', 4), ('o', 7), ('d', 3)] total: 7 workdays
Nurse1:  o n o o n n d o o o o d d d  day_stat: [('o', 7), ('n', 3), ('d', 4)] total: 7 workdays
Nurse2:  o o d o o d d n d n o o n n  day_stat: [('o', 6), ('d', 4), ('n', 4)] total: 8 workdays
Nurse3:  d n n n n o o n d n d n o o  day_stat: [('d', 3), ('n', 7), ('o', 4)] total: 10 workdays
Nurse4:  d d d d d o o d d d d n o o  day_stat: [('d', 9), ('o', 4), ('n', 1)] total: 10 workdays
Nurse5:  n d d d d o o d n d n d o o  day_stat: [('n', 3), ('d', 7), ('o', 4)] total: 10 workdays
Nurse6:  d d n d d o o d n d d d o o  day_stat: [('d', 8), ('n', 2), ('o', 4)] total: 10 workdays

Statistics per day:
Day 0:  3 2 2
Day 1:  3 2 2
Day 2:  3 2 2
Day 3:  3 2 2
Day 4:  3 2 2
Day 5:  2 1 4
Day 6:  2 1 4
Day 7:  3 2 2
Day 8:  3 2 2
Day 9:  3 2 2
Day10:  3 2 2
Day11:  3 2 2
Day12:  2 1 4
Day13:  2 1 4

2 solutions should be enough...

NumSolutions: 2
NumConflicts: 3
NumBranches: 16898
WallTime: 0.109424583

If I turn on the constraint requiring that there are no more than two night shifts in a row, I get this result:

$ python src/call_scheduler/test_twodaysoff.py
Nurse0:  o n o o o n d o o o n n d n  day_stat: [('o', 7), ('n', 5), ('d', 2)] total: 7 workdays
Nurse1:  n o o n n d d o o o o o n d  day_stat: [('n', 4), ('o', 7), ('d', 3)] total: 7 workdays
Nurse2:  o o n o o d n n d n o o d d  day_stat: [('o', 6), ('n', 4), ('d', 4)] total: 8 workdays
Nurse3:  n d d n n o o n n d n n o o  day_stat: [('n', 7), ('d', 3), ('o', 4)] total: 10 workdays
Nurse4:  d n n d d o o d n n d d o o  day_stat: [('d', 6), ('n', 4), ('o', 4)] total: 10 workdays
Nurse5:  d d d d d o o d d d d d o o  day_stat: [('d', 10), ('o', 4)] total: 10 workdays
Nurse6:  d d d d d o o d d d d d o o  day_stat: [('d', 10), ('o', 4)] total: 10 workdays

Statistics per day:
Day 0:  3 2 2
Day 1:  3 2 2
Day 2:  3 2 2
Day 3:  3 2 2
Day 4:  3 2 2
Day 5:  2 1 4
Day 6:  2 1 4
Day 7:  3 2 2
Day 8:  3 2 2
Day 9:  3 2 2
Day10:  3 2 2
Day11:  3 2 2
Day12:  2 1 4
Day13:  2 1 4

Nurse0:  o n o o o n d o o o n n d d  day_stat: [('o', 7), ('n', 4), ('d', 3)] total: 7 workdays
Nurse1:  n o o n n d d o o o o o n n  day_stat: [('n', 5), ('o', 7), ('d', 2)] total: 7 workdays
Nurse2:  o o n o o d n n d n o o d d  day_stat: [('o', 6), ('n', 4), ('d', 4)] total: 8 workdays
Nurse3:  n d d n n o o n n d n n o o  day_stat: [('n', 7), ('d', 3), ('o', 4)] total: 10 workdays
Nurse4:  d n n d d o o d n n d d o o  day_stat: [('d', 6), ('n', 4), ('o', 4)] total: 10 workdays
Nurse5:  d d d d d o o d d d d d o o  day_stat: [('d', 10), ('o', 4)] total: 10 workdays
Nurse6:  d d d d d o o d d d d d o o  day_stat: [('d', 10), ('o', 4)] total: 10 workdays

Statistics per day:
Day 0:  3 2 2
Day 1:  3 2 2
Day 2:  3 2 2
Day 3:  3 2 2
Day 4:  3 2 2
Day 5:  2 1 4
Day 6:  2 1 4
Day 7:  3 2 2
Day 8:  3 2 2
Day 9:  3 2 2
Day10:  3 2 2
Day11:  3 2 2
Day12:  2 1 4
Day13:  2 1 4

2 solutions should be enough...

NumSolutions: 2
NumConflicts: 0
NumBranches: 20513
WallTime: 0.12906609500000002

In fact, the reason the problem has no solutions is the conflict between the other “off” shift DFA, and this one. Apparently these two graphs conflict:

finite_state_machine ~Off-S1 ~Off-S1 ~Off-S2 ~Off-S2 ~Off-S1->~Off-S2 on Off Off ~Off-S1->Off off ~Off-S3 ~Off-S3 ~Off-S2->~Off-S3 on ~Off-S2->Off off ~Off-S3->Off off Off->~Off-S1 on Off->Off off

It looks to me like this constraint is perfectly compatible with the two days off in seven constraint, so what is most likely happening is that there aren’t enough nurses to satisfy both constraints while also satisfying the per day shift coverage constraints.

If I bump up the nurses to 8, I also had to make corresponding changes in the daily assignments, as there is a hard requirement for the number of off shifts per day. I just deleted that requirement, and the solver found solutions.

for j in range(num_days):
  for t in shifts:
    b = [model.NewBoolVar("") for i in range(num_nurses)]
    for i in range(num_nurses):
      model.Add(x[i,j] == t).OnlyEnforceIf(b[i])
      model.Add(x[i,j] != t).OnlyEnforceIf(b[i].Not())
    model.Add(day_stat[j, t] == sum(b))
  if j % 7 == 5 or j % 7 == 6:
    # special constraints for the weekends
    model.Add(day_stat[j, day_shift] == 2)
    model.Add(day_stat[j, night_shift] == 1)
    # model.Add(day_stat[j, off_shift] == 4)
  else:
    # workdays:
    # - exactly 3 on day shift
    model.Add(day_stat[j, day_shift] == 3)
    # - exactly 2 on night
    model.Add(day_stat[j, night_shift] == 2)
    # # - exactly 2 off duty
    # model.Add(day_stat[j, off_shift] == 2)

The only change is to comment out the “exactly” constraints on the off-duty shifts for weekdays and weekends. The result looks good. Nobody works more than three days in a row without getting an off shift. Nobody works more than two night shifts in a row. And everybody gets two off shifts in a row every seven days.

$ python src/call_scheduler/test_twodaysoff.py
Nurse0:  o d o o d d d o d o o n n d  day_stat: [('o', 6), ('d', 6), ('n', 2)] total: 8 workdays
Nurse1:  o d d o n d o o d d d o d o  day_stat: [('o', 6), ('d', 7), ('n', 1)] total: 8 workdays
Nurse2:  d d o o o n o d n n o o d d  day_stat: [('d', 5), ('o', 6), ('n', 3)] total: 8 workdays
Nurse3:  o n n d o o n d d o d o o o  day_stat: [('o', 7), ('n', 3), ('d', 4)] total: 7 workdays
Nurse4:  n o n n o o d o n o o n o n  day_stat: [('n', 6), ('o', 7), ('d', 1)] total: 7 workdays
Nurse5:  n n o d d o o n o d n d o o  day_stat: [('n', 4), ('o', 6), ('d', 4)] total: 8 workdays
Nurse6:  d o d d n o o n o n n d o o  day_stat: [('d', 4), ('o', 6), ('n', 4)] total: 8 workdays
Nurse7:  d o d n d o o d o d d d o o  day_stat: [('d', 7), ('o', 6), ('n', 1)] total: 8 workdays

Statistics per day:
Day 0:  3 2 3
Day 1:  3 2 3
Day 2:  3 2 3
Day 3:  3 2 3
Day 4:  3 2 3
Day 5:  2 1 5
Day 6:  2 1 5
Day 7:  3 2 3
Day 8:  3 2 3
Day 9:  3 2 3
Day10:  3 2 3
Day11:  3 2 3
Day12:  2 1 5
Day13:  2 1 5

Nurse0:  o n d d o d o o d d n o d o  day_stat: [('o', 6), ('n', 2), ('d', 6)] total: 8 workdays
Nurse1:  d o o d d o d o o o d d d o  day_stat: [('d', 7), ('o', 7)] total: 7 workdays
Nurse2:  o n d o o n o d n d o o n d  day_stat: [('o', 6), ('n', 4), ('d', 4)] total: 8 workdays
Nurse3:  d d o d d o o n d n o n o o  day_stat: [('d', 5), ('o', 6), ('n', 3)] total: 8 workdays
Nurse4:  n d o n o o d n d o n o o n  day_stat: [('n', 5), ('d', 3), ('o', 6)] total: 8 workdays
Nurse5:  n d d o n o o d o d d d o o  day_stat: [('n', 2), ('d', 6), ('o', 6)] total: 8 workdays
Nurse6:  d o n n d o o d n o d d o o  day_stat: [('d', 5), ('o', 6), ('n', 3)] total: 8 workdays
Nurse7:  o o n o n d n o o n o n o d  day_stat: [('o', 7), ('n', 5), ('d', 2)] total: 7 workdays

Statistics per day:
Day 0:  3 2 3
Day 1:  3 2 3
Day 2:  3 2 3
Day 3:  3 2 3
Day 4:  3 2 3
Day 5:  2 1 5
Day 6:  2 1 5
Day 7:  3 2 3
Day 8:  3 2 3
Day 9:  3 2 3
Day10:  3 2 3
Day11:  3 2 3
Day12:  2 1 5
Day13:  2 1 5

2 solutions should be enough...

NumSolutions: 2
NumConflicts: 96
NumBranches: 29215
WallTime: 0.27412520500000004

So this is exciting to me because it shows that I can split up a set of constraints into independent DFAs, and that OR-Tools will combine them without much fuss. That means I can start to tackle my really big doctor-scheduling project with this new tool in my kit, and hopefully improve the code base to make it more maintainable. And I also now have a new tool for tackling any problems that new clients bring me.