ペトリネットのシミュレーションへの応用［III］ —待ち行列を伴うシステムのシミュレーション事例—

連載鶴座

111日1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111附l 川11附11川11川H川川H川H川川11川111川H川111111川H川111川11川11川11川H刷111111川H川11川川11川川11川川11川11川11111川11川H川H川H川1111111川川H聞H川川11川H刷111川川H附11111川1111111川川H川川H川111川H川H附111川川11川川H川H川11川H川11111111附liIIllIIlII削111削111川1111111

ペトリネットのシミュ V ーションへの応用

(

1

)

一一待ち行列を伴うシステムのシミュレーション事例一一

椎塚久雄

111川111附11川11川11川川11川川11川11川11川11川川11川川11川川11川川11川川11川11川111川11川川11川川11川川11川11川川11川川11川川11川山11川川11川川11川11川川11川川11川11川川11川川11川11川川11川川11川11川川11川川11川11川11川川11川11川川11川川11川川11川川11川川11川11川川11川川11川川11川川11川川11川11川11川11川川11川川11川川11川川11川川11川川11川川11川川11川川11川11山山11川川11川11山11川川11川川11川川11川川11川川11川11川11川川11川11川川11川川11川11川11川川11川11川11川川11川11川11川11川川11川川11川11川11川11川11川11川1111川川11川11川11川川11川11川11川11川1111川11川11川11川川11川11川11川川111川11川川11川川11川川11川川11川111川111川川11川川11川111川11川川11川11川11川11川111川11川川11川11川1111川川11川111川川11川川11川川11川11川1111川11川11川川11川川11山111川11川川11川川11川川11川川11川11川川11川川11川川11川川11川川11川山11川川11川11川川11川川11川川11川11川川11川川11川川11川川11川川11川川11川川11川111川1刊川川11川111川川11川11川11川11川11川川11川11川11川11川川11川川11川11川111川11川川11川11川11111附111川11川川11川11川川11川川川1111111川11川111川川11川111川川11川111川川11聞111川川11附1111聞11聞川11川l川11川11川11川11附111川11川111川1111川11削11附11111川11川11附111川1111川11川1111附1111111附11川11l 今回は，ペトリネットの発火規則に時間遅れの概念を 導入した時間ペトリネ'"卜 (timed

P

e

t

r

i

net) を用い て，待ち行列を伴うシステムのモデル化とシミュレーシ ョンの事例を紹介する.

8

.

時間ペトリネット

トランジションが発火する毎に，その発火ステップを 1 単位時間きざみの時間軸上でコントロールすることに よって，ペトリネットに時間の概念を導入することがで きる.この場合， トランジションの発火に要する時間の 最小値を 1 単位時間 (Ut と記す)とし，各トランジショ ンでの発火時間違れを U

t

の整数倍とするものである.時 刻1m のときのマーキングをM とする .Mのもとで U

_t

遅 れのトランジション tが発火可能であれば，これを発火 させることによりマーキングはM' に変わる.次の時刻 m+l でこの新たなマーキング M' のもとで発火可能な トランジションを見つけ出しこれを発火させ，以下 同様の方法で順次時聞を進める. 一般に，遅れ T (T> l) を持つトランジションの 場合，このトランジションの発火によるマーキング の変化のさせ方には基本的に 2 つの方法が考えられ る.その l つは，図8.t (叫に示すように，発火と問 時にそのトランジションの入力プレースより l 個の トークンを取り去り ， T時間後にそのすべての出力プレ ースに 1 個ずつトークンを加える方法である.もう I つ は，まず発火と同時にそのすべての入力プレースの中の 1 つのトークンを予約済みとして登録し，他のトランジ ションの発火に関与させないようにし，そして T時間後 に予約を解除して入力プレースより l 個ずつトークンを 取り去り，すべての出力トークンに 1 個ずつトークンを しいづかひきお工学院大学電子工学科 干 160 新宿区西新宿 1-24-2

4

2

白ヲ\

ト℃

(a) トランジション時間ペトリネット I • I T 時間後 \ノ\ 一--キ 予約解除 :J---+(・ 1 (b) プレース時間ベトリネット 図 8.1 時間ペトリネットの遅れの解釈 加える方法である.この間トランジションは，悶 8.1 (b) に示すように，発火中と L 、う状態にあるものとする. 最初の方法ではトランジジョンの発火によるマーキン グの遷移則が発火期間中は成立しないように見えるので これはトランジションに実際の行動を対応させる場合の モデル化に適している.また後の方法ではマーキングの 変化が T時間後に瞬時に行なわれるのですべての時間で マーキングは遷移則を満たすように変化するから，これ はプレースに実際の行動を対応させる場合のモデル化に 適している.

チケソ|売り場

Eヨ窓

u . ②百 CJ.) I!民チ デじケ 機ゾ ト

日

日

己

日

日

日

日

シコ 1 ウインド

日盟

E

己

このように時間ベトリネットは，時間に関す るパラメータの導入の仕方によって大きく 2 つ に分類され，上述した前者のように， トランジ ションの発火に要する時間を規定する場合をト ランジション時間ペトリネ・7 ト( 11) ，また後者 のように，プレースに入力されたトークンが利 用可能になるまでの遅延時間を導入する場合を プレース時間ペトリネヴト (12) という.さらに これら両者をあわせたペトリネットモデルの研 究もされている(1 3). 両日瞬口② 配時口① キソチン 一方，システムの確率的な事象の表現と解析 を行なうために，この時間ペトリネットはさら に拡張され， トランジションが発火可能になっ たがって，使用するシミュレータの最も特徴的な点は，プ レースでのトークンの待ち時間を導入したことであり， それをプレースタイマー (place timer) と名づけた. たとえば，食堂のテーブルに対応するプレースにトー クンが入ると，それは客が食事をするために席に着いた ことを意味するが，このとき，その入力プレースとなっ ているトランジションは発火可能状態となり，これを発 火させると，次の瞬間にはトークンが出ていってしま う.つまり，客が席に着いた次の瞬間すぐに席を立って 出ていってしまうことになる.プレースタイマーは，こ の現象を避けるために，テープルに対応するプレースに モデル化する学生食堂の見取図 図 9.1 てから発火を開始するまでの時間を，連続の確率分布を 持つような確率変数で定義する確率ペトリネ'"ト {sto­ chastic Petri net も提案されている(1 4). 文献(1 5) に は，時間および確率ペトリネットに関する最近のす・ーベ イがある.

学生食堂の毛デル化とシミュレーシ

ョン事例

9

.

新しくトークンが入ると，指定したある一定の時間だけ そのトークンを使ったトランジションの発火はできない ようにコントロールするもので，各プレースにつけられ たタイマーがモデルを実行するうえで有効な働きをして 時間ペトリネットの一応用例として，ここでは筆者の 勤務する大学の学生食堂を取り上げ，食堂内における客 の食事時間および流れを待ち行列を伴う同時進行システ ムとしてとらえ，ペトリネットモデルにより客の流れの 状態をシミュレーションした事例を紹介する (16). L 、る.

9

.

2

ネヴトモデル化 図 9.1 にはペトリネットによってモデル化しようとす る学生食堂の見取り図を示す.客は出入口より入場し， ショーウインドにてメニューを選び，チケット売り場(窓 口①，②，および自動販売機)で食券を質 L 、，各自が選 んだメニューの配膳口(①，②，③，…メニュー別にな っている)へ進み，注文したメニュー品を受け取り，座 席に若いて食事をとる.座席は 1 つのテープルに 12席， 片側にそれぞれ 6 庸ずっとなっている.客は自由に腐を 選ぶことができる.食事が済んだら下謄口にて下膳し， 出入り口より退場する. このシステムをペトリネットによってそデル化したも のを図 9.2に示す.ただし，このネ γ トモデルでは，食券 売り場，配膳および下膳部分のモデルは簡単化するため

4

3

9

.

1

時間進行とプレースタイマー ここで考えるネットモデル上での時聞は，基本的には 8. で述べたプレース時間ベトリネットにしたがってい る.しかし，ネットモデルの時聞はトランジションが発 火する毎に進めるのではなく，マーキングがMのとき発 火可能なトランジジョ γ をすべて発火させた時点で単位 時間として“ 1 "進める.そして，発火が一周したとき のマーキングを M' とし ， M' の状態においても同様に発 火可能なすべてのトランジションを発火させたら，また 時聞を“ 1 "進める.このようにすることによって，疑 似的な並列処理を行なうことができる.ただし 2 つ以 上のトヲンジションの発火が競合状態にある場合には， トランジジョンの番号が小さいものを優先して発火させ ることにする.これは競合トランジションをランダムに 発火させても，ほぽ同ーのシミュレーション結果が得ら れるためである.プレース時間ベトリネ γ トを用いた理 由は，食堂での客の食事時間を考慮するためである.し 1990 年 1 月号 © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

図 9.2 学生食堂のベトリネットモデル に省略した.したがって，このモデルでは入り口にあた る場所では，客はすでに料理を受け取っているものと仮 定している. 座席のモデル化:座席は 1 つのテープルに 12席あって， 片側にそれぞれ 6 席ずつある，ここでは，立ったまま食 事をすることは考えていないので，座席の数より客が多 くなることはあり得ない.図 9.3はこれをモデル化したも ので，入口より客が入ってきて， トランジション Tt が 定の時間になれば，トランジション T_Oが発火し対応する プレース PkのトークンはプレースPj に移り，同時に客 は出口へと向かう. 通路のモデル化:通路をモデル化するときに注意しな ければならないことは，~の動きをうまくコントロール できるようなモデルを作ることである.たとえば，一度 庸に着いた客が再び戻ってきて席に着いたり，あるいは 庸に着かずに出ていってしまうことがあっては客の流れ Pk をコントロールできない.そこで客の動ける 方向を限定して，食堂内に入ってきた客は必 ずどこかの席に着くようにし，腐を立った客 は必ず出口へ向かうようにした.したがって モデル上ではこれから食事をする客と食事を 終えた客との経路は交わらないようにした. 発火条件を満たし，それを発火させるとプレ ース PJ の中にあるトーグンはプレース Pk の中に移る.すなわち，プレース PJ の中の トークンの数は空いている座席の数を表わ し，プレース P_kの中のトークンの数は食事 中の客の数を表わしている.この 2 つのプレ ースは対になって座席に役目を果たしてい る.したがって， プレースPj の中のトーク ンの数とプレース Pkの中のトークンの数を 加えたものはこの場合常に6 に等しい.食事 を終えた客'ì.，プレースタイマーによって所 図 9.3 座席のネ・y ト 図 9.2においてプレースの対 (P2， PS) ， (P_U'

P a ), (Pu , P

25 )

,

(P:帥， P:目)， (P町， P

28

) ， (P.剖，

P

50 )

,

(P日， P5S) ， (P日， P5S) ，

(Pn , P n ),

(P怖 P77) はこれから席に着こうとする客の通路上 モデル _{のある地点を表わしている.ただし，初期マ}

4

4

1 分毎に到着する客の数 ンはすぐに発火可能であるし，タイマーが 3 ならそのプ レースを入力プレースとするトランジションはモデル上 での時聞が 3 進まなければ発火できない. ここでは，次のような 2 つの場合のシミュレーション 実行例の一部を示す. 実行例出口での混乱を避けるために出口へのアー クの重みは 3 とした.テープルのプレースにまだトーク ンの入る余裕があるのに，通路のプレースにトークンが 溜ってしまうことがあるため，通路に関する初期マーキ ングを増加させ変更した.また，各テープル毎のプレー スタイマーを表9.1 に示すように， 10分から 30分までとラ ンダムに設定した.これは客の食事時聞をみな一定とす るより，客毎に食事時聞が異なるようにした方がより現 実的であるからである.初期客の食事時聞は表9.2 に示 すように，客 1 と客 2 で時間 l 分から 24分までとした. シミュレーション結果を図 9.5に示す.この結果からみ るかぎりにおいては，この食堂にはまだ余裕があるよう に思える.。 実行例 2 実行例 i の結果から，この食堂にはまだ余 裕がみられるため，各時間の入口での到着客をすべて 2 人ずつ増加してみる.トークン数では約 5 割増しである. ただし， 12:00 の到着客だけは図9.4 と同じである. 図 9.8 に示すように，モデル上の時間 20以降の客はほぼ 図 9.4 ーキングにおいてすでにトークンの入 っているプレースは，座席をモデル化 した場合と同じように，その存在によ ってもう片方のプレースにはそのトー クン数以下のトークンしか入ることが できない.これによって通路上の一点 に多数のトークンが溜ってしまうこと を防ぐことができる. 9.3 シミュレーションの実行 食堂内での客の食事時間およびシミュレーション開始 時刻にすでに何人かが食事中であるかといういわゆる初 期客も考慮し，種々の状況を想定してシミュレーション を実行することができる.食堂の入口に到着する客の待 ち行列のデータは， 1977年 7 月 2 日の 12:00から 13:00に おいて生産機械工学科の矢部研究室が調査を行なった実 測値を借用した.しかし，実際のシミュレーションでは， 計算時聞を短縮するために，実測データをもとにして各 1 分毎の客の数を計算し，それをその時間の到着客とし た.したがって，客は全くランダムに到着するのではな く 1 分毎に何人かがまとまって到着することにした.図 9.4に示すのは 1 分毎に到着する客の人数である.それ以 外のデ一九たとえば客の食事時間等はすべて推測値を 用いる.初期客というのは 12:00現在に食堂内ですでtこ食 事をしている客のことである.また，実行時間とは時計 で計った実時間ではなく，発火可能なトランジションを すべて発火し終えたとき時聞を 1 進めることにしている. モデル上で、の時間のことを意味する.プレースタイマー は，各プレースに 6 個設けた.食堂の片側のテープルに は 6 人まで座ることができるので 6 個のタイマーはそ の 6 人に対応している.あるプレースのタイマーが 0 な らば，そのプレースを入力プレースとするトランジショ

雪 10

数 (人 )5 内4

客一

876

つコ一

4

三

Jn41 一ー一ヲ t 一 8 一 9 一一ー一 273 一 4 自立年一 i 一 1 一 1 一 4 一内 4τd 一ゐ二足 HH 「じド!「 IllLIl--「lIlli11ILil--「 11l 「 lll 「 Illl 時一ス一一一一←一一一

:

事一 -O 一一 o 一ー一・一ラ一 8 一 9 一 qL 食一レ N 三 J 一 6 一 6 一 6 一 6 一 6 一 6 一 7 一 h ムプ一一一一一一一一

残コ什ゴ町ー一小ーー「引|「引

l

「

210-川

の一客一 1 一 l 一1 一 l て 11 一 11 R 一・ー一}一 O 一 1-4 一 3 一 47 コプ 6 瑚一客一 f 一 1 つ A でーつ A つー τ つ A 叫叶一ス一一一一一一一一 ので， L 一一一一一一一 -てむ一円 370 一句 r 一《 U 一-一一 4 一コ二信

佐ル

N

て

311

コココ一

4

一

4 行 τ ド l 下|一 l|-一 Illl 一Illi--T 下 Illi-­ 畠歪 4 一 4 一 3 一 2 一 1 二 U 一 9 一。。一 7

」客

7777

三一

111

，， --ei--一一一一一一

主客寸三三三

777

一

8

表一ス一

iiii 一 -a 一} レ kn 一 a

-フ 7 9 12 15

4

5

18 20 23 表 9.1 実行例 l のプレース

プ μ ス 1~1 マ|プ μ ス 1~1 マ|プ μ ス!とイマ

l20

I

33

I

20

I

57

I

￨15

I

36

I

15

I

60

I

￨10

I

37

I

10

I

61

I

l20

IωI

20

I

64

I

￨25

I

41

I

15

I

65

I

￨15

I

44

I

30

I

68

I

120

I

45

I

20

I

69

I

I

30

I

佑

I

25

I

72

I

15 20 10 4 7 9 1990 年 1 月号 15 20 20 30 25 12 15 18 20 23 © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

110から 120 の聞で安定している.言 い換えればこの時間で客の数は飽和 している.したがって，だいたいこ のあたりが許容人数の限界ではない かと考えられる. 以上示したモデル化とシミュレー ションは，時間ベトリネットのみを 用いて基本概念だけを例示した.さ らにシステムの性能評価等を行なう には，時間・確率ベトリネットを導 入することが望まれる.また，この シミュレーションはパソコン上で専 用シミュレータを開発して実行し た.しかし，パソコンでは規模が大 きくなると処理速度が問題になる. システム性能評価用ソフトウェアパ ッケ}ジの代表的なものとして，最 近， Chiola らがワークステーショ ン上で開発した Great SPN があげ られる(17). ところで，本稿で示した例でもわ かるように，ベトリネットモデルは システムをプラックボックス的に扱 うのではなく，かなりホワイトボッ クスに近い状態で扱うことができる 利点を持っているつづく) 文献 (前固までにあげたものは省く) (1

1

)

C.Ramchandani:

“

Analysis

o

f

Asynchronous Concurrent

Systems by Timed P

e

t

r

i

Nets"

,

Ph. D. Thesis

,

Department o

f

E

l

e

c

t

r

i

c

a

l

Engineering

,

MIT

,

1

2

0

8

3

\/'混

2

0

0

5

p_h

。岬

問 v F h d 戸 hυ ハ υ F D F h U 4 ハ U S A -F H J u n《 υ n u q d 戸、 υ ワω n u ワ白 戸包 唱 i n u

-P D 図 9.5 実行例 1 の結果 客 (T)

3

0

8

3

6

2

ﾜ

t

雑 4 1"千t

(

%

)

2

0

^r V

o

5 1

0

-1

5

2

0

- 2

5

3

0

3

5

40--45-S-0--5S--60a年Ii日

1

9

7

4

.

(1

2

)

J

.

Sifakis:

“

Use o

f

P

e

t

r

i

Nets f

o

r

Performaｭ

nce Evaluation"

,

i

n

Modelling and Performance

Evaluation o

f

Computer Systems

,

(H. B

elner and

E.Gelenbe( e

d

.

)

),

North-Holland

,

pp.75-93

,

1

9

77.

[

1

3

)

R.R. Razouk and C.V.Phelps:

“

Performance

Analysis Using Timed P

e

t

r

i

Nets"

,

i

n

P

r

o

t

o

c

o

l

Specification

,

Testing and V

e

r

i

f

i

c

a

t

i

o

n

VI

,

(

Y

.

Yemini e

t

a

l

.

(ed.))

,

North-Holland

,

pp.75-93

,

1

9

8

5

.

(1

4

)

M. Ajmone Marsan

,

G. Balbo and G.Conte:

図 9.6 実行例 2 の結果

“

A C

lass o

f

Generalized S

t

o

c

h

a

s

t

i

c

P

e

t

r

i

Nets

f

o

r

t

h

e

Performance Evaluation o

f

Multipro・

c

e

s

s

o

r

Systems九 ACM

Trans. Comput

,

Syst.

,

Vo

1.

2

,

No.2

,

pp.93-122

,

1

9

8

4

.

[1 5) 西尾章治郎:“システム性能評価のための時間およ び確率ペトリネットヘ計測と制御，

Vo

1.

28

,

No.9

,

p

p

.

760-769

,

1989年 9 月. [16) 椎塚久雄・末永亮・中国努:“ペトリネットによる 待ち行列システムのモデノレ化ヘ電子通信学会ネット理 論研究会論文集(第 l 回)， pp.I-14， 1986年 5 月.

[

1

7)

G. Chiola:

“

Great SPN U

ser's Manual

,

Ver.

1. 3ヘ Dipartimento

d

i

Informatica

,

Universita