スタートページ> Web教材一覧> オペレーションズリサーチ> 待ち行列
待ち行列のうちで最も基本的なモデルであるM/M/1(厳密にはM/M/1(∞)といいます)。
このMはマルコフ過程(Markov Process)の意味で、「未来の挙動が現在の値だけで決定され、過去の挙動と無関係な確率過程」であるということです。
すなわち,客の到着間隔や窓口のサービス時間は、それまでの客の到着が増加傾向にあるとかレジ時間の長いことにクレームがあるので、次の顧客到着間隔は小さくなるとかサービス時間を短くしようなどの変化はないという仮定です。
M/M/1モデルとは、
客の到着および窓口のサービスの分布がランダム
窓口の個数が1個
客が到着したときに先客がいれば,自分の番になるまで待つ
の場合を検討します。
ここでの考え方は,他の場合での基本になるものですから,十分に理解することが必要です。
客が単位時間に到着する平均値(平均到着率)をλ(ラムダと読む)[人/時],1つの窓口が単位時間にサービスを完了する人数の平均値(平均サービス率)をμ(ミューと読む)[人/時]とします。
サービスを受けている人とサービスを待っている人の全体(これを「系の中」という)の人数が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 が成立します。
しかし,上の式は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=ρnP0
となります。
ところで, P0+P1+P2+・・・+Pn+・・・=1 ですから,
(1+ρ+ρ2+・・・+ρn+・・・)P0=1
となり,
系の中の人数が0人である確率 P0=1-ρ
系の中の人数がn人である確率 Pn=ρn(1-ρ)
が得られます。
(その証明)
A=1+ρ+ρ2+・・・+ρn
ρA= ρ+ρ2+・・・ +ρ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ρ=ρ2/(1-ρ)
となります。
到着してからサービスを受けるまでの平均待ち時間Wqは,待っている人数Lqにより生じたのですし,平均到着間隔は1/λですから,全体ではLq/λの時間がかかったことになります。すなわち,
Wq=Lq/λ
となります。
系の中にいる全時間Wは,待っている時間とサービス時間の合計なので,
W=Wq+1/μ=(L-λ/μ)/λ+1/μ
=L/λ
になります(L/μではないことに注意!)。
客の平均到着率: λ[人/時] ⇔ 平均到着間隔: 1/λ[時/人] 窓口の平均サービス率: μ[人/時] ⇔ 平均サービス時間:1/μ[時/人] ρ=λ/μ 窓口の稼働率,客が到着したとき待ちが生じる確率 系の中に人がいない確率: P0=1-ρ (待たないでよい確率) 系の中にn人がいる確率: Pn=ρnP0=ρn/(1-ρ) サービスを待っている人の平均人数:Lq=ρ2/(1-ρ) サービス中も含む系内の平均人数: L=Lq+λ/μ=ρ/(1-ρ) 到着してからサービスを受けるまでの平均待ち時間: Wq=Lq/λ=λ/μ(μ-λ) 到着してからサービスを受けて去るまでの平均時間: W=Wq+1/μ=1/(μ-λ) (上の赤い部分がリトルの公式です。) なお,上式を変形すると, L =ρ/(1-ρ) W =L/λ Lq=Lρ Wq=Wρ となります。LqやWqは,LρやWρに似ていますね!?
下図は,ρとL,Lqの関係をグラフにしたものです。
これから,LやLqはρが1に近づくにつれて急激に増大することがわかります。客の到着間隔が10分,サービス時間が9分であるとき,これらが一定であれば待ちは生じないのに,それらがランダムなために,サービスを待っている人数が8人,サービスを受けている人も入れると9人になるのです。このようなことは直感とかなり異なりますね。このようなことを計画時に知っていないと,実施時に大きなトラブルになります。
有名な例を紹介しましょう(大前義次,森村英典『待ち行列の理論と実際』日科技連,1962. p.46より)。第2次世界大戦中,アメリカからイギリスへの護送船団は,ニューヨーク港から80%,バルチモア港から20%から出港していた。米海軍は,それを不経済だと考え,すべてニューヨーク港から出港することにした。ところが,出港のための所要時間が従来の2倍になってしまった。米海軍は,敵国工作員によるサボタージュが行われたのではないかと調査をしたが,そのような事実はなく理由不明であり,ORグループに原因解明を依頼した。その結果は・・・
おわかりですね。ニューヨーク港での到着率の20%の増加が,Wを急激に増大させていたのです。
系中にn人がいる確率 p(n)は、前述のように、 p(0) =1-ρ p(n) =ρn(1-ρ) になります。 系中の人数がn人以下の確率P(≦n)は、次式で求められます、 P(≦n) = p(0) + p(1) + … + p(n) = (1-ρ) + ρ1(1-ρ) + ρ2(1-ρ) + … + ρn(1-ρ) = 1 - ρn+1 「確率Pで、系中の人数はn人以下である」を求めるには、 P(≦n) = 1 - ρn+1 を変形して、 n = log(1-P)/log(ρ) - 1 になります。 しかし、 P(=0) =1-ρ ですから、P≦1-ρ のときは、n=0になります。
系中の人数 nq と n=次の関係があります。 待ち行列の長さ nq は系中の人数 n からサービス中の人を除いた数になります。 待ち行列の長さが nq の確率 pq(nq) は、系中の人数 n の確率 p(n) を用いると pq(nq) = p(n-1) になります。 しかし、n=0, 1 のときは考慮する必要があります。 n nq pq(nq) 0 0 1 0 (1-ρ)+ρ(1-ρ) 2 1 ρ2(1-ρ) 3 2 ρ3(1-ρ) n nq-1 ρnq(1-ρ) n+1 nq ρnq+1(1-ρ) 待っている人の数(待ち行列長さ)が nq 人である確率 pq pq(0) = p(0)+p(1) = 1-ρ2 pq(nq) = ρnq+1(1-ρ) 待ち行列長さが nq 人以下である確率 pq pq(0) = pq(0) = 1-ρ2 pq(nq) = pq(0) + {pq(1) + pq(2) + … + pq(nq)} = 1-ρ2 + (1-ρ){ρ2 + … + ρnq+1} = 1-ρnq+2 「確率Pqで、待ち行列長さが n 人以下である」 Pq = 1-ρnq+2 から、n = log(1-Pq)/log(ρ) - 2 (Pq≦1-ρ なら n=0)
到着してからサービスを受けるまでの時間がt以上である確率 待ち行列の長さから計算することもできるでしょうが、次の式があります。 Pq(≧t) = ρe-(1-ρ)μt 上側確率 P での待ち時間 t を求めるには、上式から次式がえられます。 t = log(ρ/P)/(1-ρ)μ 到着してからサービスを受けるまでの時間がtである密度関数 Pq(≧t)は累積確率ですので、これを t で微分すれば密度関数になりますが 上側からの累積ですので t → t-dx での微分になり、符号を反転する必要があります。 p(t) = ρ/(1-ρ)μ * e-(1-ρ)μt 系中での全時間 待ち時間にサービス時間 1/μ を加えたものが全時間ですから、 P(≧t) = Pq(≧t) + 1/μ = ρe-(1-ρ)μt + 1/μ