# 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