待ち行列の概要

待ち行列の概念

待ち行列とは

お店のレジを考えましょう。客がレジに到着し支払をして（これを「サービスを受ける」といいます）去っていきます。到着したときにレジが空いていれば，待たずにサービスを受けられますが，サービス中の人がいる場合には，自分の番がくるまで待ちますので行列ができます。待ち行列の理論（Queing Theory）とは，このような系について，待たないでサービスを受ける確率，行列の平均長さ，到着してから去るまでの平均時間などを計算する理論です。
　待ち行列には，次のように多様な例があります。

　　　客　　　　　　　窓口
　　　－　　　　　　　－－
　　　客　　　　　　　受付窓口
　　　患者　　　　　　診療
　　　自動車　　　　　有料道路料金所
　　　機械故障　　　　修理工
　　　処理要求　　　　ホストコンピュータ
　　　電話の送信　　　電話の受信（お話中）

待ち行列と到着・サービス分布の関係

客が平均５分おきに到着し，レジは平均３分かかるとします。もし，客の到着間隔とレジのサービス時間が一定であれば，待ちが生じることはありません。

しかし，実際には客の到着は平均５分であっても，３分，８分，４分というようにバラツキがありますし，レジのサービス時間も平均は３分だとしても，それより短いこともあれば，長くかかることもあります。そのときには，下図のように待ちが生じます。

もし，到着やサービスの時間間隔が平均では５分と３分であるが，その分布がデタラメ（ランダムといいます）である（「ポアソン到着，指数サービス」といいます）したとき，理論的な計算をしますと，サービスを待っている人の平均値Ｌ_qは０.９人であり，到着してからサービスを受けるまでの平均待ち時間Ｗ_qは４.５分になります。平均サービス時間が４.５分ならば，Ｌ_q＝８.１人，Ｗ_q＝４０.５分にもなってしまいます。
　このように，直感とはかなり異なる状況になるのです。このようなことを計画時に知らずに設備投資をすると，実施してから多くのトラブルを生じる危険があります。待ち行列の知識が必要になるのです。

待ち行列で用いる記号

待ち行列では，次の記号をよく用います。
　　λ（ラムダ）：客の平均到着率［人/時］⇔１/λ：客の平均到着間隔［時/人］
　　μ（ミュー）：一つの窓口の平均サービス率［人/時］⇔１/μ：窓口の平均サービス時間［時/人］
　　ｓ：窓口の個数
　　ρ（ロー）＝λ／(ｓμ)　　　　窓口が１個のときは ρ＝λ／μ
　　Ｐ₀：サービス中を含む（「系の中」という）客数が０である確率
　　　　　（窓口が１個のときは，待たずにサービスが受けられる確率）
　　Ｐ_n：系の中の客数がｎ人である確率
　　Ｌ：系の中にいる客の平均人数［人］＝１Ｐ₁＋２Ｐ₂＋３Ｐ₃＋・・・＋ｎＰ_n
　　Ｌ_q：サービスを待っている人の平均人数［人］＝１Ｐ_ｓ＋１＋２Ｐ_ｓ＋２＋３Ｐ_ｓ＋３＋・・・＋(ｎ－ｓ)Ｐ_n
　　Ｗ：系の中（到着してからサービスを受けて去るまで）の平均時間［時］
　　Ｗ_q：到着してからサービスを受けるまでの平均待ち時間［時］

待ち時間の分類（ケンドールの記号）

ケンドール（Kendall）は，待ち行列を次のように分類しました。これをケンドールの記号といいます。到着・サービスの分布，窓口の個数，行列の制限有無により分類しています。なお，この他にも，客の優先順位による区分が考えられますが，ここではすべて先着順とします。

リトルの公式

上記のような分類により多くの関係式がありますが，ほとんどの場合には次の式が成立しますので，Ｌ，Ｌ_q，Ｗ，Ｗ_qのいずれか１つを知れば，他の３つは簡単に求めることができます。これをリトルの公式といいます。
　　Ｌ＝Ｌ_q＋λ／μ
　　Ｗ_q＝Ｌ_q／λ
　　Ｗ＝Ｗ_q＋１／μ

このシリーズの目次

このシリーズでは，次のケースについて検討します。

Ｍ／Ｍ／１（or-que-mm1）

待ち行列での最も代表的なケースです。窓口が１個で，客の到着分布，窓口のサービス分布がランダム（すなわち，ポアソン到着・指数サービス）であり，客の行列の長さに制限がない場合を取扱います。
ここでの公式は，情報処理技術者試験などでも，知っているものとして出題されますので，覚えておくことが必要です。
　　Ｐ₀＝１－ρ
　　Ｐ_ｎ＝ρ^ｎＰ₀＝ρ^ｎ(１－ρ)
　　Ｌ＝ρ／(１－ρ)
　　Ｌ_q＝ρ²／(１－ρ)
　　Ｗ＝Ｌ／λ＝１／(μ－λ)
　　Ｗ_q＝Ｌ_q／λ＝λ／(μ(μ－λ))

Ｇ／Ｇ／１（or-que-gg1）

Ｍ／Ｍ／１では，その分布がランダム分布の場合でした。これを「ポアソン到着，指数分布」といいますが，ポアソン分布，指数分布について説明します。
また，到着やサービスの分布により，ＬやＷに大きな違いが出ることは，先に示しました。ここでは分布が，一定分布であるとき，アーラン分布（ランダム分布と一定分布の中間的な分布）のときについて考えます。

Ｍ／Ｍ／ｓ（or-que-mms）

窓口が複数のケースです。平均サービス率が２μである窓口が１個の場合とμの窓口が２個の場合では，ＬやＷに大きな違いがあります。これは１台の高性能設備で集中するか，複数の低性能設備に分散するかなどの検討に用いられます。

Ｍ／Ｍ／１(Ｎ)（or-que-mm1n）

行列の長さに制限があるケースです。ここまでは，行列の長さの制限はなく到着した客はかならずサービスを受けるまで待っているケースでした。ところが，駐車場のように行列に制限があるとか，長い行列があれば並ばずに去ることもあります。また，電話のお話中のように，行列そのものが存在できないこともあります。

待ち時間の分布（or-que-pt）

これまでは，主にＬやＷqなどの平均値を取扱ってきましたが，顧客の観点からは，平均待ち時間よりも，長く待つことがどれだけあるのかという尺度のほうが適切でしょう。ここでは，Ｍ／Ｍ／１およびＭ／Ｍ／Ｓについて，到着してからサービスを受けるまでの時間の分布について考えます。

プログラムとグラフ（or-que-program）

ランダム分布における代表的な尺度を計算するプログラムとグラフです。