Kingmanの近似式とその拡張

Factory Physics

  • よく待ち行列の本を見るとＭ／Ｍ／１の待ち行列やＭ／Ｄ／１の待ち行列の場合の待ち時間を算出する式は出ているのですが、私たちがファブ内の物流モデルを作りたい場合は、指数分布（Ｍ）ではなく一般（ＧＩ）のジョブ（＝ロット）到着間隔分布、指数分布（Ｍ）ではなく一般（Ｇ）の処理時間で、ステーションが複数（ｍ台）の装置から成る待ち行列、すなわちＧＩ／Ｇ／ｍでの待ち時間を知りたいです。これに答えてくれる本を私は長い間、見つけることが出来ませんでした。それは単に私の探し方が悪かっただけかもしれませんが。
  • ところがFactory Physicsでは、このＧＩ／Ｇ／ｍの待ち行列の待ち時間を算出する近似式としてKingmanの式というものと、その拡張を載せています。Kingmanの式とはＧＩ／Ｇ／１の場合のための近似式で、以下のものです。

さらにそれをｍ台装置がある場合に拡張した式として（すなわちＧＩ／Ｇ／ｍの場合の近似式として）Factory Physicsでは

    • CT_q=\left(\frac{c_a^2+c_e^2}{2}\right)\frac{u^{sqrt{2(m+1)}-1}}{m(1-u)}t_e・・・・（２）
  • という式を紹介しています。これら２つの式における各変数の意味は以下の通りです。
  • これは便利な式でして、シミュレーションをしなくてもある程度の結果を導き出すことが出来ます。さらに「故障と段取りの考慮」に示しましたように、装置故障や段取り替えの影響をこの式に反映させることも出来ます。Factory Physicsでは、この式を法則（変動）、（変動の緩衝）、（利用率）、（キャパシティ）、（処理バッチの構成）、（搬送バッチの構成）、（リワーク）を導くのに用いています。
    • Kingmanの近似式とは（１）のことを指しますが、（２）については名前がついているのかどうか私は知りません。この式についてはWhittという人がその論文（Whitt 1983 The Queueing Network Analyzer. Bell System Technology Journal 62(9): 2779 2815 ）で論じているそうなので、このブログでは仮に「Whittの近似式」と呼ぶことにします。
  • しかし、私にはこれが近似式であることが気になります。つまりこの式を使って値を出した場合どの程度その値が信頼できるのか、というのが私には疑問です。それについて私はまだ答えを持っていません。今のところ私に分かっていることを以下に示します。あまり整理は出来ていませんが・・・・

いろいろな待ち行列におけるCT_q

  • Ｍ／Ｍ／１では
    • CT_q=\frac{u}{1-u}t_e・・・・（３）
  • Ｍ／Ｍ／ｍでは
    • CT_q=\frac{m^{m-1}u^m}{m!(1-u)^2}{p_0}{t_e}・・・・（４）
      • ここにp_0はｍ台の装置が全て空いている確率を表し、
        • p_0=\frac{1}{\Bigsum_{i=\0}^{m-\1}\left{\frac{(mu)^i}{i!}\right}+\frac{(mu)^m}{m!(1-u)}}・・・・（５）
      • であることが分かっています。Ｍ／Ｍ／１がＭ／Ｍ／ｍになっただけでものすごく複雑な式になりました。かつて私はこの式を見て、「ああ、待ち行列理論は役に立たない」と思って、その応用をあきらめてしまいました。
    • ところが、世の中には逆瀬川氏（早稲田大学教授http://www.sakasega.mgmt.waseda.ac.jp/）の提案になる近似式というものがあるということをFactory Physicsは紹介していました。それが
      • CT_q=\frac{u^{sqrt{2(m+1)}-1}}{m(1-u)}t_e・・・・（６）
    • です。（この式に「逆瀬川の近似式」という呼び方があるのかどうか分かりませんが、このブログでは「逆瀬川の近似式」と呼ぶことにします。）　なお逆瀬川の近似式の精度ではこの近似式がどの程度正確か調べてみました。
  • Ｍ／Ｇ／１では
    • CT_q=\left(\frac{1+c_e^2}{2}\right)\frac{u}{1-u}t_e・・・・（７）
      • これはポラツェック＝ヒンチンの公式の変形として導かれます。これは近似式ではありません。正確な式です。
  • どうも、正確にCT_qを算出できるのは上記の場合のみのようです。これより一般的な待ち行列については、上記（１）（Kingmanの近似式）、（２）（Whittの近似式）でがまんするしかなさそうです。
    • （２）は式（１）（Kingmanの近似式）とＭ／Ｍ／１の時の式（３）を見比べて、さらに（３）と逆瀬川の近似式（６）とを見比べて類推したものです。Factory Physicsはその類推を正当化する記述をしていません。

待ち時間の式同士の関係

  • 今まで登場したCT_qを求める式同士の関係を下の図にまとめてみました。

  • 図でみず色で示した四角は厳密な式を表し、ベージュで示した四角は近似式を表しています。これをみますとKingmanの近似式はＧＩがＭの時には正確になり、Whittの近似式はＧＩとＧの両方がＭの時、逆瀬川の近似式に一致してほぼ正確になることが分かりますが、一般のＧＩ／Ｇ／１あるいはＧＩ／Ｇ／ｍの時にどの程度の精度でCT_qを近似するのかはよく分かりません。