待ち行列モデルの シミュレーション作成 14162024 福地凌 2019/2/17.

Presentation on theme: "待ち行列モデルの シミュレーション作成 14162024 福地凌 2019/2/17."— Presentation transcript:

1 待ち行列モデルの シミュレーション作成 福地凌 2019/2/17

2 内容 待ち行列モデルとは 到着過程とサービス時間 今回使用する待ち行列モデル 作成したプログラムの概要 研究結果 考察 参考資料
2019/2/17

3 待ち行列モデルとは 待ち行列モデルとは？ 身近にある待ち行列を数理的に分析するために、待ち行列に関する用 語を定めて待ち行列を抽象化して表現するモデル。 本研究では、待ち行列の推移や到着・サービス時間がアニ メーションやグラフなどでわかりやすく表示できるプログラ ムを作成することを目的としている。 2019/2/17

4 待ち行列モデルの用語 身近にある待ち行列は具体的であるので、以下の用語を定め ることで待ち行列を抽象化し、待ち行列モデルを構築する。
待ち行列システム・・・待ち室と窓口を含む全体のこと(例：銀行) 待ち室・・・行列を作って待つ場所(例：銀行の待合室) 窓口・・・サービスを行う場所(例：銀行の窓口、ATM) 到着・・・待ち行列システムに人が訪れる動作(例：来店) 退去・・・サービスを受けてシステムから立ち去ること(例：退店) 2019/2/17

5 待ち行列モデルの図 2019/2/17

6 待ち行列モデルの特徴付け どうやって待ち行列モデルは特徴付けられるのか？ 到着過程とサービス時間について ４つの特徴量で特徴付けられる。
客の到着過程 サービス時間分布 窓口の数 待ち室容量(待ち室に収容可能な最大客数) 到着過程とサービス時間について 2019/2/17

7 到着過程とサービス時間 到着過程とは？ サービス時間とは？ 客の待ち行列への到着を表す確率過程のことを指す。
今回の研究ではポアソン分布を採用した。 サービス時間とは？ 客が窓口で費やす時間のことを指す。 今回の研究では指数分布を採用した。 2019/2/17

8 ポアソン分布（１） ポアソン分布とは？ 「単位時間あたりに平均 λ 回起こる現象が、単位時間に k 回起きる確 率」を表すのに用いられる確率分布のこと。 例：１時間当たり平均４人の客が来る店に、１時間に６人の客が来る 確率 2019/2/17

9 ポアソン分布（２） 具体的な数学で表すと？ 定義：𝜆 を正の整数とする。確率変数 Χ の確率質量関数が
　　　 𝑝 𝑟 =𝑃 𝑋=𝑟 = 𝑒 −𝜆 𝜆 𝑟 𝑟! , 𝑟=0, 1, 2,…, であるとき、Χ はパラメータ 𝜆 のポアソン分布に従う 　　　　といい、Χ ~ 𝑃 𝑂 (𝜆) と書く。 平均：𝜆, 分散：𝜆 2019/2/17

10 ポアソン分布（３） 2019/2/17

11 指数分布（１） 指数分布とは？ 「単位時間あたりに平均 λ 回起こる現象の発生間隔がｔ単位時間であ る確率」を表すのに用いられる確率分布のこと。 例：１時間当たり平均４人の客が来る店に、次の客が来るまでの間隔 が１２分である確率 2019/2/17

12 指数分布（２） 具体的な数学で表すと？ 定義：正の定数 𝜆 に対して、確率変数 Χ の密度関数が
　 　𝑓 𝑥 = 𝜆 𝑒 −𝜆𝑥 (𝑥≥0) (𝑥<0) であるとき、Χ はパラメータ 𝜆 の指数分布に従う 　　　　といい、Χ ~ 𝐸𝑥𝑝(𝜆) と書く。 平均： 1 𝜆 , 分散： 1 𝜆 2 2019/2/17

13 指数分布（３）   2019/2/17

14 ポアソン分布と指数分布（１） ポアソン分布と指数分布の違いとは？ 単位時間当たりに平均 λ 回起こるようなランダムなイベントに対して、
ある事象に対して「回数」に注目するか、「発生間隔」に注目するか の違いがある。 単位時間当たりに平均 λ 回起こるようなランダムなイベントに対して、 単位時間にイベントが起きる「回数」は平均 λ のポアソン分布に従 う。 イベントの「発生間隔」は平均 1 𝜆 の指数分布に従う。 2019/2/17

15 ポアソン分布と指数分布（２） 本研究で指数分布を用いる利点
進行中のサービスが終了する確率は、それまでサービスに要した時間 に依存しない（無記憶性）。 ある時刻に開始されるサービスは、それ以前に行なわれたサービスや 到着に依存しない（独立性）。 上記２つの利点により、ランダムな到着間隔やサービス時間 の表現として主に用いられているので採用した。 2019/2/17

16 待ち行列モデルの表現方法 待ち行列モデル表現のためにケンドール記号というものが使 われている。 A / B / X / Y / Z
Z：サービスの規範（省略している場合はFCFS） 2019/2/17

17 今回使用する待ち行列モデル 本研究には、待ち行列モデルの中でも代表的なM/M/1モ デルを用いている。 M/M/1モデルとは？
M/M/1/∞/FCFSとケンドールの記号で表される待ち行列モデル。 Mはマルコフ性を表している。 2019/2/17

18 マルコフ性について マルコフ性とは？ ある時点ｔでの状態が与えられると、時点ｔ以降のシステムの確率的 な変動はｔより前の状態の履歴とは無関係（独立）である性質。 無記憶性の一種であり、指数分布はマルコフ性を保証する。 2019/2/17

19 作成したプログラムの概要（１） プログラム作成に用いたツール OS：Linux CentOS7.2（仮想環境）
仮想環境作成ソフトウェア：VirtualBox, Vagrant Webサーバーソフトウェア：Apache マークアップ言語：HTML, CSS プログラミング言語：python, JavaScript(jQuery) Webフレームワーク：tornado ヒストグラム作成ツール：Chart.js 2019/2/17

20 作成したプログラムの概要（２） プログラムの特徴 時間に応じて待ち室や窓口に人が移っていく様子をアニメーションで表 示。
到着間隔やサービス時間をそれぞれ６通りに変更可能。 累計到着人数や待ち行列の長さ等の数値をリアルタイムで表示。 今までの到着間隔やサービス時間を全てヒストグラムにして表示。 表示するヒストグラムや次の到着・サービス時間の表示が切り替え可能。 2019/2/17

21 研究結果 １画面でアニメーションをつけて待ち行列の推移を表すこと に成功した。
場合によって予期せぬ挙動が起き、アニメーションと値の整 合性が取れないこともあった。 待ち時間に関しての値を表示できなかった 2019/2/17

22 考察 より場合ごとの挙動のプログラムを洗練させれば、より安全なプロ グラムになると思われる。
待ち時間も計測できれば、より実用的なプログラムになる。 今回のプログラムの仕組みは値を変更すれば他の待ち行列モデルに も応用できるので、より複雑な待ち行列モデルもわかりやすく表す ことができる。 例：複数窓口のM/M/Cモデル、有限容量待ち行列のM/M/1/Nモデル 2019/2/17

23 感想と今後の展望 感想 デザインは簡素なので作るのは簡単であったが、どうやって計算した 値をサーバーを通じて Webページに送るか等の待ち行列モデルの仕 組みづくりに苦労した。 今後の展望 現実にある窓口（例：銀行のATM）の様子を見てデータを採り、到着 時間やサービス時間、待ち行列の長さ等の値の整合性を調べることに よって、より実用的なプログラムになると思われる。 2019/2/17

24 参考資料（１） 図書 「待ち行列理論の基礎と応用」 共立出版 川島幸之助監修 「例題でわかる待ち行列理論入門」 日本理工出版会 北岡正敏著
「待ち行列理論の基礎と応用」　共立出版　川島幸之助監修 「例題でわかる待ち行列理論入門」　日本理工出版会　北岡正敏著 「混雑と待ち」　朝倉書店　高橋幸雄・森村英典著 「講義：確率・統計」　学術図書出版社　穴太克則著 2019/2/17

25 参考資料（２） ＵＲＬ https://atarimae.biz/archives/7372
Mars/5427/math/sw_waitque2.html 2019/2/17

26 ご静聴ありがとうございました 2019/2/17