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