""" rcs.py: model for the resource constrained scheduling problem Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012 """ from gurobipy import * def rcs(J,P,R,T,p,c,a,RUB): """rcs -- model for the resource constrained scheduling problem Parameters: - J: set of jobs - P: set of precedence constraints between jobs - R: set of resources - T: number of periods - p[j]: processing time of job j - c[j,t]: cost incurred when job j starts processing on period t. - a[j,r,t]: resource r usage for job j on period t (after job starts) - RUB[r,t]: upper bound for resource r on period t Returns a model, ready to be solved. """ model = Model("resource constrained scheduling") s,x = {},{} # s - start time variable; x=1 if job j starts on period t for j in J: s[j] = model.addVar(vtype="C", name="s(%s)"%j) for t in range(1,T-p[j]+2): x[j,t] = model.addVar(vtype="B", name="x(%s,%s)"%(j,t)) model.update() for j in J: # job execution constraints model.addConstr(quicksum(x[j,t] for t in range(1,T-p[j]+2)) == 1, "ConstrJob(%s,%s)"%(j,t)) # start time constraints model.addConstr(quicksum((t-1)*x[j,t] for t in range(2,T-p[j]+2)) == s[j], "ConstrJob(%s,%s)"%(j,t)) # resource upper bound constraints for t in range(1,T-p[j]+2): for r in R: model.addConstr( quicksum(a[j,r,t-t_]*x[j,t_] for j in J for t_ in range(max(t-p[j]+1,1),min(t+1,T-p[j]+2))) \ <= RUB[r,t], "ResourceUB(%s)"%t) # time (precedence) constraints, i.e., s[k]-s[j] >= p[j] for (j,k) in P: model.addConstr(s[k] - s[j] >= p[j], "Precedence(%s,%s)"%(j,k)) model.setObjective(quicksum(c[j,t]*x[j,t] for (j,t) in x), GRB.MINIMIZE) model.update() model.__data = x,s return model def make_1r(): J, p = multidict({ # jobs, processing times 1 : 1, 2 : 3, 3 : 2, 4 : 2, }) P = [(1,2), (1,3), (2,4)] R = [1] T = 6 c = {} for j in J: for t in range(1,T-p[j]+2): c[j,t] = 1*(t-1+p[j]) a = { (1,1,0):2, (2,1,0):2, (2,1,1):1, (2,1,2):1, (3,1,0):1, (3,1,1):1, (4,1,0):1, (4,1,1):2, } RUB = {(1,1):2, (1,2):2, (1,3):1, (1,4):2, (1,5):2, (1,6):2} return (J,P,R,T,p,c,a,RUB) def make_2r(): J, p = multidict({ # jobs, processing times 1 : 2, 2 : 2, 3 : 3, 4 : 2, 5 : 5, }) P = [(1,2), (1,3), (2,4)] R = [1,2] T = 6 c = {} for j in J: for t in range(1,T-p[j]+2): c[j,t] = 1*(t-1+p[j]) a = { # resource 1: (1,1,0):2, (1,1,1):2, (2,1,0):1, (2,1,1):1, (3,1,0):1, (3,1,1):1, (3,1,2):1, (4,1,0):1, (4,1,1):1, (5,1,0):0, (5,1,1):0, (5,1,2):1, (5,1,3):0, (5,1,4):0, # resource 2: (1,2,0):1, (1,2,1):0, (2,2,0):1, (2,2,1):1, (3,2,0):0, (3,2,1):0, (3,2,2):0, (4,2,0):1, (4,2,1):2, (5,2,0):1, (5,2,1):2, (5,2,2):1, (5,2,3):1, (5,2,4):1, } RUB = {(1,1):2, (1,2):2, (1,3):2, (1,4):2, (1,5):2, (1,6):2, (1,7):2, (2,1):2, (2,2):2, (2,3):2, (2,4):2, (2,5):2, (2,6):2, (2,7):2 } return (J,P,R,T,p,c,a,RUB) if __name__ == "__main__": (J,P,R,T,p,c,a,RUB) = make_2r() model = rcs(J,P,R,T,p,c,a,RUB) model.optimize() x,s = model.__data print "Opt.value=",model.ObjVal for (j,t) in x: if x[j,t].X > 0.5: print x[j,t].VarName,x[j,t].X for j in s: if s[j].X > 0.: print s[j].VarName,s[j].X