Inventory Management (Deterministic Model): Dynamic Lot-Sizing Problem & Capacitated Lot-Sizing Problem Prof. Dr. Jinxing Xie Department of Mathematical Sciences Tsinghua University, Beijing 100084, China http://faculty.math.tsinghua.edu.cn/~jxie Email: jxie@math.tsinghua.edu.cn Voice: (86-10)62787812 Fax: (86-10)62785847 Office: Rm. 1202, New Science Building

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

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

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

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

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

单产品、无能力限制的批量问题 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找一条最短路

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

注：如何计算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)

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

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

Serial System 1 2 N

Serial System

Serial System N=3 n=4

Serial System

Serial System: Algorithm Design

Serial System: Dynamic Programming

Serial System: Computational complexity

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

Multi-stage system Distribution system General

Earlier researches in the field

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)

HGA for General CLSP

General CLSP Model

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