数理解析研究所講究録
978 巻 1997 年 34-40

34

到着率が減少する待ち行列システムの最適保全政策

1

鳥取大学工学部

小柳

鳥取大学工学部

河合淳二(Junii KOYANAGI)(Hajime KAWAI)–

はじめにゲームセンターやパチンコ店では最初は人気があった機種が時間とともに人気がなくなり到着する客が減ってくる, そのような場合, 古い機種を新しい機種に入れ替えて客足を取り戻すことが必要になる. 本研究ではこのようなモデルをサーバーの状態に依存した到着率を持つ待ち行列システムとして取り扱い, その最適保全政策の性質について考察する.

2モデルと記号$M/M/1/N$ 待ち行列システムを考え, そのサーバーは $0,1,$を持ち, 状態$k$から $l(>k)$ に推移率

サーバーの状態$k$に対し客は到着率$\beta_{k}\iota$$\lambda_{k}$システムから退去する. サーバーを状態$\ldots,$$s$の番号のついた $s+.1$ 個の状態

でマルコフ的に推移するものとする. $(\beta_{k}\iota=0(l\leq k))$でシステムに到着し, サービス率$0$$\mu$でサービスを受けてに戻すには, 保全作業が必要であり, それには, 分布関数 $H(x)$ に従う時間がかかるとする. ただし, 保全開始時点にシステム内にいた客は全て失われ,保全中客の到着はないものとする.
システムが利得を得る時点として, 2 通りの場合を考え, 次の 2 種類のモデルを扱う.

Model A 客が到着した時点で 1 単位の入場料を得る, ただし, 保全開始時に失われる客に対してはそれを払い戻す

Model$\mathrm{B}$

客がサービズを終えた時点で 1 単位のサービス料を得る.

システムの状態を系内人数$i$とサーバーの状態$k$の組 $(i, k)$ で表わし, 状態推移が生じた時点で次のどちらかの決定を行う.

Action 1 サーバーの保全を開始する.

Action 2 サーバーの稼動を続ける.
目的はシステムが得る総期待割引利得 (割引因子$\alpha$) を最大にするように各時点でのアクションを決定することである.

Uniformization$\gamma_{k}=\sum_{l=0}^{s}\beta k\iota,$$\lambda=\sum_{k=0}^{s}\lambda_{k},$$(\mathrm{s}_{\mathrm{e}\mathrm{r}}\mathrm{f}_{\mathrm{o}\mathrm{Z}\mathrm{o}[3]})$$\Gamma=\sum_{k=0}^{s}\gamma_{k},$のため次の記号を定義する.

$\gamma_{k}\iota=\beta_{k}\iota(k\neq l),$$\mathrm{A}=\lambda+\mu+\Gamma+\alpha,$$\gamma kk=\Gamma-\gamma_{k}$$h= \int_{0}^{\infty}e^{-\alpha x}dH(X)dx$.

,

35

3

定式化と仮定
$V_{A}(i, k),$ $V_{B}(i, k)$それぞれ Model$\mathrm{A},$$W_{A}(i, k),$ $W_{B}(i, k)$それぞれ Model$\mathrm{A},$$\mathrm{B}$$\mathrm{B}$で状態 $(i, k)$ に対する最適利得関数

で状態 $(i, k)$ に推移した時, 稼動を続け, 以後最適政策をとった場合の利得関数
それぞれ Model$M_{A}(i),$ $M_{B}$$\mathrm{A},$$\mathrm{B}$で状態 ( , 紛に推移した時, 保全を行い, 以後最適政策$i$をとった場合の利得関数$D_{A}(i, k),$ $D_{B}(i, k)$それぞれ Model$D.(i, k)=\{$$\mathrm{A},$$\mathrm{B}$において状態 $(i, k)$ に推移した時の最適アクション

サ– \‘‘一の保全が最適な場合

1
2

サ-(1)

\‘‘一稼動を続けるのが最適な場合とする.
$\beta_{kl}$と$\lambda_{k}$l こ関し, 次の仮定をおく

仮定 1

1. すべての2.

$\lambda_{k}$は$k$$m \text{に対し}\sum_{l=m}^{s}\beta_{k}\iota$

は$k$に関して非減少に関して非増加

仮定 11 は現在の状態が大きくなるほど, 次にさらに大きな状態に推移しやすくなることを示し,
仮定 12 は状態が大きくなるにつれて, 到着率は減少することを示す 仮定 11 に対して次の補題が成立する.
補題 1$l$$(\mathrm{S}\mathrm{t}\mathrm{o}\mathrm{y}\mathrm{a}\mathrm{n}[4])$に関して非増加な数列 fi に対し,$\sum_{0l=}^{s}\gamma klf_{i}$は$k$に関して非増加な数列となる.

到着時に料金を得る場合
到着時に客から料金 1 を得て, 保全開始時に失われる客に対してはそれを払い戻す場合 (Model A)の最適性方程式は次のようになる$W_{A}(0, k)= \frac{1}{\Lambda}[\lambda_{k}(V_{A}(1, k)+1)+\mu V_{A}(0, k)+\sum_{l=0}^{s}\gamma_{k\iota}VA(0, l)+(\lambda-\lambda k)VA(\mathrm{o}, k)]$

$W_{A}(i, k)= \frac{1}{\Lambda}[\lambda_{k}(V_{A(i}+1, k)+1)+\mu V_{A}(i-1, k)+\sum_{l=0}^{s}\gamma_{k\iota A}V(i, \iota)+(\lambda-\lambda_{k})VA(i, k)]$$(1\leq i\leq N-1)$$W_{A}(N, k)= \frac{1}{\Lambda}$[$k+\mu V_{A}(N-1,$$\lambda_{k}V_{A()}N,$$M_{A}(i)=-i+hV_{A}(0, \mathrm{o})$$V_{A}(i, k)= \max\{M_{A}(i), W_{A}(i, k)\}$$k)+ \sum_{0l=}^{s}\gamma_{k}\iota$

VA $(N,$ $l)+(\lambda-\lambda_{k})VA(N,$ ]
$k)$

36

サービス終了時に料金を得る場合

サービス終了時に客から料金 1 を得て, 保全開始時に失われる客に対するコストはかからない
場合 (Model B) に対する最適性方程式は次のようになる$W_{B}(0, k)= \frac{1}{\Lambda}[\lambda_{k}VB(1, k)+\mu V_{B}(0, k)+\sum_{0l=}^{s}\gamma k\iota VB(\mathrm{o}, l)+(\lambda-\lambda k)VB(\mathrm{o}, k)]$$W_{B}(i, k)= \frac{1}{\Lambda}[\lambda_{k}V_{B(i}+1, k)+\mu(V_{A}(i-1, k)+1)+\sum_{l=0}^{s}\gamma klV_{B}(i, l)+(\lambda-\lambda_{k})VB(i, k)]$$(1\leq i\leq N-1)$$W_{B}(N, k)= \frac{1}{\Lambda}[\lambda_{k}V_{B()}N, k+\mu(V_{B}(N-1, k)+1)+\sum_{l=0}^{s}\gamma k\iota VB(N, l)+(\lambda-\lambda_{k})VB(N, k)]$$M_{B}=hV_{B}(0, \mathrm{o})$$V_{B}(i, k)= \max\{M_{B}, W_{B}(i, k)\}$4

利得関数の性質
逐次近似法により $V.(i, k),$ $W.(i, k),$ $M_{A}(i),$ $M2$ を求める.

Model A に対する逐次近似法を
Step$V_{A(i,k)}^{0}=\lambda_{0}/\alpha$$0$

for all $(i, k)$ .

(2)

Step 1$W_{A}^{n+1}(0, k)= \frac{1}{\Lambda}[\lambda_{k}(V_{A}n(1, k)+1)+\mu V_{A}^{n}(0, k)+\sum_{l=0}^{s}\gamma_{k\iota}V_{A}n(0, l)+(\lambda-\lambda_{k})V_{A}n(\mathrm{o}, k)]$

$W_{A}^{n+1}(i, k)= \frac{1}{\Lambda}[\lambda_{k}(V_{A}n(i+1, k)+1)+\mu V_{A}^{n}(i-1, k)+\sum_{0l=}^{s}\gamma k\iota^{V^{n}}A(i, \iota)+(\lambda-\lambda_{k})V_{A}n(i, k)]$$(1\leq i\leq N-1)$$W_{A}^{n+1}(N, k)= \frac{1}{\Lambda}[\lambda_{k}V_{A()+V_{A}}^{n}N, k\mu n(N-1, k)+\sum^{s}\gamma_{k}\iota V_{A}n(N, l)+(\lambda-\lambda k)V^{n}A(N, k)]l=0$$M_{A}^{n+1}(i)=-i+hV_{A}^{n}(0, \mathrm{o})$$V_{A}^{n+1}(i, k)= \max\{M_{A}^{n+1}(i), W^{n+1}(Ai, k)\}$Step 2Let $n=n+1$ and go to Step 1.
で定義する.

Model$\mathrm{B}$に対する逐次近似法も同様に定義する.

$V^{n}.(i, k),$ $W^{n}.(i, k),$ $M_{A}n(i),$$MB$

は, $V.(i, k),$ $W.(i, k),$ $M_{A}(i),$ $MB$ に収束する.

数学的帰納法により次の性質を証明できる.

$(\mathrm{W}\mathrm{e}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{l}\mathrm{s}[5])$

37

補題 2

1.

$V_{A}(i, k)\leq\lambda_{0}/\alpha$,

2. $W_{A}(i+1, k)-W_{A(}i,$ $k)\geq-1$ ,3. $W_{A}(i, k)$ は4. もし$\lambda_{0}\leq\mu$$k$に関して非増加,ならば, $i\geq 1$ に対し $W_{A}(i, k)\geq M_{A}(i)$ ,証明)

1. の証明 $n=0$ のとき明らか,$V_{A}^{n}(i, k)\leq\lambda_{0}/\alpha$と L, て $V_{A}^{n+1}(i, k)\leq\lambda_{0}/\alpha$ を示す.

$M_{A}^{n+1}(i)=-i+hV^{n}(\mathrm{o}, \mathrm{o})\leq h\lambda_{0}/\alpha\leq\lambda_{0}/\alpha$,$W_{A}^{n+1}(i, k) \leq\frac{1}{\Lambda}[\lambda_{k}(\lambda_{0}/\alpha+1)+\mu\lambda 0/\alpha+\sum_{l=0}^{s}\gamma_{kl}\lambda_{0}/\alpha+(\lambda-\lambda k)\lambda_{0}/\alpha]$$\leq\frac{1}{\Lambda}[\lambda_{0}+\mu\lambda_{0}/\alpha+\Gamma\lambda 0/\alpha+\lambda\lambda_{0}/\alpha]$$=\lambda_{0}/\alpha$.

$V_{A}^{n+1}(i)= \max\{M_{A}^{n+1}(i), W^{n+1}(Ai, k)\}$$\lambda_{0}/\alpha$であるから$V_{A}^{n+1}\langle i,$ $k$)$\leq\lambda_{0}/\alpha$. よって砺 0, )$k$$\leq$.

2. の証明 まず $n=1$ に対して $W_{A}^{1}(i+1, k)-W_{A}^{1}(i, k)=0(0\leq i\leq N-2),$ $W_{A}^{1}(N, k)-$
$W_{A}^{1}(N-1, k)=-\lambda_{k}/\Lambda$ .
よってに対して成り立つ.
$W_{A}^{1}(i, k)$.
.

$V_{A}^{1}(i, k)$に対して, 次の 2 通りの場合を考える.

$W_{A}^{1}(i, k)<M_{A}^{\mathrm{I}}(i)$のとき,$V_{A}^{1}(i+1, k)-V_{A}^{1}(i, k)\geq M_{A}^{1}(i+1)-M_{A(i)}^{1}=-1$$W^{1}(i, k)\geq M(i)$.のとき,$V_{A}^{1}(i+1, k)-V_{A}^{1}(i, k)\geq W_{A}^{1}(i+1, k)-W_{A}^{1}(i, k)\geq-1$.

帰納法の仮定 $V_{A}^{n}(i+1, k)-V_{A}^{n}(i, k)\geq-1$ かつ $W_{A}^{n}(i+1, k)-W_{A}^{n}(i, k)\geq-1$ のもとで,$V_{A}^{n+1}(i+1, k)-V_{A}n+1(i, k)\geq-1$ か-\supset $W_{A}^{n+1}(i+1, k)-W_{A}n+1(i, k)\geq-1$ をつぎに示す.

.

$0\leq i\leq N-2$ の時,$W_{A}^{n+1}(i+1, k)-W_{A}n+1(i, k)$$= \frac{1}{\Lambda}[\lambda_{k}(V_{A}n(i+2, k)-V_{A(i}^{n}+1,$$k))+\mu(V_{A}^{n}(i, k)-V_{A(i}^{n}$–1, ))$k$$+ \sum_{l=0}\gamma k\iota(V^{n}A(i+1, \iota)-V^{n}A(i, l))+(\lambda-\lambda k)(V^{n}A(i+1, k)-V_{A}n(i, k))]$$\geq\frac{1}{\Lambda}[-\lambda_{k}-\mu-\sum^{s}\gamma k\iota-(\lambda-\lambda_{k})]l=0$$= \frac{1}{\Lambda}[-\Lambda+\alpha]\geq-1$.

38.

$i=N-1$ の時$W_{A}^{n+1}(N, k)-W_{A}^{n+}1(N - 1, k)$$= \frac{1}{\Lambda}[\lambda_{k}(V^{n}A(N, k)-VAn(N, k)-1)+\mu(V_{A}^{n}(N-1, k)-V_{A(N}^{n}$–2, ))$k$$+ \sum_{0l=}\gamma k\iota(V_{A}n(N, l)-V_{A}^{n}(N-1, l))+(.\lambda-\lambda k).(V^{n}A(N, k)-VA(N-1, k)n)]$$\geq\frac{1}{\Lambda}[-\lambda_{k}-\mu-\sum_{=l0}^{s}\gamma_{kl}-(\lambda-\lambda_{k})]$$= \frac{1}{\Lambda}[-\Lambda+\alpha]\geq-1$.

$V_{A}^{n+1}(i+1, k)-V_{A}n+1(i, k)\geq-1$$1,$$k)-W_{A}^{n}(i, k)\geq-1$

は $n=1$ の時と同様に示すことができる.と $V_{A}^{n}(i+1, k)-V^{n}A(i, k)\geq-1$ が示され, $W_{A}(i+1, k)-WA(i, k)\geq-1$

かつ砺 $(i+1, k)-V_{A(}i,$ $k)\geq-1$ となる.

.

3. の証明 まず $n=1$ の時$0\leq i\underline{<}N-1$の場合,$W_{A}^{1}(i, k+1)-W_{A}^{1}(i, k)$$= \frac{1}{\Lambda}[\lambda_{k+1}(V_{A(+k+1}^{00}i1,)+1)-\lambda k(V_{A}(i+1, k)+1)$$+\mu(V_{A(i-}^{0}1, k+1)-V_{A}^{0}(i-1, k))$$+ \sum_{0l=}^{l}\gamma_{k+}1lV^{00_{(i}}A(i, \iota)-\sum l=s0\gamma klVA,$$\iota)$$+(\lambda-\lambda_{k}+1)VA(0i, k+1)-(\lambda-\lambda_{k})V_{A}0(i, k)]$.

$= \frac{1}{\Lambda}(\lambda_{k1}+-\lambda k)\leq 0$.

$i=N$ の場合,
$W_{A}^{1}(N, k+1)-W_{A}^{1}(N, k)$$= \frac{1}{\Lambda}[\lambda_{k+1A}V0(N, k+1)-\lambda_{k}VA(0N, k)$$+\mu(V_{A}^{0}(N-1, k+1)-V_{A}^{0}(N-1, k))$$+ \sum_{0l=}^{S}\gamma_{k}+1\iota V^{00}A(N, l)-\sum_{l=0}’\gamma_{k}\iota VA(N, l)$$+(\lambda-\lambda_{k}1)+V_{A()-}0N,$$k+1(\lambda-\lambda k)VA(0N, k))]$$=0$.

$V_{A}^{1}(i, k)$

よって $W_{A}^{n}(i+$.

に対して, 次の 2 つの場合を考える.

$W_{A}^{1}(i, k+1)<M_{A}^{1}(i)$のとき,

39.

$V_{A}^{1}(i, k+1)-V_{A}^{1}(i, k)\leq M_{A}^{1}(i)rightarrow M_{A}^{1}(i)=0$$W_{A}^{1}(i, k+1)\geq M_{A}^{1}(i)$.のとき,$V_{A}^{1}(i, k+1)-V_{A}^{1}(i, k)\leq W_{A}^{1}(i, k+1)-W_{A}^{1}(i, k)\leq 0$.

次に帰納法の仮定 $V_{A}^{n}(i, k+1)-V_{A}^{n}(i, k)\leq 0$ かつ $W_{A}^{n}(i, k+1)-W_{A}^{n}(i, k)\leq 0$ を用いて

.

を示す.

$V_{A}^{n+1}(i, k+1)-Vn+1(Ai, k)\leq 0$ かつ $W_{A}^{n+1}(i, k+1)-Wn+1(Ai, k)\leq 0$$0\leq i\leq N-1$の場合,$W_{A}^{n+1}(i, k+1)-W_{A}^{n+1}(i, k)$$= \frac{1}{\Lambda}[\lambda_{k+1}(V_{A}n(i+1, k+1)+1)-\lambda k(V_{A}n(i+1, k)+1)$$+\mu(V_{A}^{n}(i-1, k+1)-V_{A}^{n}(i-1, k))$$+ \sum_{l=0}^{l}\gamma k+1\iota VAn(i, l)-\sum_{l=0}\gamma_{k}lV^{n}A(i, l))s$$+(\lambda-\lambda_{k}+1)V_{A}n(i, k+1)-(\lambda-\lambda k)VA(ni, k)]$$\leq\frac{1}{\Lambda}[\lambda_{k+1}(V_{A}n(i+1, k+1)+1)-\lambda k(V_{A}n(i+1, k)+1)$$–$$+(\lambda-\lambda_{k+}1)V_{A}n(i, k+1)--(\lambda-\lambda_{k})V_{A}n(i, k)]$. .

($\mathrm{B}\mathrm{y}$

補題

$1$

,

$\sum\gamma_{k+}1\iota V_{A}^{n}(i,$ $l)$$- \sum\gamma klV_{A}^{n}(i,$ $l)$$\leq$

$0$.)

$l=0$

$l=0$

$\leq\frac{1}{\Lambda}[\lambda_{k+1}(V_{A}n(i+1, k+1)+1)-\lambda_{k}(V_{A}^{n}(i+1, k+1)+1)$$+(\lambda-\lambda_{k+}1)V_{A}n(i, k+1)-(\lambda-\lambda_{k})V_{A}n(i, k+1)]$..

$k+11)$$= \frac{1}{\Lambda}(\lambda_{k+1}-\lambda_{k})(V_{A}^{n}(i+1, k+1)-V_{A()+}^{n}i,$$\leq 0$$V_{A}^{n+1}$$1)$$(i, k+1)-V_{A}^{n+1}(i, k)\leq 0$$-W_{A}^{n}(i, k)\leq 0$

は $n=1$ の時と同様に示すことができる. よって垣](i, $k+$から $W_{A}(i, k+1)-W_{A}(i, k)\leq 0$ となる.

4. の証明$W_{A}(i, k) \geq\frac{1}{\Lambda}[\lambda_{k}M_{A}(i)+\mu M_{A}(i-1)+(\Gamma+\lambda-\lambda_{k})M_{A}(i)]$$= \frac{1}{\Lambda}[(\lambda+\mu+\Gamma)(-i+hV_{A}(0, \mathrm{o}))+\mu]$$=-i+hV( \mathrm{O}, 0)+\frac{1}{\Lambda}[-\alpha(-i+hV(\mathrm{O}, 0))+\mu]$$\geq M_{A}(i)+\frac{1}{\Lambda}[-\alpha(-i+h\lambda_{0}/\alpha)+\mu]$$\geq M_{A}(i)+\frac{1}{\Lambda}[-\lambda_{0}+\mu]$$\geq M_{A}(i)$

.

.

40

これらの結果から最適政策の構造について次の定理を得る.
定理 1 Model A の最適政策の構造

1. $D_{A}(i, k)$ は$k$に関して非増加,

2. $D_{A}(i, k)$ は i\uparrow こ関して非減少,

3. もし
Model

$\mathrm{B}$ならば $i>0$ に対し $D_{A}(i, k)=2$$\mu>\lambda_{0}$の利得関数についても同様に次のような性質を証明することができる. (証明は略す)

補題 3

1. $V_{B}(i, k)\leq\mu/\alpha$ ,2. $W_{B}(i, k)$ は$i$

3. $W_{B}(i, k)$ は$k$に関して非減少,に関して非増加,

4. $i\geq 1$ に対し $W_{B}(i, k)\geq M_{B}$ .
これらの結果から最適政策の構造について次の定理を得る.
定理 2 Model$\mathrm{B}$の最適政策の構造

1. $D_{B}(0, k)$ は$k$に関して非増加,

2. $i\geq 1$ に対し $D(i, k)=2$ .
参考文献[1] Hajek, B., “Optimal control of two interacting service stations”, IEEE Transactions on

Automatic Control $\mathrm{A}\mathrm{C}-29(1984)491-499$ .
[2] Rosberg, Z., Varaiya, P.P., and Walrand,. “Optimal control of service in tandemqueues”, IEEE Transactions on Automatic Control.
$\mathrm{J}.\mathrm{C}$$\mathrm{A}\mathrm{C}^{-}27(1982)6\mathrm{o}\mathrm{o}-609$[3] Serfozo, R., “An equivalence between discrete and continuous time Markov decision processes”, Operations Research 27 $(1979)616-620$ .
[4] Stoyan, D., Comparison methods for queues and other stochastic models, John Wiley &Sons. (1983).
[5] Wessels, J., “Markov programming by successive approximations with respect to weighted
supremum norms”, Journal of Mathematical Analysis and Applications 58 $(1977)326-335$ .