スタートページWeb教材一覧オペレーションズリサーチ待ち行列

待ち行列の概要

オペレーションズ・リサーチ技法の一つである「待ち行列」について学習します。ここでは,その概要として,待ち行列とはどのようなものか,待ち行列で用いる用語・概念,ケンドールの記号による分類などを理解します。

キーワード

待ち行列,ケンドールの記号,リトルの公式


待ち行列の概念

待ち行列とは

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

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

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

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

一様分布の例

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

ランダム分布の例

もし,到着やサービスの時間間隔が平均では5分と3分であるが,その分布がデタラメ(ランダムといいます)である(「ポアソン到着,指数サービス」といいます)したとき,理論的な計算をしますと,サービスを待っている人の平均値Lqは0.9人であり,到着してからサービスを受けるまでの平均待ち時間Wqは4.5分になります。平均サービス時間が4.5分ならば,Lq=8.1人,Wq=40.5分にもなってしまいます。
 このように,直感とはかなり異なる状況になるのです。このようなことを計画時に知らずに設備投資をすると,実施してから多くのトラブルを生じる危険があります。待ち行列の知識が必要になるのです。

待ち行列で用いる記号

待ち行列では,次の記号をよく用います。
  λ(ラムダ):客の平均到着率[人/時]⇔1/λ:客の平均到着間隔[時/人]
  μ(ミュー):一つの窓口の平均サービス率[人/時]⇔1/μ:窓口の平均サービス時間[時/人]
  s:窓口の個数
  ρ(ロー)=λ/(sμ)    窓口が1個のときは ρ=λ/μ
  P0:サービス中を含む(「系の中」という)客数が0である確率
     (窓口が1個のときは,待たずにサービスが受けられる確率)
  Pn:系の中の客数がn人である確率
  L:系の中にいる客の平均人数[人]=1P1+2P2+3P3+・・・+nPn
  Lq:サービスを待っている人の平均人数[人]=1Ps+1+2Ps+2+3Ps+3+・・・+(n-s)Pn
  W:系の中(到着してからサービスを受けて去るまで)の平均時間[時]
  Wq:到着してからサービスを受けるまでの平均待ち時間[時]

待ち時間の分類(ケンドールの記号)

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

リトルの公式

上記のような分類により多くの関係式がありますが,ほとんどの場合には次の式が成立しますので,L,Lq,W,Wqのいずれか1つを知れば,他の3つは簡単に求めることができます。これをリトルの公式といいます。
  L=Lq+λ/μ
  Wq=Lq/λ
  W=Wq+1/μ

このシリーズの目次

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

待ち行列の種類
M/M/1(or-que-mm1
待ち行列での最も代表的なケースです。窓口が1個で,客の到着分布,窓口のサービス分布がランダム(すなわち,ポアソン到着・指数サービス)であり,客の行列の長さに制限がない場合を取扱います。
ここでの公式は,情報処理技術者試験などでも,知っているものとして出題されますので,覚えておくことが必要です。
  P0=1-ρ
  P=ρ0=ρ(1-ρ)
  L=ρ/(1-ρ)
  Lq=ρ2/(1-ρ)
  W=L/λ=1/(μ-λ)
  Wq=Lq/λ=λ/(μ(μ-λ))
G/G/1(or-que-gg1
M/M/1では,その分布がランダム分布の場合でした。これを「ポアソン到着,指数分布」といいますが,ポアソン分布,指数分布について説明します。
また,到着やサービスの分布により,LやWに大きな違いが出ることは,先に示しました。ここでは分布が,一定分布であるとき,アーラン分布(ランダム分布と一定分布の中間的な分布)のときについて考えます。
M/M/s(or-que-mms
窓口が複数のケースです。平均サービス率が2μである窓口が1個の場合とμの窓口が2個の場合では,LやWに大きな違いがあります。これは1台の高性能設備で集中するか,複数の低性能設備に分散するかなどの検討に用いられます。
M/M/1(N)(or-que-mm1n
行列の長さに制限があるケースです。ここまでは,行列の長さの制限はなく到着した客はかならずサービスを受けるまで待っているケースでした。ところが,駐車場のように行列に制限があるとか,長い行列があれば並ばずに去ることもあります。また,電話のお話中のように,行列そのものが存在できないこともあります。
待ち時間の分布(or-que-pt
これまでは,主にLやWqなどの平均値を取扱ってきましたが,顧客の観点からは,平均待ち時間よりも,長く待つことがどれだけあるのかという尺度のほうが適切でしょう。ここでは,M/M/1およびM/M/Sについて,到着してからサービスを受けるまでの時間の分布について考えます。
プログラム(or-que-program
M/M/s型の計算プログラム
図表(or-que-chart
M/M/s型の計算図表

理解度チェック

第1問

  1. 待ち行列の公式で「ラッシュアワーでの改札口の混雑を解消するために,スイカにより改札口でもたつくのを防ぐ」に適切な変数記号は何か。
    到着してから改札口を出るまでの時間:W
  2. 待ち行列の公式で「3人の修理工がいるが,2名にするためには,どのような修理方法の改善が必要になるか」に適切な変数記号は何か。
    故障してから修理工が到着するまでの時間:Wq
  3. 待ち行列の公式で「喫茶店の座席数をいくつにするか」に適切な変数記号は何か。
    窓口の数:s

第2問

  1. 身の回りにある待ち行列の例をあげて,ケンドールの記号でどのケースになるかを示せ。
  2. ちょっとした到着率やサービス率の変化が,行列の長さや待ち時間に大きな影響を与える例を列挙せよ。

過去問題: 「待ち行列」