ー般化セミマルコフ過程による生産ラインの解析
名古屋工業大学 生産システム工学科 中出 康– (Koichi Nakade) 名古屋工業大学 生産システム工学科 大野 勝久 (Katsuhisa Ohno)
1
はじめに生産システムをはじめ, 多くの現実のモデルは, 状態が離散空間で, 異なる事象が並行して進行
し, 事象が生起したときのみシステムの状態が変化する離散事象システム(Discrete Event System)
として扱うことができる. 離散事象システムに関する解析手法として, 一般化セミマルコフ過程
が, ペトリネットモデ)や, perturbation analysis とともに知られている. 一般化セミマルコフ過
程の枠組みは$\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{S}[1]$ が提案し, $\mathrm{S}\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{S}\mathrm{S}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}[2],$ $\mathrm{W}\mathrm{h}\mathrm{i}\mathrm{t}\mathrm{t}[3]$ らにより, 主に待ち行列モデルの非
感度性などの研究に応用されている. 近年, Glasserman, Yao等により, 一般化セミマルコフ過程 の構造に注目し, ある性質を持つときの挙動特性について研究がなされている $([4]-[7])$
.
これまで個々の生産モデルについて, 退去時刻や待ち時間等の再帰式の形から, 確率順序や凸 順序を用いた比較法により, パラメータや構造の異なるシステムの性能比較を行う研究がなされて いる. また, 直列型生産ラインをはじめとしたいくつかのシステムについて, 可逆性 (reversibility) などのシステム間の等価性を導く研究も多くなされている $([8]-[20])$.
これらのうち多くのモデル は–般化セミマルコフ過程を用いて定式化でき, Glasserman らが示した方法によりある程度の結 果を得るとが可能であることが知られてきている. 本報告では, 一般的なブロッキング構造をもつ, $\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{k}/\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}$ 型の開放型生産ラインについて, $-$ 般化セミマルコフ過程で定式化するとともに, 異なるシステム間の性能比較をおこなう.2
一般化セミマルコフ過程本章では, 一般化セミマルコフ過程 (generalized semi-Markov process) を定義し, その性質を
示す. 詳しくは $[6],[7]$ を参照のこと.
$S$: 可算状態空間
$A$: 事象 (event) の集合 (有限)
,
$A=\{\alpha_{1}, \ldots, \alpha_{M}\}$$\mathcal{E}=\mathcal{E}(s)$: 状態 $s$ で起こりうる事象の集合, $A= \bigcup_{s}\mathcal{E}(s)$ と仮定する. $\phi(s, \alpha)$: 状態 $s$ で事象\alpha が起きたときの状態の推移先
$\omega_{\alpha}(n)$: 事象 $\alpha$ の $n$ 回目の設定 clock. $\omega=\{(\omega_{\alpha_{1}}(n), \ldots,\omega_{\alpha_{M}}(n)), n=1,2, \ldots\}$
一般には, 推移が確率的であったり, clockの進行速度が状態により変化する形で表現されるが, こ
こでは, 推移が決定的で, 進行速度を 1 とする. 推移が確定的な GSMP を deterministic GSMP
とよぶ.
GSMP の挙動
1. 初期状態を $s_{0}$とし, $n=0,$ $\tau_{0}=0,$ $n_{\alpha}i=0,$ $c_{0}(\alpha_{i})=0,$ $i\in A$ とおく.
2. 時刻を$\tau_{n+1}$まで進ませる. ここで
$\tau_{n+1}=\tau_{n}+$ $\min\{c_{n}(\alpha_{i})\}$
.
$\alpha_{i}\in^{\epsilon}(s_{n})$
すなわち, $\mathcal{E}(s_{n})$ に属する事象のいずれかが起こるまで進ませる. この事象を$\alpha_{n+1}^{*}$とする. (同一時
刻に複数起こるときは, 添字最小のものを選ぶ.)
3. 時刻$\tau_{n+1}$において状態$s_{n+1}$は$\phi(s_{n}, \alpha_{n+}^{*})1$ となる. 時刻$\tau_{n+1}$において, 各事象の clock $c_{n+1}(\alpha_{i})$
を次のようにセットする.
$\alpha_{i}\in \mathcal{E}(s_{n+1})/(\mathcal{E}(s_{n})/\{\alpha_{n+1}^{*}\})$ $\Rightarrow$ $c_{n+1}(\alpha_{i})=\omega_{\alpha_{i}}(n\alpha i+1),$ $n_{\alpha:}arrow n_{\alpha}.\cdot+1$ $\alpha_{i}\in \mathcal{E}(S_{n+1})\cap(\mathcal{E}(_{S_{n})}/\{\alpha_{n+1}^{*}\})$ $\Rightarrow$ $c_{n+1}(\alpha_{i})=c_{n}(\alpha_{i})-(\mathcal{T}n+1-\mathcal{T}n)$
$\alpha_{i}\not\in \mathcal{E}(_{S_{n+1}})$ $\Rightarrow$ $c_{n+1}(\alpha_{i})=0$
$narrow n+1,2$へ戻る.
$T_{\alpha_{i}}(n)$ を事象\alpha ’ の $n$ 番目の生起時刻とし, $T_{\alpha:}=\{T_{\alpha_{i}}(n);n=1,2, \ldots\}$, $T=(T_{\alpha_{1}}, \ldots, \tau_{\alpha})m$ とす
る. $n$番目が起こらなければ, $T_{\alpha_{i}}(n)=\infty$ とおく. ここでは, 任意の初期状態に対し,
$P( \sup_{n>0}T_{\alpha}(in)=\infty)=1$
が成り立つと仮定する. 確率1で $\sum_{n=1\alpha_{i}}^{\infty}\omega(n)=\infty,.i=1,2,$$\ldots$,Mならばこの仮定は成り立つ.
$t$ までに
$\alpha_{i}$が起きた回数を $D_{\alpha_{i}}(t)= \sup\{n\geq 0;\tau\alpha_{i}(n)\leq t\}$
. とし, $D_{\alpha_{i}}=\{.D_{\alpha_{*}}.(t), t\geq 0\}$,
$D=(D_{\alpha_{1}\cdot\cdot\alpha_{M}},., D)$ とする.
.
GSMP から時間要素を取り除いた, 過程の構造を表す部分を -般化セミマルコフスキーム
(GSMS) といい, $\mathcal{G}=(S, A, \mathcal{E}, \phi)$ と表す. また, 事象列\mbox{\boldmath $\sigma$} $=\beta_{0}\beta 1\ldots\beta n$ (有限長) を string と呼ぶ.
定義21
ある事象\beta 0 $\in \mathcal{E}(s_{\mathit{0}})$ かつある状態列 $s_{1},$
$\ldots,$$s_{k+1}$が存在し, $\beta_{i}\in \mathcal{E}(s_{i}),$ $s_{i+1}=\emptyset(S_{i}, \beta_{i}),$ $i=$ $0,1,$$\ldots,$
$k$ が成り立つとき, $\sigma=\beta_{0\beta_{1}}\ldots$\beta kは
so
でfeasible であるという. $\blacksquare$string $\sigma\alpha$ が$s$ で feasibleであるとき,
$\emptyset(_{S,\sigma\alpha}):=\emptyset(\phi(s, \sigma),$$\alpha)$, $\phi$($s$,null) $:=s$
と定義する. string $\sigma$に対し, $[\sigma]_{i}$を事象$\alpha_{i}$の生起回数を表すとする. $[\sigma]=\{[\sigma]_{1}, \ldots, [\sigma]_{M}\}$ を$\sigma.\text{の}$
score とよぶ.
以下に, deterministic GSMS に関する各種の性質を定義する.
定義22
1) noninterruptive: $\alpha,\beta\in \mathcal{E}(s),$ $\alpha\neq\beta\Rightarrow\beta\in \mathcal{E}(\phi(s, \alpha))$, $s\in S$
.
2) permutable: $\sigma_{1},$$\sigma_{2}$ が Soでfeasibleであるとき, 以下が成り立つ.
3) strong permutable: $\sigma_{1},$$\sigma_{2}$ が soでfeasibleであるとき, 以下が成り立つ.
$[\sigma_{1}]=[\sigma_{2}]\Rightarrow\phi(s_{\mathit{0},1}\sigma)=\emptyset(S_{0}, \sigma 2)$
.
4) (M) (Monotonicity condition): $s$ で\mbox{\boldmath$\sigma$}1,$\sigma_{2}$がfeasibleであるとき, $[\sigma_{1}]\leq[\sigma_{2}]$ ならば,
$\mathcal{E}(\phi(s, \sigma 1))-A_{\sigma_{1},\sigma_{2}}\subseteq \mathcal{E}(\phi(s, \sigma 2))$
が成り立つ. ここで $A_{\sigma_{1},\sigma_{2}}=\{\alpha_{i}; [\sigma_{1}]_{i}<[\sigma_{2}]_{i}\}$である.
5) (C) (Commuting condition):
$\alpha,\beta\in \mathcal{E}(s)\Rightarrow\beta\in \mathcal{E}(\emptyset(s, \alpha)),$ $\alpha\in \mathcal{E}(\phi(s,\beta))$, $\phi(s, \alpha\beta)=\phi(s,\beta\alpha)$.
6) $(\mathrm{C}\mathrm{X})$:Convexity condition: $\sigma_{1},$$\sigma_{2}$,\mbox{\boldmath$\sigma$}\mbox{\boldmath$\sigma$}3がfeasibleであるとき,
$[\sigma_{3}]\geq[\sigma_{1}]\wedge[\sigma 2]\Rightarrow\{\mathcal{E}(\sigma_{1})\cap \mathcal{E}(\sigma 2)\}-A_{\sigma\sigma\sigma}1,2,3\subseteq \mathcal{E}(\sigma_{3})$
が成り立つ. ここで$A_{\sigma_{1},\sigma_{2},\sigma_{3}}=\{\alpha_{i}; [\sigma_{3}]_{i}>[\sigma_{1}]_{i}\wedge[\sigma_{2}]i\}$であり, $x \wedge y=(\min\{x_{1}, y1\},$ $\min\{x_{2}, y2\}$,
...
, $\min\{x_{M}, yM\})$ である $\blacksquare$このとき, 次の結果が知られている.
補題21
i) $(\mathrm{M})\Leftrightarrow \mathrm{n}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{r}\mathrm{u}\mathrm{p}\mathrm{t}\mathrm{i}_{\mathrm{V}\mathrm{e}}$ and permutable,
ii) $(\mathrm{C})\Leftrightarrow \mathrm{n}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{r}\mathrm{u}\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}$ and strong permutable,
iii) $(\mathrm{C}\mathrm{X})\Leftrightarrow \mathrm{n}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{r}\mathrm{u}_{\mathrm{P}}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}$ and
{
$[\sigma_{3}]\geq[\sigma_{1}]$A$[\sigma_{2}]\Rightarrow\{\mathcal{E}(\sigma_{1})\cap \mathcal{E}(\sigma_{2})\}\subseteq \mathcal{E}(\sigma_{3})$}.
$\blacksquare$次に, GSMS G の characteristic function を定義する.
定義2.3
各 string \mbox{\boldmath $\sigma$}及び事象\alpha $\in A$ に対し,
$\chi_{\alpha}(\sigma)=[\sigma]_{\alpha}+1\{\alpha\in \mathcal{E}(\sigma)\}$
と定義する. $\chi(\sigma)=\{\chi_{\alpha_{1}}(\sigma), ., . , \chi_{\alpha_{M}}(\sigma)\}$ とするとき, \mbox{\boldmath$\chi$}をGSMS G の characteristicfunction と
よぶ
.
$\blacksquare$特に, GSMSGがpermutableならば, $\chi$を$\chi_{\alpha}(x)=x_{\alpha}+1\{\alpha\in \mathcal{E}(x)\}$, $\chi(x)=\{\chi_{\alpha:}(x)\}$ と書
くことにする.
補題22
i) GSMSG が性質 (M) を満たす\Leftrightarrow \mbox{\boldmath $\chi$}(x) は $x$ について増加関数である, すなわち, feasible strings
$\sigma,$ $\sigma’$
について, $x=[\sigma],$ $y=[\sigma’]$ と置くとき, $x\leq y$ ならば, $\chi(\sigma)\leq\chi(\sigma’)$ が成り立つ.
ii) GSMSG が性質 $(\mathrm{C}\mathrm{X})$ を満たす\Leftrightarrow \mbox{\boldmath $\chi$}(x) は$x$ について増加かつ supermodular 関数である. ここ で, $\chi(x)$ がsupermodular であるとは, すべてのfeasible な $x,$ $y,$ $x\wedge y,$$X\vee y\in N$ について,
が成り立つことをいう
.
$\blacksquare$$\mathcal{G}$はpermutableであるとき, $N=$
{
$x\in z_{+}^{m}$ : $x=[\sigma]$ for$\sigma:s_{0}$で
feasible}
を G のscorespace と呼ぶ. $x=[\sigma]$ に対し, $\mathcal{E}(x)=\mathcal{E}(\emptyset(s, \sigma)),$ $N\alpha,n=\{x\in\lambda^{(} : X\alpha=n-1, \alpha\in \mathcal{E}(x)\}$ とお$\text{く}$
.
$N_{\alpha,n}$の各要素ごとのminimal elements を $x^{j}(\alpha, n)(j=1,2, \ldots)$ と定義する. すなわちすべての$x\in\lambda_{\alpha,n}r$
に対し,
$x\geq x^{j}(\alpha, n)$for some$j$, $xi^{x^{j}}(\alpha, n)$for all$j$
が成り立つ.
補題23
i) Gが性質 (M) を満たすならば,
$T_{\alpha}(n)= \omega_{\alpha}(n)+\min_{i}\max\{T\beta\in A\beta(X(j)\beta)\alpha, n\}$,
かつN は $\max$ closed, すなわち $x,$$y\in N\Rightarrow x\vee y\in N$
.
ii) さらに, G が性質 $(\mathrm{C}\mathrm{X})$ を満たすならば, N は$\min$ closed, すなわち $x,$ $y\in N\Rightarrow x\Lambda$ y\in Nが成
り立つ. minimal elementは唯$-$となって
$T_{\alpha}(n)= \omega_{\alpha}(n)+\max\{T\beta(x_{\beta(}\beta\in A\alpha, n))\}$
.
が成り立つ
.
$\blacksquare$補題24
$\omega_{\alpha}=\{\omega_{\alpha}(n), n=1,2, \ldots\}$は互いに独立な確率変数列であり, 異なる事象間は互いに独立であると
する. このとき, GSMS $\mathcal{G}$ が(M) を満たすならば,
$\omega_{\alpha}(:n)\leq_{st}\omega_{\alpha:}’(n)$ for all $i,$ $n\Rightarrow T_{\alpha_{i}}(n)\leq_{st}\tau_{\alpha}’.\cdot(n)$ for all $i,$ $n$
が成り立つ. さらに, $(\mathrm{C}\mathrm{X})$ を満たすならば,
$\omega_{\alpha:}(n)\leq_{icx}\omega_{\alpha}’:(n)$ for all $i,$ $n\Rightarrow T_{\alpha_{i}}(n)\leq_{icx}\tau_{\alpha}’:(n)$ for all $i,$ $n$
が成り立つ. ここで, $\leq_{st},$ $\leq_{icx}$は, おのおの (通常の) 確率順序, 非減少凸順序を表す. $\blacksquare$
3
$\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{k}/\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}$ 型多段生産システム本節では, 直列型有限バッファ生産ラインを含めた, $\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{k}/\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}$ 型の多段生産システムを考察
する. 一般化セミマルコフ過程に定式化し, 前節の結果を用いて, いくつかの結果を得る.
3.1 モデル
M 台の加工ステーションからなる多段型生産ラインを考える. 各ステーション砲 $=1,2,$$\ldots,$$M$)
はステーション$j\in U(i)$ から$-$つずつうけとり, $\mathrm{b}\mathbb{I}$
工をした後, 各ステーション $k\in D(i)$ に–つ
は次の規律に従う. 1. 加工を終えたステーション $k\in D(i)$ への仕掛品は, 次のいずれかの条件を満たす限り, ステー ション $i$ にとどまる. そうでなければ, ステーションんに進む. a) ステーション $i$ の加工を終え, かっ$k$での加工を終えていないステーション $k$にある仕掛品の数 が $a_{ik}$である. b) $k$のある後工程のステーション $k’\in D(k)$ について, a) の仕掛品の数, および $k$の加工を終え, まだステーション $k$内にとどまっている k’ へ向かう仕掛品の数の和が $c_{ikk}$’に達している.
2. 各ステーション$j\in U(i)$ からの仕掛品がすべてそろい, かつすべての $k\in D(i)$ について, 1. に
よりステーション $i$ にとどまっている仕掛品の数が $b_{ik}$に達していないとき, ステーション $i$
は次
の加工を行うことができる. ただし, $b_{ik}=0$ のときは, すべての $k\in D(\mathrm{i})$ 側が $i$ からの仕掛品を
受け入れ可能な状態である (すなわち, 1. の $\mathrm{a}$),$\mathrm{b})$ のどちらの条件も満たさない) 時のみ加工を行
うことができることを意味する.
ステーション$i$ が外部 (無限量) からの供給を受けるとき,
$0\in U(i)$, また加工した完成品がた
だちに外部に引き取られる場合は, $M+1\in D(i)$ とする. $a,$$b,$$c$ の間には, 次の関係式が成り立
つと仮定する. 各 $i=1,2,$$\ldots,$$M,$ $j\in U(i),$ $k\in D(i)$ について,
$a_{ji}\geq 1$, $b_{ik}\geq 0$, $a_{ji}+b_{ik}\geq$ $c_{jik}$, $c_{jiM+}1=a_{ji}$
.
ただし, $a_{0i}$, Coik, $b_{i,M+1}$は意味を持たないので, 特に定義しない.
本研究では, $i_{t}\in D(i_{t-1})(t=1, \ldots, k),$ $i_{0}\in D(i_{k})$ となるようなステーション列 ($i0,$il,$\ldots,$$ik$)
は存在しないものと仮定する. 各ステーション $i$ では, 初期においてステーション$j\in U(i)$
で加
工を終えた仕掛品が $m_{ji}(0\leq m_{ji}\leq a_{ji})$ 個存在すると仮定する. ステーション $i$ での
$n$ 番目の加 工時間を
Si
$(n)$ , 加工終了時刻を $T_{i}(n)$ で表す. 32 一般化セミマルコフ過程への定式化 $s_{ik}$を, ステーション $i$ で加工を終え, k で加工を終えていない仕掛品の数を表すものとし, $\alpha_{i}$は, ステーション $i$ での加工を表すとする. このとき, 次の補題を得る. 補題3.1 ステーション $i$ で加工可能となる必要十分条件は,1) $s_{ji}>0$ for all $j\in U(i)/\{0\},$ $\mathrm{B})\supset$
2) $\sum$ $s_{i_{t},i_{t+1}}<u_{I}$ for all $I\in L(i)$ $(i_{t,t+1}i)\in I$
が成り立つことである. ここで
$L(i)=$
{
$(i_{0},$il,$\ldots,$it);$i_{0}=i,$$i_{1}\in D(i_{0}),$ $i_{2}\in D(i_{1}),$$\ldots,$$i_{t}\in D(i_{t-1}),$$i_{t}\neq M+1,$$t\geq 1$
}
であり, 各 $I=(i_{0}, i_{1}, \ldots, it)\in L(i)$ について,
$u_{I}=b_{ii}0,1+ \sum_{j=1}^{t-1}Cij-1,ij,iJ+1+ai_{t-1},i_{t}$,
とする. すなわち, $L(i)$ は $i$
で加工される仕掛品が通る可能性のある加工順列の集合である. $\blacksquare$
これにより, 本モデルは以下のように GSMS に定式化される.
初期状態 $s_{0}=\{(m_{ij})\}$ 事象空間 $A=\{\alpha_{i}; i=1, \ldots, M\}:\alpha_{i}$はステーション $i$ での加工終了を表す
事象
各状態の事象集合 $\mathcal{E}(s)=\{\alpha_{i}$;$sji>0$ forall $j\in U(i)/\{0\},$$\sum_{(i_{t},i)}t+1\in ISi\iota,i_{t}+1<u_{I}$ for all $I\in$
$L(i)\}$,
推移法則$\phi(s, \alpha_{i})$
. $=S- \sum_{\{j\in U\langle i)/0\}}eji+\in(i)/\sum_{kD\{M+1\}}e_{ik}$
,
ここで, $e_{ij}$は ij 要素のみ 1 をとる単位ベクトルである.
$x_{i}$を事象\alpha ’ の生起回数とするとき, $s$ と $x$ は次の関係式をもつ.
$s_{ik}=m_{ik}+x_{i}-X_{k}$, $i=1,$$\ldots,$$M,$
.
$k\in D(i)/\{.M+1\}$.
このとき, GSMS$\mathcal{G}=(S, A, \mathcal{E}, \phi)$ について次の定理が成り立つ.
定理 31
$\mathcal{G}$は性質 $(\mathrm{C}\mathrm{X})$ を満たす.
Proof. (M) を満たすのは明か. (1)式が成り立つことを示して, 補題22を用いる. $\blacksquare$
これにより, 次の結果を得る.
定理 32
$T_{i}(n)$ $=$
Si
$(n)+ \max\{$$T_{i}(n-1),$ $\max${
$T_{i}$(n–mji)}, $j\in u_{\mathrm{t})}n$$k \in\overline{D}(i)\max\{T_{k}(n-\min(u\mathrm{t}i_{0},\ldots,it\mathrm{t}^{i_{0,\ldots,t}}i)\in L(i),it=k-)\sum_{\mathit{0}j=}^{t-1}mij^{i_{j}},+1))\}\}$
が成り立つ. ここで, $\tilde{D}(i)$は, $L(i)\text{に属する}(i_{0}, i_{1}, \ldots, k)$ が存在するステーションの集合を表す.
Proof. 補題 23, 補題31を用いる $\blacksquare$
定理 33
同じモデルについて, 二つの作業列\mbox{\boldmath $\omega$} $=\{S_{i}(n);i=1, \ldots, M, n--1,2, \ldots\}\omega’--\{s_{i}’(n);i=$
$1,$
$\ldots,$$M,$$n=1,2,$$\ldots\}$ を考え, おのおののステーション
$j$での
$n$番目の加工完了時刻を $T_{i}(n),T’i(n)$
とする. \mbox{\boldmath $\omega$},\mbox{\boldmath $\omega$}’は独立な確率乱数列であり, $S_{i}(n).\leq_{icx}S_{i}’(n)$ ならば, $T_{i}(n)\leq icx\tau’i(n)$ が成り立っ.
Proof. 補題2.4より明らか
.
$\blacksquare$3.3 システムの可逆性と等価性
前節で与えたシステムに対し, すべての向きを逆にした以下のパラメータ $m_{ij}^{T},$$U^{T}(\mathrm{i}),$$D^{r}(i)$ を
持つ reversed system を考察する.
1) 各 $i=1,2,$$\ldots,$$M$に対し,
$U^{r}(i)=D(i)$
,
$D^{r}(i)=U(i)$, $m_{ij}^{r}=m_{ji}$ $j\in D^{r}(\mathrm{i})$ただし, $M+1\in D(i)$ ならば$0\in U^{r}(i),$ $0\in U(i)$ ならば$M+1\in D^{r}(i)$ とする.
2) すべての ($\mathrm{i}_{0,}$i $i$ )
$\in L(i)$ について,
が成り立つ.
条件2) は, 次の$\mathrm{a}$)$- \mathrm{d}$) のいずれかが成り立てばよい. すべての $i=1,$
$\ldots,$$M,j\in U(i),$$k\in D(i)$
について,
a) $a_{ij}^{r}=bji$, $b_{ki}^{r}=a_{ik}$, $c_{k}^{r_{iij}}=Cik$,
b) ある定数$b$ が存在し, $b_{ik}=b,$ $a_{ji}+b=c_{jik},$ $a_{ij}^{r}=a_{ji},$ $b_{ki}^{r}=b,$ $c_{kij}^{r}=a_{ki}^{r}+b$が成り立つ.
c) ある定数 $b$ および $d_{i}(i=1, \ldots, M)$が存在し, $a_{ji}=c_{jik}=d_{i}$ for a垣 $j,$ $k$, $b_{ik}=b$, $a_{ij}^{r}=$
$a_{ji}=d_{i},$$b^{r}=kib,$$c^{r}kij=a_{ki}^{r}=d_{k}$ が成り立つ.
d) ある定数 $d_{i}(i=1, \ldots, M)$ が存在し, $a_{ji}=c_{jik}=b_{ik}=d_{i}$ for all$j$, ん, $a_{ij}^{r}=d_{j},$$b_{ki}^{r}=$
$d_{k},$$c_{kij}^{r}=d_{i}$ が成り立つ. (a)の特別な場合)
このとき, 次の結果を得る.
定理34各ステーション $i$ において, 加工時間列 $\{S_{i}(n), n=1,2, \ldots\}$ が独立で同– の確率分布に
従うものとする. このとき,
$i=1, \max\ldots,T_{i}r(n)M=_{sti}\max_{=}T(n)$,
が成り立つ.
Proof. システムは $(\mathrm{C}\mathrm{X})$ を満たすことから, 補題23の minimal elementが存在する. $x_{\alpha_{j}}(\alpha_{i}, m)$
$=$ m’ であることを $(j, m’)arrow(i, m)$ で表し, すべてのステーションの組 $(i,j)$ について $(i, 1)$ から
$(j, n)$ へのすべてのpath $(i, 1)arrow\cdotsarrow(j, n)$ の集合を$\Pi$とすると, 補題23より,
$\dot{\iota}=1,\ldots,M\in\Pi\max T_{i}(n)=\max_{\pi}\mathrm{t}^{i,)\pi}n\sum_{\in}s_{i}(n)$
が成り立つ. reversed system において, 同様に $x_{\alpha:}^{r}(\alpha_{j}, m’)=m$ であることを $(i, m)arrow r(j, m’)$
で表し, すべてのステーションの組 $(i,j)$ について $(i, 1)$ から $(j, n)$ へのすべての path $(i, 1)arrow r$
$...arrow r(j, n)$ の集合を $Pi^{r}$とするとき,
$\max_{\dot{\iota}=1,\ldots,M}Ti(rn)=\max_{\pi\in\Pi(i},\sum_{r}rr)n)\in\pi s_{i(}^{T}n$
となる. reversedsystemにおける $(i, m)arrow r(j, m’)$ と元のシステムの $(j, n+1-m^{J})arrow(i, n+1-m)$
が 1 対 1 で対応づけることができるので, 結果を得る $\blacksquare$
次に, すべての $i\in\{1, \ldots, M\},$ $j\in U(\mathrm{i}),$ $k\in D(i)$ について,
$a_{ji}+b_{ik}=Cjik$
が成り立つとする. このとき, $I=\{i_{0}, \ldots, it\}\in L(i_{0})$ について, $I_{1}=\{i_{0}, \ldots, \mathrm{i}_{j}\},$ $I_{2}=$
{
$i_{j},$$\ldots$,
it}
とすると, $u_{I}=u_{I_{1}}+u_{I_{2}}$が成り立つことに注意すると, 定理 32 の式が
$T_{i}(n)=S_{i}(n)+ \max\{T_{i}(n-1),\max_{U}\{j\in(i)\tau_{j}(n - mji)\}$’$k \in D()\max_{i}\{Tk(n-(u_{(i,k)}-m_{ik}))\}\}$
と表すことができる (ブロッキングが $a_{ik}$の条件にのみ起こるため). $u_{(i,k)}=b_{ik}+a_{ik}$に注意する.
このとき, 次のシステム $l$を考える.
$j_{q}\in D(i_{q})$ なるいくつかの組 $(i_{1},j_{1}),$
$\ldots,$$(i_{p},j_{p})$ について,
$i_{q}=D^{l}(jq)$, $m^{l}j_{q}i_{q}u=ij_{q}q-mii_{q}q$
かつすべての $i,$ $j\in U^{l}(i),$ $k\in D^{l}(i)$ について $c_{jik}^{l}=a_{ji}+b_{ik}$とする. これ以外の組は元のシステ ムと変わらないものとする. ただし, これにより $U^{l}(i)=\phi,$ $D^{l}(i)=\phi$ となるときは, おのおの $U^{l}(i)=\{0\},$ $D^{l}(i)=\{M+1\}$ システム $l$は, 元のシステムのうちいくつかの隣接したステーショ ンの組について, 処理順序を逆向きにし, かつ初期在庫数を初期の空き在庫数に置き換えたもので ある. このとき, 次の定理を得る. 定理 35 同– のサービス時間
Si
$(n)$ をもっとき, すべての $i,$ $n$ について, $T_{i}^{l}(n)=T_{i}(n)$ が成り立つ. Proof. 漸化式が–致する. $\blacksquare$4
例 41 $(\mathrm{a},\mathrm{b},\mathrm{k})$直列システム. $U(i)=\{i-1\},$ $D(i)=\{i+1\}$ となるシステムを考える. このとき, Chang and $\mathrm{Y}\mathrm{a}\mathrm{o}[13]$,
Glasserman and $\mathrm{Y}\mathrm{a}\mathrm{o}[5]$ などで知られた $(a, b, k)$ システムと–致する. と$\text{く}\}^{arrow}.,$
$aii+1=C_{ii++2}1i=$
$k_{i+1}$のとき, $b_{ii+1}=0$ ならば通信ブロッキング, $b_{ii+1}=1$ ならば生産ブロッキング $b_{ii+1}$ =k, な
らかんばん型ブロッキング (ステーション $i$ は ki個のかんばんを持つ)
となる. このとき, 定理
3.3より凸性が成り立ち, 定理3.4より, これまで得られた可逆性の結果を与える. さらに, 通信
ブロッキングについては定理35も適用できる. 4.2 単純な $\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{k}/\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}$ システム
各ステーションは入力 $U(i)$, 出力 $D(\mathrm{i})$ の–方のみが複数のステーションを持ち, さらに $b_{ji}=$
$0,$$c_{jik}=a_{ji}$ が成り立つシステムを考える. このとき, 入力が複数のステーションはJoin型, 出力
が複数のステーションは Fork型となり, 二つのステーション間は容量勺
i
のバッファでつなげた単純な $\mathrm{F}\mathrm{o}\mathrm{r}\dot{\mathrm{k}}/$join システムになる. (Join
型ステーション $i$では, サービスが完了するまで $i$ の手前の バッファにとどまるものとする.) このとき, 定理 33 より凸性が示され, さらに定理 34, 35 を適 用することができる. 定理 34, 35については, $[16]-[18]$ で (GSMP を使わずに)示したことと– 致する.
5
終わりに GSMP において, 事象生起時間が指数分布にしたがう場合については,GSMS
の同期化による 性能比較や, マルコフ決定過程の定式化による最適制御政策の単調性の解析などの研究がなされて いる. 上記以外の, たとえば閉路をもつ生産ラインの場合, デッドロックが起きないことを示す必要 がある. この点が証明されれば, 本論と同様の結果が得られることが期待される. また, 状態空間 が既約であれば, GSMS のサブスキ一ムの議論を用いてなお多くの性能比較を行うことができる. 状態間の可到達性やデッドロックについては, ペトリネットの理論との関連を含めて考察する必要 がある.参考文献
[1] Matthes, K., Zur Theorie der Bedienungsprozess, Trans. 3rd $P_{\Gamma}ague$
Conf. Inform.
Theory,Statist. Dec. Funct., Random Processes, 513-528, Prague, 1962.
[2] Schassberger, R., On the Equilibruim Distribution of a Class of Finite-State Generalized
Semi-Markov Processes, Mathematics
of
Operations Research, vol. 1, 395-406,1976.
[3] Whitt, W., Continuity of Generalized Semi-Markov Processes, Mathematics
of
OperationsResearch,vol. 5, 494-501, 1980.
[4] Glasserman, P. and Yao, D. D., “Algebraic Structure of Some Stochastic Discrete-Event
Systems, with Applications,” Discrete Event Dynamic Systems: Theory and Applications,
vol. 1, 7-35,
1991.
[5] Glasserman, P. and Yao, D. D., “Structured Buffer-Allocation Problems,” Working Paper,
1992.
[6] Glasserman, P. and Yao,D. D., “A GSMP Framework for theAnalysisofProduction Lines,”
in StochasticModeling and Analysis
of
Manufacturing Systems,Yao, D. D. Editor, Chapter4 (pp.133-188), Springer-Verlag, New York, 1994.
[7] Glasserman, P. andYao, D. D., Monotone Structure in Discrete-EventSystems, Wiley, New York,
1994.
[8] Buzacott, J. A. and Shanthikumar, J. G., Stochastic Models
of
Manufacturing Systems.Prentice-Hall, Englewood Cliffs, New Jersey, 1993.
[9] Avi-itzhak, B. and Yadin, M., A Sequencing of Two Servers with No Intermediate Queue,
Management Science, vol. 11, 553-564, 1965.
[10] Muth, E. J., The Reversibility Property of Production Lines, Management Science, vol. 25, 152-158, 1979.
[11] Yamazaki, G. and Sakasegawa, H., Properties of Duality in Tandem Queueing Systems,
Annals of the Institute ofStatistical Mathematics vol. 27, 201-212,
1975.
[12] Yamazaki, G., Kawashima, T. andSakasegawa, H., ReversibilityofTandem Blocking
Queue-ing Systems, Management Science, vol. 31, 78-83, 1985.
[13] Cheng, D. W. and Yao, D. D., “Tandem Queues with General Blocking: A Unified Model
and Comparison Results,” Journal
of
Discrete Event Dynamic Systems: Theory andAppli-cations, vol. 2, 207-234, 1993.
[14] Cheng, D. W., “Line Reversibility of Tandem Queues with General Blocking,” Management
Science, vol. 41, 864-873, 1995.
[15] Tayur, S. R., “Properties of Serial Kanban Systems,” Queueing Systems, vol. 12, 297-318, 1992.
[16] Ammer,M. H. andGershwin,S. B., “EquivalenceRelations in Queueing Models of$\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{k}/\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}$
Networks with Blocking,”
Performance
Evaluation, vol. 10, 233-245, 1989.[17] Dalley, Y. and Towsley, D., “Symmetric Property of the Throughput in Closed Tandem
Queueing Networks with Finite Buffers,” Operations Research Letters, vol. 10, 541-547,
1991.
[18] Paik, C. -H. and Tcha, D. -W., “Throughput Equivalence in $\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{k}/\mathrm{J}\mathrm{o}\mathrm{i}\mathrm{n}$Queueing Networks with Finite Buffers and General Service Times,” International Journal
of
ProductionRe-search, vol. 33, 695-703, 1995..
[19] Nakade, K. and Ohno, K., “Reversibility and Dependence in a $\mathrm{U}$-Shaped Production Line,” to appear in Queueing Systems, 1995.
[20] Nakade, K. and Ohno, K., “Analysis of Cycle Times of a $\mathrm{U}$-Shaped Production Line,”
