待ち行列の概念
待ち行列とは
お店のレジを考えましょう。客がレジに到着し支払をして（これを「サービスを受ける」といいます）去っていきます。到着したときにレジが空いていれば，待たずにサービスを受けられますが，サービス中の人がいる場合には，自分の番がくるまで待ちますので行列ができます。待ち行列の理論（Queing Theory）とは，このような系について，待たないでサービスを受ける確率，行列の平均長さ，到着してから去るまでの平均時間などを計算する理論です。
待ち行列には，次のように多様な例があります。
客 窓口
－ －－
客 受付窓口
患者 診療
自動車 有料道路料金所
機械故障 修理工
処理要求 ホストコンピュータ
電話の送信 電話の受信（お話中）
待ち行列と到着・サービス分布の関係
客が平均５分おきに到着し，レジは平均３分かかるとします。もし，客の到着間隔とレジのサービス時間が一定であれば，待ちが生じることはありません。
しかし，実際には客の到着は平均５分であっても，３分，８分，４分というようにバラツキがありますし，レジのサービス時間も平均は３分だとしても，それより短いこともあれば，長くかかることもあります。そのときには，下図のように待ちが生じます。
もし，到着やサービスの時間間隔が平均では５分と３分であるが，その分布がデタラメ（ランダムといいます）である（「ポアソン到着，指数サービス」といいます）したとき，理論的な計算をしますと，サービスを待っている人の平均値Ｌqは０.９人であり，到着してからサービスを受けるまでの平均待ち時間Ｗqは４.５分になります。平均サービス時間が４.５分ならば，Ｌq＝８.１人，Ｗq＝４０.５分にもなってしまいます。
このように，直感とはかなり異なる状況になるのです。このようなことを計画時に知らずに設備投資をすると，実施してから多くのトラブルを生じる危険があります。待ち行列の知識が必要になるのです。
待ち行列で用いる記号
待ち行列では，次の記号をよく用います。
λ（ラムダ）：客の平均到着率［人/時］⇔１/λ：客の平均到着間隔［時/人］
μ（ミュー）：一つの窓口の平均サービス率［人/時］⇔１/μ：窓口の平均サービス時間［時/人］
ｓ：窓口の個数
ρ（ロー）＝λ／(ｓμ) 窓口が１個のときは ρ＝λ／μ
Ｐ0：サービス中を含む（「系の中」という）客数が０である確率
（窓口が１個のときは，待たずにサービスが受けられる確率）
Ｐn：系の中の客数がｎ人である確率
Ｌ：系の中にいる客の平均人数［人］＝１Ｐ1＋２Ｐ2＋３Ｐ3＋・・・＋ｎＰn
Ｌq：サービスを待っている人の平均人数［人］＝１Ｐｓ＋１＋２Ｐｓ＋２＋３Ｐｓ＋３＋・・・＋(ｎ－ｓ)Ｐn
Ｗ：系の中（到着してからサービスを受けて去るまで）の平均時間［時］
Ｗq：到着してからサービスを受けるまでの平均待ち時間［時］
ポアソン分布と指数分布
客の到着が単位時間あたり平均λでランダムに発生するとき，平均がλのポアソン分布になり，ある客が到着してから次の客が到着するまでの時間の間隔は平均１／λの指数分布になります。すなわち，ポアソン分布と指数分布は裏返しの関係があるのです。
ランダムとは
ランダムとはデタラメ（＝法則性がない）のことですが，数学的には次の３つの仮定が可能であることをいいます。
- 独立性
- ある単位時間に到着する客の数は，それ以前の客の到着状況とは無関係だという性質です。先に大勢来たから今度は少ないだろうとか，これまでに増加しているのでもっと増えるだろうというような，以前の影響は受けないということです。
- 定常性
- 朝や夕方のアッシュアワーのような時間帯による変化はなく，到着の分布は常に一定であるという性質です。系の中にいる人数がｎ人である確率Ｐnは，時間によらず一定になります。
- 稀少性
- 単純にいえば，客は連れ立って来ることはなく，一人ずつ来るということです。いいかえれば，到着間隔は０にはならないということです。
ポアソン分布
単位時間内に一人の客が来る確率をｐとすれば，来ない確率は（１－ｐ）です。客の総数がＮ人であり，そのうちのｎ人が来るとすれば，その確率Ｐｎは，
Ｐｎ＝ＮＣｎｐｎ(１－ｐ)Ｎ－ｎ
の二項分布になります。このとき，Ｎｐ＝λとして，Ｎを大きくすると，
Ｐｎ＝（λｎ／ｎ！）×ｅ－λ
ｎ！ （ｎの階乗）＝１×２×３×・・・×ｎ， ｅ （自然対数の底）＝2.71828
に近づきます。これをポアソン分布といいます。このポアソン分布の平均はλ，分散もλです。
ポアソン分布のグラフを示します。ｎ＝４のとき，λ＝２のグラフのＰｎ，すなわちＰ２はほぼ０.１になります。これは，単位時間に到着する平均が２のとき，単位時間に４人が到着する確率が０.１であるということです。
各曲線がｎ＝λ付近で最大になるのは，実際に到着する人数は平均に近いことが多いということですし，λが大きくなるほど平らになるのは，平均人数が多いほど実際に来る人数のバラツキが大きくなるからです。これは常識と一致しますね。
指数分布
到着間隔がｔだということは，「ｔ時間までには来なかった」ことと「ｔ時に客が１人来た」ことのどちらかが起こるということです。ｔにおける確率をｆ(ｔ) とすれば，「ｔ時に客が１人来た」確率はｆ(ｔ)／λであり，「ｔ時間までには来なかった」のはｆ(ｔ) の０～ｔまでの積分になりますから，
が成立します。これを指数分布といます。
指数分布の平均は１／λ，分散は１／λ２です。
このｆ(t)をｔから∞まで積分すると，ｅ－λｔになります。これは，到着間隔がｔよりも大きいときの確率になります。このグラフは下のようになります。
λｔが１.６のときの確率は０.２になります。これは実際の到着ｔ＝１.６／λ［時］以上である確率が０.２であるということです。仮にλを２［人/時］（平均到着間隔は１/２［時/人］）としましょう。すると，ｔ＝１.６／２＝０.８［時］であり，これは平均到着間隔の１.６倍です。すなわち，このグラフの横軸は平均到着間隔の倍数と考えてよいのです。
なおここまでは，説明をしやすいために，客の到着を例にしましたが，窓口のサービスについても同様です。平均サービス率がμのときは次のようになります。
| 事象 | 分布の種類 | 式 | 平均 | 分散 |
| サービス完了回数 | ポアソン分布 | Ｐｎ＝（μｎ／ｎ！）×ｅ－μ | μ | μ |
|---|---|---|---|---|
| サービス時間の分布 | 指数分布 | ｆ(ｔ）＝ μｅ－μｔ | １／μ | １／μ２ |
アーラン分布（Ｍ／Ｅｋ／１）
実務では，一定分布になることは稀ですし，指数分布のようにｔ＝０のときが最大になることも少ないでしょう。指数分布と一様分布との中間に相当する分布にアーラン分布があります。ｋをパラメタ（位相）として，次式で表されます。
ｆ(ｔ）＝｛(μｔ)ｋ－１／(ｋ－１)！｝×μｅ－μｔ
上式で，ｋ＝１とすると，｛ ｝の中が１になり，指数分布と一致します。また，ｋ＝∞のときは，ｆ(ｔ）＝１／μになり，一様分布と一致します。アーラン分布をイメージ的に解釈すると（客の到着では）ｋ人おきの客を対象としたことになります。
なお，ｋを変化させたときのグラフは，次のようになります。
アーラン分布の平均は １／μ，分散は １／ｋμ２ になります。
待ち時間の分類（ケンドールの記号）
ケンドール（Kendall）は，待ち行列を次のように分類しました。これをケンドールの記号といいます。到着・サービスの分布，窓口の個数，行列の制限有無により分類しています。なお，この他にも，客の優先順位による区分が考えられますが，ここではすべて先着順とします。
リトルの公式
上記のような分類により多くの関係式がありますが，ほとんどの場合には次の式が成立しますので，Ｌ，Ｌq，Ｗ，Ｗqのいずれか１つを知れば，他の３つは簡単に求めることができます。これをリトルの公式といいます。
Ｌ＝Ｌq＋λ／μ
Ｗq＝Ｌq／λ
Ｗ＝Ｗq＋１／μ
このシリーズの目次
このシリーズでは，次のケースについて検討します。
最も基本的なものはＭ／Ｍ／１で、これは初級レベルの情報技術者試験でも出題されています。他のモデルは、私たちのレベルを越えますが、実社会ではむしろ一般的です。イメージを理解してもらうために掲げました。
単一窓口
- Ｍ／Ｍ／１（or-que-mm1）
- 待ち行列での最も代表的なケースです。窓口が１個で，客の到着分布，窓口のサービス分布がランダム（すなわち，ポアソン到着・指数サービス）であり，客の行列の長さに制限がない場合を取扱います。
Ｐ0＝１－ρ
Ｐｎ＝ρｎＰ0＝ρｎ(１－ρ)
Ｌ＝ρ／(１－ρ)
Ｌq＝ρ2／(１－ρ)
Ｗ＝Ｌ／λ＝１／(μ－λ)
Ｗq＝Ｌq／λ＝λ／(μ(μ－λ)) - Ｇ／Ｇ／１（or-que-gg1）
- Ｍ／Ｍ／１では，その分布がランダム分布の場合でした。これを「ポアソン到着，指数分布」といいますが，ポアソン分布，指数分布について説明します。
また，到着やサービスの分布により，ＬやＷに大きな違いが出ることは，先に示しました。ここでは分布が，一定分布であるとき，アーラン分布（ランダム分布と一定分布の中間的な分布）のときについて考えます。 - Ｍ／Ｍ／１(Ｎ)（or-que-mm1n）
- 行列の長さに制限があるケースです。ここまでは，行列の長さの制限はなく到着した客はかならずサービスを受けるまで待っているケースでした。ところが，駐車場のように行列に制限があるとか，長い行列があれば並ばずに去ることもあります。また，電話のお話中のように，行列そのものが存在できないこともあります。
複数窓口
- Ｍ／Ｍ／ｓ（or-que-mms）
- 窓口が複数のケースです。平均サービス率が２μである窓口が１個の場合とμの窓口が２個の場合では，ＬやＷに大きな違いがあります。これは１台の高性能設備で集中するか，複数の低性能設備に分散するかなどの検討に用いられます。
- 待ち時間の分布（or-que-pt）
- これまでは，主にＬやＷqなどの平均値を取扱ってきましたが，顧客の観点からは，平均待ち時間よりも，長く待つことがどれだけあるのかという尺度のほうが適切でしょう。ここでは，Ｍ／Ｍ／１およびＭ／Ｍ／Ｓについて，到着してからサービスを受けるまでの時間の分布について考えます。
- プログラム（or-que-program）
- Ｍ／Ｍ／ｓ型の計算プログラム
- 図表（or-que-chart）
- Ｍ／Ｍ／ｓ型の計算図表
シミュレーション
待ち行列を検討する現実の対象は複雑なので、これらの理論的な公式を単純に適用できないことが多くあります。そのような対象には、複雑な定式化を考えるよりも、現実のプロセスをモデル化して、机上実験するほうが適切です。
そのようなアプローチをシミュレーションといい、ＯＲの大きな分野になっています。これに関しては、別章「シミュレーション」を参照してください。