3.2.1 A Simple Nurse Scheduling (nurses)

Run LPL Code  ,  PDF Document

Problem

Problem: Find an optimal assignment of nurses to shifts (tasks) for a duration of 7 days. Each nurse can request to be assigned to specific shifts. Each shift can only be assigned to exactly one nurse. In a day, a nurse works at most in one shift. Furthermore, each nurse should work the same number of shifts than another nurse in the whole period if possible. The optimal assignment maximizes the number of fulfilled shift requests (the problem is from OR-Tools).

Modeling Steps

Let’s introduce three sets: (1) for the nurses: n N = {1,,N}, (2) for the periods (days): d D = {1,,D}, and for the shifts (tasks): s S = {1,,S}. A Boolean relationsship for the shift requests is introduced as reqn,d,s which is true if nurse n made a request to be assigned to shift s in day d. A binary variable xn,d,s (“shifts” in the code) defines whether nurse n works on shift s in day d (=1) or not (=0). The parameter minS is a minimal number of shifts that a nurse must work at least to fullfill all assignments. maxS is just at most one bigger than minS.

The whole model is:

         ∑
max             xn,d,s
      n,d,s|reqn,d,s
s.t   ∑   x    =  1   forall d ∈ D, s ∈ S            (1 )
           n,d,s
      ∑n
          xn,d,s ≤ 1   forall n ∈ N, d ∈ D            (2 )
       s       ∑
      minS  ≤     xn,d,s ≤ maxS     forall n ∈ N     (3 )
               d,s

Constraint (1) specifies that for each shift in all days exactly one nurse is assigned. Constraint (2) determines that each nurse works at most one shift per day. Constraint (3) distribute evenly the amount of work (all shifts: D S) to every nurse. On average each nurse must work D S∕N. If this is not an integer then some nurses must work D S∕Nand some must work an additional shift. Hence, every nurse must work in at least minS shifts and at most maxS shifts.

LPL code (run nurses)

model nurses "A Simple Nurse Scheduling"; 
  parameter N,num_nurses := 5; 
            D,num_days   := 7; 
            S,num_shifts := 3; 
  set n,all_nurses := 1..N; 
  set d,all_days   := 1..D; 
  set s,all_shifts := 1..S; 
  set req{n,d,s} "shift requests"; 
  Read{n,d,s}('nurses.txt,;1',n,d,s,req); 
  parameter minS := Trunc((S*D)/N); 
    maxS := minS + if(S*D%N,1); 
  binary variable shifts{n,d,s}; 
  constraint C1{d,s}: sum{n} shifts = 1; 
    C2{n,d}: sum{s} shifts <= 1; 
    C3{n}: minS <= sum{d,s} shifts <= maxS; 
  maximize Req: sum{req[n,d,s]} shifts; 
  Write{d}('Day %d' n%s%s', d, 
     Format{n,s|shifts}(' Nurse %d works in shift %s %s' n', n, 
       s, if(req,'(requested)','')), 
     Format{n,s|~shifts and req}(' Nurse %d requested shift %s but does not work' n', n, 
       s); 
  Write('The number of requests fulfilled: %d out of %d' n',Req,sum{req}1); 
end

The data file is (see nurses.txt) :

5 7 3 //number nurses/days/shifts

// the request list is:

1 1 3 //nurse 1 requests in day 1 shift 3

1 5 3

....

Python/or-tools code (download nurses.py)

from ortools.sat.python import cp_model 
def main(): 
    num_nurses = 5 
    num_shifts = 3 
    num_days = 7 
    all_nurses = range(num_nurses) 
    all_shifts = range(num_shifts) 
    all_days = range(num_days) 
    shift_requests = 
    [[[0,0,1], [0,0,0], [0,0,0], [0,0,0], [0,0,1], [0,1,0], ...] 
    model = cp_model.CpModel() 
    shifts = {}                  # declare variables 
    for n in all_nurses: 
      for d in all_days: 
        for s in all_shifts: 
          shifts[(n, d, 
            s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s)) 
    for d in all_days:          # constraint 1 
      for s in all_shifts: 
        model.AddExactlyOne(shifts[(n, d, s)] for n in all_nurses) 
    for n in all_nurses:        # constraint 2 
      for d in all_days: 
        model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts) 
    min_shifts_per_nurse = (num_shifts * num_days) // num_nurses 
    if num_shifts * num_days % num_nurses == 0: 
      max_shifts_per_nurse = min_shifts_per_nurse 
    else: 
      max_shifts_per_nurse = min_shifts_per_nurse + 1

continuing with Python code ...

    for n in all_nurses:        # constraint 3 
      num_shifts_worked = 0 
      for d in all_days: 
        for s in all_shifts: 
          num_shifts_worked += shifts[(n, d, s)] 
      model.Add(min_shifts_per_nurse <= num_shifts_worked) 
      model.Add(num_shifts_worked <= max_shifts_per_nurse) 
    model.Maximize( 
      sum(shift_requests[n][d][s] * shifts[(n, d, s)] for n in all_nurses 
        for d in all_days for s in all_shifts)) 
    solver = cp_model.CpSolver() 
    status = solver.Solve(model) 
 
    if status == cp_model.OPTIMAL:  # output 
      print('Solution:') 
      for d in all_days: 
        print('Day', d) 
        for n in all_nurses: 
          for s in all_shifts: 
            if solver.Value(shifts[(n, d, s)]) == 1: 
              if shift_requests[n][d][s] == 1: 
                print('Nurse', n, 'works shift', s, '(requested).') 
              else: 
                print('Nurse', n, 'works shift', s, 
                      '(not requested).') 
            print() 
        print(f'Number of shift requests met = {solver.ObjectiveValue()}', 
              f'(out of {num_nurses * min_shifts_per_nurse})') 
    else: 
      print('No optimal solution found !') 
 
if __name__ == '__main__': 
  main()