4
$\begingroup$

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!

$\endgroup$
7
  • 1
    $\begingroup$ There are actually 2 questions in your post: the first one is a modeling question, the second is related to PuLP. I suggest you first focus on the model to have your constraints 4-6 correct, and then we can see how to write things correctly with PuLp. $\endgroup$
    – Kuifje
    Apr 9, 2021 at 10:06
  • $\begingroup$ So shall I remove the code from the question? thanks for your help @Kuifje! $\endgroup$
    – Tommy Lees
    Apr 9, 2021 at 10:07
  • 2
    $\begingroup$ I'd recommend removing the code and post the mathematical model with Mathjax, instead. $\endgroup$
    – joni
    Apr 9, 2021 at 10:14
  • 1
    $\begingroup$ I agree with @joni, perhaps remove the code, and write the mathematical model first. $\endgroup$
    – Kuifje
    Apr 9, 2021 at 11:49
  • $\begingroup$ Also, although we are not there yet, it is highly recommended to NOT use "AddConstraint()". Instead, use prob +=, as in the official docs. $\endgroup$
    – Kuifje
    Apr 9, 2021 at 11:59

2 Answers 2

4
$\begingroup$

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 $$

$\endgroup$
2
$\begingroup$

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

enter image description here

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))
$\endgroup$
5
  • $\begingroup$ Is this Pyomo specific ? $\endgroup$
    – Kuifje
    May 17, 2021 at 15:57
  • $\begingroup$ No, it can be coded in Pulp, GAMS or any other optimization tool $\endgroup$ May 17, 2021 at 23:32
  • $\begingroup$ I think you should remove the Pyomo part in the title and mention the previous comment at the end. $\endgroup$
    – Kuifje
    May 18, 2021 at 5:13
  • 1
    $\begingroup$ (or add Pyomo specific content to justify the title) $\endgroup$
    – Kuifje
    May 18, 2021 at 11:59
  • 1
    $\begingroup$ Added the Pyomo Code + Github link $\endgroup$ May 18, 2021 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.