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.

Answer 2

Bonjour Laurent !

Thanks a lot for the suggestion it worked. Here is the full code :

!pip install --upgrade ortools
from ortools.sat.python import cp_model
import pandas as pd


def get_availiabilities_df(volunteers_availiabilities):
    df = pd.DataFrame({"volunteers": list(volunteers_availiabilities.values())})
    availiabilities_df = df['volunteers'].apply(pd.value_counts).fillna(0).astype(int)
    ids = list(volunteers_availiabilities.keys())
    availiabilities_df.index = ids
    availiabilities_df = availiabilities_df.reindex(sorted(availiabilities_df.columns), axis=1)

    return availiabilities_df


volunteers_availiabilities = {
  "vol_1":[23],
  "vol_2":[4,9,10,16,17,23,24],
  "vol_3":[16],
  "vol_4":[8,15,24],
  "vol_5":[2,9,16],
  "vol_6":[7,10,11,12,13,14,21,23,24,25,26,28],
  "vol_7":[7,14,21,28],
  "vol_8":[1,2,4,5,6,7,8,11,12,13,14,15,17,18,19,21,24,25,26,28],
  "vol_9":[2,9,10,16,17,19,21,23,24],
  "vol_10":[4,8,10,11,17],
  "vol_11":[4,9,10,11,16,17,18,23,24,25],
  "vol_12":[9,10,23,24],
  "vol_13":[16,17,23,24],
  "vol_14":[4,9,10,11,16,17,18,25],
  "vol_15":[11],
  "vol_16":[4,10,17],
  "vol_17":[1,2,4,8,10,11,12,13,15,18,19,23,24,25,26,28],
  "vol_18":[6,12,13],
  "vol_19":[2,10,16,17,23,24],
  "vol_20":[25],
  "vol_21":[4,11,12,25],
  "vol_22":[2,7,10,11,15,19,21,23]
}

availiabilities_df = get_availiabilities_df(volunteers_availiabilities)
var_D = availiabilities_df.to_numpy()

# Referents 
referents = ['vol_1','vol_2','vol_4','vol_5','vol_6','vol_7','vol_8','vol_9','vol_10','vol_11','vol_14','vol_15']

df_volunteers = pd.DataFrame({"volunteers": list(volunteers_availiabilities.keys())})
df_volunteers = df_volunteers.to_numpy()

y = []

for vol in df_volunteers:
  if(vol in referents):
    y.append(1)
  else :
    y.append(0)

# Initialisation
nb_vols = len(volunteers_availiabilities)
nb_perms = availiabilities_df.shape[1]

all_volunteers = range(nb_vols)
all_permanence = range(nb_perms)

model = cp_model.CpModel()
var_X = {}

for i in all_volunteers:
    for p in all_permanence:
        var_X[(i, p)] = model.NewBoolVar(f"X_i{i}_p{p}")

min_volunteers = 3
max_volunteers = 4

is_feasible = {}
var_nb_ref = {}


# Constraints on shift
for p in all_permanence:
    is_feasible[(p)] = model.NewBoolVar(f"V_nb_vols{p}")

    # Min 3 volunteers by shift
    model.Add(sum((var_X[i, p] * var_D[i][p]) for i in all_volunteers) >= min_volunteers).OnlyEnforceIf(is_feasible[p])

    # Max 4 volunteers by shift
    model.Add(sum((var_X[i, p] * var_D[i][p]) for i in all_volunteers) <= max_volunteers).OnlyEnforceIf(is_feasible[p])

    # At least one referent by shift
    model.Add(sum(((var_X[i, p] * var_D[i][p])*y[i]) for i in all_volunteers) >= 1).OnlyEnforceIf(is_feasible[p])


# Constraints on Volunteers

# Max 3 shift every month
for i in all_volunteers:
    model.Add(sum(var_X[i, p] for p in all_permanence) <= 3)

# Break of 6 days between shift
time_break = 6
range_max = range(nb_perms - time_break)

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


# Objective function 

model.Maximize(
    sum(
        is_feasible[p]
        for p in all_permanence
    )
)

solver = cp_model.CpSolver()

solution_printer = cp_model.ObjectiveSolutionPrinter()
status = solver.Solve(model, solution_printer)

print(f"Status = {solver.StatusName(status)}")
print(f"Number of solutions found: {solution_printer.solution_count()}")


## PRINTER

def get_volunteer_name(df, id):
  return df.index[id]

def get_volunteer_id(df, name):
  return df[name]

def get_day_name(df, id):
  return df.columns[id]


if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print("Solution:")
    nb_perm_organised = 0;
    nb_assignement = 0;
    volunteers_assigned = []  

    for p in all_permanence:
        day = get_day_name(availiabilities_df, p)
        nb_availiable = 0;
        volunteer_list = []
        print(f"Jour {day} du mois")
        if (solver.Value(is_feasible[(p)])) == 1:
          nb_perm_organised += 1;
          for i in all_volunteers:
            if solver.Value(var_X[(i, p)]) == 1:
              nb_assignement +=1
              vol_name = get_volunteer_name(availiabilities_df, i)
              volunteer_list.append(vol_name)
              volunteers_assigned.append((vol_name, p))
          print(f"Permanence possible avec {str(volunteer_list)}")
        print()
    print(f"Number of perm organised = {str(nb_perm_organised)} out of {nb_perms}")
    print(f"Number of assignement to perm = {str(nb_assignement)}")

else:
    print("No solutions found !")