# Shift SchedulingΒΆ

The shift scheduling problem is to cover the hourly demand as indicated in a schedule by a set of potential schedules. Suppose there are \(m\) hours to cover, and there are \(n\) potential schedules to choose. Then the problem is to

\[\text{minimize } c x := \text{minimize } \sum_{i=1}^n c_i\, x_i\]

such that

\[A x \geq b\]

where

- \(x=(x_1,\ldots, x_n)\) is the shift vector such that \(x_i\) is the number of type \(i\) shifts to be planned
- \(c = (c_1, \ldots, c_n)\) is the cost vector such that \(c_i\) is the cost of choosing schedule \(i\),
- \(b = (b_1,\ldots, b_m)\) is the load vector such that \(b_i\) is the minimum amount of servers required at hour \(i\),
- \(A\) contains the schedules: \(A_{ij} = 1\) if schedule \(i\) provides one unit of service in hour \(j\) and \(A_{ij} = 0\) otherwise.

```
import numpy as np
from pulp import *
```

We first specify the different shift types and the associated costs.

```
shifttypes = []
costtypes = []
# the types of shift
# 9 hour shift, with 1 hour break
shifttypes.append([1,1,1,1,0,1,1,1,1])
# cost of this shift is 140 Euro
costtypes.append(140)
shifttypes.append([1,1,1,1,1,0,1,1,1])
costtypes.append(140)
# 5 hour shifts
shifttypes.append([1,1,0,1,1])
costtypes.append(80)
shifttypes.append([1,1,1,0,1])
costtypes.append(80)
```

The hourly loadprofile contains the number of servers minimally required at a certain hour.

```
b = [2,2,3,4,4,4,3,2,3,5,5,4,2,1]
```

The actual shifts, i.e., tours, are the shifttypes shifted by one hour. We next generate the shifts.

```
def generateShifts(shifttypes, costtypes, b):
# compute the number of columns necessary for A
totShifts = 0
for T in shifttypes:
totShifts += len(b) - len(T) + 1
A = np.zeros([len(b),totShifts])
c = np.zeros(totShifts) # costs
col = 0
for T,C in zip(shifttypes,costtypes):
for row in range(len(b)-len(T) + 1):
A[row:row+len(T),col] = T
c[col] = C
col += 1
#print A.T; quit()
return A, c
A, c = generateShifts(shifttypes, costtypes, b)
shifts = range(len(c))
```

Now we solve the problem with Pulp.

```
prob = LpProblem("Shift Scheduling", LpMinimize)
shiftVars = LpVariable.dicts("shifts", shifts,0, None,LpInteger)
#objective
prob += lpSum( [c[i]*shiftVars[i] for i in shifts] )
# constraints
for i in range(len(b)):
prob += lpSum( [A[i,j]*shiftVars[j] for j in shifts] ) >= b[i]
prob.writeLP("shiftScheduling.lp")
#prob.solve(GLPK())
prob.solve()
print "Status:", LpStatus[prob.status]
```

```
Status: Optimal
```

Print schedules and associated costs.

```
inverse = dict((v,k) for k, v in shiftVars.iteritems())
x = np.zeros_like(c)
for v in prob.variables():
x[inverse[v]] = v.varValue
if v.varValue > 0:
print A[:,inverse[v]], v.varValue, v.varValue*c[inverse[v]]
# Print surplus
print "Schedule profile"
print np.dot(A,x)
print "surplus"
surplus = np.dot(A,x) - np.array(b)
print surplus
# The optimised objective function value is printed to the screen
print "Total cost of schedule = ", value(prob.objective)
```

```
[ 1. 1. 1. 1. 0. 1. 1. 1. 1. 0. 0. 0. 0. 0.] 1.0 140.0
[ 0. 0. 1. 1. 1. 1. 0. 1. 1. 1. 1. 0. 0. 0.] 1.0 140.0
[ 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 1. 1. 0.] 1.0 80.0
[ 1. 1. 1. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.] 1.0 80.0
[ 0. 0. 0. 1. 1. 1. 1. 0. 1. 1. 1. 1. 0. 0.] 2.0 280.0
[ 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 0. 1. 0.] 1.0 80.0
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 0. 1.] 1.0 80.0
Schedule profile
[ 2. 2. 3. 4. 4. 4. 3. 2. 6. 6. 5. 4. 2. 1.]
surplus
[ 0. 0. 0. 0. 0. 0. 0. 0. 3. 1. 0. 0. 0. 0.]
Total cost of schedule = 880.0
```