数理解析研究所講究録 1457 巻 2005 年 194-199

194

離散時間待ち行列におけるスマート客問題
鳥取大学工学部

1

小柳(KOYANAGI Junji),淳二

河合一(KAWAI Hajime)

はじめに

本研究では, 待ち行列システムに到着した, 特殊な客 (スマート客) がスマート客のみが利用できる待機場所を持つ場合, 高い待ちコストを支払って待ち行列に並ぶか, 安い待機コストを支払って待機場所で待つかを選択できるモデルを扱う. スマート客はただ一人のみがシステム内に存在できるものとし、 複数のスマート客は存在しないものとする。 スマート客は待機場所で常時行列を観測でき, 待機終了後に行列に並ぶときには, 待機終了時点の待ち行列の最後尾に並ぶことができる. 例えば, 行列に並ぶとタバコが吸えない場合,タバコを吸いたい人は行列に並ぶ前に喫煙場所でタバコを吸って待つことができる. 行列に並ぶよりタバコを吸っていたほうが待ち行列に並ぶよりイライラせずにすむが, 吸っている間に来た他の客に先を越されてしまうリスクがあるような状況である.
このようなモデルは Mandelbaum and Yechiali [1] が $M/G/1$ 待ち行列システムにおいて 「スマート客」 (smart customer) の最適政策として定式化したものがある. そこで扱われたモデル (以後 Modelと表す) ではスマート客は行列到着時に 3 つの選択肢を持つ.
$\mathrm{S}$Al. 行列に並ぶ.
A2. 待機場所で待機し, 現在サービス中の客が退去するのを待つ.
A3. 並ばずに立ち去る.

A2 を選択した場合, サービス中の客が退去したとき再び行列長を観測し, 観測後 3 つの選択肢のいずれかをとる.

それぞれのアクションをとった場合のコストは(1) 行列に並んだ場合, サービス終了までの系内時間に比例したコストを仮定する, すなわち系
内人数 の時に $i+1$ 番目の客として並んだとき期待コスト $c(i+1)$ とする,
(2) 待機場所で待機した場合コスト を支払う.
を支払う(3) 並ばずに立ち去った場合コスト
$i$

$b$

$d$

Model
Model

$\mathrm{S}$における最適政策は次のような構造を持つことが示されている.の最適政策の構造があり, 系内人数閾値$\mathrm{S}$$s_{1},$$s_{2}$$i$が(1) $0\leq i<s_{1}$ であれば, 行列に並ぶ.
(2)$s_{1}\leq i<\mathit{8}2$(3)$s_{2}\leq i$であれば, 待機場所で待つ.

であれば, 立ち去る.

本研究では, 離散時間待ち行列モデルにおける上記のような問題を考え, 待機場所での待機時闇として扱う.

1 単位時間待機する、 2 単位時間待機するの 2 種類のいずれかを選択できる場合を取り

195
2

モアル

まず, 立ち去るというアクションがない場合を考える. すなわち、 行列に並ぶ、 1 単位時聞待機する、 2 単位時間待機するの 3 つのアクションから選択する場合である。

サーバーが一つの離散時間待ち行列システムを考え, 1 単位時間ごとにサービス中の客は の確の確率で到着するものとする. 簡単のため $\overline{p}=1-p,$ $\overline{q}=1-q$ ,率で退去し, 直後に新たな客が$q$$p$$r=pq+\overline{pq}$($p\overline{q}$十$r$

十$\overline{p}q=1$) とする. この待ち行列システムに特別な客 (スマート客) が一人だ

け到着したとき, その客は待ち行列で並んで待つか, 待ち行列外の待機場所で 1 単位時間か,2単位時間過ごして再び待ち行列に戻るかを選択できる.
コストとして(1) 待ち行列内で過ごすと 1 単位時間あたり のコストがかかる.のコスト, 2 単位時間待機場所で過ごす (中断はできな(2) 1 単位時問待機場所で過ごすと$c$$b_{1}$い)とのコストがかかる.

$b_{2}$という状況を考える。
また, それぞれのアクションが意味を持つために(1) $b_{1}<c$ (待機場所で待つより待ち行列で待つほうがコスト大きい),(2) $b_{2}<2b_{1}$ ($2$

単位時間待機 1 回より,1 単位時間待機を 2 回のほうがコスト大きい)とする.

3

定式化$i=0$ では行列に入るのが明らかに最適であるので,状態として系内人数$i$

以後 $i\geq 1$ の場合を扱う.

を用いて, 次の関数を定義する.

$V(i)$: 系内人数が$i$の時点からの最適コスト$B_{k}(i)$: 系内人数が$i$の時点から$W_{k}(i)$: 系内人数が$i$の時,$k$$k$

単位時間待機を選択した以降の最適コスト $(k=1,2)$

単位時問待機時問が残っている状態からの最適コスト $(k=0,1,2)$

定義より( 十 ) $/q,$ $B_{1}(i),$ $B_{2}(i)\}$$V(i)$$=$$\min\{c$$B_{k}(i)$$=$$b_{k}+W_{k}(i)$$W_{k}(i)$$=$$p\overline{q}W_{k-1}(i+1)+rW_{k-1}(i)+\overline{p}qW_{k-1}(i-1)$$W_{0}(i)$$=$$V(i)$$i$$1$$(k=1,2)$$(k=1,2)$が成り立つ.
最適政策が, 系内人数が増加するにつれて,並ぶ\rightarrow 1 単位時間待機\rightarrow 2 単位時間待機のように単調に変化する (1 単位時間待機が最適になる領域は存在しないこともある.) 性質があることを以下のように証明する

196(1) 定理 1 で系内人数が増加するにつれ、 並ぶが最適なアクションから 1 単位時問待機か、 2単位時間待機のいずれかに変化し、 再び並ぶに戻ることはないことを示す。
(2) 定理 2で、 ある系内人三で 1 単位時間待機が最適なアクションであるとき、 $i+1$ では 2$i$単位時間待機が最適であることを示す。
(3) 定理 3 で、 ある町内人数で 2 単位時間待機が最適なアクションであるとき、 $i+1$ では 2$i$

単位時間待機が最適であることを示す。
定理 1 の証明に必要な補題をまず示す。

補題 1$i\geq 1$に対して以下の不等式が成立する.
$B_{k}(i+1)-B_{k}(i\rangle\leq c/q (k=1,2)$

口

証明$V^{0}(i)=0,$ $(i\geq 0)$とおいて, 以下の逐次近似法を実行する.

$W_{0}^{n}(i)$$=$$V^{n}(i)$$W_{k}^{n}(i)$$=$$p\overline{q}W_{k-1}^{n}(i+1)+rW_{k-1}^{n}(i)+\overline{p}qW_{k-1}^{n}(i-1)$$B_{k}^{n}(i)$$=$$b_{k}+W_{k}^{n}(i)$$V^{n+1}(i)$$=$$\min\{c(i+1)/q, B_{1}^{n}(i), B_{2}^{n}(i)\}$$(k=1,2)$$(k=1,2)$

各 $n$ に対して $V^{n}(i+1)-V^{n}(i)\leq c/q,$ $W_{k}^{n}(i+1)-W_{k}^{n}(i)\leq c/q,$ $B_{k}^{n}(i+1)-B_{k}^{n}(i)\leq c/q$ は帰納法で示すことができる.

$\lim_{narrow\infty}B_{k}^{n}(i)=B_{k}(i)$であるから補題が示される.

口

補題より次の定理を示すことができる.
定理 1
系内人数

$i$で行列に加わらないのが最適であれば,$i$で行列に加わらないのが最適であるので,$j\geq i$

でも行列に加わらないのが最適である.

口証明

陣内人数

$B_{1}(i)\leq c(i+1)/q$ か $B_{2}(i)\leq c(i+1)/q$のいずれかが成立する.
$B_{1}(j)\leq B_{1}(i)$ここで補題より

十 $c(j-i)/q\leq c(j+1)/q$ か $B(j)\leq B_{1}(i)$ 十 $c(j-i)/q\leq c(j+1)/q$のいずれかが成立するため,$j$

でも行列に加わらないが最適となる.

定理 2 の証明に必要な補題を次に示す.

補題 2$i\geq 1$に対して Wl0)\leq bl+W2(のが成立する.

口口

187
証明

最適性方程式より$W_{1}(i)$(の $+\overline{p}qV(i-1)$$=$$p\overline{q}V(i+1)+rV$$\leq$$p\overline{q}(b_{1}+W_{1}(i+1))$ 十 $r(b_{1}+W_{1}(i))+\overline{p}q(b_{1}+W_{1}(i-1))$$=$$b_{1}+W_{\mathit{2}}(i)$. 口

補題 2 を用いて次の定理 2 を示す.
定理 2

ある人数

$i$

で 1 単位時間待機が最適であれば,$i+1$ では 2 単位時間待機が最適である.

口

証明
$i$

で 1 単位時間待機が最適であれば, $i+1,$ $i+2$間待機のいずれかが最適となる.
ことを示す.

$i,$では定理 1 より,1 単位時間待機か 2 単位時$i+1$ で 1 単位時間待機が最適ならば条件 $2b_{1}>b_{2}$ に反する

(1) $i+2$ においても 1 単位時間待機が最適とすると$B_{1}(i+1)$$=$$b_{1}+p\overline{q}V(i+2)+rV(i+1)+\overline{p}qV(i)$$=$$b_{1}+p\overline{q}(b_{1}+W_{1}(i+2))$ 十 $r(b_{1}+W_{1}(i+1))+\overline{p}q(b_{1}+W_{1}(i))$$=$$2b_{1}+p\overline{q}W_{1}(i+2)$(1)

十 $rW_{1}(i+1)+\overline{p}qW_{1}(i)$が成立する. また(2)$B_{2}(i+1)=b_{2}+p\overline{q}W_{1}(i+2)+rW_{1}(i+1)+\overline{p}qW_{1}(i)$1 単位時間待機が最適であることから $B_{1}(i+1)\leq B_{2}(i+1)$ すなが成り立たなければならない. これは条件に反する.

であるから, $i+1$ では
わち $2b_{1}\leq b_{2}$(2) $i+2$ において 2 単位町彫待機が最適とすると$B_{1}(i+1)$$=$$b_{1}+p\overline{q}V(i+2)+rV(i+1)+\overline{p}qV(i)$$=$$b_{1}+p\overline{q}(b_{2}+W_{2}(i+2))+r(b_{1}+W_{1}(i+1))+\overline{p}q(b_{1}+W_{1}(i))$$=$$(1+r+\overline{p}q)b_{1}+p\overline{q}b_{2}+p\overline{q}\nu V_{1}(i+2)+rW_{1}(i+1)+\overline{p}qW_{1}(i)$(3)

また補題 2 を用いて
$B_{2}(i+1)$が成立する.

$B_{1}\langle i+1$

$B_{1}(i+1)$$=$$\leq$$=$$b_{2}+p\overline{q}W_{1}(i+2)+rW_{1}(i+1)+\overline{p}qW_{1}(i)$$\leq$$b_{2}+p\overline{q}(b_{1}+W_{2}(i+2))+rW_{1}(i+1)+\overline{p}qW_{1}(i)$(4)) $\leq B_{2}(i+1)$ より$(1+r+\overline{p}q)b_{1}+p\overline{q}b_{2}+p\overline{q}W_{1}(i+2)+rW_{1}(i+1)+\overline{p}qW_{1}(i)$$B_{2}(i+1)\leq b_{2}+p\overline{q}(b_{1}+W_{2}(i+2))+rW_{1}(i+1)+\overline{p}qW_{1}$(の198であるから$(1+r+\overline{p}q)b_{1}+p\overline{q}b_{2}$$\leq$$b_{2}+p\overline{q}b_{1}$$(1+r+\overline{p}q-p\overline{q})b_{1}$$\leq$$(1-p\overline{q})b_{2}$$(1+1-p\overline{q}-p\overline{q})b_{1}$$\leq$$(1-p\overline{q})b_{2}$$2b_{1}\leq b_{2}$となり, 条件に反する.
よって,$i,$$i+1$ で最適アクションがともに 1 単位時間待機となることはない.

アクションが次に$i$

すなわち$i$で最適

1 単位時間待機であれば $i+1$ では 2 単位時間待機が最適アクションとなる.

で 2 単位時間待機が最適であれば,

口$i+1$ でも 2 単位時間待機が最適であることを定理3 で示す.
定理 3で 2 単位時間待機が最適であれば,$i$$i+1$ でも 2 単位時間待機が最適である.

口

証明
$i$

で 2 単位時間待機が最適であり,$i+1$ では 1 単位時間待機が最適であるとすると,$i+2$ では 2 単位時開待機が最適である.
$B_{1}(i+1)$

定理 2 より

よって$=$$b_{1}+p\overline{q}V(i+2)+rV(i+1)+\overline{p}qV(i)$$=$$b_{1}+p\overline{q}(b_{2}+W_{2}(i+2))+r(b_{1}+W_{1}(i+1))+\overline{p}q(b_{2}+W_{2}(i))$$=$$(1 +r)b_{1}+(p\overline{q}+\overline{p}q)b_{2}+p\overline{q}W_{2}(i+2)$

十 $rW_{1}(i+1)+\overline{p}qW_{2}(i)$(5)

また, 補題 2 を用いて
$B_{2}(i+1)$$B_{1}(i+1)\leq B_{2}(i+1)$となり, 条件に反する.

$=$$b_{2}+p\overline{q}W_{1}(i+2)+rW_{1}(i+1)+\overline{p}qW_{1}(i)$$\leq$$b_{2}+p\overline{q}(b_{1}+W_{2}(i+2))$ 十 $rW_{1}$( 十 1) $+\overline{p}q(b_{1}+W_{2}(i))$
$i$

(6)

より

$(1+r)b_{1}+(p\overline{q}+\overline{p}q)b_{2}$$\leq$$b_{2}+p\overline{q}b_{1}+\overline{p}qb_{1}$$(1+r-p\overline{q}-\overline{p}q)b_{1}$$\leq$$(1-p\overline{q}-\overline{p}q)b_{2}$$2rb_{1}$$\leq$$rb_{2}$$2b_{1}$$\leq$$b_{2}$

よって$i$で 2 単位時間待機が最適であれば $i+1$ で 1 単位時間待機が最適になることはない. すなわち, 2 単位時間待機がいったん最適となるとクションの変化は生じない. 口$i$の増加に伴う最適ア1884結論
本研究では, 行列到着時に行列の外で安いコストで待つことのできる特別な客を想定し, その最適政策について考えた. 待ち行列外で待つ場合, 1 期間待つか,のとし, その最適政策の性質として次のことを導き出した.

2 期間待つかを選択できるも(1) 最適アクションは, 行列に並ぶから, 1 単位時間待機, 2 単位時間待機へと系内人数が増加するにつれて変化する.
(2) 1 単位時間待機が最適アクションとなる系内人数は, あったとしても, ある特定の人数の場合のみである.

参考文献[1] A. Mandelbaum and U. Yechiali, Optimal entering rules for a customer with wait option
at an $M/G/1$ queue, Management Science, 29-2, 174-187 (1983)[2] R. Hassin and M. Haviv To queue or not to queue, Kuluwer Academic Publishers, London(2003).