RCPSP
RCPSP (Resource Constraint Project Scheduling Problem, 資源制約プロジェクトスケジューリング問題)とは、先行制約(Precedence Constraints)と資源制約(Resource Constraints)のもとで、決定変数を各作業の開始日とし、目的関数を最小化する組合せ最適化問題で、次のように定式化（またはモデル化）表されます。
![\[\displaystyle{\boxed{\begin{array}{cl} {\bf min}&\ Objective\ Function\\ {start\ times}&\\ {\bf subject\ to}&1^\circ\ Precedence\ Constraints\\ &2^\circ\ Resource\ Constraints \end{array}}}\]](https://cacsd1.sakura.ne.jp/wp/wp-content/ql-cache/quicklatex.com-e06beb8547aee1ddb83a85eeb795ffb6_l3.png "Rendered by QuickLaTeX.com")
これを拡張した問題に対する商用ソルバーとして、OptSeqがあります。そこで使用可能なクラス、インスタンス、メソッドを以下に示します。
●クラス「モデル」
model=Model()
●クラス「作業」
act=model.addActivity(name=””,duedate=”inf”,backward=False,weight=1,autoselect=False,quadratic=False)
act.addModes(mode1,mode2,…)
●クラス「モード」
mode=Mode(name,duration=0)
mode.addResource(resource,requirement={(start,finish):req},rtype=None)
mode.addBreak(start=0,finish=0,maxtime=’inf’)
mode.addBreak(start=0,{(start,finish):req},’break’)
mode.addParallel(start=1,finish=1,maxparallel=’inf’)
mode.addState(state,fromValue=0,toValue=0)
●クラス「資源」
res=model.addResource(name,capacity,rhs=0,direction=’<=',weight='inf')
res.addCapacity(start,finish,amount)
res.addTerms(coeffs,vars,values)
●クラス「時間制約」
model.addTemporal(pred,succ,tempType=’CS’,delay=0,pred_mode=None,succ_mode=None)
●クラス「状態」
model.addState(name)
基本的例題
例1（プッシュ型とプル型） ある作業の納期と作業期間が与えられるとき、納期までどれくらい余裕があるのか(prob1a)、または納期にジャストインするためにはいつから作業に取りかかればよいか(prob1b)という問題を考えます。そのために作業をどう前詰めするか、納期に後詰めするかが問われ、それぞれプッシュ型とプル型に対応します。
#prob1a.py
from optseq import *
#=====リソース
prob1=Model()
res=prob1.addResource("worker",1)
#=====データセット
#i:[期間、後続、納期]
data={
1:[5,2,'inf'],\
2:[1,0,10]\
}
#=====アクティビティ
act={}
for i in data:
act[i]=prob1.addActivity("Act[{0}]".format(i))
#=====先行制約
for i in data:
if data[i][1]!=0:
prob1.addTemporal(act[i],act[data[i][1]])
#-----納期日
for i in data:
if data[i][1]==0:
prob1.addTemporal("source",act[i],"SS",delay= data[i][2]-1)
prob1.addTemporal(act[i],"source","SS",delay=-data[i][2]+1)
#====資源制約
mode={}
for i in data:
mode[i]=Mode("Mode[{0}]".format(i),duration=data[i][0])
mode[i].addResource(res,requirement=1)
act[i].addModes(mode[i])
#=====最適化
prob1.Params.Makespan=True
prob1.Params.TimeLimit=1
#prob1.Params.OutputFlag=True
prob1.optimize()
prob1.write("prob1a.txt")
prob1.writeExcel("prob1a.csv")
#=====prob1a.txt
# activity mode duration 1 2 3 4 5 6 7 8 910
#---------------------------------------------------
# Act[1] Mode[1] 5 ==========
# Act[2] Mode[2] 1 ==
#---------------------------------------------------
# resource usage/capacity
#---------------------------------------------------
# worker 1 1 1 1 1 0 0 0 0 1
# 1 1 1 1 1 1 1 1 1 1
#---------------------------------------------------
OptSeqは指定がなければ前詰めが実行されます。納入作業は10日目に行うと考えて、開始のタイミングを９日目終了に合わせています。
#prob1b.py
from optseq import *
#=====リソース
prob1=Model()
res=prob1.addResource("worker",1)
#=====データセット
#i:[期間、後続、納期]
data={
1:[5,2,10],\
2:[1,0,10]\
}
#=====アクティビティ
act={}
for i in data:
act[i]=prob1.addActivity("Act[{0}]".format(i),duedate=data[i][2],backward=True)
#=====先行制約
for i in data:
if data[i][1]!=0:
prob1.addTemporal(act[i],act[data[i][1]])
#-----納期日
for i in data:
if data[i][1]==0:
prob1.addTemporal("source",act[i],"SS",delay= data[i][2]-1)
prob1.addTemporal(act[i],"source","SS",delay=-data[i][2]+1)
#====資源制約
mode={}
for i in data:
mode[i]=Mode("Mode[{0}]".format(i),duration=data[i][0])
mode[i].addResource(res,requirement=1)
act[i].addModes(mode[i])
#=====最適化
prob1.Params.Makespan=True
prob1.Params.TimeLimit=1
#prob1.Params.OutputFlag=True
prob1.optimize()
prob1.write("prob1b.txt")
prob1.writeExcel("prob1b.csv")
#=====prob1a.txt
# activity mode duration 1 2 3 4 5 6 7 8 910
#---------------------------------------------------
# Act[1] Mode[1] 5 ==========
# Act[2] Mode[2] 1 ==
#---------------------------------------------------
# resource usage/capacity
#---------------------------------------------------
# worker 0 0 0 0 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1 1
#---------------------------------------------------
作業の定義において、納期の指定（duedate）と後詰めの指定（backward=True）を行っています。そのためにデータセットで主作業（Act[1]）にも納期を指定する必要があることに注意してください（後続作業として納品作業があるので本来は不要であるように思われますが）。
例2（その場待機と置き場待機） 種々の制約があると待機期間が生じます。リソース（作業員、作業機械、作業場所）によっては待機中も確保が必要になります。たとえば、リソースが作業場所の場合、その作業場所で待機をするその場待機と、どこか待機場所を確保する置き場待機が考えられます。
#prob2a.py
from optseq import *
#=====リソース
prob2=Model()
res=prob2.addResource("place",1)
#=====データセット
#i:[期間、後続、納期]
data={
1:[5,2,'inf'],\
2:[1,0,10]\
}
#=====アクティビティ
act={}
for i in data:
act[i]=prob2.addActivity("Act[{0}]".format(i))
#=====先行制約
for i in data:
if data[i][1]!=0:
prob2.addTemporal(act[i],act[data[i][1]],tempType="CS",delay=0)
prob2.addTemporal(act[data[i][1]],act[i],tempType="SC",delay=0)
#-----納期日
for i in data:
if data[i][1]==0:
prob2.addTemporal("source",act[i],"SS",delay= data[i][2]-1)
prob2.addTemporal(act[i],"source","SS",delay=-data[i][2]+1)
#====資源制約
mode={}
for i in data:
mode[i]=Mode("Mode[{0}]".format(i),duration=data[i][0])
mode[i].addResource(res,requirement=1)
mode[i].addBreak(0,'inf')
#mode[i].addBreak(0,'inf',maxtime=2)
#mode[i].addBreak(0,0)
mode[i].addResource(res,{(0,'inf'):1},'break')
act[i].addModes(mode[i])
#=====最適化
prob2.Params.Makespan=True
prob2.Params.TimeLimit=1
#prob2.Params.OutputFlag=True
prob2.optimize()
prob2.write("prob2a.txt")
prob2.writeExcel("prob2a.csv")
#=====prob2a.txt: mode[i].addBreak(0,'inf')
# activity mode duration 1 2 3 4 5 6 7 8 910
#---------------------------------------------------
# Act[1] Mode[1] 5 ==========........
# Act[2] Mode[2] 1 ==
#---------------------------------------------------
# resource usage/capacity
#---------------------------------------------------
# place 1 1 1 1 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1 1
#---------------------------------------------------
#=====prob2a.txt: mode[i].addBreak(0,'inf',maxtime=2)
# activity mode duration 1 2 3 4 5 6 7 8 910
#---------------------------------------------------
# Act[1] Mode[1] 5 ========....==....
# Act[2] Mode[2] 1 ==
#---------------------------------------------------
# resource usage/capacity
#---------------------------------------------------
# place 1 1 1 1 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1 1
#---------------------------------------------------
#=====prob2a.txt: mode[i].addBreak(0,0)
# activity mode duration 1 2 3 4 5 6 7 8 910
#---------------------------------------------------
# Act[1] Mode[1] 5 ........==========
# Act[2] Mode[2] 1 ==
#---------------------------------------------------
# resource usage/capacity
#---------------------------------------------------
# place 1 1 1 1 1 1 1 1 1 1
# 1 1 1 1 1 1 1 1 1 1
#---------------------------------------------------
ここでは、待機期間の取り方を３種類考えて、その場待機を実現しています。
#prob2b.py
from optseq import *
#=====リソース
prob2=Model()
res0=prob2.addResource("place",1)
res1=prob2.addResource("stock",1)
#=====データセット
#i:[期間、後続、納期]
data={
1:[5,-2,"inf"],\
2:[1,0,10]\
}
#=====アクティビティ
act={}
for i in data:
act[i]=prob2.addActivity("Act[{0}]".format(i))
#=====先行制約
for i in data:
if data[i][1]!=0:
prob2.addTemporal(act[i],act[data[i][1]],tempType="CS",delay=0)
#-----納期日
for i in data:
if data[i][1]==0:
prob2.addTemporal("source",act[i],"SS",delay= data[i][2]-1)
prob2.addTemporal(act[i],"source","SS",delay=-data[i][2]+1)
#====資源制約
mode={}
for i in data:
mode[i]=Mode("Mode[{0}]".format(i),duration=data[i][0])
mode[i].addResource(res0,1)
act[i].addModes(mode[i])
#=====仮想作業
d_act={}
for i in data:
if data[i][1]<0:
d_act[i]=prob2.addActivity("Wait[{0}]".format(i))
prob2.addTemporal(act[i],d_act[i],tempType="CS")
prob2.addTemporal(d_act[i],act[i],tempType="SC")
prob2.addTemporal(d_act[i],act[abs(data[i][1])],tempType="CS")
prob2.addTemporal(act[abs(data[i][1])],d_act[i],tempType="SC")
d_mode={}
for i in data:
if data[i][1]<0:
d_mode[i]=Mode("d_Mode[{0}]".format(i))
d_mode[i].addBreak(0,0)
d_mode[i].addResource(res1,{(0,"inf"):1},"break")
d_act[i].addModes(d_mode[i])
#=====最適化
prob2.Params.Makespan=True
prob2.Params.TimeLimit=1
#prob2.Params.OutputFlag=True
prob2.optimize()
prob2.write("prob2b.txt")
prob2.writeExcel("prob2b.csv")
#=====prob2b.txt
# activity mode duration 1 2 3 4 5 6 7 8 910
#---------------------------------------------------
# Act[1] Mode[1] 5 ==========
# Act[2] Mode[2] 1 ==
# Wait[1] d_Mode[1] 0 ........
#---------------------------------------------------
# resource usage/capacity
#---------------------------------------------------
# place 1 1 1 1 1 0 0 0 0 1
# 1 1 1 1 1 1 1 1 1 1
#---------------------------------------------------
# stock 0 0 0 0 0 1 1 1 1 0
# 1 1 1 1 1 1 1 1 1 1
#---------------------------------------------------
ここでは、待機場所を別に確保して、待機中はそこを使うようにしています。この置き場待機を実施するかどうかは、データセットにおける後続作業の番号が負であるかどうかで判断しています。