OR-Tools Maximise feasible shift in Employee Scheduling

Question

I work for an NGO and we are trying the organise shifts for the volunteers.

The goal : assigning volunteers to shift maximising the number of feasible shifts and respecting the availiability of everyone.

Number of shift = Number of days of the month (1 shift per day)

Constraints on feasibility of shifts :

• To be feasible a shift must have 3 volunteers
• To be feasible a shift can not exceed 4 volunteers
• To be feasible a shift must have one volunteer considered as a "referent"

Constraints on volunteers :

• A volunteer cannot do more than 3 shifts a day
• A volunteer must do a break of six days between 2 shifts

Based on this example I succeeded to model the problem.

# X_is = 1 if volunteer i is assigned to shift s

var_X = {}

for i in all_volunteers:
    for s in all_shifts:
        var_X[(i, s)] = model.NewBoolVar(f"X_i{i}_s{s}") 

# At least 3 volunteers by shifts

for s in all_shifts:
    model.Add(sum(var_X[i, s] for i in all_volunteers) >= 3)

# Maximum 4 volunteers by shift

for s in all_shifts:
    model.Add(sum(var_X[i, s] for i in all_volunteers) <= 4)

# At least one referent by shift with y[i] = 1 if volunteer i is referent

for s in all_shifts:
    model.Add(sum((var_X[i, s]*y[i]) for i in all_volunteers) >= 1)

# Max 3 shifts by volunteer

for i in all_volunteers:
    model.Add(sum(var_X[i, s] for s in all_shifts) <= 3)

# Break of 6 days between shifts

time_break = 6
range_max = range(nb_shifts - time_break)

for i in all_volunteers:
    for s in range_max:
        model.Add(sum(var_X[i, w] for w in range(s, s + (time_break + 1))) <= 1)

# Objective function with var_D[i][s] = 1 if volunteer i is availiable on shift s:

model.Maximize(
    sum(
        (var_X[(i,s)] * var_D[i][s])
        for i in all_volunteers
        for s in all_shifts
    )
)

All works fine but I have one majors issue:

The current model tries to maximise the assignements but the goal is to the maximise the number of feasible shift (a shift doesn't have to take place every day). How to define the model accordingly ? Should I add a binary variable that encourage the model to produce feasible shift ?

Thanks for your expertise!

Answer 1

create one bool var per shift that will be true if the shift is performed, then maximize the sum of these variables.