queue.js は、単純な待ち行列モデルでよく用いられる処理を JavaScript の関数ライブラリにまとめたものです。本ページは、その利用解説書です。
queue.js は、 http://www.kogures.com/hitoshi/javascript/queue.js にあります。 また、後述の個別関数の説明の個所で該当関数のソースコードを表示できます。 これらの関数は独立しているので、単体で動きます。 これらのソースコードのご利用は自由ですが、私はこの分野の専門家ではありませんので、関数の信頼性の保証はできません。 誤りをご指摘・ご教示いただければ幸甚です(これが公開の目的!?)。 上記の queue.js のURLをご自身の HTML に script として組み込むのはお勧めできません。 勝手に改変したり、他の位置に移動する可能性があるからです。
すべての関数の戻り値は連想配列形式になっています。次のような記述で戻り値を受け取ります。 var rtn = mm1(λ,μ); var ρ = rtn["ρ"]; var P0 = rtn["P0"]; : 関数と戻り値の一覧を示します。 表中の〇は、戻り値が存在すること、Vは、その戻り値が通常のベクトル形式になっていることを示します。 ↓関数 戻り値→ ρ P0 Pq L Lq W Wq Pn Cn Pqn Cqn Np Nqp Pt Pqt Ptg Pqtg Tg Tqg M/M/1(∞) mm1(λ,μ) 〇 〇 〇 〇 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ mm1n(λ,μ,n) 〇 〇 〇 ・ ・ ・ ・ 〇 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ mm1nv(λ,μ) 〇 〇 〇 ・ ・ ・ ・ V V V V ・ ・ ・ ・ ・ ・ ・ ・ mm1p(λ,μ,p) 〇 〇 〇 〇 〇 ・ ・ 〇 〇 ・ ・ 〇 〇 ・ ・ ・ ・ ・ ・ mm1pv(λ,μ) 〇 〇 〇 〇 〇 ・ ・ V V ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ mm1t(λ,μ,t) 〇 〇 〇 ・ ・ 〇 〇 ・ ・ ・ ・ ・ ・ 〇 〇 〇 〇 ・ ・ mm1tv(λ,μ) 〇 〇 〇 ・ ・ 〇 〇 ・ ・ ・ ・ ・ ・ V V V V ・ ・ mm1pt(λ,μ,p) 〇 〇 〇 ・ ・ 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ 〇 〇 mm1ptv(λ,μ) 〇 〇 〇 ・ ・ 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ V V M/M/1(1) mm11(λ,μ) 〇 〇 〇 〇 ・ 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ M/M/1(S) mm1s(λ,μ,s) 〇 〇 〇 〇 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ mm1sn(λ,μ,s,n) 〇 〇 〇 〇 〇 〇 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ mm1snv(λ,μ,s) 〇 〇 〇 〇 〇 〇 〇 V V ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ M/G/1(∞) md1(λ,μ) 〇 〇 〇 〇 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ me1(λ,μ,k) 〇 〇 〇 〇 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ me1kv(λ,μ) 〇 〇 〇 〇 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ M/M/S(∞) mms(λ,μ,s) 〇 〇 〇 〇 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ mmsn(λ,μ,s,n) 〇 〇 〇 ・ ・ ・ ・ 〇 ・ 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ mmsnv(λ,μ,s) 〇 〇 〇 ・ ・ ・ ・ V V V V ・ ・ ・ ・ ・ ・ ・ ・ mmst(λ,μ,s,t) 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ 〇 〇 ・ ・ mmstv(λ,μ,s) 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ V V ・ ・ mmsp(λ,μ,s,p) 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ 〇 〇 mmspv(λ,μ,s) 〇 〇 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ V V M/M/S(S) mmss(λ,μ,s) 〇 〇 〇 〇 ・ 〇 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ mmssn(λ,μ,s,n) 〇 〇 〇 ・ ・ ・ ・ V V ・ ・ ・ ・ ・ ・ ・ ・ ・ ・
P :密度確率、C :累積確率、L :平均人数、W :平均時間、T :個別時間 q :待ち行列(サービスを受けるまで)。これがないときは系内(サービス中を含む) g :~以上 平均諸元 ρ: 稼働率 = λ/μ(窓口1のとき)、 λ/sμ(窓口sのとき) P0: 系内人数が0人。窓口1のときは、窓口の空き確率=待たずにサーブが受けられる確率 Pq: 待ちが生じる確率。系内に窓口数以上の人がいる確率 L: 平均系内人数 Lq: 平均待ち行列の長さ W: 平均系内滞留時間 Wq: 平均待ち時間(サービスを受けるまでの時間) 人数と確率 Pn: 系内人数がn人の確率 Cn: 系内人数がn人以下の確率 Pqn: 待ち行列人数がn人の確率 Cqn: 待ち行列人数がn人以下の確率 Np: 確率 p で系内に Np 以下の人がいる。 Nqp: 確率 p で待ち行列に Nqp 以下の人がいる。 時間と確率 Pt: 系内滞留時間が t 時間になる確率 Pqt: サービスを受けるまでに t 時間待たされる確率 Ptg: 系内滞留時間が t 時間以上になる確率 Pqtg:サービスを受けるまでに t 時間以上待たされる確率 Tg: 割合 p の人の系内滞留時間が Tg 以上になる Tqg: 割合 p の人のサービス待ち時間が Tqg 以上になる その他(上表には掲載していない) C: M/G/1 = 標準偏差/平均 サービス分布でのポラチェック・ヒンチンのC A: M/G/1 = (1+C*C)/2 それによる補正係数 An: M/M/S = (sρ)^n / n! Pn = As*P0 系内人数n(≦s)の係数 As: M/M/S = (sρ)^s / s! Pq = An*P0 窓口が塞がっている B: M/M/S = A0 + A1 + … + As
上の表で関数名をクリックすると、該当関数の個所に移動します。大体、次のような構成になっています。 ・[コード表示]をクリックすると該当関数のコードが別ウインドウにポップアップします。 ・主要な戻り値の意味と簡単な算出根拠を掲げています。 ・FORM でデータ入力して、結果を表示するようになっています。 入力データの妥当性チェックはしていません。
説明(Webテキスト):「待ち行列の基本形(M/M/1)」
λ:平均到着率(単位時間に来る平均客数) [人/時] 1/λ:客の平均到着間隔 [時/人] μ:平均サービス率(単位時間に終了するサービス数) 1/μ:平均サービス時間[時/人] ρ(稼働率)=λ/μ は0<ρ<1 ∴ λ<μ でなければなりません。 このチェックはしていないので、入力指定で注意してください。 窓口は1つ。 「系内」とは、到着してから去るまで、「待ち行列」とはサービスを受けるまでのことです。 到着した客はサービスを受けるまで、去ることなく、行列の最後に並びます。 M/M/1(∞) は、単にM/M/1といいます。最も基本的なモデルなので、多様な関数を作成しました。
λ,μを与えて、諸元を求めます。戻り値は連想配列になります。 rtn = mm1(λ,μ) rtn["ρ"] = λ/μ (<1)稼働率 rtn["P0"] = 1 - ρ 系内人数が0、待たないでサービスが受けられる確率 rtn["Pq"] = ρ 到着したとき待たされる確率 rtn["L"] = ρ/(1-ρ) 平均系内人数(サービス中を含む) rtn["Lq"] = L*ρ 平均待ち行列人数 rtn["W"] = L/λ 平均系内時間(到着してから去るまでの全時間) rtn["Wq"] = W*ρ 平均待ち時間(サービスを受けるまでの時間)
Pn: 系内人数がn人の確率 Pn = (1-ρ) * ρn Cn: 系内人数がn人以下の確率 Cn = P0 + P1 + … + Pn = 1 - ρn+1 Pqn: 待ち行列人数がn人の確率 mm1nv() の説明参照 Cqn: 待ち行列人数がn人以下の確率
以下の戻り値はベクトルになります。 Pn[n]: 系内人数がn人の確率 Pn = (1-ρ) * ρn Cn[n]: 系内人数がn人以下の確率 Cn = P0 + P1 + … + Pn = 1 - ρn+1 Pqn[n]: 待ち行列人数がn人の確率 Cqn[n]: 待ち行列人数がn人以下の確率 待ち人数がn人とは、系内の人n+1人いるということです。 Pqn[0] = Pn[0] + Pn[1] 誰もいない+1人がサービス中 Pqn[1] = Pn[2] 1人がサービス中で1人が待っている : Pqn[n] = Pn[n+1] 1人がサービス中でn人が待っている 実行結果を見ると、n=0 以外では、Pqn, Cqn は Pn, Cn と1行ずれていることがわかります。
戻り値 Np: 確率 p で系内に Np 以下の人がいる。 Nqp: 確率 p で待ち行列に Nqp 以下の人がいる。 mm1n() の逆計算です。実行結果は 「p=90%の確率で、系内人数は Np = 7人以下、待っている人は Nqp = 6人以下である」 ことを示しています。 Np の計算 mm1n() での Pn = (1-ρ) * ρn を変形すると n = log(1-Pn)/log(ρ) - 1 になります。 ここでは、p = Pn、Np = n としているので、Np = log(1-p)/log(ρ) - 1 となります。 ただし、p は待つ確率 Pq より小のときは、系内の人数は0なので Np = 0 となります。 Nqp の計算 mm1n() で示したように、待っている人数は系内人数からサービスを受けている人を引けばよいので、 Nqp = Nq - 1 になりますが、これも系内人数が2以上であることが前提になります。 P0 + P1 = (1-ρ) + ρ(1-ρ) = 1-ρ2 より p が小なら、Nqp = 0 になります。
実行例を見ると、mm1p() の説明の通り、Tqp[i] = Tp[i] -1 になっています。 p = 90% では 系内人数は Np = 7人以下、待っている人は Nqp = 6人以下なのは mm1p() と同じです。 p が小さくなるとは、対象となる人が小さくなるのは当然です。 pの値は不等間隔になっています。それで P[i], Tp[i], Tqp[i] のようにベクトルになります。
Pt: 系内滞留時間が t 時間になる確率 Pqt: サービスを受けるまでに t 時間待たされる確率 Ptg: 系内滞留時間が t 時間以上になる確率 Pqtg:サービスを受けるまでに t 時間以上待たされる確率 Pqtg については、有名な公式があります。 Pqtg = ρe-(1-ρ)μt Pqt は、Pqtg を t で微分して求められます(Pqtg が右下がりなので符号を反転) Pqt = ρ/μ(1-ρ) * ρe-(1-ρ)μt = ρ/μ(1-ρ) * Pqtg 系内滞留時間は、サービス時間 = 1/μ だけ余計に時間がかかるのですから、 Pqtg での t と Ptg が t-1/μ のときが同じになるので、上式で t-1/μ とすればよいのです。 t がサービス時間より小なことは起こりえないので0になります。 実行例 待ち時間が 2 である確率が 0.5 % 待ち時間が 2 以上である確率が 1.11 % 系内時間が 2 である確率が 0.8% 系内時間が 2 以上である確率が 1.16 % 系内時間の確率のほうが大きいのは、直感的にも理解できましょう。
t[i]: 時間 Pt[i]: 系内滞留時間が t 時間になる確率 Pqt[i]: サービスを受けるまでに t 時間待たされる確率 Ptg[i]: 系内滞留時間が t 時間以上になる確率 Pqtg[i]:サービスを受けるまでに t 時間以上待たされる確率
Tg: 割合 p の人の系内滞留時間が Tg 以上になる Tqg: 割合 p の人のサービス待ち時間が Tqg 以上になる mm1t() での公式 Pqtg = ρe-(1-ρ)μt を変形して、t = log(ρ/Pqtg) /μ(1-ρ) t を Tqg、Pqtg を p として、Tqg = log(ρ/p) /μ(1-ρ) となります。 Tg = Tqg + 1/μ になります。 ただし p > ρ の場合は 確率>稼働率 なので、系内に誰もいなくても成立するので、Tg, Tqg = 0 になります、
説明(Webテキスト):「行列に制限がある場合の待ち行列(M/M/1(N))」
窓口が塞がっていたら、待たずに去ります。 電話をかけたらお話中あるいは輻輳している状況です。 待ち行列が生じないので、次の諸元しかありません。 サービスが受けられる確率 P0 = 1/(1+ρ) (MM1のP0と同じ) 窓口が塞がっている確率 P1 = 1 - P0 サービスを受けている時間 W = 1/μ
説明(Webテキスト):「行列に制限がある場合の待ち行列(M/M/1(s))」
系内の人数がs人に制限される状態です。 待合室にs-1人しか入れず、満員なら去るモデルです。
ρ = λ/μ 稼働率 到着したとき待たされる確率 P0 = (1-ρ)/(1-ρs+1) 系内人数が0、待たないでサービスが受けられる確率 Pq = P0*ρs 棄却率。系内人数がs人である確率。客はそのまま去る L = 0P0 + 1P1 + 2P2 + … + sPs} 平均系内人数 = {(1-(s+1)ρs+sρs+1)/(1-ρs+1)}*{ρ/(1-ρ) Lq = 1P2 +2P3 + … + sPs} 平均待ち行列人数 = {(1-sρs-1+(s-1)ρs)/(1-ρs+1)}*{ρ2/(1-ρ) W = L/λ(1-Pq) 平均系内時間(到着してから去るまでの全時間) Wq = Lq/λ(1-Pq) 平均待ち時間(サービスを受けるまでの時間)
P0 = (1-ρ)/(1-ρs+1) 系内人数が0、待たないでサービスが受けられる確率 Pn = P0 * ρn 系内に n 人いる確率 Cn = P0 * (1-ρn+1)/(1-ρ) 系内の人数が n 以下の確率
P0 = (1-ρ)/(1-ρs+1) 系内人数が0、待たないでサービスが受けられる確率 Pn = P0 * ρn 系内に n 人いる確率 Cn = P0 * (1-ρn+1)/(1-ρ) 系内の人数が n 以下の確率
参照(Webテキスト):一般分布での待ち行列(G/G/1型)
M/M/1(∞) の拡張として、サービス時間が指数分布以外の場合を取り扱います。 M/D/1 サービス時間が一定 平均は 1/μ,標準偏差は 0 M/Ek/1 サービス時間が位相kのアーラン分布 アーラン分布は、位相k=1なら指数分布、K=∞なら一様分布になる分布です。 平均は 1/μ,標準偏差は 1/μ√k 平均待ち時間 M/M/1(∞) の平均待ち時間は Wq = ρ2/λ(1-ρ) でしたが、 ポラチェック・ヒンチンの公式により C = 標準偏差/平均 とすれば A = (1+C2)/2 として、 Wq = ρ2/λ(1-ρ) * A で求められます。 平均 標準偏差 C A = (1+C2)/2 M/M/1 1/μ 1/μ 1 1 M/D/1 1/μ 0 0 1/2 M/k/1 1/μ 1/μ√k 1/√k (1+k)/2k 他の平均諸元、 Wq がわかれば,リトルの公式により,W,Lq,Lを求めることができます。 W=Wq + 1/μ, Lq=λWq, L=λW
k = 1, 2, 3, 4, 5, 10, 100 で計算します。 k=1 のときは指数分布 mm1() k→大のときは一様分布 md1() と一致します。
参照(Webテキスト):複数窓口での待ち行列(M/M/s)
銀行のATMのように、多数の窓口があり、客は全体に1列に並び、どこかの窓口が開くと、そこでサービスを受けて系内から去るというモデルです。ここでは、どの窓口も同じサービス率だとします。
ここで、窓口数をsとし、稼働率ρは ρ=λ/sμ と定義します。
M/M/s(∞) では、かなり複雑な式になります。 ρ=ρ=λ/sμ An=(sρ)n/n! B=A0 + A1 + … + As とすると, P0 = 1/{B+Asρ/(1-ρ)} 系内人数0の確率 Pn = An * P0 (0≦n<s) 系内人数nの確率 = As * ρn-s * P0 (s<n) Ps = As * P0 系内人数s Pq = Ps + Ps+1 + Ps+2 + … n >= s の確率 待つ確率 = 1/(1-ρ) * As * P0 = Ps/(1-ρ) Lq = 1Ps+1 + 2qPs+2 + 3Ps+3 + … 平均待ち行列の長さ = ρ/(1-ρ)2 * As * P0 Pqtg = Pq * e-(1-ρ)sμt 待ち時間がt以上になる確率 Ptg = Pq * e-(1-ρ)sμ(t-1/μ) 系内滞留時間がt以上になる確率 となり、Lq がわかれば L = Lq + sρ、Wq = Lq/λ、 W = Wq + 1/μ でこれらの値も計算できます。
rtn = mms(λ,μ, s) rtn["ρ"] 全体の稼働率 =λ/sμ rtn["P0"] 系内人数が0 rtn["Ps"] 系内人数がs rtn["Pq"] n > s の確率 待つ確率 rtn["L"] 平均系内人数(サービスを含む) rtn["Lq"] 平均待ち行列長さ rtn["W"] 平均系内時間 rtn["Wq"] 平均待ち時間 補助変数 rtn["As"] = (sρ)s / s! Pq = As * P0 rtn["B"] = A0 + A1 + … + As P0 = 1/{B+Asρ/(1-ρ)}
P0 = 1/{B+Asρ/(1-ρ)} 系内人数0の確率 Pn = An * P0 (0≦n<s) 系内人数nの確率 = As * ρn-s * P0 Pqn = Pn(n+1) = ρ*Pn (s<n) = 0 (0≦n<s) 待ち行列人数nの確率 Ps = As * P0 系内人数s Pq = 1/(1-ρ) * As * P0 = Ps/(1-ρ) n >= s の確率 待つ確率 補助変数 As = s! Pq = As * P0 B = A0 + A1 + … + As P0 = 1/{B+Asρ/(1-ρ)} Pqn と Pn の関係 Pqn[n] - Pn[n+1] = As * ρn-s+1 * P0 = ρ*Pn ここでは、処理効率の理由により Pn の累積 Cn は計算していません。 次の mmsnv() で Cn[n] として計算されます。
Pn[n] 系内人数がn人の確率 n=1/ρ 付近で最大になります Cn[n] 系内人数がn人以下の確率 Pqn[n] 待ち人数がn人の確率 n≦s では0 Cqn[n] 待ち人数がn人以下の確率 補助変数 An = (sρ)n / s! Pq = As * P0 As = (sρ)s/ s! Pq = As * P0 B = A0 + A1 + … + As P0 = 1/{B+Asρ/(1-ρ)}
Pqtg 待ち時間が t 時間以上の確率(公式 Pqtg = Ps * Math.exp(-(1-ρ)*s*μ*t) ) Ptg 系内時間が t 時間以上の確率(上式で t を t-1/μ にする。t≦1/μ なら Ptg=1)
t[i] 時間 Pqtg[i] 待ち時間が t[i] 時間以上の確率(公式 Pqtg = Ps * e-(1-ρ)sμt ) Ptg[i] 系内時間が t[i] 時間以上の確率(上式で t を t-1/μ にする。t≦1/μ なら Ptg=1)
Tg: 割合 p の人の系内滞留時間が Tg 以上になる Tqg: 割合 p の人のサービス待ち時間が Tqg 以上になる mmst() の逆関数 Pq:待つ確率 Pqtg = Ps * e-(1-ρ)sμt → t = log(Pq/Pqtg) /(1-ρ)sμ Ptg = Ps * e-(1-ρ)sμ(t-1/μ) → t = log(Pq/Ps) /(1-ρ)sμ + 1/μ ここでの記号に書換え Tqg = log(Pq/p) /(1-ρ)sμ Tg = log(Pq/p) /(1-ρ)sμ + 1/μ = Tqg + 1/μ p ≧ Ps のときは常に成立するので人数は0になる 実例で、p=0.1 のとき Tg = 0.797, Tqg=0.287 とは 確率10%で系内人数は0.797人以下、待ち人数は0.287人以下 逆にいえば、 90%の確率で、系内人数は0.797人以上、待ち人数は0.287人以上 になります。
参照(Webテキスト):複数窓口での待ち行列(M/M/s)
s個の窓口がすべて塞がっていれば、待たないで去る場合です。場外では待てない駐車場で、満車ならば他の駐車場を探すなどで去るようなケースです。このときは、サービス時間は駐車時間です。
M/M/s(s) では、待ち行列が生じないので、簡単になります。 ρ=ρ=λ/sμ、 An=(sρ)n/n!、 B=A0 + A1 + … + As とすると, P0 = 1/B 系内人数(サービス中の窓口数)が0人の確率 Pn = An * P0 系内人数がn人(n≦s)の確率 Pq = As * P0 n=sでの確率 すべての窓口が塞がっておりサービスが受けられない棄損率 L = B * P0 平均系内人数 W = 1/μ 平均系内時間 補助変数 As = (sρ)^n / n! Pq = As * P0 B = A0 + A1 + … + As P0 = 1/B
rtn = mmss(λ,μ, s) rtn["ρ"] 全体の稼働率 =λ/sμ rtn["P0"] 系内人数が0 rtn["Pq"] 系内人数がs サービスが受けられない確率 rtn["L"] 平均系内人数(サービスしている窓口) rtn["W"] 平均系内時間 =1/μ 補助変数 rtn["As"] rtn["B"]
Pn 系列人数がn人である確率
Pn 系列人数がn人である確率 Cn 系列人数がn人以下である確率