Inventory Management (Deterministic Model): Dynamic Lot-Sizing Problem & Capacitated Lot-Sizing Problem Prof. Dr. Jinxing Xie Department of Mathematical.

Presentation on theme: "Inventory Management (Deterministic Model): Dynamic Lot-Sizing Problem & Capacitated Lot-Sizing Problem Prof. Dr. Jinxing Xie Department of Mathematical."— Presentation transcript:

1 Inventory Management (Deterministic Model): Dynamic Lot-Sizing Problem & Capacitated Lot-Sizing Problem Prof. Dr. Jinxing Xie Department of Mathematical Sciences Tsinghua University, Beijing , China Voice: (86-10) Fax: (86-10) Office: Rm. 1202, New Science Building

2 Review: EOQ and ELSP EOQ (EPQ / EMQ)
Deterministic, statistic demand (not time-varying) Single stage (uncapacitated), infinite planning horizon ELSP (Economic Lot-Sizing Problem): Multiple products Single stage (Single Capacitated Machine) Multiple stage: Echelon Inventory; Powers-of-Two Policies How about finite horizon case? Constant demand: Equal cycles, or EOQ approximation Dynamic demand (time-varying): Lot-sizing Problem

3 单产品、无能力限制的批量问题 （Single-level Uncapacitated Lotsizing）
某工厂生产某种产品用以满足市场需求,且已知在时段t中的市场需求为dt . 在某时段t, 如果开工生产, 则生产开工所需的生产准备费为st , 单件产品的生产费为ct . 在某时段t期末, 如果有产品库存, 单件产品的库存费为ht . (假设这些参数非负) 假设初始库存为0, 不考虑能力限制, 工厂应如何安排生产, 可以保证按时满足生产, 且使总费用最小?

4 单产品、无能力限制的批量问题 d(t) T t

5 整数（０－１）规划模型: 非线性／线性？ 假设在时段t, 产品的生产量为xt , 期末产品的库存为It (I0 =0); 用二进制变量yt表示在时段t工厂是否进行生产准备. （假设不允许缺货） xt <=M*yt, yt ＝0 or 1, M充分大

6 单产品、无能力限制的批量问题 假设费用均非负，则在最优解中 ，即 注：当ct为常数，目标函数可变为 定理 (Zero-switch Property; Zero-Inventory Property) 一定存在满足条件 的最优解. 可以只考虑

7 单产品、无能力限制的批量问题 1 2 3 4 5 w11 w33 w22 w44 w34 w23 w12 w13 w24 w14
记wij为第i时段生产 　时所导致的费用(包括生产准备费、生产费和库存费), 即 其中 网络：从所有节点i到j (> i)连一条弧, 弧上的权为wi,j-1 , 如T=4时： 1 2 3 4 5 w11 w33 w22 w44 w34 w23 w12 w13 w24 w14 即从节点1到5找一条最短路

8 动态规划求解 用ft表示当t时段初始库存为0时，从t时段到T 时段的子问题的最优费用值 (即从节点t到T+1的最短路长) 最优值（费用）为 f1 . 计算复杂性为 1990(OPERIONS RESEARCH), 1991(Management Science): 对s, c, h 与t无关的情形，找到O(T)的算法；否则找到O(T logT )的算法

9 注：如何计算wij？ in O(T2)? for i=1,2,…,T { A=0; B=0; C=0; for j=i,i+1,…,T 记
{ A=A+dj; if (j>i) B=B+hj-1; C=C+B*dj; if (A=0) wij=0; else wij=si+ci*A+C; } 记 算法（计算wi,j） in O(T2)

10 单产品、无能力限制的批量问题：另一种建模方法
1 2 3 4 I1 x1 x2 x3 x4 I2 I3 d1 d2 d3 d4 模型扩展： 提前期非０ 允许缺货 价格折扣 非线性成本 Inflation 有限能力 多级系统 …… 凹费用（concave cost）最小费用流问题

11 Lot-sizing in Serial System
Serial system （Love，1972, MS):

12 Serial System 1 2 N

13 Serial System

14 Serial System N=3 n=4

15 Serial System

16 Serial System: Algorithm Design

17 Serial System: Dynamic Programming

18 Serial System: Computational complexity

19 Multi-stage system Serial system （Love，1972, MS):
Assembly system： IN-TREE (1984, MS):

20 Multi-stage system Distribution system General

21 Earlier researches in the field

22 General multi-stage system
When production capacity is INFINITE, Dynamic lot-sizing problem (DLSP) (also called uncapacitated CLSP, since DLSP sometimes refers to Discrete Lot-Sizing Problem) When production capacity is incorporated, then problem is much more difficult (strongly NP-hard) Capacitated lot-sizing problem (CLSP)

23 HGA for General CLSP

24 General CLSP Model

25 Review of this lecture: DLSP & CLSP
Finite horizon, Dynamic demand Single stage (WW algorithm) Serial system (Love) Assembly system Distribution system General system What can be generalized to DLSP and CLSP Zero-Switch Policy Nested Policy Echelon Inventory