WIXLIB

A New Algorithm and a New Heuristic for Serial SupplySystems.Guillermo Gallego Department of Industrial Engineering and Operations ResearchColumbia University†Özalp ÖzerDepartment of Management Science and EngineeringStanford UniversitySeptember 1, 2004AbstractWe present a new dynamic programming formulation for the stochastic multi-stage serialinventory system based on the cost of sub-system with fewer stages. A heuristic based on judiciously selected common downstream holding costs requires solving one newsvendor problemper stage. A closed form approximate upper bound allows for accurate sensitivity analysis. 1Key words: stochastic inventory systems; multi-echelon; newsvendor bound Corresponding Author: 326 Mudd Building, Columbia University, New York, NY gmg2@columbia.edu.Research Supported by NSF Grant DMI-02-181041Acknowledgments: We wish to thank Haengju Lee, Ozge Sahin and Jay Sethuraman for useful suggestions onearlier versions of this note.†

1Series SystemsThe study of multi-stage serial inventory systems is central to the study of supply chain managementboth as a benchmark and as a building block for more complex supply networks. Existing policyevaluation and optimization algorithms are, unfortunately, difficult to understand and communicate.We provide a dynamic programming (DP) formulation based on the idea of optimally allocatinga given echelon-inventory level between the upstream stage and the downstream series system.This formulation yields an algorithm that can be improved by incorporating gradient updates.We develop a simple, near-optimal, heuristic that follows from the DP formulation by judiciouslyselecting a common holding cost for the downstream stages. The heuristic calls for solving a singlenewsvendor problem per stage and is very accessible to students and practitioners. The need todevelop accurate and accessible spreadsheet-based heuristics was recently identified by Shang andSong [13] who develop a heuristic based on solving two newsvendor problems per stage. We evaluateour heuristic and compare it to that of Shang and Song by testing it on the set of test problems inGallego and Zipkin [8] and Shang and Song [13] and in additional experiments designed to test theperformance when different stages have different lead times. Our numerical results indicate thatour heuristic is near optimal with an average error that is lower than the Shang and Song heuristic.Finally, we provide an approximate distribution-free bound that accurately reflects the sensitivityof the optimal average cost to changes in system parameters.Consider a series system consisting of J stages as illustrated in the figure. Stage j J procuresfrom Stage j 1 and Stage J replenishes from an outside supplier with ample stock. Customerdemand occurs only at Stage 1 and follows a (compound) Poisson process, {D(t), t 0} with arrivalrate λ and random demand size X with E[X 2 ] . It takes Lj units of time for a unit to arriveat Stage j once it is released by its predecessor.Unsatisfied demand is backordered at each stage but only Stage 1 incurs a linear backorderpenalty cost p, per unit, per unit time. We assume without loss of generality that each stage addsvalue as the item moves through the supply chain, so echelon holding costs hej are positive. ThePlocal holding cost for stage j is hj he [j, J] Ji j hei , where sums over empty sets will be definedas zero. In particular, hJ 1 0. The system is operated under continuous review, so an order isplaced every time a demand occurs. As pointed out by Zipkin [14], this is justified for expensiveand/or slow moving items.The following random variables describe the state of Stage j in equilibrium:Dj leadtime demand,Ij on-hand inventory,Bj backorders.1

The total long run average cost for any policy can be expressed asE[JXhk Ik pB1 k 1JXhk Dk 1 ].(1)k 2Optimality of an echelon base stock policy (sJ , . . . , s1 ) for this series system is well known(see Federgruen and Zipkin [4], Chen and Zheng [2] and Zipkin [14], and the original work byClark and Scarf [3]). Under this policy, the manager continuously monitors the echelon inventoryorder position at each stage and places an order from Stage j 1 to bring it up to sj wheneverit is below this level. An echelon base stock policy (s̃J , s̃J 1 , . . . , s̃1 ) is equivalent to (sJ , . . . , s1 )where sj min(s̃J , . . . , s̃j ), so there exists an echelon base-stock policy satisfying the propertysJ sJ 1 . . . s1 . Let so 0 and let s0j sj sj 1 , j 1 denote the local base stock level atstages j 1, . . . , J. This local base stock policy is equivalent to the echelon base stock policy (seeAxsater [1] Propositions 1 and 2 or Zipkin [14] pg 306). The following recursion gives the steadystate distribution of the local on-hand inventory Ik and the backorder Bk at Stage k starting withBJ 1 0.Ik (s0k Dk Bk 1 ) Bk (Bk 1 Dk s0k ) k J, . . . , 1.(2)Then, the total long-run average cost can be expressed asgJ (sJ , . . . , s1 ) E[JXhk (s0k Dk Bk 1 ) pB1 k 1JXhk Dk 1 ].(3)k 2Consider the sub-system consisting of Stages {j, . . . , 1} for some j {1, . . . , J 1} and assumethat Stage j replenishes its inventory from an external supplier with ample supply. This subsystem is equivalent to the original J stages series system with Dk 0, hk 0 for all k j.Let gj (sj , . . . , s1 ) be the long-run total average cost for an echelon base-stock policy (sj , . . . , s1 ).Then gj (sj , . . . , s1 ) can be obtained via equations (2) and (3) by replacing J by j starting thecomputations with Bj 1 0.The next result provides a link between the cost of the different sub-systems.Proposition 1g1 (s) E[h1 (s D1 ) p(D1 s) ],and for j 2, . . . , Jgj (sj , . . . , s1 ) E[hj (s0j Dj ) gj 1 (min(sj 1 , sj Dj ), sj 2 , . . . , s1 ) hj Dj 1 ].Proof.Let go (s) p( s) , then for j 1,g1 (s) E[h1 (s D1 ) pB1 ] E[h1 (s D1 ) p(D1 s) ] E[h1 (s D)1) go (min(0, s1 D1 )).2(4)

This shows that the result holds for j 1. Suppose the result holds for some j J. We now showthat it holds for j 1. Clearly from Equation (3),gj 1 (sj 1 , sj , . . . , s1 ) Ehj 1 (s0j 1 Dj 1 ) E[jXhk (s0k Dk Bk 1 ) pB1 k 1jXhk Dk 1 ] hj 1 EDj .k 2The term in square brackets looks exactly as the definition of gj (sj , . . . , s1 ) except that Bj 1 (Dj 1 s0j 1 ) instead of 0. Thus, the echelon base-stock level at Stage j is given by sj Bj 1 min(sj , sj 1 Dj 1 ) instead of sj and this justifies (4) for j 1, completing the proof.2We now provide a recursion to find the optimal expected cost at each stage for an arbitraryechelon base stock level, as well as an algorithm to find optimal base-stock policies for each subsystem {j, . . . , 1} for j 1, . . . , J.Let c1 (s) g1 (s) and for j 2, . . . , J definecj (s) min cj (x; s)x {0,.,s}(5)recursively, viacj (x; s) E[hj (x Dj ) cj 1 (min(s x, s Dj )) hj Dj 1 ].(6)Let N {0, 1, . . . , } be the set of non-negative integers and lets j min{s N : cj (s) hj 1 } for j 1, . . . , J,(7)We will show that cj (s) is the long run average cost of optimally managing the sub-system{j, . . . , 1} given echelon base stock level s and that optimal base stock levels are given by (7).Before we prove this result formally, we will provide an intuitive link between equations (6) and (5).Suppose that we have computed cj (·) and consider the sub-system {j 1, . . . , 1}. Our goal is tocompute cj 1 (·) from the knowledge of cj (·). To link the two sub-systems, we decompose the echelonbase stock level s of sub-system {j 1, . . . , 1} by allocating x units to Stage j 1 and s x units forsub-system {j, . . . , 1}. Given this allocation, the net inventory at Stage j 1 will be (x Dj 1 ) which accrues at cost rate hj 1 . Since Stage j 1 will face a shortage when Dj 1 x 0, theeffective echelon inventory for sub-system {j, . . . , 1} is s x (Dj 1 x) min(s x, s Dj 1 ).Thus, a finite local base stock level at Stage j 1 imposes an externality to the sub-system {j, . . . , 1}whose expected cost is now Ecj (min(s x, s Dj 1 )). As a result, when we allocate x s units oflocal base stock level to Stage j 1, the cost of managing a series system with j 1 stages is givenby (6).Theorem 1 1) cj (s) is convex in s for all j 1, . . . , J and given by (5) for j 2, . . . , J; 2)xj (s) (s s j 1 ) minimizes cj (x; s) for j 2, . . . , J; 3) The echelon base stock policy (s j , . . . , s 1 )is optimal and cj (s j ) is the optimal expected cost for sub-system {j, . . . , 1}, j 1, . . . , J.3

Proof. For j 1, the optimal cost of managing the subsystem given echelon base stock level s issimply c1 (s) g1 (s) since there is nothing to optimize. Notice that c1 (s) c1 (s 1) c1 (s) (h1 p)P r(D1 s) p is non-decreasing in s so c1 (s) is convex. The largest optimal base stocklevel is given by s 1 min{s N : c1 (s) 0} which is consistent with (7) since h2 0 forthe sub-system consisting only of Stage 1. As a result c1 (s 1 ) is the optimal expected cost for thesub-system consisting of Stage 1 only. This establishes Parts 1 and 3 for j 1.Consider now the sub-system {2, 1} and notice thatc2 (s) ming2 (s, s1 )minE[h2 (s s1 D2 ) g1 (min(s1 , s D2 )) h2 D1 ]s1 {0,.,s}s1 {0,.,s}min E[h2 (x D2 ) c1 (min(s x, s D2 )) h2 D1 ]x {0,.,s}min c2 (x; s),x {0,.,s}where the second equality is from Equation (4) and the third is by substituting x for s s1 .Therefore, c2 (s) is given by (5). Now let c2 (x; s) c2 (x 1; s) c2 (x; s). Then, c2 (x; s) [h2 c1 (s x 1)]P r(D2 x).Notice that c2 (x; s) 0 for all x 0 on account of D2 0. The convexity of c1 implies that c1 (s x 1) is decreasing in x. As a consequence, c2 (x; s) has at most one sign change overthe range x {0, . . . , s} and this would have to be from to . From Equation (7), s 1 is thesmallest non-negative integer y such that c1 (y) h2 . Notice that s 1 is the largest minimizer of thenewsvendor problem with holding cost h1 h2 , backorder cost p h2 and demand D1 . In particular,s 1 is independent of the distribution of D2 . We have shown that x (s s 1 ) is a minimizer ofc2 (·; s) establishing Part 2 for j 2. This result implies that allocating s 1 units of echelon basestock level to Stage 1 is optimal when s s 1 . Therefore, we havec2 (s) c2 ((s s 1 ) ; s) E[h2 ((s s 1 ) D2 ) c1 (min(s 1 , s D2 )) h2 D1 ] E[h2 (s s 1 D2 ) c1 (min(s 1 , s D2 )) h2 D1 ],where the last equation follows since (x a) (x a) when a 0. To see that c2 is convex,notice that c2 (s) h2 P r(D2 s s 1 ) X c1 (s x)P r(D2 x).x (s 1 s 1 ) Let 2 c2 (s) c2 (s 1) c2 (s), then 2 c2 (s) X 2 c1 (s x)P r(D2 x) [h2 c1 (s 1 1)]P r(D2 s 1 s 1 ).x (s 2 s 1 ) Now, 2 c1 (s x) 0 on account of the convexity of c1 , so the first term is non-negative. Thesecond term is also non-negative by the definition of s 1 . This establishes Part 1 for j 2. Recall4