定盤計画の難しさ

問題の規模

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

$\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)

制御系CAD

制御を意識したモノつくりを目指して

定盤計画の難しさ