定盤計画の難しさ

投稿日時: 投稿者:

問題の規模

例題２に対して、次式に基づいて、「問題の規模」を計算してみます。

\displaystyle{(1)\quad N(L,B,\ell,b)=(L-\ell+1)(B-b+1) }

L=4、B=4だから、ブロックBLK1については

\displaystyle{(2)\quad N_{\rm BLK1}(4,4,1,2)=(4-1+1)(4-2+1)=4\times 3=12 }

ブロックBLK2については

\displaystyle{(3)\quad N_{\rm BLK2}(4,4,1,2)=(4-2+1)(4-1+1)=3\times 4=12 }

ブロックBLK3については

\displaystyle{(4)\quad N_{\rm BLK3}(4,4,2,2)=(4-2+1)(4-2+1)=3\times 3=9 }

したがって、例題２に対して問題の規模は

\displaystyle{(15)\quad N_{\rm BLK1}N_{\rm BLK2}N_{\rm BLK3}=12\times 12\times 9=1296 }

と計算できます。

本書では、すべてのRCPSPについて、問題の規模を次のコードで、モードの総数として求めていますす。

OptSeq 

#====問題の規模:      
A=[]
for a in prob.act: A.append(a.name) 
print("アクティビティ:",A)  
N=len(prob.act)
print("アクティビティ総数（含待機数）:",N)  
M=[]
for a in prob.act: M.append(len(a.modes)) 
print("モード数:",M)  
print("平均モード数:",round(sum(M)/N))
P=math.ceil(math.log10(round(sum(M)/N)**N))
print("問題の規模: 10**",P)

ここで、RCPSPとして定式化されたモデルを{\bf prob}としています。{\bf prob.act}により、すべてのアクティビティ名のリスト{\bf A}を求めて、その長さを{\bf N}としています。また各アクティビティに付されたモードの個数を並べたリスト{\bf M}を求めています。平均モード数{\bf sum(M)/N}を求め、これを{\bf N}乗することで、問題の規模としています。