WIXLIB

Multi-Echelon InventoryOptimization: An Overview1LARRY SNYDERDEPT. OF INDUSTRIAL AND SYSTEMS ENGINEERINGCENTER FOR VALUE CHAIN RESEARCHLEHIGH UNIVERSITYEWO SEMINAR SERIES – NOVEMBER 13, 2008

Outline2y Introductiony Single-stage models (building blocks)y Multi-echelon models{ Network Topology{ Deterministic Models{ Stochastic Modelsy Decentralized systems

Introduction3

Factors Influencing Inventory Decisions4y Why hold inventory?{ Lead times{ Economies of scale / fixed costs / quantity discounts{ Service levels{ Concerns about future availability{ Sales / promotionsy Why avoid inventory?{ Cost of capital{ Shelf space{ Perishability{ Risk of theft / fire / etc.

Classifying Inventory Models5y Deterministic vs. stochasticy Single- vs. multi-echelony Periodic vs. continuous reviewy Discrete vs. continuous demandy Backorders vs. lost salesy Global vs. local controly Centralized vs. decentralized optimizationy Fixed cost vs. no fixed costy Lead time vs. no lead time

Costs in Inventory Models6y Holding cost h ( / item / unit time)y Stockout penalty p ( / item / unit time)y Fixed cost k ( / order)y Purchase cost c ( / item){ Often ignored in optimization models

A Brief History of Inventory Theory7y Harris (1913): EOQ modely ? (19?): newsvendor modely Wagner and Whitin (1958): time-varyingdeterministic demandsy Clark and Scarf (1960): serial stochastic systemsy Roundy (1985): serial deterministic systems w/fixedcosts, power-of-2 policiesy Graves and Willems (2000): guaranteed-servicemodels

Single-Stage Models8(BUILDING BLOCKS)

The EOQ Model9y Continuous, deterministic demand at rate λ per yeary Fixed cost k per ordery Holding cost h per item per yeary Stockouts not allowedinventorylevelQtime

The EOQ Model: Optimization10y Average annual cost:kλ hQc(Q) Q2y First-order condition:kλ hc' (Q) 2 0Q2y Optimal solution:2kλQ* hc(Q*) 2kλh hQ *

The Newsvendor Model11y Each day, newsvendor buys newspapers fromyyyyypublisher for 0.25 eachSells newspapers for 0.75 eachUnsold papers are sold back to publisher for 0.10Daily demand is stochastic, N(50, 102)No inventory carryover [perishable inventory]No backorder carryover [lost sales]y How many newspapers to buy?{ Probably 50, but how many?

A More General Formulation12y Periodic, stochastic demand{ pdf f, cdf F{ We’ll assume normal distribution (φ, Φ standard normal)y Inventory carryover allowed [non-perishable] or not{ Either way, “overage” cost h{ May include salvage value/costy Backorders or lost sales{ Either way, “underage” cost p{ May include lost profit, loss of goodwill, admin costsy Decision variable: base-stock level y{ In each period, order up to y

Expected Cost Function13y 0yc( y ) h ( y x) f ( x)dx p ( x y ) f ( x)dxy Convex solve first-order condition (Leibniz’s rule)y Optimal solution: p μ σzαy* μ σΦ p h 1where α p / (p h) (the newsvendor ratio)

Interpretation of Optimal Solution14y* μ σzαcycle stocksafety stocky No stockouts if demand μ σzα{ Occurs with probability α{ α optimal service levely If lead time (L) 0:y* μL σzα Lμ μ σzα

Multi-Echelon Models15PART 1:NETWORK TOPOLOGY

Network Topology16y System is composed of stages (nodes, items, sites )y Stages are grouped into echelonsy Stages can represent:{ Physical locations{ Items in BOM{ Processing activities

Terminology17y Stages to the left are upstreamy Those to the right are downstreamy Downstream stages face customer demandy Network topologies, in increasing order of complexity:

Serial System18y Each stage has at most one predecessor and at mostone successor

Assembly System19y Each stage has at most one successor

Distribution System20y Each stage has at most one predecessor

Tree System21y No restrictions on neighbors, but no cycles

General System22y No restrictions on cycles

Multi-Echelon Models23PART 2:DETERMINISTIC SYSTEMS(WITH FIXED COSTS)

Assumptions24y Each stage functions like an EOQ system:{ Continuous, deterministic demand (last stage only){ Fixed ordering cost{ No stockouts allowedy We’ll consider serial systems only

The Optimization Problem25Need to choose Q at all stages simultaneouslyy Properties of optimal solutions:y{{Zero-inventory ordering (ZIO): order only when inventory 0Stationary: same Q for every orderÙ{y(but different for different stages)Nested: whenever one stage orders, so does its customerInstead of optimizing over Q, we optimize over u (reorderinterval){u Q/λQu

NLIP Formulation26 k j h j λu jmin C (u) 2j uju j θ j u j 1s.t. uj 0θ j {1,2,3, }y Non-convex mixed-integer NLPy Optimal solution u* is not known{In fact, no guarantee an optimal solution exists, except in limity Therefore, get lower bound by solving relaxed problemy And upper bound by rounding relaxed solution to feasiblesolution

Relaxed Problem27min C (u)s.t. u j u j 1uj 0y Convex NLPy Could solve using NLP solvery But there’s a better way

Solving the Relaxed Problem28y Partition the stages:y In each partition, require every stage to have thesame uj u{Find u by solving EOQ—easy!y If we use the “correct” partition, we solve the relaxedproblem{Find correct partition by finding upper concave envelope of setof points in 2D—easy!

Power-of-2 Policies29y Let û be a fixed base period{ e.g., 1 week, 3 days, etc.y Power-of-2 policy: each uj is an integer-power-of-2multiple of ûy To get feasible solution, round solution to relaxedproblem to nearest power-of-2 policyy Power-of-2 policies are simple to implement andintuitive{(Stage 1 orders every 2 weeks, stage 2 orders every week, etc.)

Worst-Case Error Bound30y Let u* be the (unknown) optimal policyy Let u be the power-of-2 policyy Theorem (Roundy 1985): For any û,3C (u ) 1.06C (u*) 2 2y If we can choose û, then the bound reduces to 1.02

Multi-Echelon Models31PART 3:STOCHASTIC SYSTEMS(WITHOUT FIXED COSTS)

Assumptions32y Each stage functions like a newsvendor system:{ Periodic, stochastic demand (last stage only){ No fixed ordering cost{ Inventory carryover and backordersy Each stage follows base-stock policyy Lead time (L) deterministic transit time betweenstagesy Waiting time (W) stochastic time between whenstage places an order and when it receives it{Includes L plus delay due to stockouts at supplier

Stochastic- vs. Guaranteed-Service Models33y Two main modeling approachesy Stochastic-service models:{ Each stage meets demands from stock whenever possible(W L){ Excess demands are backordered and incur W Ly Guaranteed-service models:{ Each stage sets a committed service time (CST) and guaranteesthat W CST for every demand{ Demand is assumed to be boundedy Let α service level (% with W CST){ Stochastic service: CST 0, α 1{ Guaranteed service: CST 0, α 1

34Stochastic-Service Models

Serial Systems: The Clark-Scarf Algorithm35y Objective function:c(y ) j [hE[on - hand inventory] pE[backorders]]y E[on-hand] and E[backorders] at stage j depend on y at jand upstreamy Clark and Scarf (1960) rewrite c(y) so that systemdecomposes by stage{{{{yj can be determined at each stage in sequenceUse decisions from downstream stages but ignore upstream onesAt each stage, solve 1-variable convex minimization problem(At last stage, it’s a newsvendor problem)y Easy computationally but cumbersome to implementy Good heuristics exist: e.g., Shang and Song (1993)

Assembly Systems36y Theorem (Rosling 1989): Every assembly systemcan be reduced to an equivalent serial system{Solve using Clark-Scarf algorithmy Based on inventory balance principle:213{{If inventory of 2 inventory of 3, the extra is uselessTherefore, attempt to keep I2 I3 at all times

Distribution Systems37y Inventory balance principle does not applyy Allocation rule becomes critical factory The one-warehouse, multiple retailer (OWMR) system{ Famous special case{ Exact algorithm: Axsäter 1993{ Heuristics:Sherbrooke 1968 (METRIC): approximate waiting time with its meanÙ Graves 1985: 2-moment approximation of backorder levelsÙ Gallego, Özer, and Zipkin 2007: newsvendor approximationÙ Rong, Bulut, and Snyder 2008: decompose into serial systemsÙ

Extensions38y Fixed ordering costsy Stochastic lead timesy Limited capacityy Imperfect qualityy Some are hard, some are not{ Tractability of standard problems is somewhat “fragile”

39Guaranteed-Service Models

Guaranteed-Service Models: Overview40y Each stage promises to deliver every item within afixed number of periods{Called the committed service time (CST)y Requires assumption that demand is bounded{ e.g., D μ σzα{ Equivalently, ignore excess demand when D exceeds boundy CST assumption allows us to treat waiting time (W)as deterministicy References: Kimball 1955, Simpson 1958, Graves1988, Graves and Willems 2000, 2003

Net Lead Time413T3S32T2S21T1S1y Each stage has:{ Processing time T{ CST Sy Net lead time (NLT) at stage i Si 1 Ti – Si“bad” LT “good” LT

Net Lead Time vs. Inventory42y Suppose Si Si 1 Ti{ e.g., inbound CST 4, proc time 2, outbound CST 6{ Don’t need to hold any inventory{ Operate entirely as pull (make-to-order, JIT) systemy Suppose Si 0{ Promise immediate order fulfillment{ Make-to-stock system

Net Lead Time vs. Inventory43y In general:y* μ NLT σzα NLTy NLT replaces LT in earlier formulay Choosing inventory levels choosing NLTs, i.e.,choosing S at each stage

Optimization44y Objective:{ Find optimal S values (CSTs){ To minimize expected holding cost{ Subject to end-customer service requirementy Solution methods:{{{Serial systems: dynamic programming (Graves 1988)Tree systems: dynamic programming (Graves and Willems2000)General systems: piecewise-linear approximation CPLEX(Magnanti et al., 2006)

Key Insight45y It is usually optimal for only a few stages to holdinventory{Other stages operate as pull systemsy Theorem (Graves 1988): In a serial system, everystage either:{{holds zero inventory (and quotes maximum CST)or quotes CST of zero (and holds maximum inventory)

Case Study46PART 2CHARLESTON ( 7)14814PART 5CHICAGO ( 155)45545PART 6CHARLESTON ( 2)3232PART 7CHARLESTON ( 30)881414PART 3AUSTIN ( 2)141467PART 4BALTIMORE ( 220)PART 1DALLAS ( 260)015555(Adapted from Simchi-Levi, Chen, and Bramel,The Logic of Logistics, 2nd ed., Springer, 2004)y # below stage processing timey # in white box CSTy In this solution, inventory is held of finished productand its raw materials

A Pure Pull System47PART 2CHARLESTON ( 7)14814PART 5CHICAGO ( 155)45545PART 6CHARLESTON ( 2)3232PART 7CHARLESTON ( 30)8PART 3AUSTIN ( 2)1414PART 4BALTIMORE ( 220)8675551414y Produce to ordery Long CST to customery No inventory held in systemPART 1DALLAS ( 260)1577

A Pure Push System48PART 2CHARLESTON ( 7)14814PART 5CHICAGO ( 155)45545PART 6CHARLESTON ( 2)3232PART 7CHARLESTON ( 30)8PART 3AUSTIN ( 2)1414PART 4BALTIMORE ( 220)86PART 1DALLAS ( 260)75551414y Produce to forecasty Zero CST to customery Hold lots of finished goods inventory150

A Hybrid Push-Pull System49PART 2CHARLESTON ( 7)7814PART 5CHICAGO ( 155)45545PART 6CHARLESTON ( 2)3232PART 7CHARLESTON ( 30)8814PART 3AUSTIN ( 2)914PART 4BALTIMORE ( 220)67PART 1DALLAS ( 260)301585push/pull boundary14y Part of system operated produce-to-stock, partproduce-to-ordery Moderate lead time to customer

CST vs. Inventory Cost50Push System 14,000Inventory Cost ( /year) 12,000Push-Pull System 10,000 8,000 6,000 4,000Pull System 2,000 00102030405060Committed Lead Time to Customer (days)7080

Optimization Shifts the Tradeoff Curve51 14,000Inventory Cost ( /year) 12,000 10,000 8,000 6,000 4,000 2,000 00102030405060Committed Lead Time to Customer (days)7080

Decentralized Systems52

Decentralized Systems53y We have assumed the system is centralized{ Can optimize at all stages globally{ One stage may incur higher costs to benefit the system as awholey What if each stage acts independently to minimize itsown cost / maximize its own profit?