待ち行列モデルによる時分割サービスのシミュレーション
高橋茉穂

1(指導教員：吉田裕亮)
2.3

はじめにシミュレーション手順

現在の時刻を i とし, 総シミュレーション時間を timeとする. 次の客が到着するまでの時間を R とし, 客の残りのサービス時間を S と表す.

待ち行列とは何かを待つことによる, 「到着時間」と「到着人数」, 「サービス期間」と「サービス人数」などの関係を数学的に把握するための理論である. 銀行のＡＴＭや空港の出国審査窓口など私たちの身近に多く存在し, 同様に計算機の内部でも待ち行列が使われている. 時分割サービスと呼ばれる方法と割り込み処理で, 見かけ上複数人が同時に一台の計算機を利用することを可能にしている.

1). 初期値の設定 R = 0, S = 0, time = 10000, i = 0.
2). [客の到着] R = 0 なら, 客が到着し, R を更新する. (指数分布) R = 0 なら, R を 1 減らす.
3). [サービスの開始と完了] S = 0 なら, 次の客がサービスを受ける. S を更新する. (指数分布)

どのようなサービス方法が良いかは待ち行列理論の大きな課題の１つである. サービス方法の評価に関しては, 平均待ち時間やその分散が小さいほど良いシステムといえる. 本研究では, 時分割サービスのモデルに関して数値シミュレーションを行い, 効率の良い待ち行列を検証する.

4). S>0 なら, S を 1 減らす.
5). i = time なら, i を 1 増やして 2) へ.

2

待ち行列のシミュレーション

32.1

指数分布とポアソン分布

時分割サービス (モデル０)
時間を微小の単位に分け, 順番に別の客をサービスする方法. サービス時間が残っている客は最後尾に並び直す. このような通常の時分割サービスを以後, モデル０と呼ぶことにする.

通常の待ち行列を考えると, まったく客がこない場合もあれば, 一度にたくさんの客が到着することがある. 待ち行列のシミュレーションを行うには, 客の到着間隔と, サービス時間を指数分布に従う乱数で発生させるか, 単位時間あたりの客の到着人数と, 単位時間あたりのサービス人数をポアソン分布に従った乱数によって決定させることが考えられる. このように, 実はポアソン分布と指数分布は表裏一体であり, 指数分布に従った時間間隔で客が到着すると, 単位時間あたりの到着数はポアソン分布になる.
本研究では時間間隔の方を乱数で発生させるシミュレーションを行うことにする. 平均値 m の指数分布に従う乱数 X は, [0, 1] の一様乱数を R として,モデル１
提案モデル１は, 残りのサービス時間が少ない客が連続でサービスを受け続けるモデルである.

1). 到着した客は列の先頭に入る.
2). 先頭の客が窓口でサービスを 1 単位時間受ける.
3). 残りのサービス時間が a 分以下 (a = 21) の客はサービスが終わるまで連続でサービスを受け, それ以外の客は列の最後尾に並び直す.

X = −m ∗ ln (1 − R)
で与えられる.

2.2

モデル２提案モデル２は, 優先度順に並ぶモデルである. 優
先度は数字が小さいほど高くなる. 待ち時間の長さにより優先度をあげることによって優先度の低い客が待たされ続けることを避ける.

Ｍ/Ｍ/１モデル

Ｍ/Ｍ/１というのはケンドールの記法で表記された
待ち行列のモデルで, 到着間隔, サービス時間がそれぞれ指数分布に従い, 窓口が１つであるモデルのことである.
待ち行列に加わる人

待ち行列

提案モデル

優先度１ 残りのサービス時間が b 分未満 (b = 23)の客優先度２ 残りのサービス時間が b 分以上で, c 分以上(c = 59) 待っている客
優先度３ 残りのサービス時間が b 分以上の客サービスを受ける人

図１: Ｍ/Ｍ/１モデル

優先度３

待ち行列のシミュレーション手法としては, イベン
トドリブン型とタイムドリブン型がある. 本研究では,イベントドリブン型を用いてシミュレーションを行う.
ここでイベントは, 客の到着, サービスの開始, サービスの終了の３つである.

優先度２優先度１

図２: モデル２のイメージ

551). 到着した客はそれぞれの優先度の列の先頭に並ぶ.

実験１では, サービスを完了した客数はモデル０〜２でほとんど差がない. しかし待ち時間は, モデル０に比べてモデル１, ２が約半分の時間になった. さらに, 待ち人数や標準偏差もモデル１, ２がモデル０より小さいという結果が出た.

2). 先頭の客が窓口でサービスを 1 単位時間受ける.
3). サービスの残り時間や待ち時間によって, それぞれの優先度の列の最後尾に並び直す.

4

実験２

実験概要

サービス完了人数

待ち時間

待ち人数

モデル 1

646.93817.101048.67224.40147.28
63.89

モデル 2

820.70303.1762.64

サービス完了人数

待ち時間

待ち人数

モデル 0

22.72

118.60

19.31

モデル 1

19.89
20.51

31.57
39.33

8.75
8.51

M/M/1 モデルのシミュレーションでは, イベントの発生時にその都度, 次のイベントの発生時刻を計算していたが, 本研究では指数分布によって決定させた客の到着間隔とサービス時間をそれぞれ 10000 個× 30通り用意し, そのデータを用いて１モデルあたり 30 回のシミュレーションを行う. ３つのモデルのサービスを終えた平均客数, 平均待ち時間, 平均待ち人数とそれらの標準偏差を比較する.

モデル 0設定

モデル 2

表３

表４: 実験２における標準偏差• 1 単位時間は 1 分• 客の平均到着間隔は 10 分 (1 時間で 6 人到着)
• 平均サービス時間は 15 分 (1 時間で 4 人サービスを受ける)

窓口数を１にしたことで, 利用率が１より大きくな
る実験２では, サービスを完了した客数がモデル０よりモデル１, ２のほうが 200(人) 程多い. つまりスループットが高いということが分かる.

実験１
窓口数は２とする. このとき, 客の到着率 λ = 6/60 =0.1, サービス率 µ = 4/60 = 0.067, 窓口数 s = 2 となる. サービスの利用率 ρ は λ/sµ で求められるので, 窓口数２のときの利用率は ρ = 0.75 である.

6

実験結果からモデル１, ２はモデル０よりも平均待ち時間やその標準偏差が小さく, さらにスループットが高いので, 通常の時分割サービスより良いモデルであると考えられる. 実験１では, 単位時間あたりにサービスを終える客数が到着する客数を超えない設定だったため, サービスを完了した客数に差がなかったと思われる. しかし, 実験２でサービスの利用率を１より大きくすることによってモデル１, ２のスループットの高さが検証された.
このように, サービスの処理方法や並び方を工夫することで, 効率が良い待ち行列モデルを発見することができる.

図３: 実験１のイメージ
実験２
窓口数は１とする. このときのサービスの利用率は
ρ = 1.5 である. 利用率が 1 より大きくなると, 待ち行列が徐々に長くなることを意味する.

57

実験１
待ち時間待ち人数

モデル 0938.77

14.002.77

モデル 1939.53
939.60

7.68
7.93

2.18
2.20

モデル 2

参考文献

表１

[1] 宮沢政清, 待ち行列の数理とその応用, 2006

サービス完了人数

待ち時間待ち人数

モデル 1

26.16
25.93

3.28
1.57

0.36
0.20

モデル 2

25.97

1.51

0.19

モデル 0

今後の課題

今回の実験結果からは, モデル１とモデル２で待ち時間などにほとんど差がないため, どちらのほうが良いモデルであるかは判断しにくい. したがって, 今後は客の到着間隔やサービス時間, または窓口数や並び方を変更した場合にどのような結果が得られるか検証したい. そして現在の提案モデルよりも, 平均待ち時間や分散が小さく, さらに計算時間が短くなるようなモデルを探したいと考えている.

結果
サービス完了人数

考察[2] 待ち行列のシミュレーション(http://www.f.ait.kyushu-u.ac.jp/˜arakawa/wpcontent/uploads/2009/04/enshu20100628kaisetsu.pdf)

表２: 実験１における標準偏差56