一 般 化 確 率 ペ トリネ ッ トに よ る有 限容 量 同 時 サ ー ビス 並 進 待 ち行 列 の モ デル 化
中 村 隆 志
1.ま え が き
独 立 な到 着 過 程 を 持 つ 複 数 個 の 待 合 室 が あ り,す べ て の待 合 室 に客 が い る と き に扱 い者 が 各 待 合 室 か ら一 人 ず つ 客 を 受 け入 れ て 同 時 に サ ー ビス を行 う よ う な 待 ち 行 列 を同 時 サ ー ビス 並 進 待 ち 行 列 と呼 ぶ[2]。 例 と し て は,複 数 の 下 請 会 社 か らの 部 品 の 到 着 を待 ち,そ れ らの す べ て が揃 っ た と き に組 み立 て を行 う工 場 や デ ー タ フ ロ ー 計 算 機 な どが 挙 げ られ る。 この 待 ち行 列 シス テ ム は トラ フ ィ ック密 度 の 大 小 に よ らず,本 質 的 に不 安 定 で あ る こ とが 知 られ て い る[1, 2コ。 こ の た め,現 実 の シス テ ム に お い て は 何 らか の安 定 化 の た め の 方 策 が 必 要 と な る。 これ に は入 力 制 御[2,3],客 の 途 中 放 棄[4],待 合 室 の容 量 制 限[5,6]な どが 考 え られ る。 筆 者 らは 文 献[7]に お い て,待 合 室 容 量 が 有 限 の2並 進 シ ス テ ム を連 続 時 間 マ ル コ フ連 鎖 と して モ デ ル化 して 解 析 し,そ の 基 本 的特 性 を 明 らか に した 。
しか し,そ の 後 の検 討 に よ り,一 般 化 確 率 ペ トリネ ッ トを用 い て,こ の シス テ ム を記 述 す れ ば,よ り簡 潔 に モ デ ル化 が 可 能 で あ る こ と が わ か っ た。
ペ トリネ ッ ト[8,9]は 非 同 期 的 ・並 行 的 ・分 散 的 な シ ス テ ム の 挙 動 を記 述 す る の に 有 用 で あ り,事 象 生 起 の論 理 的 な 関係 を記 述 す る もの で あ る が,こ れ に確 率 的 な時 間 の概 念 を導 入 し た もの が 確 率 ペ トリ ネ ッ トで あ る。 一 般 化 確 率 ペ トリ ネ ッ ト(GeneralizedStochasticPetriNet;GSPN)[10,11]は 確 率 ペ ト リネ ッ トを拡 張 し,時 間 的 な構 造 に加 え,論 理 的 な構 造 を 記 述 可 能 に した
〔39〕
も の で あ り,指 数 分 布 の 発 火 遅 延 時 間 を 持 つ 時 間 ト ラ ン ジ シ ョ ン(timed transition)と,ゼ ロ 時 間 で 発 火 す る 瞬 間 トラ ン ジ シ ョ ン(immediatetransition) の2種 の トラ ン ジ シ ョ ン を 持 つ 。
本 論 文 で は,こ の 一 般 化 確 率 ペ ト リ ネ ッ トに よ る 有 限 容 量 同 時 サ ー ビ ス 並 進 待 ち 行 列 の モ デ ル 化 に つ い て 述 べ,そ の 有 用 性 を 明 ら か に す る 。
2.同 時 サ ー ビス 並 進待 ち行 列 のGSPNに よ る モ デル 化
本 論 文 で 扱 う 同 時 サ ー ビ ス並 進 待 ち行 列 シス テ ム と は 図1の よ う な もの で あ る。M個 の 待 合 室 が あ り,客 は待 合 室Q‑(1≦m≦M)に 独 立 に そ れ ぞ れ 到 着 率 あ で 到 着 す る。 扱 い 者 は す べ て の待 合 室 に 少 な くと も一 人 の客 が い る と
き に,そ れ ぞ れ 一 人 ず つ 先 着 順 に 客 を受 け 入 れ て,同 時 に サ ー ビ ス 率 μの 指 数 サ ー ビス を行 う。 す べ て の待 合 室 に客 が 揃 わ な い 場 合 に は,た とえ 窓 口が 空
きで あ っ て もサ ー ビス を 開始 し な い。
λ1→
λ2→
λM→
図1同 時 サ ー ビス並進 待 ち行列
こ の シ ス テ ム をGSPNで 表 現 す る と図2の よ う に な る。 各 トラ ン ジ シ ョ ン
と プ レー ス の 意 味 は 次 の とお りで あ る 。
一般 化確率ペ トリネッ トによる有 限容量 同時サ ービス並進待 ち行列の モデル化
tl
1P
μ
図2同 時 サ ー ビ ス 並 進 待 ち行 列 のGSPNに よ る 表 現
ti,t2,…,tM:待 合 室1,2,…,Mへ の 客 の 到 着(時 間 ト ラ ン ジ シ ョ ン Z.2,,…,2.)
'。:サ ー ビ ス の 開 始(瞬 間 ト ラ ン ジ シ ョ ン)
'ゐ:サ ー ビ ス の 終 了(時 間 ト ラ ン ジ シ ョ ン;発 火 率 μ) Pi,p2,…,PM:客 が 待 合 室1,2,…,Mで 待 機 中
ρ。:サ ー ビ ス 中 あ:窓 口 が 空 き
4ヱ
発 火 率
本 論 文 で は シ ス テ ム安 定化 の た め に 待 合 室 の容 量 を制 限 す る こ と とす る。 す
な わ ち,待 合 室 の容 量 は01,Q,,…,(2Mと も,す べ てNと す る。 また,以 下 で は
簡 単 の た め2並 進(M=2)の 場 合 の み を扱 う。 こ の 場 合 のGSPNは 図3の よ
う に な る。ρf,p2'は 待 合 室 の 容 量 を有 限 とす る た め に必 要 と な るPiとp2と の
1P
P2,
図3有 限容 量2並 進 の場 合 のGSPN
補 プ レー ス で あ り,そ れ ぞ れ,Q,,Q,の 空 き容 量 を示 す 。 図3は シ ス テ ム に 客 が い な い状 態 を 表 し て い る。 瞬 間 トラ ンジ シ ョ ンはt。1個 の み で あ る の で, 瞬 間 トラ ンジ シ ョン の プ ラ イ オ リテ ィや 重 み を考 え る必 要 は な い 。
マ ー キ ング を
M,=(M(P1),M(♪f),M(P、),M(pi),M(Pa),M(Pb)) (1)
で 表 す 。 こ こ で,M(Px)は プ レ ー スpxの トー ク ン 数 で あ る 。
Nニ4と し,初 期 マ ー キ ン グM。=(0,4,0,4,0,1)と し て 求 め た 可 達 グ
ラ フ を 図4に 示 す 。 点 線 で 囲 っ て い る16個 の マ ー キ ン グ は 瞬 間 ト ラ ン ジ シ ョ ン
OM
*131301
◎o口瞳・φ
*221301
◎oロ曝,ψ
at
*311301
◎e嗣圏.φ
aψ
*401301
■「■,φ
Otangiblemarking
図4
atφoり 8*132201
噂匂ロ■・φ
8*222201 噂亀賜属・φ
塵*312201
◎匂罎■"φ
a■
健*402201 欄レoロ唱.φ
φ 顧 脚 喧 や う'Oロロ.
可達 グ ラフ
att 瞳*133101
◎o画口◎φ
脚*223101
・φ
・*313101 qレo嗣■̀,
置*403101 噂 ●口■・φ
vanishingMarking
a' 書*134001
◎o麿願,ひ
璽*224001 qレo鱒唱・φ
ae 匿*314001
◎o電ロ,φ
・暫*404001 噂o・鵬・,
ー露許譲樹λプG樋粍プ甲∩謄ぴ録琿蜴︹即図烈ヰー篤メ鷺欝蕪ぴ識翌㊦串寓ぞ詩職恥
云 、を発 火 可 能 とす るバ ニ シ ン グ マ ー キ ング で あ り,他 は,時 間 トラ ンジ シ ョ ン が 発 火 可 能 な タ ン ジ ブ ル マ ー キ ング で あ る。
3.解 析
3.1一 般 的 解 析 法
有 界 なGPSNの 挙 動 は,有 限 状 態 空 間 の 連 続 時 問 セ ミ ・マ ル コ フ 過 程 と し て 表 現 で き る 。 各 マ ー キ ン グ は セ ミ ・マ ル コ フ過 程 の 状 態 に対 応 し,推 移
(GSPNの 発 火)時 点 に 着 目 し た 隠 れ マ ル コ フ 連 鎖(EmbeddedMarkov Chain;以 後EMCと 略 記)を 用 い て,そ の平 衡 状 態 確 率 等 を 求 め る こ とが で き る[11]。 そ の 概 略 は 次 の とお りで あ る 。
GSPNの トラ ン ジ シ ョ ンの 集 合 を
T=lt,,t、,…,左}
(2)
と す る 。 ま た,
W=IWI,W、,…,W、}
(3)
とす る 。 π の 要 素 臨 は 各 トラ ン ジ シ ョン に 対 応 し,姦 が 時 間 トラ ン ジ シ ョ ン の 場 合 は発 火 率(発 火 遅 延 の 指 数 分 布 パ ラ メ ー タ),瞬 間 トラ ン ジ シ ョ ン の場 合 は発 火 確 率 計 算 の た め の 重 み を表 す 。
Rsを 状 態 空 間(可 達 集 合),TRSを タ ン ジ ブ ル マ ー キ ン グ に 対 応 す る 状 態 部 分 集 合,VRSを バ ニ シ ン グマ ー キ ン グ に対 応 す る状 態 部 分 集 合 とす る。
Rs=TRSUVRS,TRS∩VRS=φ
EMCの 推 移 確 率 行 列U=[物]は 次 式 で得 られ る。
物 二(ΣWk)/qi
々=∫々∈ 易(躍̀)
(4)
(5)
一般化確率 ペ トリネ ッ トによる有限容量 同時サ ービス並進待 ち行列 のモデル化 45
ここで,
qi=Σwk(6)
ゐ:'々∈ 易(%)
で あ る。Eブ(M,)は マ ー キ ン グM,で 発 火 可 能 な トラ ン ジ シ ョ ンの 中 で 発 火 す る こ とに よ りM,に 遷 移 す る トラ ン ジ シ ョ ンの 集 合,E(M,)は マ ー キ ン グM,で 発 火 可 能 な トラ ンジ シ ョ ンの集 合 を表 す 。
状 態 の番 号 を適 当 に付 け替 えて,バ ニ シ ン グ マ ー キ ン グ に対 応 す る状 態 に若 い番 号 を与 え る と,Uは 次 の よ う に表 され る。
u・A+B=〔ll〕+じ;〕 (7)
行 列AはVRS内 の 状 態 か らの推 移 確 率 の み,行 列BはTRS内 の 状 態 か ら の 推 移 確 率 の み を記 述 し,他 は0と した もの で あ る 。
c=[砺],D=属],E=[θ ザ],F=[乃] (8)
と す る 。
TをEMCの 平 衡 状 態 確 率 ベ ク トル とす る と,こ れ は,
{
璽 「=μ「ひ
(9) 璽rlT=1
を解 くこ と に よ り得 られ る。 こ こ で1は,す べ て の 要 素 が1の 行 ベ ク トル で あ る 。GSPNに 対 応 す る セ ミ ・マ ル コ フ過 程 の 平 衡 状 態 確 率 は,Tと 各 状 態 の平 均 滞 在 時 間 を用 い て 求 め る こ とが で きる 。
しか し なが ら,バ ニ シ ング マ ー キ ング に対 応 す る状 態 の滞 在 時 間 は0で あ る
こ と は 明 らか で あ る の で,タ ン ジ ブ ル マ ー キ ング 間 の 状 態 推 移 の み に着 目 した
縮 約 隠 れ マ ル コ フ 連 鎖(ReducedEMC;以 後REMCと 略 記)に モ デ ル を縮
小 す る こ と に よ り,推 移 確 率 行 列 の サ イ ズ を小 さ くし て計 算 を容 易 に す る こ と
が で き る 。
こ のREMCの 推 移 確 率 行 列U'=[,"ヴ]は 次 の よ うに 求 め られ る 。 協=夙 愚'〃Pレ ーs}ゐ(1・)
こ こ で,P{r→s}ゐ は バ ニ シ ン グ マ ー キ ングMrか ら タ ン ジ ブ ル マ ー キ ン グ 砺 へ,バ ニ シ ン グ マ ー キ ン グ の み を経 由 して 任 意 の ス テ ッ プ で 推 移 す る確 率
で あ る。
{ 璽r'=璽r'u' T'1T==1 (11)
を 解 く こ と に よ りREMCの 平 衡 状 態 確 率 ベ ク トルT'=[賜 コが 得 ら れ る 。 マ ー キ ン グ 砿 を 基 準 マ ー キ ン グ と し,連 続 す る2回 のM,へ の 訪 問 の 問 に 任 意 の マ ー キ ン グ 砺 を 訪 問 す る 平 均 回 数 砺 は
砺 二 璽「γ 璽「㌃ 働
と な る 。
タ ン ジ ブ ル マ ー キ ン グ 砺 ・に 対 応 す る セ ミ ・マ ル コ フ 過 程 の 平 衡 状 態 確 率 πノ は 次 式 と な る 。
πブ=砺E[Siz,1]/CYてM,)㈲
こ こ で,E[SJI」]は 状 態 ブ の 平 均 滞 在 時 間,CY(砿)は マ ー キ ン グM,を 出 発 し て か ら戻 っ て く る ま で の 平 均 時 間 で あ り,そ れ ぞ れ 次 の よ う に 求 め ら れ る 。
E[釧}]・=1/(Zゴ(14)
CY(M,)=Σv、kE[SJ,]㈲
k:礁 ∈TRS
タ ン ジ ブ ル マ ー キ ン グ に 対 応 す る 状 態 集 合TRS上 でREMCを 生 成 す る こ
と はGSPNに 対 応 す る セ ミ ・マ ル コ フ過 程 を 連 続 時 間 マ ル コ フ連 鎖 に 変 換 す
一般化確 率ペ トリネッ トに よる有 限容量 同時サー ビス並 進待 ち行 列の モデル化47
る こ と に 相 当 す る 。 こ の 連 続 時 間 マ ル コ フ 連 鎖 の 状 態 推 移 速 度 行 列Q'=[,qij]
は 次 の よ う に 求 め ら れ る 。
鈴一{饗]:膨 ⑯
タ ン ジ ブ ル マ ー キ ン グ に 対 応 す る状 態 の 平 衡 状 態 確 率 ベ ク トル π は,次 式 か ら直 接 計 算 す る こ とが で き る 。
{
πO'=0 π1T=1
㈲
3.2平 衡 状 態 確 率 と平 均 待 ち行 列 長
図4の よ う な 可 達 グ ラ フ とな る 本 論 文 のGSPNの 場 合 は,前 述 した 手 法 を 適 用 す る と,結 局,バ ニ シ ン グ マ ー キ ング を,そ れ に 続 くタ ンジ ブ ル マ ー キ ン グ に 併 合 して消 去 した 図5の よ うな 連 続 時 間 マ ル コ フ 連 鎖 と同等 と な る。 これ よ り,式 ㈲ を用 い て 平 衡 状 態 確 率 を 計 算 で き る 。 総 状 態 数 は(N+1)2+2N+1 個 で あ る。
状 態(M(p1),M(ρf),M(p2),M(pi),M(Pa),M(Pb))の 平 衡 状 態確 率 を π(M(Pi),M(ρf),M(P、),M(pi),M(Pa),M(P,))
で 表 す 。
待 合 室(滋 にi人 い る確 率 π廊(待 合 室 容 量=N)は,次 式 に よ り求 め られ る 。
πli=P{M(Pユ)・=i}
=π(i ,N‑i,0,N,0,1)
+Σ π(i,N‑i,h,N‑k,1,0);i=1,2,…,N k=O
⑯
130401 λ
220401 λ
310401 λ
μ 044010 λ
134010 λ
224010 λ
314010 λ
図5連 続時 間マ ル コフ連鎖 の 状態推 移 速度 図
蜘4幽詣藩帆N酷器鼻姫
一般化 確率ペ トリネッ トに よる有 限容量 同時サー ビス並進待 ち行 列のモデ ル化
π10=P{M(P1)=0}
ユ
=Σ Σ π(o ,N,k,N一 ゑ あ1一 ブ)
ブ50k=O
π2iニP{M(P2)=i}
=π(0 ,N,i,N‑i,0,1)
+Σ π(k,N‑k,i,N‑i,1,0) h=O
π20=P{M(P2)=0}
ユ
=Σ Σ π(h
,N一 ん,o,N,ブ,1一 ブ)
ブ=Ok=0
.微㍍
NΣ司︻ガ
五
;i=1,2,…,N
