Maximum-length-series-of-shifts slow down solving speed

2022-05-22
2 min read

This project is an answer project for StackOverflow per the following link.

https://stackoverflow.com/questions/63546231/maximum-length-series-of-shifts-in-google-or-tools-employee-scheduling

Specifications

… However I keep struggling to implement the following rule:

Employees cannot work more than 5 consecutive days. The code natively supports bounds on the length of series of the same shift type (e.g. forbid n consecutive morning shifts or night shifts). However, there is no way to limit the length of series of back-to-back shifts if they are not of the same type (e.g. night/night/morning/night/morning).

I managed to implement this rule by adding the following piece of code:


    for e in range(num_employees):
            for d in range(num_days):                 
                   model.Add(work[e, 0, d] == 1).OnlyEnforceIf( (work[e, 1, d-5] or work[e, 2, d-5] or work[e, 3, d-5] or work[e, 4, d-5] )
                                                                and (work[e, 1, d-4] or work[e, 2, d-4] or work[e, 3, d-4] or work[e, 4, d-4] )
                                                                and (work[e, 1, d-3] or work[e, 2, d-3] or work[e, 3, d-3] or work[e, 4, d-3] )
                                                                and (work[e, 1, d-2] or work[e, 2, d-2] or work[e, 3, d-2] or work[e, 4, d-2] )
                                                                and (work[e, 1, d-1] or work[e, 2, d-1] or work[e, 3, d-1] or work[e, 4, d-1] ))

However, this implementation increases the run-time of the program drastically (from 30 seconds without the constraints, to about 15 minutes including it). Therefore I’m looking for a way to prohibit employees from being scheduled 5 or more consecutive days that doesn’t increase run-time as much.

Implementation

We have implemented it ,based on the following project.
Long-term balancing for nurse scheduling problem

Define Shifts

Note that the rest is the complement of Woking Shifts.

We describe the fig.above as follows.  

Row Constraints

There are two ways to prohibit working more than 5 consecutive days: method 1 and method 2.
Either may be used. No performance difference will occur at least up to 20 shifts in Schedule Nurse Ⅲ.
✓ is complement of the shift.
Note that Day Type includes the last 5 days of the last month to avoid discontinuity from last month.

Solve it!

Solution

Project File

File → Open Project File from Github