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

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

「ダイナミック・ジョブ・ショップ（２）」の続きです。

ジャクソン開放型待ち行列ネットワーク

  • 仮定
    • 外部から単一クラスの（集約された）ジョブがレート\lambdaのポアソン過程に従って到着する。
    • マシンセンターiでのジョブのサービス時間が平均1/\mu_iのiidの指数分布確率変数である。
    • もしマシンセンターiにn個のジョブがあるならば、総処理レートは\mu{r_i}(n)である。（例えば、もしc_i台の同一の装置があるならばr_i(n)=\min\{n,c_i\}）
    • サービス・プロトコル（キュー規律）はジョブ・サービス時間要求と独立である。例えばＦＣＦＳあるいはランダム。

ジャクソン・ネットワーク

もしN_i(t)が時刻tでのマシンセンターiでのジョブ数であり、

  • p(n)=\lim_{t\rightar\infty}P\{N_1(t)=n_1,...,N_m(t)=n_m\}

ならば、

  • p(n)=\prod_{i=1}^mp_i(n_i)

つまり、ネットワークは積形式解を持つ。もし個々のマシンセンターが１台の装置からなるならば、そしてもし\rho_i=\lambda_i/\mu_i<1ならば

  • p(n)=\prod_{i=1}^m(1-\rho_i)\rho_i^{n_i}

ネットワークは独立なM/M/1待ち行列に分解出来る。（もし各々のセンターに複数台の装置があるならば、M/M/c_i）

個々のステーションに１台装置

マシンセンター内の平均ジョブ数：

  • E[N_i]=\frac{\rho_i}{1-\rho_i}

システム内のジョブ総数：

  • E[N]=\Bigsum_{i=1}^m\frac{\rho_i}{1-\rho_i}

ジョブの平均フロー時間：

  • E[T]=\frac{1}{\lambda}\Bigsum_{i=1}^m\frac{\rho_i}{1-\rho_i}=\Bigsum_{i=1}^m\frac{v_i}{\lambda_i}\frac{\rho_i}{1-\rho_i}=\Bigsum_{i=1}^mv_iE[T_i]

システム内のジョブ数の分散

  • Var[N]=\Bigsum_{i=1}^m\frac{\rho_i}{(1-\rho_i)^2}

タスクのマシンセンターへの割付

任意のジョブについての平均タスク数=Kを満たすようにしてE[T]を、同等であるがE[N]を最小にする。よってタスク割当ては

  • \Bigsum_{i=1}^mv_i=K

のもとでのv_iの値を決定する。もし与えられたタスクがマシンセンターiに割当てられると、それは指数分布（\mu_i）の時間を要求すると仮定する。

  • E[N]=\Bigsum_{i=1}^m\frac{\rho_i}{1-\rho_i}=\Bigsum_{i=1}^m\frac{{\lambda}v_i/\mu_i}{1-\lambda{v_i}/\mu_i}

最適解

  • v^*=\frac{1}{\lambda}\left(\mu_i-\left(\Bigsum_{j=1}^m\mu_j-\lambda{K}\right)\frac{\sqrt{\mu_i}}{\Bigsum_{j=1}^m\sqrt{\mu_j}}\right)

最適訪問レートの達成

全てのジョブ・タイプにいてのタスクの全体集合：　\alpha=\{1,...,L\}
任意のジョブについてタスクiを実行するのに必要な平均回数をw_iとする。理想的には、

  • \Bigsum_{j\in{S}}w_j=v_j^*

を満たすような\alpha=S_1{\cup}S_2{\cup}...{\cup}S_mを見出す。
より現実的には、k=1,...,mについて

  • \Bigsum_{i=1}^{l(k)}w_i{\le}\Bigsum_{j=1}^kv_j^*　（l(m)=L）

を満足するような最も大きなタスク指標としてl(k)を見つける。つぎにもし、

  • \Bigsum_{i=1}^{l(k)}w_i<\Bigsum_{j=1}^kv_j^*

ならばタスクl(k)+1をマシンセンターkとk+1の両方に割り付ける。


http://www.public.iastate.edu/~smryan/ie613/Chapter7pt1.pptはここで終わっています。


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