"""
staff_sched.py: model for staff scheduling
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
"""
import random
from gurobipy import *
def staff(I,T,N,J,S,c,b):
"""
staff: staff scheduling
Parameters:
- I: set of members in the staff
- T: number of periods in a cycle
- N: number of working periods required for staff's elements in a cycle
- J: set of shifts in each period (shift 0 == rest)
- S: subset of shifts that must be kept at least consecutive days
- c[i,t,j]: cost of a shit j of staff's element i on period t
- b[t,j]: number of staff elements required in period t, shift j
Returns a model, ready to be solved.
"""
Ts = range(1,T+1)
model = Model("staff scheduling")
x = {}
for t in Ts:
for j in J:
for i in I:
x[i,t,j] = model.addVar(vtype="B", name="x(%s,%s,%s)" % (i,t,j))
model.update()
model.setObjective(quicksum(c[i,t,j]*x[i,t,j] for i in I for t in Ts for j in J if j != 0),
GRB.MINIMIZE)
for t in Ts:
for j in J:
if j == 0:
continue
model.addConstr(quicksum(x[i,t,j] for i in I) >= b[t,j], "Cover(%s,%s)" % (t,j))
for i in I:
model.addConstr(quicksum(x[i,t,j] for t in Ts for j in J if j != 0) == N, "Work(%s)"%i)
for t in Ts:
model.addConstr(quicksum(x[i,t,j] for j in J) == 1, "Assign(%s,%s)" % (i,t))
for j in J:
if j != 0:
model.addConstr(x[i,t,j] + quicksum(x[i,t,k] for k in J if k != j and k != 0) <= 1,\
"Require(%s,%s,%s)" % (i,t,j))
for t in range(2,T):
for j in S:
model.addConstr(x[i,t-1,j] + x[i,t+1,j] >= x[i,t,j], "SameShift(%s,%s,%s)" % (i,t,j))
model.update()
model.__data = x
return model
def make_data():
T = 7 # number of periods
N = 5 # number of working periods of each staff element in a cycle
J = range(4) # shift set; 0 == rest
S = [2,3] # subset of shifts that must be kept at least consecutive days
# staff set, base cost
I,c_base = multidict({1:8000, 2:9000, 3:10000, 4:11000, 5:12000, 6:13000, 7:14000, 8:15000})
c = {}
for i in I:
for t in range(1,T+1):
for j in J:
if j == 0:
continue
c[i,t,j] = c_base[i]
if j == 3: # night shift, more expensive
c[i,t,j] *= 2
if t == T-1 or t == T: # weekend, more expensive
c[i,t,j] *= 1.5
b = {
(1,1):2, (1,2):3, (1,3):1,
(2,1):2, (2,2):3, (2,3):1,
(3,1):2, (3,2):2, (3,3):1,
(4,1):1, (4,2):1, (4,3):1,
(5,1):3, (5,2):3, (5,3):1,
(6,1):4, (6,2):4, (6,3):2,
(7,1):5, (7,2):5, (7,3):2,
}
return I,T,N,J,S,c,b
def make_data_trick():
T = 7 # number of periods
N = 5 # number of working periods of each staff element in a cycle
J = range(4) # shift set; 0 == rest
S = [2,3] # subset of shifts that must be kept at least consecutive days
# staff set, base cost
I,c_base = multidict({1:8000, 2:9000, 3:10000, 4:11000, 5:12000, 6:13000, 7:14000, 8:15000})
c = {}
for i in I:
for t in range(1,T+1):
for j in J:
if j == 0:
continue
c[i,t,j] = c_base[i]
if j == 3: # night shift, more expensive
c[i,t,j] *= 2
if t == T-1 or t == T: # weekend, more expensive
c[i,t,j] *= 1.5
b = {
(1,1):2, (1,2):2, (1,3):2,
(2,1):2, (2,2):2, (2,3):2,
(3,1):2, (3,2):2, (3,3):2,
(4,1):2, (4,2):2, (4,3):2,
(5,1):2, (5,2):2, (5,3):2,
(6,1):2, (6,2):2, (6,3):2,
(7,1):2, (7,2):2, (7,3):2,
}
return I,T,N,J,S,c,b
if __name__ == "__main__":
I,T,N,J,S,c,b = make_data_trick()
# I,T,N,J,S,c,b = make_data()
model = staff(I,T,N,J,S,c,b)
model.optimize()
status = model.Status
if status == GRB.Status.OPTIMAL:
x = model.__data
print "Optimum solution found"
print "\n\nstaff schedule: (shift on each day)"
for i in I:
s = "worker %s:\t" % i
for t in range(1,T+1):
for j in J:
if x[i,t,j].X > .5:
s += str(j)
print s
print "\n\nuncovered shifts:"
for t in range(1,T+1):
s = "day %s:\t" % t
for j in J:
if y[t,j].X > .5:
s += "%s:%s, " % (j,int(y[t,j].X+.5))
print s
elif status == GRB.Status.INFEASIBLE:
print "Infeasible instance..."
model.computeIIS()
for c in model.getConstrs():
if c.IISConstr:
print c.ConstrName
elif status == GRB.Status.UNBOUNDED or status == GRB.Status.INF_OR_UNBD:
print "Unbounded instance"
else:
print "Error: Solver finished with non-optimal status",status