Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (`python`)

Question

I am trying to write a program to schedule a team of 8 individuals into shifts.

I want to know how to model that every individual must get at least one night shift break, and must not work two consecutive shifts. Finally, we want to ensure as close to equal numbers of night shifts and total shifts for each individual as possible.

More specifically I have the following problem:

• 8 Individuals
• 3 Shifts per day (morning, afternoon, night)
• 18 Days

I want to distribute individuals to shifts to meet the following criteria:

1. There must be 3 people on each shift
2. Every individual must work 1 shift per day
3. Every individual must not work more than 2 shifts per day
4. Every individual must get at least one night shift break, preferably two. This means that individual A can work night shift 1, but then cannot work night shift 2 (and preferably not 3), returning to night shift 4. I.e. each individual must do a maximum of 1 night shift in every 2 nights, preferably 1 night shift in every 3 night shifts.
5. We should distribute these shifts as evenly as possible, especially night shifts but also the total number of shifts.
6. Each individual must not work consecutive shifts (e.g. the night shift on Day 1 and the morning shift on Day 2)

I need to know how to either write these as constraints or otherwise, to include them in an objective function.

As an objective function: I have considered minimising the maximum difference in the number of night shifts, or else, minimising the maximum difference in the total number of shifts.

I need some help writing this as a mathematical model. I don't know where to start with this!

Answer 1

There are certainly different ways of achieving what you want. Here is how I would proceed:

Start by predefining the set of all possible schedules which satisfy your constraints $2,3,4,6$. Although there are many, I believe that with your constraints, it may be not too difficult to derive them somewhat automatically. Here is a subset of them in the table below, if there were only $3$ days.

$$ \begin{array}{l|l|l|l|l|l|l} & & Schedule 1 & Schedule 2 & Schedule 3 & … & Required \\ {Day 1} & Morning & 1 & 0 & 1 & & 3 \\ & Afternoon & 1 & 1 & 1 & & 3 \\ & Night & 0 & 1 & 0 & & 3 \\ {Day 2} & Morning & 1 & 0 & 1 & & 3 \\ & Afternoon & 1 & 1 & 1 & & 3 \\ & Night & 0 & 0 & 0 & & 3 \\ {Day 3} & Morning & 1 & 1 & 0 & & 3 \\ & Afternoon & 1 & 1 & 0 & & 3 \\ & Night & 0 & 0 & 1 & & 3 \end{array} $$

You can see the the above schedules do satisfy constraints $2,3,4,6$.

Once you have your schedules, you can solve your problem as follows. Define a binary variable $x_i$ for each schedule $i \in I$, and a binary parameter $a_{ij}$ that takes value $1$ if and only if schedule $i \in I$ is "active" during shift $j \in J$. So for example, for the first schedule, $a_{11}=1$, but $a_{13}=0$. You need to solve the problem with the following constraints:

• You need $8$ individual schedules over the total time span: $$ \sum_{i \in I} x_i = 8 $$
• You need $3$ people on each shift: $$ \sum_{i \in I} a_{ij} x_i = 3 \quad \forall j\in J $$

At this point, you have taken account each of your constraints except for constraint $(5)$. You could define a pairwise coefficient $b_{ik}$ for each pair of shifts $i,k \in I\times I$. This coefficient would be a measure of how "uneven" the schedules are. And so you would solve the above constraint problem while minimizing the sum of such coefficients. Since they are pairwise, this means you also need pairwise binary variables $y_{ik}$. This way you minimize $$ \sum_{i,k}b_{ik}y_{ik} $$ with the additional constraints $$ x_i+x_k \le y_{ik}+1 \quad \forall i,k $$

Answer 2

Math Formulation + Pyomo model

We need to define 3 sets i: 1 to 8 staffs j: 1 to 3 shifts t: 1 to 18 days

$X_{i,j,t} \in {0/1} $ Binary

• There must be 3 people on each shift

• $\forall t,j $ then $\sum_i X_{i,j,t} =3$

• Every individual (i) must work 1 shift per day\

• $\forall t,i $ then $\sum_j X_{i,j,t} \geq 1 $

• Every individual must not work more than 2 shifts per day\

• $\forall t,i $ then $\sum_j X_{i,j,t} \leq 2 $

• Every individual must get at least one night shift break, preferably two.\

• $\forall t,i $ then $X_{i,3,t}+ X_{i,3,t+1} \leq 1 $

• Each individual must not work consecutive shifts (e.g. the night shift on Day 1 and the morning shift on Day 2) \

• $\forall t,i $ then $X_{i,3,t}+ X_{i,1,t+1} \leq 1 $

• $\forall i \sum_t X_{i,3,t} \leq Z$

• $\min Z $, Z represent the maximum number of nightshift for all staffs

Github Link

model = AbstractModel()
model.i = RangeSet(1,8)
model.j = RangeSet(1,3)
model.t = RangeSet(1,18)

model.X = Var(model.i,model.j,model.t, within=Binary)
model.Nshift= Var( within=NonNegativeReals)

def Rule_C1(model,t,j):
    return sum(model.X[i,j,t] for i in model.i)==3
model.C1=Constraint(model.t,model.j,  rule=Rule_C1)

def Rule_CA(model,t,i):
    return sum(model.X[i,j,t] for j in model.j)<=2
model.CA=Constraint(model.t,model.i,  rule=Rule_CA)

def Rule_CB(model,t,i):
    return sum(model.X[i,j,t] for j in model.j)>=1
model.CB=Constraint(model.t,model.i,  rule=Rule_CB)

def Rule_C2(model,t,i):
    if t<18:
        return model.X[i,3,t]+ model.X[i,3,t+1] <=1
    else:
        return Constraint.Skip
model.C2=Constraint(model.t,model.i,  rule=Rule_C2)

def Rule_C3(model,t,i):
    if t<18:
        return model.X[i,3,t]+ model.X[i,1,t+1] <=1
    else:
        return Constraint.Skip
model.C3=Constraint(model.t,model.i,  rule=Rule_C3)

def Rule_C4(model,i):
    return sum(model.X[i,3,t] for t in model.t)  <=model.Nshift
model.C4=Constraint(model.i,  rule=Rule_C4)

def rule_OF(model):
    #return quicksum(model.X[i,j,t] for i in model.i for j in model.j for t in model.t )
    return model.Nshift+quicksum(model.X[i,j,t] for i in model.i for j in model.j for t in model.t ) 
model.obj1 = Objective(rule=rule_OF, sense=minimize)

opt = SolverFactory('gurobi')
instance = model.create_instance()
results = opt.solve(instance) # solves and updates instance
print('OF= ',value(instance.obj1))