$\mathrm{d}\mathrm{p}$ (Katsuhisa $\mathrm{o}\mathrm{m}\mathrm{o}$) Aichi Institute of Technology (Takahiro Ito) Nagoya Institute of Te

Size: px

Start display at page:

Download "$\mathrm{d}\mathrm{p}$ (Katsuhisa $\mathrm{o}\mathrm{m}\mathrm{o}$) Aichi Institute of Technology (Takahiro Ito) Nagoya Institute of Te"

ありあいざわ
5 years ago
Views:

383: 64-7 Issue Date 24-7 URL http://hdlhandlenet/2433/2575

1 Title ニューロ DP による多品目在庫管理の最適化 ( 不確実で動的なシステムへの最適化理論とその展開 ) Author(s) 大野勝久 ; 伊藤崇博 ; 石垣智徳 ; 渡辺誠 Citation 数理解析研究所講究録 (24) 383: 64-7 Issue Date 24-7 URL Right Type Departmental Bulletin Paper Textversion publisher Kyoto University

2 $\mathrm{d}\mathrm{p}$ (Katsuhisa $\mathrm{o}\mathrm{m}\mathrm{o}$) Aichi Institute of Technology (Takahiro Ito) Nagoya Institute of Technology (Tomonori Ishigaki) Osaka Prefecture University NTT (Makoto Watanabe) NTT DoCoMo Tokai 93 FWHarris Omo et a[3] (EOQ) 3 (UMDP) 4 $\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{f}_{}\mathrm{e}\mathrm{d}$ SCM ( Policy Iteration Meffiod MPIM) [2-4] 7 2 SBMPIM [5] 5 SMART $\mathrm{l}\mathrm{a}\mathrm{x}\mathrm{e}\mathrm{d}-\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{t}$ SBPI 6 ( DP ) 2 SBMPIM (MDP) Bellman 95 SMART $\mathrm{l}\mathrm{a}\mathrm{x}\mathrm{e}\mathrm{d}-\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{t}$ SBPI (Policy Iteration Method Omo et a[3 PIM) Howard[l] Puterman[2] Omo et a[3 2 PIM MDP DP $N$ [4] (Reinforcement $\mathrm{x}=$ $(x_{}x2 \cdots x_{n})^{t}$ Leaming)[5] (NeurO-Dynamic $x_{n}\in \mathrm{z}=\{\pm \pm 2\cdots\}(n\in \mathrm{n}=\{2\cdotsn\})$ Programming $\mathrm{d}\mathrm{p}$)[$67$ $T$ Johnson[6] $\mathrm{d}\mathrm{p}$ MDP f $(y_{}y2 \cdotsy_{n})^{t}\in \mathrm{z}^{n}$ $\mathrm{y}=$ Das et a[8] Gosavi[9] MDP $K$(Xy) (SMDP) $\mathrm{d}=$ $(D_{}D2 \cdotsd_{n})^{t}$ SMART $D_{n}\in \mathrm{z}_{+}=\{2\cdots\}$ $(n\in \mathrm{n})$ RELAXED-SMART $\mathrm{d}$ $\phi(\mathrm{y}\mathrm{d})$ He et a[] PIM SBPI $l(\mathrm{y}\mathrm{d})$ $L(\mathrm{y})$ $\mathrm{t}\mathrm{d}$ Gosavi et al[] SMART (Temporal Differnce) $\lambda$-smart

3 $\mathrm{x}\mathrm{y}\mathrm{z}\in \mathrm{x}$ $\mathrm{c}$ $\mathrm{x}\leq \mathrm{y}$ (x $\mathrm{o}\sum_{\mathrm{e}\mathrm{b}}\phi(\mathrm{x}\mathrm{d})=$ i) \mathrm{n}}a_{n}x_{n}^{+}\leq\overline{\mathrm{m}}\}$ \mathrm{n}}a_{n}x_{n}\leq\overline{\mathrm{m}}\}$ $\overline{\mathrm{m}}$ $\mathrm{i}\mathrm{i}\mathrm{i})$ $v(\mathrm{x})=k$(x \mathrm{t}$ 95 $L( \mathrm{y})=\sum_{\mathrm{d}\geq }\phi(\mathrm{y}\mathrm{d})l(\mathrm{y}\mathrm{d})$ $\mathrm{y}\in \mathrm{z}^{n}$ ) 4 ($x_{n}\leq y_{n}$ $(n\in \mathrm{n})$ $\mathrm{x}<\mathrm{y}$ \mathrm{y}$ $\mathrm{x}\leq $\mathrm{x}\neq \mathrm{y}$ $u(\mathrm{y}\mathrm{d})$ $=\mathrm{y}-\mathrm{d}$ $u_{b}$ (y $\mathrm{d}$) 3 UMDP $=([\gamma_{}-d_{}\mathrm{r}[\gamma_{2}-d_{2\mathrm{f}}\cdot\triangleright_{n} -D_{N}]+)^{T}$ $u_{l}$ (y $\mathrm{d}$) : $\int y_{n}-d_{n}\mathrm{r}=\max\{y_{n}-d_{n}\}$ $(n\in \mathrm{n})$ ( (B) $)$ (L) $\mathrm{x}_{b}=\{\mathrm{x}\in \mathrm{z}^{n}$ ; $\sum_{n\epsilon g(x)+u(x)=y?\sim }){K(x $\mathrm{d})$)$\}$ $\mathrm{y}$) $+L( \mathrm{y})+\sum_{\mathrm{d}\epsilon \mathrm{b}}\phi(\mathrm{y}\mathrm{d})$v(u(y $g( \mathrm{x})=\min_{\mathrm{y}\epsilon \mathrm{y}}\{\sum_{\mathrm{y}\in \mathrm{y}}\phi(\mathrm{y}\mathrm{d})g(u(\mathrm{y}\mathrm{d}))\}$ (2) () $\mathrm{y}=\{\mathrm{y}\in \mathrm{x};\mathrm{y}\geq \mathrm{x}\}$ $\mathrm{x}_{l}=\{\mathrm{x}\in \mathrm{z}_{+}^{n}$ ; $\sum_{n\epsilon $\mathrm{y}(\mathrm{x})=\{\mathrm{y}\in \mathrm{y}:g(\mathrm{x})=\sum_{\mathrm{d}\mathrm{e}\mathrm{b}}\phi\langle \mathrm{y}\mathrm{d})g(u(\mathrm{y}\mathrm{d}))\}$ $a_{n}$ $n$ $g(\mathrm{x})$ $o(\mathrm{x})$ $x_{n}^{+}= \max\{x_{n}\}$ $n\in \mathrm{n}$ $X_{B}$ X $X$ $\mathrm{x}<\mathrm{y}<\mathrm{z}$ $\sigma$ $f$ $\sigma$ $s(\cdot)$ $f=(\sigmas())$ $<K$(x $+K$(yz) $=$ $\sigma$ $K$(x $\mathrm{z}$) $\mathrm{y}$) $K$ (x ) 2 $S(\mathrm{x})$ $L(\mathrm{x})=\infty$ $\mathrm{x}\in\sigma$ l $\mathrm{x}arrow-\infty$ $\mathrm{x}\in \mathrm{x}$ $M$ $\mathrm{x}\not\geq \mathrm{z}_{m}$ $\mathrm{x}\in\sigma^{c}\equiv \mathrm{x}-\sigma$ $L(\mathrm{x})>M$ $\sigma^{c}$ $\mathrm{z}_{7}\in \mathrm{x}$ $\sigma$ 3 $\mathrm{x}\in \mathrm{x}$ $(\sigmas())$ $\sigma^{c}\subset(\sigma^{}f=\{\mathrm{x}\in \mathrm{x};\mathrm{x}\geq \mathrm{z}_{g^{}}\}$ (3) $\mathrm{b}\subset \mathrm{z}_{+}^{n}$ 4 $x_{n}=$ 2 $M$ $\mathrm{z}_{\mathrm{g}^{}}$ $\mathrm{x}\in \mathrm{x}$ $n\in \mathrm{n}$ $g^{}$ $x_{n}>u_{n}$ (XD) Johnson[6] $K>$ $K(\mathrm{x}\mathrm{y})=K\delta(\mathrm{y}-\mathrm{x})+\mathrm{c}\cdot(\mathrm{y}-\mathrm{x})$ $\delta()=$ $\mathrm{x}>$ $\delta(\mathrm{x})=$ $g^{}= \min_{\mathrm{y}\epsilon \mathrm{x}}\{l(\mathrm{y})+\sum_{\mathrm{d}\in \mathrm{b}}\phi(\mathrm{y}\mathrm{d})k$(u(y $\mathrm{d}\lambda \mathrm{y}$ )} $\mathrm{i}\mathrm{i})$ $S(\mathrm{x})\in\sigma^{c}$ $\mathrm{x}\in\sigma $N$ 2 3 $X$ $S(\mathrm{x})$) $+o(s(\mathrm{x}))$ $\mathrm{x}\in\sigma$ $(4)$ (5)

4 $\mathrm{x}\in \mathrm{x}^{}$ $\mathrm{x}\in \mathrm{x}^{}$ $\mathrm{x}\in \mathrm{x}^{}$ $\mathrm{x}\in \mathrm{x}_{v}$ $\mathrm{x}_{}$ $\mathrm{x}\in \mathrm{x}^{}$ 88 $\mathrm{x}^{}$ $(\sigma^{})^{\rho} \cup\{u(\mathrm{x}\mathrm{d})$ for all $\mathrm{x}\in(\sigma^{}) $ $\mathrm{d}\in \mathrm{b}\}$ $l=\cdots m-$ $w^{/+}(\mathrm{x})=r(\mathrm{x}f^{k+}(\mathrm{x}))$ $+ \sum_{\mathrm{d}\in \mathrm{b}}\phi(\mathrm{x}\mathrm{d})w^{l}(\mathrm{x} )$ $\mathrm{x}^{}$ $N^{}$ $\mathrm{x}^{}$ $\mathrm{x}^{}$ $ v^{k+}(\mathrm{x})-o^{k}(\mathrm{x}) <\epsilon$ $f^{k+}$ (X) $\mathrm{x}^{}$ $g^{k+}$ $v^{k+}$ (xr) (X) $\mathrm{x}\not\in \mathrm{x}^{}$ $S(\mathrm{x})$ $k=k+$ 2^ (5) 2 MPIM MDP $\mathrm{d}\mathrm{p}$ $\mathrm{x}^{}$ $g(\mathrm{x})$ \mathrm{x}$ 2 $\mathrm{x}\in MPIM $\mathrm{x}^{}$ $g(\mathrm{x})=g$ () (2) $v(\mathrm{x})$ $\mathrm{x}_{\nu}$ (6) DP SBMPIM ( Simulation-Based Modified Policy Iteration Method) [5] [SBMPIM][5] $\mathrm{d}\mathrm{p}$ 4 $\mathrm{x}^{\mathrm{s}}$ : $\mathrm{x}_{}$ (6) PIM $m$ $\lambda(\leq\lambda\leq )$ MPIM (value iteration method) $\mathrm{x}_{v}=\mathrm{x}_{t}=\phi$ ( (linear programming) [2 2-4] ) $TC=$ $\mathrm{x}=\mathrm{x}_{}$ $k=l=$ $\mathrm{x}_{v}=\mathrm{x}_{v}\cup\{\mathrm{x}\}\mathrm{r}$ $r(\mathrm{x}\mathrm{y})=k(\mathrm{x}\mathrm{y})+l(\mathrm{y})$ 2; $\mathrm{x}\not\in \mathrm{x}_{v}$ $g+v( \mathrm{x})=\min_{\mathrm{y}\epsilon \mathrm{y}}\{k$(x $\mathrm{y}$) $+L( \mathrm{y})+\sum_{\mathrm{d}\mathrm{e}\mathrm{b}}\phi(\mathrm{x}\mathrm{d})u(u(\mathrm{x}\mathrm{d}))$} $\text{}$ [MPIM] [4] $\mathrm{x} =u(\mathrm{y}\mathrm{d})$ $u^{}$ : $u_{}(s_{r})=$ $v(\mathrm{x})=$ $f^{}$ $\epsilon$ $m_{\mathrm{f}}$ $k=$ $\langle$ 2:( ) $\mathrm{x}\in \mathrm{x}^{}$ $v^{k+}(\mathrm{x})=w^{m}(\mathrm{x})-w^{m}$ (xr) $\mathrm{x}_{t}=\mathrm{x}_{\mathit{}}\cdot\cup\{\mathrm{x}\}$ $v(\mathrm{x})=$ $f(\mathrm{x})$ $\mathrm{x}_{t}=\mathrm{x}_{t}\cup\{\mathrm{x}\}$ \mathrm{x}_{t}$ $\mathrm{x}^{l}$ $\mathrm{x}\not\in $\mathrm{x}\in $v(\mathrm{x})=v(\mathrm{x})+$ \mathrm{x}_{t}$ $f$(x) $\mathrm{x} $ $TC=TC+r(\mathrm{x}f(\mathrm{x}))$ $g^{k+}( \mathrm{x})=\mathrm{m}\mathrm{i}\mathrm{p}_{s})\{*\in Kr(\mathrm{x}\mathrm{y})+\sum_{\mathrm{D}\mathrm{e}\mathrm{B}}\phi(\mathrm{x}\mathrm{D})o^{k}(\mathrm{x} )-o^{k}(\mathrm{x})\}$ $l=m$ 3^ $f^{k}$ (X) (x) : $g^{k+}$ $l=l+$ 2^ $f^{k+}(\mathrm{x})=f^{k}$ (x) 3:( $g$ ) $g$ $g^{k+}$ (x) $f^{k+}$ (x) 3:( ) $w^{}(\mathrm{x})=v^{k}(\mathrm{x})+\mathrm{o}^{k+}$ (x) $\mathrm{x}=\mathrm{x} $ $g=tc/m$ $v(\mathrm{x})$ 4: ( ) $\mathrm{x}_{v}$ $\mathrm{x}_{r}$ $o(\mathrm{x}_{r})=(-\lambda v(\mathrm{x}_{r})/m\mathrm{x}w(\mathrm{x}_{r})_{-g})+(\lambda v(_{\mathrm{x}})/m\mathrm{x}r(\mathrm{x}_{r}f(\mathrm{x}_{r}))_{-g})$ $\mathrm{x}(\neq \mathrm{x}_{r})\in \mathrm{x}_{v}$

5 \mathrm{x}_{v}$ $\alpha_{}$ $\mathrm{l}\mathrm{a}\mathrm{x}\mathrm{e}\mathrm{d}-\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{t}$ 87 $U(\mathrm{x})=(-\lambda v(\mathrm{x})/m\mathrm{x}w(\mathrm{x})-g)+(\lambda o(\mathrm{x})/m\mathrm{x}^{\gamma}(\mathrm{x}f(\mathrm{x}))-g)-u(\mathrm{x}_{r})$ $\mathrm{y}^{\mathrm{t}}$ 6: 3 $o(\mathrm{x}_{r})=$ $k=$ $TC$ $g$ } $o(\mathrm{x})=r(\mathrm{x}_{r}f(\mathrm{x}_{r}))-g$ $TC=TC+r(\mathrm{x}\mathrm{x} \mathrm{y}^{\mathrm{s}})$ $T=T+$ 5:( ) $\mathrm{x}\in $g=tc/t$ $v(\mathrm{x})=r(\mathrm{x}f(\mathrm{x}))-g-v(\mathrm{x}_{r})$ 7: $Q_{old}$ $($ X (Xy) $w(\mathrm{x})=\mathrm{m}\mathrm{y}\mathrm{e}n(\mathrm{x}$f(){r(x $\mathrm{y})=q_{new}$ 8: $+ \sum_{\mathrm{d}\in \mathrm{b}}\phi(\mathrm{y}\mathrm{d})u(\mathrm{x} )\}$ $\mathrm{y}$ ) $k$ $k=k+$ $\{\}$ $2\wedge\circ$ Gosavi[9] SMART $v(\mathrm{x})=$ $N$(X $f$(x)) RELAXED-SMART $\emptyset(\mathrm{y}\mathrm{d})>$ $\mathrm{x}\not\in \mathrm{x}_{v}$ $f$(x) [ SMART $\mathrm{x}_{v}=\mathrm{x}_{v}\cup\{\mathrm{x} \}$ ( $v(\mathrm{x} )=$ $f$(x )SMDP $\mathrm{x}^{*}$ $\mathrm{m}\mathrm{d}\mathrm{p}$ [$\mathrm{l}\mathrm{a}\mathrm{x}\mathrm{e}\mathrm{d}-\mathrm{s}\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{t}$ ] $[9]$ $w(\mathrm{x} )=r(\mathrm{x} f(\mathrm{x} ))$ 3\sim 578 [SMART] $o(\mathrm{x} )=r(\mathrm{x} f(\mathrm{x} ))-r(\mathrm{x}_{r}f(\mathrm{x}))$ : $\mathrm{q}$-factor $Q_{new}$ (x $\mathrm{y}$) $=Q_{\mathit{}/d}($X $\mathrm{y})=$ $w(\mathrm{x})$ $f$(x) $w(\mathrm{x})$ $TC=$ $T=$ $g$ = $k=$ $w(\mathrm{x})$ $f$(x) $p_{}$ $\beta$ $k$ $\mathrm{x}_{t}=\phi$ $TC=\mathit{}$ =l $k=k+$ 2: $k$ $\alpha_{k}$ $p_{k}$ 2 A $\text{}$ $\alpha_{k}=a_{}/k$ $p_{m}=p_{}/m$ $\beta_{k}=\beta_{}/k$ 5 SMART SBPI MPIM SBMPIM $\mathrm{y}^{\mathrm{t}}$ 6: 3 NDP $TC$ $T$ $g$ $\mathrm{x} \mathrm{y})$ [SMART] $TC=(-\beta_{k})TC+\beta_{k }$(x [8 $\mathrm{x}\in \mathrm{x}$ : T=-\beta T+\beta k $\mathrm{a}\backslash$ $\mathrm{y}\in K$(x){ $\mathrm{q}$-factor $Q_{new}$ (x $f$) $=Q_{old}$ (x $f$) $=-$ $g=tc/t$ $TC=$ $T=$ $g=$ $\mathrm{p}\mathrm{i}\mathrm{m}$ He et a[] (learning rate) SBPI (Simulation $k=$ (exploration probability) $(\alpha_{}\alpha_{\tau}p p_{\mathrm{r}})$ [SBPI ] [ 2: $k$ $\alpha_{k}$ $\{f_{}(\mathbb{x});\mathrm{x}\in \mathrm{x}\}$ : $p_{k}$ $\alpha_{k}=\alpha_{}(\alpha_{\tau}+k)/(k^{2}+k+\alpha_{\tau})$ 2 Based Policy $\mathrm{a}$ lteration) 7/ $\langle$ $k=$ 2:( ) $p_{k}=p_{}(p_{\mathrm{r}}+k)/(k^{2}+k+p_{\tau})$ 2-a:( ) $\sim$ 3: $(-p_{k})$ $Q_{new}$ (xy) $\mathrm{x}_{}\cdots\mathrm{x}_{m}$ $\mathrm{y}^{*}$ $p_{k}$ $\mathrm{y}$ $\mathrm{i}\mathrm{i}$) $\mathrm{y}$ $K$(x) $(\mathrm{x}_{n}\mathrm{x}_{n+})$ $\mathrm{x}_{}$ i) $g^{k}=$ $n=\cdotsm$ -l $g^{k}$ $\mathrm{y}$ 4: $\mathrm{x} $ $g^{k}=(-/(n+))g^{k}+(/(n+))r(\mathrm{x}_{n}\mathrm{x}_{n+}f^{k}(\mathrm{x}_{n}))$ $r(\mathrm{x}\mathrm{x} \mathrm{y})$ 2-b:( 5: $Q_{new}$ (xy) $v^{k}($x) ) i) 2-a $Q_{new}(\mathrm{x}\mathrm{y})=(-\alpha_{k})Q_{\mathit{}/d}(\mathrm{x}\mathrm{y})$ $\mathrm{x}^{*}$ $\mathrm{x} \mathrm{y}$ $+\alpha_{k}\{$ $\mathrm{y} $)$\}$ r(x ) (X $-g+ \min_{\mathrm{y} \in K(\mathrm{x} )}Q_{old}$

6 $\mathrm{x}\in \mathrm{x}$ $ \urcorner$ $\mathrm{i}\mathrm{i})$ $\mathrm{i}\mathrm{i}\mathrm{i})$ ) (CPU - $\mathrm{g}$ $\text{}j\triangleright \mathrm{z}\mathrm{f}^{\backslash } )\text{^{}*}\text{}$ $\mathrm{g}$ $\lambda$ 68 $\mathrm{x}_{}$ 2 3 MPIM $L$ MPIM 4 $(\mathrm{x}_{}\mathrm{x}_{}\cdots\mathrm{x}_{n}=\mathrm{x})$ $\vee$ $l=\cdotsl$ ) MPIM $(\mathrm{x}_{n}\mathrm{x}_{n+})$ $w(\mathrm{x}_{l})$ $i$ $\cdot$ =l $n$ 3 MPIM $w(\mathrm{x}_{i})=w(\mathrm{x}_{j})+\gamma_{j}\lambda^{n-i}d_{n}$ $-$ $\gamma_{i}$ $s_{j}$ $\leq\lambda\leq $ $\mathrm{m}=$ =l $d_{\hslash}=r(\mathrm{x}_{n}\mathrm{x}_{n }f^{k}(\mathrm{x}_{n}))-g^{k}+w(\mathrm{x}_{n+})-w(\mathrm{x}_{n})$ SBMPIM $\mathrm{x}_{}=(2)\mathrm{x}^{*}=(89)$ =5 $\mathrm{i}\mathrm{v})v^{k}(\mathrm{x})=4^{\mathrm{x}})-w(\mathrm{x}_{r})$ \in X 3:( ) $f^{k+}( \mathrm{x})=\arg \mathrm{m}\mathrm{i}\mathrm{p}_{\mathrm{x})}\{\mathrm{y}\in\kappa r(\mathrm{x}\mathrm{y})+\sum_{\mathrm{b}\mathrm{d}\epsilon}\phi(\mathrm{y}\mathrm{d}\}_{2}^{k}(\mathrm{x} )\}$ : SMART RELAXED-SMART $\mathrm{m}$=l SBPI $\mathrm{m}=$ $\alpha_{^{=}}9$ $\mathrm{p}_{}\triangleleft-3$ $\alpha=$ $\mathrm{p}_{\tau}=-^{\zeta}--$ $\alpha ^{=}\underline{9_{-}}\mathrm{p}\mathrm{o}=3$ $\mathrm{m}=$ $\mathrm{l}$=l $\lambda=9$ 2 $\mathrm{g}$ 4: (x) $f^{k+}(\mathrm{x})=f^{k}$ $\mathrm{x}\in \mathrm{x}$ $f^{k}$ (x) $k=k$ () 2^ MPIM SBMPIM $49\pm 43$ $\iota$ 6 SMART VB (Visual Basic) $\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\underline{\mathrm{x}}\underline{\mathrm{e}}\mathrm{d}-$-smart655 4 $\mathrm{d}\mathrm{o}\mathrm{s}/\mathrm{v}$ :Pentium4 $24\mathrm{G}\mathrm{H}\mathrm{z}$ SBPI 4327 $\underline{92}$ $2\mathrm{G}\mathrm{B}$ : 6 3 MP SBMPIM 5 ;2 2 SBMPIM ;23 $\mathrm{x}_{}=(788)$ x*=(566) $i$ $D_{i}$ (i=l2) 2 2 $\phi_{j}(d_{i})$ ; 3 $\mathrm{a}()=/27$ A $()=2/9$ $\phi(2)=4/9$ $\mathrm{a}(3)=8/27$ 2 SBMPIM $\phi_{2}()=/6$ $\phi_{2}(3)=/4$ ; $\emptyset$ 2 $()=/4$ $\phi_{2}(4)=/6$ $\emptyset$ 2 $(2)=3/8$ $K(\ \mathrm{y})=5\delta(\mathrm{y}-\mathrm{x})+\delta(y_{}-x_{})+5\delta(y_{2}-x_{2})$ $+6(y_{}-x_{})+3(y_{2}-x_{2})$ ; $l(\mathrm{y}\mathrm{d})=2[y_{}-d_{}]^{+}+2[y_{2} " D_{2}]^{+}+2[D_{}-y_{}]^{+}$ 5 $ $ $\mathrm{g}$ 3 $\mathrm{f}\mathrm{a}\mathrm{i}$ () MPIM $54\overline{89}-$ 4537 SBMPIM $5494\pm 4$ 327 $+4[D_{2}-y_{2}]^{+}$ 6 2 SBMPIM 4 5 ( (B) () SBMPIM 43885) ( (C) (2) ) $\mathrm{g}$

7 $\mathrm{p}\mathrm{p}$ BaIto: $\mathrm{p}\mathrm{p}$ 88 [ R A $\mathrm{h}\mathrm{o}\mathrm{w}\pi \mathrm{d}$:dynamic Programming and Markov Processes MIT PTess (96) ( reinforcement leaming approach to a single leg 97) airline revenue management problem with multiple fare classes and overbooking [2] M L Puteman: Markov Decision Processes Transactions John Vol 34 pp (22) Wiley& Sons (994) [2] : - [3] K Ohno T lshigaki and T Yoshii: $A$ New $a$ Algorithmfor Multi-item Periodic Review Invenlory Vol 29 No 6 PP (985) ${\rm Res}$ System ZOR-Math Methods of Oper Vol 39 [3 K Ohno and K Ichiki: Computing optimal $ $ policies for controlled tandem queueing systems $\mathrm{v}\mathrm{o}\mathrm{l}$ $[4]\mathrm{S}$ Russell and P Norvig I Operations Research 35 No $\mathrm{p}\mathrm{p}2-26$ (987) 997 [4 K Ohno: Modified policy iteration algoriffim $\mathrm{g}$ [5] R S Su on and A Reinforcement with nonoptimality tests for undiscounted Markov Learning MIT Press (998) ( decision process Working Paper Dept of 2) Infomation System and Management Science [6] D P Bertsekas and J N Tsitsiklis: Konan University Japan (985) - NeurO-Dynamic Programming Athena Scientific [5] : (996) [7] R V Roy: NeurO-dynamic programming: - overview and recent ends pp in E A Feinberg and A Schwartz ed Handbook of VO 54 No 5 pp (23) Markov Decision Processes Kluwer Academic [6] E L Johnson: Optimality and Computation of Publishers (22) ($\sigmas$) Policies in the Multi-item Infinite Horizon [8 T K Das A Gosavi S Mahadevan and Nich Inventory Problem $\mathit{4}anagement$ Science 3 Marchalleck: Solving semi-markov decision $475-49(967)$ problem using average reward reinforcement [7] : leaming Management Science Vol 45 N4 pp (999) [9 A Gosavi: Doctor Thesis $\mathrm{e}\mathrm{d}\mathrm{u}/\mathrm{g}\mathrm{o}\mathrm{s}\mathrm{a}\mathrm{v}\mathrm{i}/\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{s}$ h p $://\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{y}$uscolo hbnl (999) [ Y He M C Fu and S I Marcus: A Simulation- based policy iteration algorithm for average cost unichain Markov decision processes M Laguna and J L G Velarde $\mathrm{e}\mathrm{d}$ Computing Iools for Modeling Optimization and Simulation Kluwer Academic pp6-82(2) [ A Gosavi N Bandla and T K Das: A (22) [8] : Vol 46 No 4 pp 95-2 (2)

8 $ $ $\mathrm{t}$ $2\mathrm{t} $ $ $ $[7 ]$ 7 7 [7 6

9 $\mathrm{o}\gamma \mathrm{j}\mathrm{d}$ $\mathrm{a}\text{}$ $\Re^{-}\text{}\mathrm{t}\mathrm{F})$ $\partial \mathrm{e}\mathrm{f}\mathrm{f}6$ $\partial \mathrm{g}f\grave{\mathrm{f}}6$ $\mathit{5}_{\frac{\mathrm{g}\grave{\dot{f}}_{-}^{-}}{6}}$ $\overline{6}$ $\text{}\mathrm{f}\mathrm{f}$ $\mathit{}$ fl $ ^{\prod_{}}\text{}$ MPIM SBMF SBPI $ $ (3 ) 3 36 MPIM SMART RELAXED-SMART $\mathrm{q} \mathrm{l}\mathrm{f}\not\supset \text{}\underline{}$ $4-$ $4$ $6$ $\frac{}{5}$ $$ $$ $242$ $$ $$ (3 ) 237

torsj03-18.dvi

torsj03-18.dvi Transactions of the Operations Research Society of Japan 2006 49 46-61 ( 2003 3 31 ; 2005 7 28 ) :,,,, 1. 1 Tantawi and Towsley[19] Kameda et al.[9] Li and Kameda[10] Shivaratri et al.[17] Eager et al.[5]