第13回 - Morito Lab. 森戸研究室

最適化・シミュレーション演習
第１３回 CによるM/M/1モデルの実装
（ディスカッションと講評）
• 授業サポートページ
http://www.morito.mgmt.waseda.ac.jp/optsim/
• 数理計画による最適化と（離散事象型）シミュレーションに
関する演習を行う．使用するソフトウェアは，AMPL（＋
GurobiまたはCPLEX)，および，Simul8を想定している．
• 演習では，数理計画による最適化やシミュレーションの実践
的能力を身につけることを目指す。履修者は，Cを使用でき
る環境を有するPCを持参すること。受講者は，実験室にて，
演習で使用する C，AMPL，Simul8をダウンロードできる。
1
本日のトピックス
• 離散型シミュレーションの基本概念（復習）
– 事象処理ロジック
– 事象ルーチン
• 単一サーバー待ち行列𝑀/𝑀/1のシミュレー
ションの実装（前回の宿題）
– 基本的考え方
• 離散型シミュレーションプログラムの構成
• C++による𝑀/𝑀/1の実装（今泉先生）
2
離散型シミュレーションのモデル化
（World view）
１．プロセス中心のモデル化（Simul8，S^4など）
システム中を動き回る要素に着目し、要素の
到着から消滅に至るライフサイクルのプロセス
を定義することによってシステムを記述
２．事象中心のモデル化（Cによるプログラム）
事象に着目し、事象がシステムの状態に及ぼ
す影響を定義することによってシステムを記述
３．アクティビティ中心のモデル化
3
離散型シミュレーションの基本概念
• シミュレーションクロック（時刻）：シミュレーションにお
ける現在時刻
• 事象（Event）：システムの状態を変化させる瞬時的な
出来事（時間の経過を伴わない）
– 例：顧客の到着、サービスの終了
• 事象カレンダ：将来発生予定の事象が時刻順に並べ
られた、一種の予定表
• 事象ルーチン：事象発生時にシステムの状態がどう変
化するかを記述したもの
• 事象処理ロジック：事象ルーチンによってシステムの
状態変化を発生させながら、時間とともに起こるシス
テムの状態変化を司るもの
4
顧客到着事象の事象ルーチン
顧客到着事象
××分布に従う乱数𝑡𝐴 発生させ，
現時刻+ 𝑡𝐴 に次の顧客到着事象
が予定されることを記憶する
キャッシュ・マシン
は空いているか
No
Yes(サービス開始)
キャッシュ・マシンを使用
中の状態にする
待っている人が
△人いるか？
Yes(あきらめて帰る)
No
○○分布に従う乱数𝑡𝑠 発生させ，
現時刻+ 𝑡𝑠 に顧客のサービス終了
事象が予定されることを記憶する
終了
顧客を待ち行列に加える
5
事象ルーチンの考え方
• 事象が発生した瞬間に、システムの変化やその
事象に伴って将来発生する予定の事象を記述
– システムの状態を表す変数が変化
– 要素が待ち行列に入れられて待機状態に変化
– アクティビティが始まり、その終了事象を将来事象と
して登録
• 事象ルーチン実行時に時刻は変わらないことに
注意
• 将来発生する事象が出てきたときには、当該事
象を事象カレンダに登録（将来のことは、予定表
に書く！）
6
サービス終了事象の事象ルーチン
サービス終了事象
待っている人はいるか?
No
Yes
待ち行列の先頭の人がキャッ
シュ・マシンを使い始める
○○分布に従う乱数𝑡𝑠 発生させ，
現時刻+ 𝑡𝑠 に顧客のサービス終了
事象が予定されることを記憶する
終了
キャッシュ・マシンを空の
状態にする
離散型シミュレーションの事象処理ロジック
Start
将来事象カレンダーに
将来事象はあるか?
No
Stop
Yes
将来事象カレンダの先頭(事象発生時刻が一番早い)
の事象を取り出す
シミュレーション時刻を取り出された事象の発生時刻
に更新する
取り出された事象に対する事象をルーチンを実行する
8
シミュレーションの構成ルーチン
• 事象処理ロジック
• 事象ルーチン（ユーザが提供すべきもので，問題呼応）
• 将来事象登録ルーチン（ENQUEUE）
– 事象カレンダ（ファイル）に将来事象を挿入する
• 最早事象抜き取りルーチン（DEQUEUE）
– 事象カレンダ（ファイル）から再早の事象を抜き取る
• 待ち行列挿入ルーチン（ENQUEUE）
– 待ち行列（ファイル）に要素（アイテム）を挿入する
• 待ち行列抜き取りルーチン（DEQUEUE）
– 待ち行列（ファイル）から要素（アイテム）を抜き取る
•
•
•
•
統計計算ルーチン
結果出力ルーチン
乱数発生ルーチン
（アニメーションのルーチン）
9
モデルを動き回る要素の実体
• モデルを動き回る要素＝Simul8のワークアイテ
ム
• 要素の実体＝要素の「属性」（Simul8におけるラ
ベル）
• モデルの内容に依存しない属性
１）事象発生（予定）時刻
２）事象番号（到着，サービス終了など，事象の
種類を識別するためのコード番号）
• モデルの内容に依存する属性（ユーザが決定）
– 例1：顧客到着時刻
– 例2：顧客のサービス時間（宅配ピザの例）
10
シミュレーションのプログラム
• 要素（ワークアイテム）の動きを，発生時刻順に
追っていくプログラム
• 要素の動きに伴って，要素の待ち時間や系内滞
留時間の情報を収集したり，稼働率などのリ
ソースの情報を収集
• シミュレーションのプログラムは，要素を事象カ
レンダ（ファイル）や待ち行列（ファイル）に挿入し
たり，抜き取ったりの繰り返し
• 複数のファイルへの挿入，ファイルからの抜き取
り＝リスト処理
11
リスト処理
• 事象カレンダも、顧客の待ち行列も、いずれもリ
スト（広義のQUEUE）
• 違いはエントリの並び順
– 事象カレンダは、事象時刻が早い順
– 待ち行列は、行列の優先規律
• FIFO(=FCFS)、LIFO（=LCLS）、その他の優先規律
• 将来事象登録と待ち行列追加は統合可能
• 最早事象抜き取りと待ち行列抜き取りも統合可
能
• 本来は、（配列ではなく）リスト構造（おそらく双方
向リスト）を用いて表現すべきところ
12
課題／宿題１３
（プログラム、結果、考察を提示すること）
• 課題／宿題１３．１（宿題１２．１と同じであるが，
今日，第13回の授業をもとに，プログラムの修
正を考えてほしい）
到着が平均10（分）の指数分布、サービスが平
均s（分）の指数分布にしたがう待ち行列の定常状
態における各顧客の平均待ち時間を推定しなさい。
また、平均サービス時間s（分）の変化に伴う、平
均待ち時間の変化を図示しなさい。
13
参考文献
［１］森戸晋，逆瀬川浩孝，システムシミュレー
ション，朝倉書店，2000．
14
トレース（自分のメモ程度）
clock updated to 0.000000 with current event type = 1, atribute = 0.000000
num_list = 0, num_que = 0
arrival called with tnow = 0.000000, lambda = 0.100000
schedule called with type = 1, time = 0.012520, atribute = 0.012520, num_list = 0
current event calender with num_list = 1
no.= 1, time = 0.012520, type = 1, atrib = 0.012520
In main num_list = 1, num_queue = 0
clock updated to 0.012520 with current event type = 1, atribute = 0.012520
num_list = 0, num_que = 0
arrival called with tnow = 0.012520, lambda = 0.100000
schedule called with type = 1, time = 2.160607, atribute = 2.160607, num_list = 0
current event calender with num_list = 1
no.= 1, time = 2.160607, type = 1, atrib = 2.160607
In main num_list = 1, num_queue = 0
clock updated to 2.160607 with current event type = 1, atribute = 2.160607
num_list = 0, num_que = 0
arrival called with tnow = 2.160607, lambda = 0.100000
schedule called with type = 1, time = 18.701849, atribute = 18.701849, num_list = 0
current event calender with num_list = 1
no.= 1, time = 18.701849, type = 1, atrib = 18.701849
In main num_list = 1, num_queue = 0
clock updated to 18.701849 with current event type = 1, atribute = 18.701849
num_list = 0, num_que = 0
arrival called with tnow = 18.701849, lambda = 0.100000
schedule called with type = 1, time = 27.496841, atribute = 27.496841, num_list = 0
15

Download Report