工場統計力学（建設中！）

ダイナミック・ジョブ・ショップ（４）

待ち行列ネットワークへの助走

http://www.public.iastate.edu/~smryan/ie613/Chapter7pt1.pptの続きと思われるhttp://www.public.iastate.edu/~smryan/ie613/Chapter7pt2.pptを訳していきます。
ブログ上では「ダイナミック・ジョブ・ショップ（３）」の続きになります。

一般ジャクソン・ネットワーク（近似分解法）

到着過程と出発過程は再生過程によって近似され、ステーションはそれぞれG1/G/m待ち行列として解析される。
パフォーマンス尺度
- $E[N],E[W]$
は４つのパラメータ
- $\{C_{a_{0j}}^2,C_{S_j}^2,\lambda_{0j},\mu_j\}$
によって近似される。（正確な分布を必要としない）
参考文献
- Whitt, W. (1983a), "The Queuing Network Analyzer," Bell System Technical Journal, 62, 2779-2815
- Whitt, W. (1983b), "Performance of Queuing Network Analyzer," Bell System Technical Journal, 62, 2817-2843.
- Bitran, G. and R. Morabito (1996), "Open queuing networks: optimization and performance evaluation model for discrete manufacturing systems," Production and Operations Management, 5,2, 163-193.

１クラスＧＩ／Ｇ／１開放型ネットワーク・システム

記法

$n$ ＝ネットワーク内の内部ステーションの数
とする。全てのについて
- - ステーション $j$ での外部からの到着のレートの期待値。
  - $\lambda_{0j}=1/E[(A_{oj})]$
- - ステーション $j$ での外部からの到着間隔の変動係数の２乗（ｓｃｖ）
  - $C_{a_{0j}}^2=[Var(A_{0j})]/[E(A_{0j})^2]$
- - ステーション $j$ でのサービス・レートの期待値
  - $\mu_j=1/E(S_j)$
- - ステーション $j$ でのサービス時間のｓｃｖ
  - $C_{S_{0j}}^2=[Var(S_j)]/[E(S_j)^2]$
の全ての組について
- ＝ステーションでのサービスの完了後、ステーションにジョブが向かう確率。
  - 即座戻りがないと仮定する。 $p_{ii}=0$
$n$ 個のノードについて、入力は $n^2+4n$ 個の数からなる。

完全な分解は本質的に３つのステップで記述される。

ステップ１:ネットワークのステーション間の相互作用の解析
ステップ２：個々のステーションでのパフォーマンス尺度の見積り
ステップ３：ネットワーク全体のパフォーマンス尺度の見積り

ステップ１

ステーションの２つのパラメータを決定する。
- (i)　期待到着レート
  - $\lambda_j=1/E[A_j]$
  - ただし $A_j$ はステーション $j$ での到着間隔である。
- (ii)　到着間隔の２乗変動係数（ｓｃｖ）
  - $C_{a_i}^2=Var(A_j)/E(A_j)^2$
３つのサブステップからなる。
- (i)　到着過程の重ね合わせ
- (ii)　全体出発過程
- (iii)　行先に従った出発の分割

ステップ１(i)

到着レートの重ね合わせ

は「交通量方程式」から得ることが出来る。
- について、
  - $\lambda_j=\lambda_{0j}+\Bigsum_{i=1}^n\lambda_{ij}$
- ただし
  - $\lambda_{ij}=p_{ij}\lambda_i$
- はステーションからステーションへの期待到着レートである。我々はまた
  - $\rho_j=\lambda_j/\mu_j$ 、 $0{\le}\rho_j<1$ （利用率あるいは「提供負荷」）
- も得る。
ステーションからステーション０への期待（外部）出発レートは
- $\lambda_{jo}=\lambda_j\left(1-\Bigsum_{i=1}^np_{ji}\right)$
で与えられる。
スループット
- $\lambda_0=\Bigsum_{j=1}^n\lambda_{0j}\text{ or }\Bigsum_{j=1}^n\lambda_{j0}$
期待訪問回数　
- $v_j=E(K_j)=\lambda_j/\lambda_0$
到着時間のｓｃｖは交通変動方程式（Whitt(1983b）)
- $C_{a_j}^2=w_j\Bigsum_{i=0}^n\frac{\lambda_{ij}}{\lambda_j}C_{a_{ij}}^2+1-w_j$ ・・・（１）
- ただし
  - $w_j=\frac{1}{1+4(1-\rho_j)^2(x_j-1)}$ 　
- かつ
  - $x_j=\frac{1}{\Bigsum_{i=0}^n\left(\frac{\lambda_{ij}}{\lambda_j}\right)^2}$
によって近似出来る。

ステップ１(ii)：出発過程

$C_{d_j}^2$ はステーション $j$ からの出発間隔の変動係数である。

$C_{d_j}^2=\rho_j^2C_{S_j}^2+(1-\rho_j^2)C_{a_j}^2$ ・・・（２）
もし到着時間過程とサービス過程がポアソンである、つまり、
- $C_{a_j}^2=C_{S_j}^2=1$
ならば、
- $C_{d_j}^2$
は正確であり、
- $C_{d_j}^2=1$
を導くことに注意しよう。
もし
- $\rho_j\rightar{1}$
ならば、
- $C_{d_j}^2{\rightar}C_{S_j}^2$
を得、反対にもし
- $\rho_j\rightar{0}$
ならば、
- $C_{d_j}^2{\rightar}C_{a_j}^2$
を得る。

ステップ１(iii)：出発の分割

$C_{a_{ji}}^2$

ステーション $j$ からステーション $i$ への到着間隔変動係数

$C_{d_{ji}}^2$

ステーション $j$ から $i$ への出発時間変動係数
$C_{a_{ji}}^2=C_{d_{ji}}^2=p_{ji}C_{d_j}^2+1-p_{ji}$ ・・・（３）

式（１）、（２）、（３）は

$C_{a_j}^2,C_{d_j}^2,C_{a_{ij}}^2=C_{d_{ij}}^2$

についての連立一次方程式、交通変動方程式、を形成する。

ステップ２

KreamerとLagenbach-Belzの公式［Whitt(1983a)によって修正］を用いて期待待ち時間を求める。
- $E(W_j)=\frac{\rho_j(C_{a_j}^2+C_{S_j}^2)g(\rho_j,C_{a_j}^2,C_{S_j}^2)}{2\mu_j(1-\rho_j)}=\frac{(C_{a_j}^2+C_{S_j}^2)g(\rho_j,C_{a_j}^2,C_{S_j}^2)}{2}E[W]_{M/M/1}$
- ただし
  - もし、ならば、
    - $g(\rho_j,C_{a_j}^2,C_{S_j}^2)=\exp\left\{\frac{-2(1-\rho_j)(1-C_{a_j}^2)^2}{3\rho_j(C_{a_j}^2+C_{S_j}^2)}\right\}$
  - もし、ならば、
    - $g(\rho_j,C_{a_j}^2,C_{S_j}^2)=1$

ステップ３

任意のジョブにおける期待リードタイム（待ち時間＋サービス時間）
- $E(T)=\Bigsum_{j=1}^nv_j(E(W_j)+E(S_j))$

「ダイナミック・ジョブ・ショップ（５）」に続きます。