Supply Chain Management with Overtime and Premium Freight
Eric Logan Huggins hugginse@engin.umich.edu Department of Industrial and Operations Engineering University of Michigan Tava Lennon Olsen olsen@olin.wustl.edu John M. Olin School of Business Washington University in St. Louis January 26, 2002 Abstract We consider a two-stage supply chain under centralized control. The downstream facility faces discrete stochastic demand and passes supply requests to the upstream facility. The upstream facility always meets the supply requests from downstream. If the upstream facility can not meet the supply requests from inventory on hand, the shortage must be filled by either overtime production and/or premium freight shipments, both incurring per unit and setup costs. Overtime production occurs at the end of the period and incurs relatively high production costs; premium freight refers to building products at the beginning of the period they are needed and shipping them very quickly with relatively high shipping costs. Focusing primarily on the case where only one method of filling shortages is available, we determine novel optimal inventory policies under centralized control. At both stages, threshold policies that depend only on the current inventory in the system are optimal; for the total inventory in the system, a base-stock policy is optimal. Numerical analysis provides insight into the optimal policies and allows us to compare the supply chain under centralized and decentralized control. 1 Introduction In traditional supply chain situations, downstream facilities make decisions about their order quantities without regard to the actual inventory available upstream. If the upstream facilities do not have enough inventory on hand to fill the orders, it is often assumed that the downstream facility will take what it can get and backorder the rest. We consider a problem with stochastic demand where the downstream facility's supply requests are always met by the upstream facility. If the downstream facility orders more than the upstream facility has on hand, the upstream facility must meet the shortage with either overtime production or with what we call `premium freight'. Premium freight consists of building parts the same period they are required downstream and shipping them in an expedited fashion (e.g., by airplane or helicopter). In our problem, both methods of filling shortages are expensive, incurring fixed and per unit costs. Under these conditions, we examine how an upstream facility and a downstream facility can minimize system costs by working together; the upstream facility will always meet supply requests, and the downstream facility will avoid causing shortages upstream unless absolutely necessary. We have modeled our problem after the actual inventory control problems faced by a large automobile parts supplier in Michigan, which we will refer to as `PartCo'. PartCo produces mostly engine parts used in vehicle assembly at one of the big three American automobile manufacturers. At PartCo, inventory levels are relatively low, yet they follow a policy of meeting all supply requests, frequently using overtime production and/or premium freight when shortages occur. Backordering is not considered an option because the parts they send downstream are essential in keeping the assembly lines moving, and the cost of shutting down the assembly lines at the automobile manufacturer is extremely high. We have heard a wide range of estimates for this cost, but all have been in tens of thousands of dollars per hour! Therefore, overtime production and premium freight shipments are "commonly" used, according to our contacts at PartCo. We model a centrally controlled, two-stage supply chain where the upstream facility always meets supply requests from downstream. In our model, we have attempted to capture the essence of the situation at PartCo. We feel that our model and results may apply elsewhere in the automobile industry and in other 1 industries, and that our results show that supply requests can always be met, but at a cost. According to an article in The Detroit News [Smith, 2001], Willow Run Airport outside of Detroit has recently become the nation's third largest cargo airport due to shipment of automobile parts. The article states that "hardly a car or truck is made anywhere in the United States that doesn't include parts that have traveled through Willow Run Airport" and that "increasingly, Detroit's automakers are flying parts from city to city and from continent to continent." Clearly, shipping parts by air is a significant issue in the automotive supply chain. We feel that our model may apply to the computer and electronics industries as well, where many manufacturers, notably Dell, have reduced or even eliminated their requirements for warehousing and receive parts in just-in-time fashion. Finally, we feel that our results yield new insight into a common assumption made in the inventory literature. In many single location inventory models, it is assumed that supply requests upstream are always met, without considering how and at what cost. Our results show that supply requests can always be met upstream using some form of expediting, but that it may be much less expensive for the system if the downstream facility is sensitive to the inventory situation upstream and adjusts supply requests accordingly. We have determined the optimal policies for this supply chain under centralized control when both options for filling shortages are available. However, for clarity of exposition, we will consider only one of the two mathematically equivalent options, overtime production, throughout most of this paper. The results are the same if we consider only premium freight. We include the slightly more complicated optimal policies and proofs when both options are considered in Appendix 2. Our proof of the optimal policies proceeds as follows. We define our cost per period in terms of variables representing the inventory levels and inventory positions at the assembler and the supplier. We then substitute variables representing the inventory level and position for the entire system, replacing those of the supplier. To simplify the problem, we relax some of the constraints on the possible inventory levels for the assembler and the system, which leads to an optimal cost function that we can solve. Having relaxed some of the contraints, the optimal policy for the assembler becomes a myopic problem. We solve this myopic problem which leaves us with an optimality equation that depends on the system 2 variables only, so we derive the optimal policy for the system inventory. Finally, we show that the results of our relaxed problem meet the conditions of our original, fully constrained problem. All of our results are for the infinite horizon case, bypassing finite horizon results to avoid end-of-horizon effects. In our previous paper, Huggins and Olsen [2001], we examined the same supply chain, but under decentralized control. In other words, both the supplier and the assembler function independently without sharing any information or inventory decisions. In the decentralized case, the assembler ignores the situation at the supplier and follows a simple base-stock policy, since the assembler's supply requests are always met. At the supplier, we include a fixed cost for regular production and show that the optimal policy is an (s, S) policy for regular production. The overtime production policy depends upon the problem data. In some cases, only one of the methods (either overtime production or premium freight) is used for all shortages. In other cases, there exists a threshold where premium freight is used for small shortages and overtime production is used for large shortages (or vice-versa). An interesting result is that it may be optimal to use overtime production to not only fill a shortage, but also to produce up to a positive inventory level. This case will not occur in our centralized model because we assume that there is no fixed cost for regular production at the supplier. The most important distinction to note between the decentralized and centralized cases is that in the decentralized case, the assembler ignores the high expense to the supplier caused by shortages. A shortage of a single unit forces the supplier to pay a possibly high fixed cost for either overtime production or premium freight. In the centralized case, we will show that the assembler is very sensitive to shortages and the optimal policy for the assembler will reflect this sensitivity. In this paper, we consider a two-stage supply chain with two methods of expediting. For a review of single location models with expediting, we refer the reader to Chiang and Gutierrez [1998], Tagaras and Vlachos [2001], or our previous paper. A thorough overview of supply chain literature may be found in the text edited by Tayur, Ganeshan, and Magazine [1998]. The seminal work of Clark and Scarf [1960] first considered a multi-echelon inventory problem and Federgruen and Zipkin [1984] showed that the same results hold over the infinite horizon. In their paper, they assume that if the supplier can not meet supply requests from 3 the assembler, the assembler is satisfied with as much as it can get. They prove that the optimal policy for the assembler is to ignore the supplier and follow an (s, S) policy (or a base-stock policy with no fixed cost for production). The optimal policy for the supplier is a base-stock policy, with an additional penalty for possibly not meeting supply requests that effectively increases the base-stock level. The literature on supply chains with expediting or setup costs upstream is limited. Chen and Zheng [1994] consider supply chains with stochastic demand, constant lead times, and with setup costs at all stages. They establish lower bounds on the system costs under centralized control. Lawson and Porteus [1998] consider an m + 1 stage supply chain where decisions must be made at each echelon about how many products to ship by regular means (which takes 1 period) and how many to expedite (which occurs instantaneously). Each expedited unit incurs a per unit cost higher than the per unit cost of regular shipping. They show that a "top-down" base-stock policy is optimal where the upstream managers ignore downstream decisions. Moinzadeh and Aggarwal [1997] consider a two-stage system with one warehouse and several retailers. They assume modified one-for-one (S - 1, S) policies for both regular and expedited orders and develop a procedure to find optimal policy parameters. Although our paper is related to those just mentioned, our model has two methods of expediting, each incurring fixed costs, each with no lead time, and hence our results differ. Similarly, our paper is related to papers where outsourcing is used to meet shortages, but our results still differ. One reason is that we include a fixed cost when shortages occur, whereas most outsourcing assumptions only include a per unit cost. For example, in Gavirneni, Kapuscinski, and Tayur [1999], the cost of outsourcing is the same as it is from within the supply chain. Another difference is that we do not allow backorders at the upstream facility, which strongly affects our analysis. In Lee, So, and Tang [2000], the authors transform their outsourcing costs into backorder penalties, effectively allowing negative inventory levels upstream, even though supply requests are always met. Finally, in our proof of the centralized model, we use results discussed by the following authors: Porteus [1990], Zheng [1991], Bertsekas [1995], and Rosling [1998]. In Zheng's paper, he shows that (s, S) policies are optimal given that the expected one period cost function is quasiconvex, which we show using a result from Porteus. We use this result 4 to prove the optimal policy for the system inventory. The text by Bertsekas has several useful propositions; specifically, one proposition states that the optimal cost function satisfies Bellman's equation under assumptions we show to be true in our model. Finally, we assume that our demand distribution is logconcave, and Rosling discusses properties of logconcave functions. The rest of this paper is organized as follows. In Section 2, we define our model, develop cost functions, substitute system variables for supplier variables and relax two constraints. Under these relaxed conditions, we determine the optimal policies for the assembler and for the system in Section 3. We prove that the optimal policies under the relaxed conditions are optimal for the original problem in Section 4. In Section 5, we conduct a numerical analysis and discuss managerial insights. Section 6 concludes the paper and additional proofs are included in the appendices. 2 The Model and Cost Functions We consider a two-stage supply chain where an upstream supplier (stage 2) must deliver products to a downstream assembler (stage 1). A single manager with perfect information about both stages makes all decisions in an effort to minimize total system discounted costs over the infinite horizon. This manager must decide how much to produce at stage 1 and at stage 2 each period. Stage 1 experiences exogenous demand; the demand experienced by stage 2 is equal to the amount to be produced at stage 1 the next period. Thus, the production decision at stage 1 directly influences the costs incurred by stage 2. If stage 1 orders more than stage 2 has on hand, stage 2 is forced to run overtime production to meet the shortage and will incur high overtime production costs. If stage 1 orders everything stage 2 has on hand or less, stage 2 will avoid overtime production. The optimal policies for both stages will eventually reflect this relationship. Define the following variables: Dt = the demand during period t x1,t = the inventory level at stage 1 after demand has been experienced during period t y1,t+1 = the inventory position chosen for stage 1 for period t + 1 x2,t = the inventory level at stage 2 before it experiences demand from stage 1 during 5 period t. y2,t+1 = the inventory position chosen for stage 2 for period t + 1. The inventory decisions take place after demand is experienced at stage 1. At this point, the inventory at stage 1 is x1,t (which equals y1,t - Dt ) and the inventory at stage 2 is x2,t (which equals y2,t ). The manager must decide the inventory positions at both stages, y1,t+1 and y2,t+1 . The decision for stage 1 (y1,t+1 ) determines the demand experienced at stage 2, which is y1,t+1 - x1,t . If y1,t+1 - x1,t > x2,t , there is a shortage at stage 2 and they must produce (y1,t+1 - x1,t ) - x2,t units with overtime production. Note that y1,t+1 x1,t and y2,t+1 ((y1,t+1 - x1,t ) - x2,t )+ . Both of these decisions incur various costs, which we assume to be stationary. At stage 1, linear costs are assessed for production (c1 ), holding (h1 ) and backordering (b1 ). At stage 2, linear costs are assessed for production (c2 ) and holding (h2 ), and overtime production incurs linear (co ) plus fixed (Ko ) costs. We also make the following assumptions about our model. First, the discount factor is assumed to be between 0 and 1. Second, we assume that demand is discrete, stationary and from a logconcave probability distribution and that the expected value of demand is positive and finite. Third, we let pd be the the probability that demand equals d, F (d) be the probability that demand is less than or equal to d, and we assume that demand is non-negative. Fourth, we assume that the per unit cost of overtime production is greater than the per unit cost of production at stage 2. Finally, to ensure that stage 1 policy is reasonable, we assume that the backordering cost at stage 1 is relatively high and the holding cost at stage 2 is relatively low. For later reference, we label our assumptions as follows: (A1) 0 < < 1. (A2) The demand distribution is logconcave and for all t, 0 < E[Dt ] < . (A3) pd = 0 for d < 0. (A4) co > c2 . (A5) b1 co + ((1 - )c1 - c2 ) and h2 h1 + (1 - )c1 . We now proceed to define the various cost functions associated with the model described above. We originally define our cost per period in terms of stage 1 and stage 2 variables, but then make a substitution replacing the stage 2 variables with variables representing the 6 system inventory. Next, we relax some of the constraints on the cost per period to get our relaxed cost per period, gr (·). Lastly, we formally define our relaxed optimal cost function
fr (·) and show that the stage 1 problem is now myopic. In later sections, we solve the relaxed problem and show that it's results are also optimal for the original problem. For a thorough review of infinite horizon, discounted total cost minimization problems, we refer the reader to Bertsekas [1995]. In our problem we first consider the cost per period g(period k variables), which consists of all the costs incurred by the system during decision period k. For a given policy , the total, expected, discounted cost over the infinite horizon is f (x0 ), where x0 is the initial inventory. Mathematically,
N -1 f (x0 ) lim E
N k=0 k g(period k variables) . We are interested in finding the optimal policy out of all possible policies and hence the optimal total, expected, discounted cost over the infinite horizon, f (x0 ). f (x0 ) min f (x0 ).
Dropping the time subscripts for notational convenience, define our cost per period as: g1 (x1 , y1 , x2 , y2 , D) c1 (y1 - x1 ) + Ko ((y1 - x1 ) - x2 ) + co ((y1 - x1 ) - x2)+ + h2 (x2 - (y1 - x1 ))+ + c2 (y2 - (x2 - (y1 - x1 ))+ ) + h1 (y1 - D)+ + b1 (y1 - D)- with y1 x1 and y2 (x2 - (y1 - x1 ))+ . The first term is the production cost at stage 1, the next two terms are overtime production costs, the fourth term is the holding cost at stage 2, the fifth term is the production cost at stage 2, and the last two terms are holding and backordering costs at stage 1. Moving the -c1 x1 back to the previous period (as in Veinott [1966]), we get: g2 (x1 , y1 , x2 , y2 , D) (1 - )c1 y1 + 2 c1 D + Ko ((y1 - x1 ) - x2 ) + co ((y1 - x1 ) - x2 )+ + h2 (x2 - (y1 - x1 ))+ + c2 (y2 - (x2 - (y1 - x1 ))+ ) + h1 (y1 - D)+ + b1 (y1 - D)- 7 under the same restrictions. Now, we will define system variables and substitute for the stage 2 variables. Let the system inventory level be xs x1 + x2 and the system inventory position be ys y1 + y2 and substitute: g3 (x1 , y1 , xs , ys , D) (1 - )c1 y1 + 2 c1 D + Ko (y1 - xs ) + co (y1 - xs )+ + h2 (xs - y1 )+ + c2 (ys - y1 - (xs - y1 )+ ) + h1 (y1 - D)+ + b1 (y1 - D)- = ((1 - )c1 - c2 )y1 + 2 c1 D + h1 (y1 - D)+ + b1 (y1 - D)- + Ko (y1 - xs ) + co (y1 - xs )+ + (h2 - c2 )(xs - y1 )+ + c2 ys with y1 x1 and ys y1 + (xs - y1 )+ . Note that the second restriction is equivalent to ys max{y1 , xs }. Also, we can rewrite g3 (·) as g3 (x1 , y1 , xs , ys , D) = L1 (y1 , D) + L2 (y1 , xs ) + c2 ys where L1 (y1 , D) represents the terms on line (1) and L2 (y1 , xs ) represents the terms on line (2). We can now write the fully constrained optimal cost function which we would like to solve. f (x1 , xs ) =
ys max{xs ,y1 },y1 x1 (1) (2) min ED [g3 (x1 , y1 , xs , ys , D) + f (y1 - D, ys - D)] . In order to solve this equation, we relax some of the constraints; later we will show that these constraints are always met by the optimal solution to the relaxed problem, and thus solve the original, fully constrained problem. First, we drop the constraint that y1 x1 . Second, we drop the constraint that ys y1 in the case when y1 > xs . For later reference, we label the relaxed assumptions as: (R1) y1 x1 . (R2) ys y1 when y1 > xs . After relaxing the constraints, our relaxed cost per period has the same costs as g3 (·) but with only one constraint. gr (x1 , y1 , xs , ys , D) L1 (y1 , D) + L2 (y1 , xs ) + c2 ys with ys xs . Now, we show that gr (·) 0 and then apply a result from Bertsekas [1995] to obtain our relaxed optimal cost function. 8 Lemma 1 gr (x1 , y1 , xs , ys , D) 0 Proof: The proof is in the Appendix 1. Because gr (x1 , y1 , xs , ys , D) 0, Proposition 1.1 of Bertsekas (1995, page 137) holds and
the relaxed optimal cost function fr satisfies fr (xs ) = min ED [gr (x1 , y1 , xs , ys , D) + fr (ys - D)] min {ED [L1 (y1 , D)] + L2 (y1 , xs ) + c2 ys + ED [fr (ys - D)]} y1 ,ys xs y1 ,ys xs (3) = Now notice that y1 has no effect on either ys or the cost to go, ED [fr (ys - D)]. Thus, fr (xs ) = min min {ED [L1 (y1 , D)] + L2 (y1 , xs )} + c2 ys + ED [fr (ys - D)] y1 min {m(xs ) + c2 ys + ED [fr (ys - D)]} ys xs = ys xs (4) where m(xs ) = miny1 {ED [L1 (y1 , D)] + L2 (y1 , xs )}. Finding the optimal inventory policy for stage 1 has become a myopic problem which we solve in the first part of the next section. 3 Optimal Policies for the Relaxed Problem In this section, for the relaxed problem, we determine the optimal inventory policies for stage 1 and for the system. We study the function m(xs ) and show that the stage 1 policy depends only on the system inventory level xs . Next, we show that the optimal inventory policy for the system is a base-stock policy. Define NH (y1 ) and NL (y1 ) as NH (y1 ) = ((1 - )c1 - h2 )y1 + ED [2 c1 D + h1 (y1 - D)+ + b1 (y1 - D)- ] and NL (y1 ) = (((1 - )c1 - c2 ) + co )y1 + ED [2 c1 D + h1 (y1 - D)+ + b1 (y1 - D)- ]. We now have that m(xs ) = min {ED [L1 (y1 , D)] + L2 (y1 , xs )} y
1 ED [L1 (y1 , D)] + (h2 - c2 )(xs - y1 ) if y1 xs = min y1 ED [L1 (y1 , D)] + Ko + co (y1 - xs ) 9 if y1 > xs  E [2 c D + h (y - D)+ + b (y - D)- ] D 1 1 1 1 1 = min y1 K - c x + (((1 - )c - c ) + c )y + o o s 1 2 0 1 2 + - (h2 - c2 )xs + NH (y1 ) if y1 xs = min y1 (h2 - c2 )xs + ((1 - )c1 - h2 )y1 + if y1 xs if y1 > xs ED [ c1 D + h1 (y1 - D) + b1 (y1 - D) ] Ko - co xs + NL (y1 ) if y1 > xs = min (h2 - c2 )xs + miny1 xs {NH (y1 )} Ko - co xs + miny1 >xs {NL (y1 )} Before continuing out study of m(xs ), we derive properties about NL (y1 ) and NH (y1 ) in the following lemma. Lemma 2 Define yH = arg miny1 {NH (y1 )} and yL = arg miny1 {NL (y1 )}. (1) NL (y1 ) and NH (y1 ) are convex in y1 . (2) 0 yL yH . Proof: The proof of (1) is straightforward. To prove (2), we examine the differential of both functions. See Appendix 1 for details. Returning to our study of m(xs ) and defining N (xs ) ((1 - )c1 - c2 )xs + ED [2 c1 D + h1 (xs - D)+ + b1 (xs - D)- ], we have that m(xs ) = min
(h2 - c2 )xs + miny x {NH (y1 )} s 1 K - c x + min o o s y1 >xs {NL (y1 )} (h - c )x + N (y ) if x y 2 2 s H H s H (h2 - c2 )xs + NH (xs ) if xs < yH Ko - co xs + NL (xs ) = min if xs > yL if xs yL if xs yH if xs < yH if xs > yL if xs yL Ko - co xs + NL (yL ) (h - c )x + N (y ) 2 2 s H H N (xs ) = min K + N (x ) o s K - c x + N (y )
o o s L L 10 = min N (xs ) Ko - co xs + NL (yL ) (h2 - c2 )xs + NH (yH ) if xs yH if xs < yH if xs yL Define tL as the smallest w such that N (w) Ko - co w + NL (yL ). We get that
(h - c )x + N (y ) if x y 2 2 s H H s H N (xs ) Ko - co xs + NL (yL ) m(xs ) = if tL xs < yH if xs < tL . (5) So, we have defined m(xs ) explicitly and in the process we have determined the optimal inventory control policy at stage 1. If the system inventory is large, xs yH , we order up to yH . If the system inventory is medium, tL xs < yH , we use up the system inventory, xs . Finally, if system inventory is small, xs < tL , we order up to yL .
Theorem 1 Let y1 be the optimal inventory position at stage 1 for the relaxed problem. Then
y H if xs yH if tL xs < yH if xs < tL . QED (6) y1 = xs yL Proof: By definition of m(xs ). variables only. From equation (4), we have
fr (xs ) = min {m(xs ) + c2 ys + ED [fr (ys - D)].} Given m(xs ), we now have that the optimal relaxed cost function is in terms of system ys xs Now, we move the m(xs ) term back to the previous period and get
frm (xs ) = ys xs min {c2 ys + ED [m(ys - D)] + ED [frm (ys - D)].} = ys xs min {G(ys ) + ED [frm (ys - D)].} where G(ys ) = c2 ys + ED [m(ys - D)]. We need to justify two steps here. First, we can
move m(xs ) back a period and fr (·) will have the same optimal policy as frm (·) using a similar argument as Veinott [1966]. Second, to prove the existence of frm (·), we must show 11 that g(ys ) (c2 ys + m(ys - D)) 0 according to Proposition 1.1 of Bertsekas (1995, page 137). To prove g(ys ) is non-negative and to later prove that G(ys ) is quasiconvex, let us examine the function g + (w) c2 w + m(w). Graphically, the function looks as in Figure 1. 300 250 200 g^+(w) 150 100 50 0 -25 -15 -5 5 15 25 35 45 55 65 75 w Figure 1: Graph of g + (w) Starting from the left, g + (·) decreases at rate -(co - c2 ) until point tL - 1. (The big dot on the left is tL - 1, the big dot in the middle is yL , and yH is the big dot on the right). From tL to yH - 1, it follows c2 w + N (w), decreasing at first, then increasing. From yH on, it increases at rate h2 + (1 - )c2 . Lemma 3 The function g + (·) has exactly one minimum which occurs between tL and yH - 1 and is positive. 12 Proof: The proof is in Appendix 1. Theorem 2 For the relaxed problem, the optimal inventory control policy for the system inventory is a base-stock policy. Proof: Consider g(ys ): g(ys ) = (c2 ys + m(ys - D)) = (c2 ys - c2 D + c2 D + m(ys - D)) = (c2 D + g + (ys - D)) 0 where the inequality holds because the g + (·) 0. Note from Figure 1 or Lemma 3 that g + (·) is a quasiconvex function with a minimum point. Now consider G(ys ): G(ys ) = ED [c2 ys + m(ys - D)] = (c2 ED [D] + ED [g + (ys - D)]). The first term is a constant, and the second term is a convolution of a quasiconvex function (g + (ys - D)) and a logconcave probability distribution by assumption (A2). Thus, according to Porteus [1990, page 619], G(·) is a quasiconvex function. Since G(·) is quasiconvex, the desired result follows from Zheng [1991]. QED 4 Optimal Policies for the Original Problem In the previous section, we determined the optimal policies for the relaxed problem
fr (xs ) = min {m(xs ) + c2 ys + ED [fr (ys - D)]} min ED [gr (x1 , y1 , xs , ys , D) + fr (ys - D)]. ys xs = ys xs ,y1 Recall that our fully constrained problem is f (x1 , xs ) = min ED [gr (x1 , y1 , xs , ys , D) + f (y1 - D, ys - D)] . ys max{xs ,y1 },y1 x1 We must show that the optimal policies for the relaxed problem minimize the fully constrained problem and that both (R1) and (R2) are met. To do so, we need one additional 13 assumption that our initial inventory at stage 1 does not exceed the maximum order level at stage 1, yH . (A6) x1 yH . Theorem 3
f (x1 , xs ) = fr (xs ) Proof: The optimal policies for the relaxed problem minimize the costs for the fully constrained problem because both relaxed constraints are met and y1 does not affect ys or the
costs-to-go. If xs < tL , y1 = yL tL xs x1 . If tL xs < tH , y1 = xs x1 . Finally, if xs tH , y1 = yH x1 by assumption (A6). Thus, the first relaxation (R1) is satisfied. To show that (R2) is satisfied, define ys to be the optimal system inventory position, S to be the optimal system base-stock level, and y2 to be the optimal inventory position for stage 2. We must show that ys y1 when y1 > xs . The only time when y1 > xs is when xs < tL
(otherwise, y1 = xs or y1 = yH xs ). In this case, y1 = yL S = ys . The inequality holds because 0 y2 = ys - y1 = S - yL . QED For the original, fully constrained problem, we now know the optimal policies for stage 1, stage 2, and for the system.
y H xs if xs yH if tL xs < yH if xs < tL , y1 = yL ys = xs S if xs > S if xs S , and y2 = ys - y1 . These policies hold when only one of the two options for filling shortages (either overtime production or premium freight) is available. When both options are available, the proof of optimality is more complicated and is included in Appendix 2. However, the system and 14 stage 2 policies remain the same and the stage 1 policy becomes
y H xs = y M y
L if xs yH if tM xs < yH if tL xs < tM if xs < tL . y1 where tM is the threshold between underordering and using premium freight, tL is now the threshold between premium freight and overtime production, and yM is the order-up-to level given premium freight will be utilized. 5 Numerical Analysis and Managerial Insights The optimal policies for the decentralized and centralized supply chains, as discussed in the introduction, are quite different. In the decentralized case, stage 1 and stage 2 both follow base-stock policies. In the centralized case, as we have just shown, stage 1 and stage 2 follow interesting policies that only depend on the system inventory level. A natural question that arises from this difference is how much can be saved by using the centralized optimal policy rather than the decentralized optimal policy? To answer this question, we wrote a C++ program and performed numerical analyses for various parameters and demand distributions. 5.1 Numerical Analysis In our experiment, we set c1 = 10 and = 0.95. (We initially varied , but the outcomes were similar. We chose = 0.95 as a trade-off between realism and fast convergence times.) We varied the other parameters as follows. For stage 1, we let h1 = 2, 4, 8 and b1 = 5, 10, 20. For stage 2, we let c2 = 3, 5, 9 and h2 = 2, 4, 8. For overtime production, we let co = 4, 6, 10 and Ko = 0, 25, 100. These variations lead to a total of 36 = 729 possible combinations. However, many of the combinations violate either assumption (A4) or (A5) and these results were not considered. For each combination, we made several calculations. We calculated the optimal basestock levels, the total costs, and the inventory/overtime costs for stage 1 and stage 2 in 15 the decentralized case. For the centralized case, we calculated the optimal inventory control parameters for stage 1: tL , yL , and yH . Using these parameters, we calculated the system base-stock level S and the total cost and inventory/overtime costs for the system under centralized control. Finally, we calculated three statistics comparing the centralized case and the decentralized case: the percentage savings in total costs, the percentage savings in inventory and overtime costs, and the percentage reduction in system inventory. We averaged these savings over all feasible combinations. We compared the results for four different demand distributions: Poisson(mean), Uniform(lower bound, upper bound), Normal(mean, standard deviation), and Exponential(mean). Since we consider discrete demand, we used discrete approximations for the last three distributions. Also, we truncated each distribution below at zero and above at forty-nine to fit into our probability array, and adjusted the probabilities appropriately to ensure the total probability was one. (Again, we chose a probability array of size fifty as big enough to distinguish different distributions, but small enough to converge quickly.) The average results for several demand distributions are in the table below. Demand Distribution Uniform(25,25) Normal(25,1) Normal(25,5) Poisson(25) Uniform(0,49) Exponential(15) Total Savings 0.0% 1.1% 3.9% 4.0% 7.9% 11.2% Inv/OT Savings 0.0% 10.9% 20.5% 20.8% 23.1% 24.7% Inventory Reduction 0.0% 1.6% 6.3% 6.2% 15.4% 15.7% Table 1: Average Savings of the Centralized Optimal Policy We ran the experiment for constant demand (Uniform(25,25)) as one way to check the accuracy of our computer code. When the demand is stochastic, observe that the three statistics can be quite significant, particularly when demand is exponentially distributed. Also, observe that as demand variance increases, so do the savings and inventory reduction. We will discuss these observations further in Section 5.2. We feel that insight can be gained by examining a typical numerical example along with an atypical numerical example. 16 As a typical example, consider a problem that has Poisson demand with mean 25. The per unit costs at stage 1 are 10 for production, 4 for holding, and 20 for backorders. The per unit costs at stage 2 are 5 for production, 2 for holding, and 6 for overtime production; the fixed cost for overtime production is 100. The discount factor is 0.95. Under centralized control, the optimal policy at stage 1 is to order up to 28 if the system inventory is 18 or less, use up the available system inventory if the system inventory is between 19 and 31, and order up to 32 if the system inventory is 32 or more. The optimal policy for the system is to order up to a base-stock level of 57 and the optimal policy at stage 2 is to order the difference between the system inventory and the inventory at stage 1. Under decentralized control, the optimal policy at stage 1 is to order up to a base-stock level of 29 and the optimal policy at stage 2 is to order up to a base-stock level of 33. Note that the decentralized system carries a total of 62 units. So, under the centralized policy, the system carries 5 less units of inventory. This is an inventory reduction of 8.1%, which is one factor that contributes to cost savings. The other factor that contributes is how often stage 2 is forced to run overtime production. In the centralized case, stage 2 must run overtime when the system inventory after demand is less than the low threshold, or when 57-D < 19. The probability that stage 2 must run overtime equals the probability that D 39, which is 0.0034. In the decentralized case, stage 2 must run overtime when demand is greater than 33; the probability that D > 33 is 0.034. So, for this particular example, stage 2 must run overtime production ten times as often under the decentralized optimal policy! These two factors lead to a total cost savings of 3.2% and an inventory/overtime cost savings of 17.5%. These results are typical for the majority of our experimental outcomes. Now, as an atypical example, consider a problem that has exponential demand with mean 15. The per unit costs at stage 1 are 10 for production, 8 for holding, and 10 for backorders. The per unit costs at stage 2 are 3 for production, 8 for holding, and 6 for overtime production; the fixed cost for overtime production is 25. The discount factor is 0.95. Under centralized control, the optimal policy at stage 1 is to order up to 6 if the system inventory is -1 or less and to use up the available system inventory if the system inventory is 17 0 or greater. Stage 1 will never order up to it's high inventory level of 48, because that value is greater than the optimal base-stock level for the system inventory, which is 21. Under decentralized control, the optimal policy at stage 1 is to order up to a base-stock level of 10 and the optimal policy at stage 2 is to order up to a base-stock level of 9. Note that the decentralized system carries a total of 19 units. So, under the centralized policy, the system actually carries 2 more units of inventory than under the decentralized policy, or an inventory reduction of -10.5%. However, the total cost savings is 13.4% and the inventory/overtime cost savings is 23.0%. The reason for such significant savings despite the inventory increase is that under decentralized control, the probability that stage 2 uses overtime production is 0.50, so stage 2 incurs the fixed overtime cost half of the time! Under centralized control, this probability decreases to 0.20. Note again that this type of result is uncommon; an inventory increase for the centralized policy occurred in only 2% of our experimental outcomes. 5.2 Managerial Insights As shown in Table 1, the centralized optimal policy generally affects significant savings over the decentralized optimal policy. In real situations it could be costly to coordinate the two stages and share information, but it may well be cost-effective considering that the inventory/overtime savings are typically over 20%. In particular, if the demand experienced by stage 1 is highly variable, following the centralized optimal policy seems worth the effort. Clearly, to cut costs in this kind of supply chain, stage 1 must be sensitive to the amount of inventory available at stage 2. Stage 1 must be willing to occasionally "underorder" in order to save significant overtime production costs at stage 2. By the same token, stage 2 must be willing to produce extra units when stage 1 underorders, trusting that stage 1 will want those additional units the next period. Here it is interesting to compare our centralized results with those of Federgruen and Zipkin [1984]. In their model, stage 1 completely ignores stage 2 and follows a base-stock model dependent on only stage 1 cost parameters; stage 2 also follows a base-stock policy, but with a higher base-stock level to reduce the chance of not filling supply requests from stage 1. In our model, stage 1 is sensitive to the costs and inventory available at stage 2, and orders accordingly; stage 2 orders more when stage 18 1 underorders, bringing the system inventory up to a base-stock level. Finally, in most scenarios, the centralized policy is an effective way to reduce the total inventory in the system. For managers interested in following a lean inventory paradigm, the centralized optimal policy offers a way to reduce inventories and costs simultaneously. Not only that, but the centralized optimal policy generally reduces the likelihood of overtime production and/or premium freight, an outcome with which most managers would be very happy. 6 Conclusion and Extensions In this paper we have modeled a two-stage supply chain where supply requests are always met by the upstream facility. We have shown that the optimal inventory control policies for both stages depend only on the system inventory, and that the optimal policy for the system inventory is a base-stock policy. We solved the problem by substituting variables for system inventory and then relaxing two constraints. After this relaxation, we get a myopic problem for stage 1 that we solve for the optimal policy which depends on two thresholds and the system inventory. Next, we solve the optimality equation for the system and show that a base-stock policy is optimal. Finally, we show that the solutions for the relaxed problem solve the original, fully constrained problem, and hence we have found the overall optimal policies. We performed an experiment for several different demand distributions and parameter values. The results of this experiment clearly indicate that the centralized optimal policy affects significant savings over the decentralized optimal policy. Numerical examples yield insight into where the savings occur. Our main managerial insights are that savings are significant, that to cut costs stage 1 must occasionally underorder, and that inventory levels can generally be reduced by following the centralized policy. We feel that some of our analyses and results are distinctive when compared to traditional inventory literature. Traditional two-echelon proofs proceed by separating variables and then solving two independent problems. We tried this approach at first, but we were unable to decouple our equations. However, we found that by substituting system variables and 19 relaxing some constraints, we could first solve a myopic problem then solve a straightforward dynamic program. Our optimal policies also vary from traditional optimal inventory policies. Our stage 1 policy of ordering up to two (or three) separate inventory levels and occasionally underordering is quite different from traditional inventory policies. Hence, we feel that our base-stock result for the system is also interesting. The most obvious extension to this model is channel coordination. Is there a way to induce both stage 1 and stage 2 to follow the centralized optimal policy? If so, how will the the two stages share the various costs involved? We are currently working on this problem and can make a few observations about possible solutions. First, the two stages must share information to achieve the centralized results. The centralized policies depend only on the system inventory, which is the sum to the inventories at both stages, and thus at least one of the stages must know the system inventory to order appropriately. Second, for a cost structure to coordinate both stages, the cost structure will very likely be two-tiered in order to create the two thresholds that determine inventory positions at both stages. 20 Appendix 1
Proof of Lemma 1
We consider the case where y1 xs and the case where y1 > xs . Note that in both cases, it is possible that y1 < 0 since backorders are allowed at stage 1. When y1 xs , gr (x1 , y1 , xs , ys , D) h2 (xs - y1 ) - c2 xs + c2 ys c2 (ys - xs ) 0. The first inequality holds because we drop non-negative terms from equations (1) and (2) and cancel the c2 y1 terms. The second inequality holds since ys xs . When y1 > xs , gr (x1 , y1 , xs , ys , D) -c2 y1 + co (y1 - xs ) + c2 ys = co (y1 - xs ) - c2 (y1 - ys ) co (y1 - xs ) - c2 (y1 - xs ) = (co - c2 )(y1 - xs ) 0. The first inequality holds because we drop non-negative terms from equations (1) and (2), the second inequality holds since ys xs and the third inequality holds since co c2 by assumptions (A1) and (A4). QED Proof of Lemma 2, part (2)
Note that the middle inequality is satisfied because -h2 < 0 < co - c2 by assumptions (A1) and (A4). To prove the other inequalities, we define the differential of each function as Ni (y1 ) = Ni (y1 + 1) - Ni (y1 ) for i = L, H. To calculate yL , we must solve NL (y1 ) = 0. If the solution to this equation is not integer, yL will be either the ceiling or the floor of the solution to this equation. Consider NL (y1 ) = NL (y1 + 1) - NL (y1 ) = (((1 - )c1 - c2 ) + co )(y1 + 1) + ED [2 c1 D + h1 (y1 + 1 - D)+ + b1 (y1 + 1 - D)- ] - 21 ((1 - )c1 - c2 ) + co )y1 - ED [2 c1 D + h1 (y1 - D)+ + b1 (y1 - D)- ] = (((1 - )c1 - c2 ) + co ) + ED [h1 (y1 + 1 - D)+ - h1 (y1 - D)+ + b1 (y1 + 1 - D)- - b1 (y1 - D)- ] = (((1 - )c1 - c2 ) + co ) + h1 F (y1 ) - b1 (1 - F (y1 )) = ((1 - )c1 - c2 ) + co - b1 + (h1 + b1 )F (y1 ) Similarly, NH (y1 ) = (1 - )c1 - h2 - b1 + (h1 + b1 )F (y1 ). Thus, at each respective minimum, NL (yL ) = ((1-)c1 -c2 )+co -b1 +(h1 +b1 )F (yL ) 0 and NH (yH ) = (1-)c1 -h2 -b1 +(h1 +b1 )F (yH ) 0. Or, yL F -1 ( b1 -((1-)c1 -c2 )-co ) h1 +b1
-(1-)c and yH F -1 ( b1 +h2h1 +b1 1 ). For yL and yH to exist, we require that the first fraction is non-negative and that the second fraction is less than or equal to one. So, we require that b1 - ((1 - )c1 - c2 ) - co 0 and b1 + h2 - (1 - )c1 h1 + b1 which both hold by assumption (A5). Under these conditions, we have that 0 yL yH . QED Proof of Lemma 3
To the left of tL , the slope of g + (·) is -(co - c2 ) < 0 and to the right of yH - 1, the slope of g + (·) is h2 + (1 - )c2 > 0. Also note that g + (tL ) g + (tL - 1) by definition of tL . Thus, any minima of the function occur between tL and yH - 1. Between these values, g + (·) follows c2 w + N (w), a convex function, and thus there is exactly one minimum. The minimum value is positive since c2 w + N (w) = c2 w + ((1 - )c1 - c2 )w + ED [2 c1 D + h1 (w - D)+ + b1 (w - D)- ] (1 - )(c1 + c2 )w + ED [b1 (w - D)- ] 0. The first inequality is true because we drop two non-negative terms. The second inequality depends on whether w is negative or not. If w 0, the second inequality is obvious. If w < 0, the second inequality is true because we get c2 w + N (w) (1 - )(c1 + c2 )w - b1 w + ED [D] 0 by assumptions (A2) and (A5). 22 QED Appendix 2
In this appendix, we study the problem where both overtime production and premium freight are viable options. We follow the previous proof but add additional comments or proofs when necessary. In this problem, the manager must actually make three decisions: how much to produce at stage 1, how much to produce during overtime at stage 2, and how much to produce during regular production at stage 2. Now, if stage 1 orders more than stage 2 has on hand, stage 2 must fill the shortage with some combination of overtime production and/or premium freight shipments. Define a new variable z2,t = the amount produced with overtime production at stage 2 during time t. Again, the inventory decisions take place after demand is experienced at stage 1. The manager must decide the inventory position at stage 1, y1,t+1 , the overtime production quantity at stage 2, z2,t , and the inventory position at stage 2, y2,t+1 . As before, stage 2 begins overtime with x2,t - (y1,t+1 - x1,t ) units on hand; stage 2 then produces z2,t units during overtime, bringing the inventory level up to x2,t - (y1,t+1 - x1,t ) + z2,t . If this quantity is negative, premium freight must be used to fill the remaining shortage incurring linear (cp ) and fixed (Kp ) costs. Note that y1,t+1 x1,t , z2,t 0, and y2,t+1 (x2,t - (y1,t+1 - x1,t ) + z2,t )+ . When both options are viable, we require three additional assumptions. First, we modify assumption (A5) slightly. Second, to simplify the analysis, we assume that the fixed cost for overtime production is not less than the discounted fixed cost for premium freight and that the per unit cost of overtime is not more than the discounted per unit cost of premium freight plus regular production at stage 2. Similar results hold when these inequalities are reversed. We label these assumptions as: (A5) b1 ((1 - )c1 + cp ) and h2 h1 + (1 - )c1 . (A6) Ko Kp (A7) co (cp + c2 ) Here we develop similar cost functions to those of Section 2, using the same notation where possible. g1 (x1 , y1 , x2 , y2 , z2 , D) c1 (y1 - x1 ) + Ko (z2 ) + co z2 + h2 (x2 - (y1 - x1 ) + z2 )+ +Kp ((x2 - (y1 - x1 ) + z2 )- ) + cp (x2 - (y1 - x1 ) + z2 )- 23 +c2 (y2 - (x2 - (y1 - x1 ) + z2 )) + h1 (y1 - D)+ + b1 (y1 - D)- with y1 x1 , z2 0, and y2 (x2 - (y1 - x2 ) + z2 )+ . Again, we move the -c1 x1 term back to get: g2 (x1 , y1 , x2 , y2 , z2 , D) (1 - )c1 y1 + 2 c1 D + Ko (z2 ) + co z2 + h2 (x2 - (y1 - x1 ) + z2 )+ +Kp ((x2 - (y1 - x1 ) + z2 )- ) + cp (x2 - (y1 - x1 ) + z2 )- +c2 (y2 - (x2 - (y1 - x1 ) + z2 )) + h1 (y1 - D)+ + b1 (y1 - D)- under the same restrictions. Substituting system variables, we get: g3 (x1 , y1 , xs , ys , z2 , D) (1 - )c1 y1 + 2 c1 D + h1 (y1 - D)+ + b1 (y1 - D)- +Ko (z2 ) + (co - c2 )z2 + h2 (xs - y1 + z2 )+ +Kp ((xs - y1 + z2 )- ) + cp (xs - y1 + z2 )- - c2 xs +c2 ys with y1 x1 , z2 0, and ys y1 + (xs - y1 + z2 )+ = max{y1 , xs + z2 }. We can rewrite g3 (·) as g3 (x1 , y1 , xs , ys , z2 , D) = L1 (y1 , D) + L2 (y2 , xs , z2 ) + c2 ys where L1 (y1 , D) represents the terms on line (7) and L2 (y2 , x2 , z2 ) represents the terms on lines (8) and (9). At this point, our fully constrained optimal cost function is f (x1 , xs ) = min ED [g3 (x1 , y1 , xs , ys , z2 , D) + f (y1 - D, ys - D)] . (7) (8) (9) ys max{y1 ,xs +z2 },z2 0,y1 x1 Again, to solve this equation we relax some constraints. First, we drop the constraint that y1 x1 . Second, we relax the constraint on the system inventory position so that ys xs . For later reference, we label the relaxed assumptions as: (R1) y1 x1 . (R2) ys max{y1 , xs + z2 } ys xs . After relaxing the constraints, our cost per period becomes gr (x1 , y1 , xs , ys , z2 , D) L1 (y1 , D) + L2 (y1 , xs , z2 ) + c2 ys 24 with z2 0 and ys xs . The function gr (·) can be shown to be non-negative by analysis similar to Lemma 1 and we can thus use the same result from Bertsekas (1995, page 137)
for the optimal cost function fr . fr (xs ) = ys xs ,z2 0,y1 ys xs ,z2 0,y1 min ED [gr (x1 , y1 , xs , ys , z2 , D) + fr (ys - D)] {ED [L1 (y1 , D)] + L2 (y1 , xs , z2 ) + c2 ys + ED [fr (ys - D)]} (10) = min Now notice that y1 and z2 have no effect on either ys or the cost to go, ED [fr (ys - D)]. Thus,
fr (xs ) = ys xs ys xs min z2 0,y1 min {ED [L1 (y1 , D)] + L2 (y1 , xs , z2 )} + c2 ys + ED [fr (ys - D)] = min {m(xs ) + c2 ys + ED [fr (ys - D)]} (11) where m(xs ) = minz2 0,y1 {ED [L1 (y1 , D)] + L2 (y1 , xs , z2 )}. Again, finding the optimal inventory policy for stage 1 has become a myopic problem that depends only on y1 and z2 . Now consider m(xs ) under two cases, when stage 1 does not order more than the system inventory on hand (y1 xs ) and when stage 1 does order more than the system inventory on hand (y1 > xs ). In the first case, we get that L2 (y1 , xs , z2 ) = Ko (z2 ) + (co - c2 )z2 + h2 (xs - y1 + z2 ) - c2 xs = Ko (z2 ) + (h2 + co - c2 )z2 + h2 (xs - y1 ) - c2 xs which is minimized when z2 = 0 and thus L2 (y1 , xs , z2 ) = h2 (xs - y1 ) - c2 xs when y1 xs . In the second case, there are four options.
K + c (y - x ) - c x p p 1 s 2 s Ko + Kp + (co - (cp + c2 ))z2 + cp (y1 - xs ) - c2 xs K + (c - c )(y - x ) - c x o o 2 1 s 2 s K + (h + c - c )z + h (x - y ) - c x o 2 o 2 2 2 s 1 2 s if z2 = 0 if 0 < z2 < y1 - xs if z2 = y1 - xs . if z2