4 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
6 from pyscipopt
import Model, quicksum, multidict
8 def rcs(J,P,R,T,p,c,a,RUB):
9 """rcs -- model for the resource constrained scheduling problem
12 - P: set of precedence constraints between jobs
14 - T: number of periods
15 - p[j]: processing time of job j
16 - c[j,t]: cost incurred when job j starts processing on period t.
17 - a[j,r,t]: resource r usage for job j on period t (after job starts)
18 - RUB[r,t]: upper bound for resource r on period t
19 Returns a model, ready to be solved.
21 model = Model(
"resource constrained scheduling")
25 s[j] = model.addVar(vtype=
"C", name=
"s(%s)"%j)
26 for t
in range(1,T-p[j]+2):
27 x[j,t] = model.addVar(vtype=
"B", name=
"x(%s,%s)"%(j,t))
31 model.addCons(
quicksum(x[j,t]
for t
in range(1,T-p[j]+2)) == 1,
"ConstrJob(%s,%s)"%(j,t))
34 model.addCons(
quicksum((t-1)*x[j,t]
for t
in range(2,T-p[j]+2)) == s[j],
"ConstrJob(%s,%s)"%(j,t))
37 for t
in range(1,T-p[j]+2):
40 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))) \
41 <= RUB[r,t],
"ResourceUB(%s)"%t)
45 model.addCons(s[k] - s[j] >= p[j],
"Precedence(%s,%s)"%(j,k))
47 model.setObjective(
quicksum(c[j,t]*x[j,t]
for (j,t)
in x),
"minimize")
54 """creates example data set 1"""
61 P = [(1,2), (1,3), (2,4)]
66 for t
in range(1,T-p[j]+2):
70 (2,1,0):2, (2,1,1):1, (2,1,2):1,
74 RUB = {(1,1):2, (1,2):2, (1,3):1, (1,4):2, (1,5):2, (1,6):2}
75 return (J,P,R,T,p,c,a,RUB)
78 """creates example data set 2"""
86 P = [(1,2), (1,3), (2,4)]
91 for t
in range(1,T-p[j]+2):
97 (3,1,0):1, (3,1,1):1, (3,1,2):1,
99 (5,1,0):0, (5,1,1):0, (5,1,2):1, (5,1,3):0, (5,1,4):0,
101 (1,2,0):1, (1,2,1):0,
102 (2,2,0):1, (2,2,1):1,
103 (3,2,0):0, (3,2,1):0, (3,2,2):0,
104 (4,2,0):1, (4,2,1):2,
105 (5,2,0):1, (5,2,1):2, (5,2,2):1, (5,2,3):1, (5,2,4):1,
107 RUB = {(1,1):2, (1,2):2, (1,3):2, (1,4):2, (1,5):2, (1,6):2, (1,7):2,
108 (2,1):2, (2,2):2, (2,3):2, (2,4):2, (2,5):2, (2,6):2, (2,7):2 }
109 return (J,P,R,T,p,c,a,RUB)
112 if __name__ ==
"__main__":
114 model =
rcs(J,P,R,T,p,c,a,RUB)
118 print(
"Optimal value:",model.getObjVal())
120 if model.getVal(x[j,t]) > 0.5:
121 print(x[j,t].name,
"=",model.getVal(x[j,t]))
124 if model.getVal(s[j]) > 0.:
125 print(s[j].name,
"=",model.getVal(s[j]))