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

行列に制限がある場合の待ち行列(M/M/1(N))

学習のポイント

ここでは,行列に制限がある場合の待ち行列を考えます。電話をかけたときにお話中である確率(呼損率)や,待合室の座席数などがテーマになります。さらに窓口が複数のときの呼損率を取扱うアーランB式についても考えます。


M/M/1(1)

窓口が1つで,系の中にいる人数が1以下というのですから,現在サービスを受けている人以外はいないということで,客が到着したときに窓口が塞がっていたら,待たないで去るケースです。電話をかけたときお話中だったら切る場合などがこれに相当します。

公式を求める

 系の中に誰もいない確率をP0,1人いる確率をP1とします。
 P0とP1以外はないのですから,
   P0+P1=1     ・・・A
 現在,系の中にいる人数が0人であり,微小時間⊿t後に1人になるのはλP0⊿tで,現在が1人なのが⊿t後に0人になるのはμP1⊿tです。安定している状態では,
   λ⊿tP0=μ⊿tP1
ですから,ρ=λ/μとすると
   P1=ρP0      ・・・B
が成立します。AとBから,
   P0=1/(1+ρ)
となります。

すなわち,電話をしたときに
   電話が通じる確率:P0=1/(1+ρ)
   お話中である確率:P1=ρ/(1+ρ)
となります。なお,このP1呼損率といいます。
 また,当然ながらLqやWqは存在せず,L=P1=ρ/(1+ρ)となります。W=1/μであることは明らかですが,これはW=L/λとは一致しません。

M/M/1(∞)とM/M/1(1)との比較

両者の比較をすると,次のような違いがあります。
       M/M/1(∞)   M/M/1(1)
   P0    1-ρ       1/(1+ρ)
   L    ρ/(1-ρ)     ρ/(1+ρ)
   W    ρ/(1-ρ)λ    1/μ=ρ/λ
 グラフにすると,次のようになります。

P0とLのグラフ

上図でのP0のM/M/1(1)のグラフを見てください。ρ=1の確率は0.5になっています。ρ=1とは,客の到着間隔と窓口のサービス時間が等しいときですから,窓口は常にふさがっているのではないでしょうか? M/M/1(∞)では0になっています。なぜ,N=1のときは0にならないのでしょうか?

ある客が到着したときを考えてみましょう。このとき窓口が空いていれば窓口を1/μの時間だけ占有します。次の客が来るのは1/λ後ですが,1/λ<1/μのときに来たときには待たないで帰ってしまいます。1/λ>1/μのときは前の客のサービスが終わっているのでサービスを受けることになります。
 ρ=1のときは1/λ=1/μではありますが,これらは統計的な値ですから,あるときは1/λ<1/μになるし,あるときは1/λ>1/μになります。その比率は等しいのですから,1/λ>1/μである確率,すなわち到着したときに窓口が空いている確率は0.5になるのです。

行列に制限があるときは,ρ<1でなければ待ち行列の意味がないのですが,行列に制限があると,ρ≧1でも,すなわち到着がサービスよりも大きくても意味があるのです。


M/M/1(N)

これは,窓口が1つで系の中にいる人数がN人以下に制限されている場合です。到着したときに,サービスを受けている人も含めてN人より少なければ並んで待つが,N人いたときには帰ってしまうという場合や,待合室の収容人数がN-1人である場合などに相当します。

公式を求める

 状態方程式は,M/M/1に次の最後の式が加わります。
    μP1=λP0
    μPn+1+λPn-1=(λ+μ)Pn   (0<n<N)
    μPN=λPN-1
これを解くと,
  系の中にn人いる確率: Pn=ρn0
  窓口が空いている確率: P0=(1-ρ)/(1-ρN+1)
  系の中にN人いる確率: PN=ρN0=ρN(1-ρ)/(1-ρN+1)
が得られます。なお,このPNは,到着しても行列に並ぶことができす,帰ってしまう確率であり,呼損率あるいは棄却率といいます。
 これから,人数に関しては
  系の中にいる平均人数: L=1P1+2P2+3P3+・・・+N・PN
               ={(1-(N+1)ρN+NρN+1)/(1-ρN+1)}×{ρ/(1-ρ)}
  サービスを受けるまでの平均待ち時間: Lq=1P2+2P3+・・・+(N-1)PN
               ={(1-NρN-1+(N-1)ρN)/(1-ρN+1)}×{ρ2/(1-ρ)}
が得られます。どちらも,第2項はM/M/1のときのLやLqですから,第1項が行列制限による補正だと解釈できます。また,このときも,L=Lq+ρが成立します。

それに対して,待ち時間でのW=L/λは成立しません。PNの割合で行列に並ばないで帰ってしまいますので,λではなく,λ(1-PN)で割ることになります。
  到着してからサービスを受けて去るまでの平均時間: W=L/{λ(1-PN)}
  到着してからサービスを受けるまでの平均待ち時間: Wq=Lq/{λ(1-PN)}

公式の確認

かなり複雑な式になりましたので,M/M/1(1)やM/M/1とのチェックをしておきましょう。

 M/M/1(N)の公式で,N=1とすれば,M/M/1(1)の式になるはずです。
   P0=(1-ρ)/(1-ρ)=1/(1+ρ)
   P1=ρ(1-ρ)/(1-ρ)=ρ/(1+ρ)
   L={(1-(N+1)ρN+NρN+1)/(1-ρN+1)}×{ρ/(1-ρ)}=ρ/(1+ρ)=P1
   W=L/(λ(1-P1)}={ρ/(1+ρ)}/{μρ(1-ρ/(1+ρ))}=1/μ
     (λ=μρの関係があるので)
となり,前述に示した公式と一致します。

また,M/M/1(N)の公式で,N→∞とすれば,M/M/1型になるはずです。
 N→∞のときは,ρ→0,Nρ→0になります。
   P0=(1-ρ)/(1-ρN+1)=(1-ρ)/(1-0)=1-ρ
   L={(1-(N+1)ρN+NρN+1)/(1-ρN+1)}×{ρ/(1-ρ)}=ρ/(1-ρ)
   Lq={(1-(N+1)ρN+NρN+1)/(1-ρN+1)}×{ρ/(1-ρ)}=ρ/(1-ρ)
 また,PN=ρN(1-ρ)/(1-ρN+1)→0ですから,
   W=L/{λ(1-PN)}=L/λ
   Wq=Lq/{λ(1-PN)}=Lq/λ
となり,おなじみの式になります。

グラフによる吟味

数式の羅列でウンザリしましたね。ムードを変えましょう。

Nを変化させたとき

ρ=0.6として,Nを変化させたときのグラフを示します。点線はN=∞のときに収斂する値です。P0とPNはNが5以上,LとLqはNが10以上のときは,N=∞のときとあまり変らないとして取扱えると考えてよいでしょう。
 それは,M/M/1(∞)のとき,ρ=0.6のときにLやLqが10以上になる確率がかなり少ないことと一致します。すなわち,Nがある程度大きく,あるいはρが小さくて,客が行列に並ばず帰ってしまうことが少ない場合には,M/M/1(N)はM/M/1(∞)で近似できるのです。

ρ=0.6のときのグラフ

0とPNのグラフ

行列の制限Nをいろいろ変えたときの,窓口が空いている確率P0と呼損率(棄却率)PNのグラフは下図のようになります。

P0とPNのグラフ

M/M/1(1)でも指摘しましたが,行列に制限があるときは,ρが1以上になっても意味があるのです。
 上右図N=1(黒実線)のときは,ρが4(すなわち,窓口の処理能力の5倍の客が殺到しても,5回に1回(0.2)はサービスを受けることができるのです。このように,タイミングにより運がよいことが発生するのです。
 それに対して,Nが2以上のときは,サービスを待っている人がおり,前の人へのサービスが終わるとすぐに窓口を占有してしまいます。待っている人はNが大きくなるほど多いのですから,窓口が空いている確率は小さくなります。

点線のPNは,到着したときに系の中にN人いたら,行列に並ばないで帰ってしまう確率です。Nを待合室や駐車場のスペースだとすれば,Nが小さいほど入れない確率は高くなります。あるいは,気の短い人は行列に並ぶ確率は小さいともいえましょう。

qとLのグラフ

下のグラフは,LqとLを示したものです。L=Lq+ρですから,点線は実線より高くなるのは当然です。また,Nが小さいときは,行列の上限が抑えられているので,LqやLが小さくなるのも当然です。

LqとLのグラフ

N=1のときは,客が到着したとき窓口が塞がっていたときには帰ってしまうのですから,Lqは存在しません。L(黒い実線)は,サービスを受けている客の平均人数ですから,L=1[人]×Pになり,呼損率の曲線と一致します。
 N=∞のときは,ρが大きくなるにつれて,LqもLも急激に増大します。これがポアソン到着・指数サービス型の待ち行列の特徴でした。ところが,行列の長さがNに制限されていますので,ρがいかに大きくなってもL<Nになるのは当然です。


M/M/s(s)

複数窓口(s個)で行列に制限がある(N人)とき,すなわちM/M/s(N)のときを考えます。次のようにかなり複雑なものになりますが,N=sのときは比較的簡単になります。
アーランB式の定式化
 N=sの場合は,代表電話番号で受ける電話が数台あるようなとき,あるいは電話局での回線の容量を考える場合など,通信では重要なケースであり,上のPアーランB式と呼ばれでいます。
 アーランB式のグラフは下のようになります。同じρであっても,窓口数sが増加するにつれて,窓口がふさがっている確率は小さくなり,サービスを受けられる確率が増大することがわかります。

アーランB式のグラフ

たとえば,1回の電話では平均3分話をする(μ=1/3)として,平均1分おきにかかってくる(λ=1/2)ならば,λ/μ=3になります。もし受信用の電話が2台ある(s=2)ならば,ρ=3/2=1.5になり,上右図のs=2のグラフ(青線)から,お話中である確率は0.53であることがわかります。

逆に,λ/μ=3のときに,0.9の確率でサービスが受けられるようにする(P=0.1)には,電話が何台必要かを考えましょう。
 上左図からs=2ではρ=0.3になりますが,s=(λ/μ)/ρですからs=3/0.3=10となり,不足してしまいます。これを多様なsについて計算すると,
        グラフからのρ (λ/μ)/ρからのs
   s=3    0.42      7.1      不足
   s=5    0.58      5.1      ほぼ一致
   s=10   0.75      4.0      過剰

となるので,5台が答となります。