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

待ち行列の基本形(M/M/1)

学習のポイント

待ち行列のうちで最も基本的なモデルであるM/M/1(厳密にはM/M/1(∞)といいます),すなわち,
   客の到着および窓口のサービスの分布がランダム
   窓口の個数が1個
   客が到着したときに先客がいれば,自分の番になるまで待つ
の場合を検討します。
 ここでの考え方は,他の場合での基本になるものですから,十分に理解することが必要です。

それには、実際の客の動きをシミュレーションしてみるのが適切です。→参照:「M/M/1型待ち行列のシミュレーション」


公式を求めるプロセス

客が単位時間に到着する平均値(平均到着率)をλ(ラムダと読む)[人/時],1つの窓口が単位時間にサービスを完了する人数の平均値(平均サービス率)をμ(ミューと読む)[人/時]とします。

系の中にn人がいる確率

サービスを受けている人とサービスを待っている人の全体(これを「系の中」という)の人数がn人である確率をPnとします。

状態推移の図

系の状態が安定しているということは,ある時刻tでのPnと,t+⊿tでのPnが等しいということですから,
    tでn-1人だったのが,t+⊿tでn人になる   λ⊿tPn-1
  + tでn-1人だったのが,t+⊿tでn人になる   μ⊿tPn+1
  = tでn人だったのが,t+⊿tでn+1人になる   λ⊿tPn
    tでn人だったのが,t+⊿tでn-1人になる   μ⊿tPn
が成立する必要があります。すなわち,λPn-1+μPn+1(λ+μ)Pn が成立します。
 しかし,上の式はn=0のときには,Pn-1がP-1になってしまいます。P0とP1の間では,⊿tの間に,
    tで0人だったのが,t+⊿tで1人になる   λ⊿tP0
  = tで1人だったのが,t+⊿tで0人になる   μ⊿tP1
すなわち, λP0=μP1 となります。

この状態方程式
   λPn-1+μPn+1=(λ+μ)Pn
   λP0=μP1
を,ρ=λ/μとおいて解くと,
   Pn=ρ0
となります。
 ところで, P0+P1+P2+・・・+Pn+・・・=1 ですから,
   (1+ρ+ρ+・・・+ρ+・・・)P0=1
となり,
   系の中の人数が0人である確率  P0=1-ρ
   系の中の人数がn人である確率  Pn=ρn(1-ρ)
が得られます。 (その証明)

     A=1+ρ+ρ+・・・+ρ
    ρA=  ρ+ρ+・・・   +ρn+1
(1-ρ)A=1-ρn+1
     A=(1-ρn+1)/(1-ρ)
ここで,0<ρ<1 ですから,n→∞のときはρn+1→0になります。
従って, A=1/(1-ρ) が得られます。

人数と時間の平均値

系の中にいる人数(サービス中の人数も含む)の平均値Lは,
   L=1P1+2P2+・・・+nPn+・・・
    =(1ρ+2ρ2+・・・+nρn+・・・)(1-ρ)
    =ρ/(1-ρ)
となります。 (その証明)

    B=1ρ+2ρ2+・・・+nρn
   ρB=   1ρ2+・・・+(n-1)ρn+nρn+1
(1-ρ)B={1ρ+1ρ2+・・・+1ρn}-nρn+1
n→∞のときnρn+1→0であり,{ }の中はρA=ρ/(1-ρ) なので
B={ρ/(1-ρ) }/(1-ρ)=ρ/(1-ρ)2
したがって, L=B(1-ρ)=ρ/(1-ρ) が得られます。

到着してからサービスを受けるまで待っている(サービス中の人は含まない)の平均値Lqは,
   Lq=1P2+2P3+・・・+(n-1)Pn+・・・
    =(1ρ2+2ρ3+・・・+(n-1)ρn+・・・)(1-ρ)
    =Lρ=ρ/(1-ρ)
となります。

到着してからサービスを受けるまでの平均待ち時間Wqは,待っている人数Lqにより生じたのですし,平均到着間隔は1/λですから,全体ではLq/λの時間がかかったことになります。すなわち,
   Wq=Lq/λ
となります。
     系の中にいる全時間Wは,待っている時間とサービス時間の合計なので,
   W=Wq+1/μ=(L-λ/μ)/λ+1/μ
    =L/λ
になります(L/μではないことに注意!)。

公式のまとめ(これは覚えてください)

  客の平均到着率:    λ[人/時] ⇔ 平均到着間隔:  1/λ[時/人]
  窓口の平均サービス率: μ[人/時] ⇔ 平均サービス時間:1/μ[時/人]
    ρ=λ/μ 窓口の稼働率,客が到着したとき待ちが生じる確率

  系の中に人がいない確率: P0=1-ρ (待たないでよい確率)
  系の中にn人がいる確率: Pn=ρn0=ρn/(1-ρ)
  
  サービスを待っている人の平均人数:Lq=ρ2/(1-ρ)
  サービス中も含む系内の平均人数: L=Lq+λ/μ=ρ/(1-ρ)

  到着してからサービスを受けるまでの平均待ち時間: q=Lq/λ=λ/μ(μ-λ)
  到着してからサービスを受けて去るまでの平均時間: W=Wq+1/μ=1/(μ-λ)
   (上の赤い部分リトルの公式です。)

なお,上式を変形すると,
   L =ρ/(1-ρ)   W =L/λ
   Lq=Lρ       Wq=Wρ
となります。LqやWqは,LρやWρに似ていますね!?

L,Lqのグラフ

下図は,ρとL,Lqの関係をグラフにしたものです。
 これから,LやLqはρが1に近づくにつれて急激に増大することがわかります。客の到着間隔が10分,サービス時間が9分であるとき,これらが一定であれば待ちは生じないのに,それらがランダムなために,サービスを待っている人数が8人,サービスを受けている人も入れると9人になるのです。このようなことは直感とかなり異なりますね。このようなことを計画時に知っていないと,実施時に大きなトラブルになります。

ρとL,Lqのグラフ
米海軍の例

有名な例を紹介しましょう(大前義次,森村英典『待ち行列の理論と実際』日科技連,1962. p.46より)。第2次世界大戦中,アメリカからイギリスへの護送船団は,ニューヨーク港から80%,バルチモア港から20%から出港していた。米海軍は,それを不経済だと考え,すべてニューヨーク港から出港することにした。ところが,出港のための所要時間が従来の2倍になってしまった。米海軍は,敵国工作員によるサボタージュが行われたのではないかと調査をしたが,そのような事実はなく理由不明であり,ORグループに原因解明を依頼した。その結果は・・・
 おわかりですね。ニューヨーク港での到着率の20%の増加が,Wを急激に増大させていたのです。

理解度チェック

第1問

  1. 1台のレジがある。客の到着が1時間あたり平均12人であり,レジでの所要時間は平均3分であるとき,次の値を求めよ。
     1 到着したとき,すぐにサービスが受けられる確率
     2 系の中にいる人の平均人数
     3 サービスを待っている人の平均人数
     4 到着してからサービスを受けて去るまでの平均時間
     5 到着してからサービスを受けるまでの平均待ち時間
    客の到着が1時間あたり平均12人→λ=12/60=1/5[人/時]
    レジでの所要時間は平均3分→μ=1/3[人/時]
      ρ=λ/μ=(1/5)/(1/3)=3/5=0.6
    1 P0=1-ρ=1-0.6=0.4
    2 L=ρ/(1-ρ)=0.6/(1-0.6)=1.5[人]
    3 Lq=Lρ=1.5×0.6=0.9[人]
    4 W=L/λ=1.5×5=7.5[分]
    5 Wq=Wρ=7.5×0.6=4.5[分]
  2. 上記の客の到着が2倍の平均24人になった。到着してからサービスを受けて去るまでの平均時間を変えないためには,レジの平均サービス時間を何分にしなければならないか。
    客の到着が2倍になったのだから,窓口のサービスも2倍にすればよいと考えて,3/2秒とするのは誤りです。
     W=1/(μ-λ) ですから,客が増加したときの平均到着率をα,平均サービス率をβとすれば,
       1/(μ-λ) =1/(β-α)
       β=μ-λ+α
        =(1/3)-(1/5)+(24/60)=8/15
      ∴ 1/β=15/8≒1.9[分/人]