最適化・シミュレーション演習 第１２回 離散型シミュレーションの考え方 • 授業サポートページ http://www.morito.mgmt.waseda.ac.jp/optsim/ • 数理計画による最適化と（離散事象型）シミュレーションに 関する演習を行う．使用するソフトウェアは，AMPL（＋ GurobiまたはCPLEX)，および，Simul8を想定している． • 演習では，数理計画による最適化やシミュレーションの実践 的能力を身につけることを目指す。履修者は，Cを使用でき る環境を有するPCを持参すること。受講者は，実験室にて， 演習で使用する C，AMPL，Simul8をダウンロードできる。 1 本日のトピックス • • • • 離散型シミュレーションの基本概念 事象処理ロジック 事象ルーチン 単一サーバー待ち行列𝑀/𝑀/1のシミュレー ションのCによる実装 – 基本的考え方 – 実装の詳細 2 離散（事象）型シミュレーション Discrete (Event) Simulation • 待ち行列型のモデルで表現されるシステム のシミュレーション • 混雑現象のシミュレーション • 応用例 – 銀行のキャッシュマシン、生協食堂、コールセン ター、病院、工場のショップ（ジョブショップ等）、 電話、通信ネットワーク、．．． • 商用ソフトウェア（国内で代表的なもののみ） WITNESS、Simul8、S^4、SLAM 3 離散事象シミュレーションの特徴 • 時間は（通常）連続時間を考慮 • システム内を動き回る要素（entity）を考慮 – 例：顧客、工場内を流れる製品、ジョブ、注文 • 要素にサービスを提供する静的な要素と考えられる、 広義のリソース(resource）の存在 – 例：キャッシュマシン、機械、CPU、事務処理者 • システムの状態（state） – 例：待ち人数、サーバーの状態(idle/busy） • システムの状態変化が離散的に（事象発生時に）の み変化すると見る捉え方 – 例：顧客の到着時、サービス終了時 • 時間の進め方は、事象ー事象進行方式 • 離散事象シミュレーションのベースとなっているモデル は待ち行列モデル 4 待ち行列モデル Queueing Models • 待ち行列モデルは何で規定されるんだろう？ • 待ち行列モデルの分類 A/B/X/Y/Z – A: – B: – X： – Y： – Z： 到着パターン（到着時間分布） サービスパターン（サービス時間分布） 並列サーバー数 システム容量（=サービス中＋待機中）上限 待ち行列規律 • 例： M/M/1，M/G/m，M/D/2/∞/FCFS 𝑀 𝑋 /G/𝑐/𝑐 5 待ち行列モデルの分類 A/B/X/Y/Z （A）（B）: M＝指数分布、D＝一定、G＝一般 𝐸𝑘 ＝タイプ𝑘アーラン分布 PH＝相型分布 （X）： 並列サーバー数 1,2,…,∞ （Y）： システム容量（=サービス中＋待機中） 1,2,…,∞ （Z）： 待ち行列規律 FCFS、LCFS RSS（ランダム）、PR（優先規律） GD（一般） 6 離散型シミュレーションの基本概念 • シミュレーションクロック（時刻）：シミュレーションにお ける現在時刻 • 事象（Event）：システムの状態を変化させる瞬時的な 出来事（時間の経過を伴わない） – 例： 顧客の到着、サービスの終了 • 事象カレンダ：将来発生予定の事象が時刻順に並べ られた、一種の予定表 • 事象ルーチン：事象発生時にシステムの状態がどう変 化するかを記述したもの • 事象処理ロジック：事象ルーチンによってシステムの 状態変化を発生させながら、時間とともに起こるシス テムの状態変化を司るもの 7 顧客到着事象の事象ルーチン 顧客到着事象 ××分布に従う乱数𝑡𝐴 発生させ， 現時刻+ 𝑡𝐴 に次の顧客到着事象 が予定されることを記憶する キャッシュ・マシン は空いているか No Yes(サービス開始) キャッシュ・マシンを使用 中の状態にする 待っている人が △人いるか？ Yes(あきらめて帰る) No ○○分布に従う乱数𝑡𝑠 発生させ， 現時刻+ 𝑡𝑠 に顧客のサービス終了 事象が予定されることを記憶する 終了 顧客を待ち行列に加える 8 事象ルーチンの考え方 • 事象が発生した瞬間に、システムの変化やその 事象に伴って将来発生する予定の事象を記述 – システムの状態を表す変数が変化 – 要素が待ち行列に入れられて待機状態に変化 – アクティビティが始まり、その終了事象を将来事象と して登録 • 事象ルーチン実行時に時刻は変わらないことに 注意 • 将来発生する事象が出てきたときには、当該事 象を事象カレンダに登録（将来のことは、予定表 に書く！） 9 サービス終了事象の事象ルーチン 各自で考えてもらうために意図的に以下は空白にしてあります 10 離散型シミュレーションの事象処理ロジック Start 将来事象カレンダーに 将来事象はあるか? No Stop Yes 将来事象カレンダの先頭(事象発生時刻が一番早い) の事象を取り出す シミュレーション時刻を取り出された事象の発生時刻 に更新する 取り出された事象に対する事象をルーチンを実行する 11 シミュレーションのサポートルーチン • • • • • • • • 将来事象登録ルーチン（ENQUEUE） 最早事象抜き取りルーチン（DEQUEUE） 待ち行列追加ルーチン（ENQUEUE） 待ち行列抜き取りルーチン（DEQUEUE） 統計計算ルーチン 結果出力ルーチン 乱数発生ルーチン （アニメーションのルーチン） 12 リスト処理 • 事象カレンダも、顧客の待ち行列も、いずれもリ スト（広義のQUEUE） • 違いはエントリの並び順 – 事象カレンダは、事象時刻が早い順 – 待ち行列は、行列の優先規律 • FIFO(=FCFS)、LIFO（=LCLS）、その他の優先規律 • 将来事象登録と待ち行列追加は統合可能 • 最早事象抜き取りと待ち行列抜き取りも統合可 能 • 本来は、（配列ではなく）リスト構造（おそらく双方 向リスト）を用いて表現すべきところ 13 離散型シミュレーションのモデル化 （World view） １．事象中心のモデル化 事象に着目し、事象がシステムの状態に及ぼ す影響を定義することによってシステムを記述 ２．プロセス中心のモデル化 システム中を動き回る要素に着目し、要素の 到着から消滅に至るライフサイクルのプロセス を定義することによってシステムを記述 ３．アクティビティ中心のモデル化 14 課題／宿題１２ （プログラム、結果、考察を提示すること） • 課題／宿題１２．１ 到着が平均10（分）の指数分布、サービスが平 均s（分）の指数分布にしたがう待ち行列の定常状 態における各顧客の平均待ち時間を推定しなさい。 また、平均サービス時間s（分）の変化に伴う、平 均待ち時間の変化を図示しなさい。 15 参考文献 ［１］森戸晋，逆瀬川浩孝，システムシミュレー ション，朝倉書店，2000． ［２］森戸晋，黒澤隆，大久保寛基，仕事のやり 方を変えるヒント：シミュレーションによる効率化， Parade Books，2015． 16 トレース（自分のメモ程度） 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 17 サービス終了事象の事象ルーチン サービス終了事象 待っている人はいるか? No Yes 待ち行列の先頭の人がキャッ シュ・マシンを使い始める ○○分布に従う乱数𝑡𝑠 発生させ， 現時刻+ 𝑡𝑠 に顧客のサービス終了 事象が予定されることを記憶する 終了 キャッシュ・マシンを空の 状態にする
© Copyright 2024 ExpyDoc
