動的ロットサイズ決定問題

出典: ORWiki

【どうてきろっとさいずけっていもんだい (dynamic lotsizing problem)】

概要

在庫管理のモデルの一種で, 各期の需要は確定的に既知であるが必ずしも一定でない場合を考える. すなわち, 計画期間T\,中の各期t\,の需要をd_{t}\,, 製品1個あたりの発注費用をc_{t}\,, 発注量に無関係に必要な発注費用をK_{t}\,, 製品1個の1期間あたりの在庫維持費用h_{t}\,が所与のとき, 計画期間の開始時の在庫が0として, 総費用を最小化するような各期の発注量を求める問題.

詳説

　経済発注量(EOQ)モデルが「需要が既知で一定」という仮定をおいていた. これに対して, 動的ロットサイズ決定問題 (dynamic lot sizing problem)では, 需要は既知であるものの, 期によって需要量が異なることを許す. それゆえ本モデルは動的EOQとも呼ばれ, また, ワグナーとウィッティン(Wagner and Whitin)が考案したことから [1] , ワグナー・ウィッティンモデルの名で呼ばれることもある. なお, MRP計算において, 期別の正味所要量から品目ごとにロットを編成し計画オーダを作る問題は, 動的ロットサイズ決定問題にほかならない.

　ここで, 期間の長さ T\, の計画を立案することを考える. 各期 t\, の需要 d_{t}( > 0) \, が既知, 各期 t\, の製品1個当りの発注費用が c_{t}\, , 発注量に無関係に1回の発注に対する各期 t\, の発注費用が K_{t}\, , 製品1個を1期間保持するための各期 t\, の在庫保管費用が h_{t} \,, t=0 \, における初期在庫量を0とする. また, リードタイムは0すなわち発注と同時に納入され, 納入は期首にされる. 需要に対する品切れは許されない.

ここで, y_{t}\, を t\, 期の発注量, I_{t} \, を各期の期末在庫量としたときに, 総費用を最小化するような各期の発注量を決定する問題は, 以下のように定式化できる.


\begin{array}{ll} \mbox{min.} & \displaystyle{\sum_{t=1}^{T}} \biggl[ K_{t} \delta(y_{t}) + c_{t}y_{t} + h_{t} I_{t} \biggr] \\ \mbox{s. t. } & I_{t} = \displaystyle{\sum_{j=1}^{t}} (y_{j} - d_{j})\; \; \; (t=1,\ldots, T), \\ & \quad \ I_{t} \geq 0 \ \ \ (t=1,\ldots, T), \\ & \quad \quad I_{0} = 0, \\ & y_{t} \geq 0, \ \ \ (t=1,\ldots, T), \\ \end{array} \,


ただし \delta(y_{t})\, は y_{t}>0\, のとき 1 \, , さもなくば 0\, である.

　次に, 本問題の最適解を得ることを考えよう. 本問題の最適解を得る上で, 「最適な発注方策は, ゼロ在庫発注方策, すなわち


y_{t}I_{t-1}=0, \ \ \ t=1,2,\ldots,T \,


という関係を満足する」という重要な性質がある. この式が意味するところは,

  • ある期に発注を行う場合は, 前の期の期末在庫量は0である
  • ある期の期末在庫量が0のときの次の期首における発注量は, 次の期以降の連続する何期か分の需要をちょうど満足する量であるとなる.

　この性質を使い, 動的計画法によって最適解を見つけることを考える. 1 \leq i \leq j \leq T + 1\, について, l_{ij}\, を, i \, 期から, i+1,\ldots,j-1 \,期までの需要を満足するために t\, 期においてかかる費用とすれば,


l_{ij} = K + h \sum_{t=i}^{j-1}(t-i)d_{t} \,


となる. ここで, f_{i} \, を「 i \, 期以降, 最適な方策にしたがったときの費用」とすると,


f_{i} = \min_{j>i}(l_{ij} + f_{j}), \ \ \ i=1,\ldots,T \,　　　　　(1)\,


と書ける. f_{T+1}=0 \, としたとき, この再帰方程式を i=T,T-1,\ldots,1 \, と後から前に向かって計算することで, 順次 f_{i} \, が得られる.


図1：動的ロットサイズ決定問題における最短路ネットワーク

図1：動的ロットサイズ決定問題における最短路ネットワーク



　ちなみに, l_{ij} \,を点 i \, から点 j \, への枝の長さと考えたとき, 本問題はネットワークにおける最短路問題とみなすことができる(図1). 点 1 \, から点 T+1 \, への最短路の長さは, 1期から T \, 期までの需要を満足する上での最小費用となる.

　動的計画法によって最適解を得る際の計算の手間は {\rm O}(T^2) \, であるが, 最近の研究では {\rm O}(T) \, の手間で最適解を得られるアルゴリズムが開発されている [2]. また, 近似解を得るための種々のヒューリスティック解法が提案されている [5].

　動的ロットサイズ決定問題は, 発注量や期末在庫量に上限がある場合, 品切れを許し品切れ時の需要がバックオーダーされる場合, 多段階の場合など, ざまざまな拡張がなされている [2] [4].



参考文献

[1] H. M. Wagner and T. M. Whitin, "Dynamic Version of the Economic Lot Size Model," Management Science, 5(1958), 89-96.

[2] J. Bramel and D. Simchi-Levi, The Logic of Logistics, Springer, 1997.

[3] H. L. Lee and S. Nahmias, "Single-Product, Single-Location Models," in Logistics of Production and Inventory, S. C. Graves, A. H. G. Rinnooy Kan and P. H. Zipkin, eds., North-Holland, 1993.

[4] S. C. Graves, "A Review of Production Scheduling," Operations Research, 29(1981), 646-675.

[5] E. A. Silver, D. F. Pyke and R. Peterson, Inventory Management and Production Planning and Scheduling, Third Edition, John Wiley & Sons, 1998.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E5%8B%95%E7%9A%84%E3%83%AD%E3%83%83%E3%83%88%E3%82%B5%E3%82%A4%E3%82%BA%E6%B1%BA%E5%AE%9A%E5%95%8F%E9%A1%8C" より作成