Scheduling : How to enforce consecutiveness of shifts for an employee

I have a scheduling problem where an employee can work maximum of say, 4 hours out of total allowable 8 hours in a day. For these 4 hours, I want them to be consecutive.

For example, decision variables (binary) are whether an employee will work in a particular hour or not. So a sample solution could look like below:

hrs : 0 1 2 3 4 5 7  [8 hours in a day]
dv  : 0 1 1 1 1 0 0  [employee works from 2nd hour through 5th hour]

A solution / approach in an open-source solver would really help me.

To allow a maximum of one shift restrict the number of starts. A start happens when we go from dv[t-1]=0 to dv[t]=1.

 start[t] >= dv[t] - dv[t-1]   for all t
 sum(t,start[t]) <= 1
 start[t] ∈ {0,1} (or even ∈ [0,1])

This will give you just one start, so one shift. This is a fairly standard formulation that is used very often in scheduling. Worthwhile to know.

This can be formulated as a mixed integer linear program. My approach is as follows:

1. Create binary variables by employee (e) by hour of the day (t), s_et

2. Calculate shift changes, and store them in a variable, say, w_et, so:
   w_et = s_et - s_et-1, for t > 0, e

3. w_e0 = s_e0, for all e

4. Create binary variable, that will capture when the shift will start, say, v_et, put the following constraint:
   v_et = max(0, w_et), for all e, t

5. we want shift to only start once, so enforce the following constraint:
   sum_over_t(v_et) <= 1, for all e

Below is the implementation of the above in Google-OR-tool's linear solver. Please note that we will have to linearise the max function.

from ortools.linear_solver import pywraplp
s = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

shift_length = 8

# decision variable : whether the shift was worked or not
# s_t following above explanation. I have taken 1 employee for simplicity
shift_bool = 
展开收缩

# constraint : employee can work for max 4 hours
s.Add(sum(shift_bool) == 4)

# decision variable : capture shift changes from one hour to another.
# w_t following above explanation.
shift_diff = 
展开收缩
for i in range(shift_length - 1):
    s.Add(shift_diff[i+1] == shift_bool[i+1] - shift_bool[i])

# for first hour:
s.Add(shift_diff[0] == shift_bool[0])

# decision variable : to capture shift start
# v_t following above explanation
shift_max = 
展开收缩
s.Add(sum(shift_max) == 1)

# we need to linearise the `max` operation, so say, u = max(a0, a1, a2)
# u >= a_i, for all i
# u <= a_i + (1 - b_i) * M, for all I
# sum_over_i(b_i) = 1
# b_i is binary variable
# M is the upper bound on u

# I have implemented the above logic below:
# essentially, for each hour we need to take max between
# 0 and shift_diff
for i in range(shift_length):
    bool_var = 
展开收缩
    s.Add(shift_max[i] >= shift_diff[i])
    s.Add(shift_max[i] >= 0)
    s.Add(shift_max[i] <= shift_diff[i] + (1 - bool_var[0]) * 5)
    s.Add(shift_max[i] <= 0 + (1 - bool_var[0]) * 5)
    s.Add(sum(bool_var) == 1)
    
# dummy objective
obj = sum(shift_bool)
s.Minimize(obj)
s.Solve()

# shift_assigned values:
[shift_bool[i].SolutionValue() for i in range(shift_length)]
# [0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]
   

just to play around, if you add an additional constraint : s.Add(shift_bool[0] + shift_bool[1] == 0), then the solution looks as follows: [0, 0, 0, 1, 1, 1, 1, 0]