European Journal of Operational Research 127 (2000) 483±506
www.elsevier.com/locate/dsw
Theory and Methodology
Decentralized inventory control in a two-level distribution system Jonas Andersson, Johan Marklund
*
Department of Industrial Engineering, Lund University, P.O. Box 118, 221 00 Lund, Sweden Received 1 September 1998; accepted 1 April 1999
Abstract We consider a model for decentralized inventory control in a two-level distribution system with one central warehouse and N non-identical retailers. All installations use continuous review installation stock
R; Q-policies for replenishing their inventories. Our approach is based on an approximate cost evaluation technique, where the retailers replace their stochastic lead-times by correct averages. By introducing a modi®ed cost-structure at the warehouse, the multi-level inventory control problem can be decomposed into N 1 single level sub-problems, one problem for each installation. The sub-problems are then solved in an iterative manner by a simple coordination procedure, which can be interpreted as a negotiation process. In the case of normally distributed demand we show that the procedure converges to a near optimal solution. To assess the quality of the involved approximation an upper bound for the relative cost increase of using the obtained solution is derived. We also provide a numerical study illustrating the performance of our approach. Ó 2000 Elsevier Science B.V. All rights reserved. Keywords: Supply chain; Inventory; Multi-echelon; Decentralization; Stochastic; Arborescent systems; Batch ordering
1. Introduction An important issue in managing a supply chain is to reduce the cost of capital tied up in inventory, while still maintaining a high service level towards the end customers. To succeed, the inventory decisions at dierent installations in the supply chain need to be eciently coordinated. For small systems where, typically, all installations belong to
* Corresponding author. Tel.: +46-46-222-4811; fax: +46-46222-4649. E-mail address:
[email protected] (J. Marklund).
the same organization and all relevant information about the system is readily available, the natural approach to achieve such coordination is to centralize all inventory decisions. For larger systems, especially when dierent organizations are involved, centralized control is often not a viable option. The diculties that arise are both technical and managerial. Technically it is a huge challenge to obtain and process all the relevant data for the entire system centrally. From a managerial point of view it is very dicult to centralize the inventory control if the basic organizational structure is decentralized. These problems are of course even more accentuated in supply chains where the
0377-2217/00/$ - see front matter Ó 2000 Elsevier Science B.V. All rights reserved. PII: S 0 3 7 7 - 2 2 1 7 ( 9 9 ) 0 0 3 3 2 - X
484
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
installations belong to independently owned companies. In this paper we focus on a model for highly decentralized inventory control in a two-level distribution system with one central warehouse and N non-identical retailers. It is especially suitable for decentralized organizations, where each installation is seen as a cost center responsible for the costs it can aect. The model is based on a simple approximate cost allocation scheme where the central warehouse is charged a penalty cost based on its inability to deliver on time to the retailers in the system. The approximation involved is closely related to the well known METRIC approach, see Sherbrooke (1968), where the stochastic lead-times perceived by the retailers are replaced by their correct averages. In other words, the decentralized model is based on limited information about the lead-time characteristics. A more technical description of our approach, reveals that it is an extension of the decentralized control procedure in Andersson et al. (1998), to the case of completely non-identical retailers. The outlay of the paper is as follows: The rest of this section is devoted to a brief literature review and a discussion of related models. Section 2 contains a detailed description of the inventory system. We discuss the speci®c assumptions made, and de®ne the cost functions used in the exact and approximate models, respectively. Section 3 focuses on how to solve the approximate problem by decomposing the entire system into N 1 coordinated single level problems. In Section 4 we derive an upper bound on a performance ratio relating the total cost obtained from the approximate solution, to the true minimum cost. To compute the bound we need to derive the lead-time distribution for each retailer. In Appendix A we present a method, which provides an accurate approximation of this distribution. In Section 5 we discuss a simple approximate expression for the expected lead-time perceived by a certain retailer. We also investigate in detail how to solve the generated sub-problems. Finally, we present some numerical results to illustrate the performance of our coordination procedure and the approximations involved. Section 6 concludes and summarizes our results.
1.1. Literature review A lot of research has been devoted to cost evaluation and optimization of stochastic multiechelon inventory systems under various control policies. For recent general overviews we refer to Axsater (1993), Federgruen (1993), Van Houtum et al. (1996) and Diks et al. (1996). A number of these existing models use control policies based on centralized information. An important example is echelon stock policies, where decisions at each site depend on information from all downstream installations. The echelon stock concept was ®rst introduced in the seminal work by Clark and Scarf (1960). For recent applications to divergent systems under continuous review see, for example, Chen and Zheng (1997) and Axsater (1997). In another important class of models the decisions made at each installation depend only upon local information. One common example of this type of control policy is an installation stock
R; Q-policy. In this policy the decisions to order from an upstream installation depend only upon the local inventory position. From this perspective many control methods are decentralized. However, in most of the existing models, even though the control variables are de®ned using local information, the determination of optimal control policies is done in a centralized manner. A model for joint optimization of reorder points in a multi-level system using installation stock
R; Q-policies is, for example, centralized from this perspective, see Axsater (1998), for an exact model when the demand is compound Poisson. To a large extent these `decentralized' models still suer from the technical and managerial diculties discussed above. Models for stochastic multi-echelon inventory control, which are decentralized also in terms of the way the optimal control policies are evaluated, represent a small but growing body of the literature. Lee and Whang (1994) provide an incentivecompatible scheme for a serial system based on the Clark and Scarf model, where the installations are managed as cost centers. The scheme is based on transfer payments between the dierent installations. The idea to achieve decentralization by designing new cost structures also governs the work
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
by Axsater (1995), which deals with a conceptual framework for decentralized inventory control of divergent systems. Andersson et al. (1998) focus on a model for decentralized control of a divergent distribution system, under the restriction of limited information availability. As mentioned above, their model is closely related to ours but restricted to the case where all retailers use an identical order quantity. Chen (1997) like Lee and Whang (1994) considers a serial system and bases the analysis on the Clark and Scarf model. Otherwise these two models are quite dierent. Instead of designing new cost structures Lee and Billington (1993) facilitate decentralized control by using service-level constraints for upstream installations. There also exist some earlier work by Muckstadt and Thomas (1980), followed up by Hausman and Erkip (1994). In both cases decentralized control policies for multi-echelon inventory systems with low-demand items in an emergency resupply model are considered. More precisely, they compare the use of single echelon models with service level constraints to the performance of a multi-echelon model for the same system. Although the main feature of our model is the decentralization aspect, an important ingredient in our approach is the quality of the imposed lead-time approximation. As indicated above, the idea to approximate the stochastic retailer leadtime with its mean originates from the METRIC model by Sherbrooke (1968). One of the most well known examples where this idea has been applied to a divergent batch ordering system is the model by Deuermeyer and Schwarz (1981). They consider a system similar to ours with the exceptions that in their case demand is Poisson and all retailers are identical. Their objective is to compute good approximations of the ®llrate at all the installations in the system. Apart from using the discussed lead-time approximation they also approximate the warehouse lead-time demand with a normal distribution. Based on a numerical study they conclude that the method performs quite well and closely estimates the exact ®llrates. An evaluation of how well the Deuermeyer±Schwarz approach works when used to approximate the costs of the system was done in Svoronos and Zipkin (1988), which investigates several re®ne-
485
ments of the Deuermeyer±Schwarz model. The most notable ones are that they estimate both the mean and variance of the retailer lead-time in order to approximate the retailer lead-time demand. They also use a mixture of two translated Poisson distributions (called an MTP distribution) to approximate the warehouse lead-time demand. Based on a numerical study, they conclude that their method is more accurate than the Deuermeyer±Schwarz model when it comes to evaluating the system costs, especially for situations where the standard deviation of the leadtime demand is large compared to its mean. Recently, Forsberg (1997) presented a method for exact cost evaluation of a slightly more general system than investigated in Svoronos and Zipkin (1988) where the retailers are allowed to be completely non-identical. A small numerical study veri®es that the Svoronos±Zipkin model performs quite well especially for low demand intensities. A comparison between our approximate model and the Deuermeyer±Schwarz method implies that our model should be more robust although not necessarily always better. The motive being that we invoke only one of the approximations used by Deuermeyer and Schwarz. Qualitatively relating our model to the one by Svoronos and Zipkin is more dicult and we have therefore performed a small numerical study, see Appendix B, for the special case where all retailers use the same order quantity (the most general case the Svoronos± Zipkin model can handle). In all these numerical examples our method produced near optimal policies of better quality than the Svoronos±Zipkin model. 2. Problem formulation 2.1. The inventory system As indicated above, the inventory system under consideration consists of one central warehouse and an arbitrary number of non-identical retailers, see Fig. 1. The customer demand takes place at the retailers, which replenish their stock from the
486
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
N Q
qi Fig. 1. The structure of the multi-echelon inventory system.
warehouse. Transportation times for such deliveries are assumed to be constant but additional delays may occur due to stockouts at the warehouse. The warehouse on the other hand replenishes its stock from an outside supplier, which provides constant delivery lead-times. The warehouse only allows for complete deliveries. This means that in case of stockouts no deliveries to a certain retailer will be executed until the whole order quantity is available at the warehouse. This is a plausible policy not uncommon in practice (see for example Deuermeyer and Schwarz, 1981), especially when there is a ®xed cost connected to each transport. The otherwise prevailing assumption in the literature on modeling divergent multi-level inventory systems is to use a delivery policy allowing for partial deliveries, i.e., units are shipped to the designated retailer as soon as they are available at the warehouse. Stockouts at both echelons are handled according to a ®rst-come®rst-served strategy and all facilities apply continuous review installation stock
R; Q-policies. This means that as soon as the inventory position at a certain installation ( inventory on hand + outstanding orders ) backorders) drops to or below the reorder point, R, an order of size Q is initiated to the upstream installation. The motives for studying this particular policy, even though it might not be the optimal one, are its wide practical application and its high generality. Concerning the cost structure we consider holding costs at both echelons and shortage costs proportional to the time until delivery at the retailers. For a further discussion of the assumptions de®ning our system, we need to introduce some notation:
Qi Q0 L0 li Li Li
number of retailers (i 1; 2; . . . ; N ), the size of a subbatch in number of units (we de®ne a subbatch to be the largest common divisor of all order quantities in the system), the batch size used by retailer i, expressed in units of Q, the batch size used by retailer i, expressed in number of units, Qi qi Q, warehouse batch size, in units of Q, constant lead-time for an order to arrive at the warehouse, transportation time between the warehouse and retailer i, lead-time for an order to arrive at retailer i, stochastic variable (s.v.), expected lead time for an order to arrive at retailer i
Li ELi .
We assume that all order quantities are ®xed and predetermined, which means that the only decision variables under consideration are the reorder points: Ri R0 RE 0 RA 0
reorder point for retailer i, continuous variable
i 1; 2; . . . ; N , warehouse reorder point, in units of Q, true optimal warehouse reorder point, in units of Q, optimal warehouse reorder point in the approximate model, in units of Q.
The assumption of predetermined and ®xed order quantities might appear as a signi®cant weakness of our model. However, we argue that this restriction is not as damaging as it might seem. Physical restrictions such as container size often leave little room for varying the order quantities. Furthermore, indications are that using deterministic lot sizing methods in a stochastic environment will only have a marginal eect on the expected cost, provided that the reorder points are adjusted accordingly, see for example Zheng (1992) and Axsater (1996). An appealing heuristic, suggested by several researchers, see for example Chen and Zheng (1997), is therefore to use a deterministic model to determine the order quantities. Near optimal reorder points, for the given set of order
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
quantities, can then be found by applying a stochastic model to the system. The motive for restricting the warehouse reorder point to be in units of Q, is that if the initial inventory position at the warehouse is an integer multiple of Q, it follows from the ordering policy at the retailers that one optimal value of R0 must also be an integer multiple of Q. We further restrain the analysis to values of R0 greater than or equal to )1, i.e. ÿQ units. The restriction means that each retailer order will be covered by items from a warehouse order initiated at the retailerordering instance or earlier. This limits the maximum stockout delay that a retailer order can experience to L0 . It also means that the lead-time for a certain retailer order is independent of the demand at the warehouse after the retailer order in question has been placed. Consequently, the leadtimes, Li
i 1; 2; . . . ; N , can from the retailers point of view be treated as exogenously generated stochastic variables. An important characterization of the system is the properties of the stochastic demand faced by the retailers. Initially we assume, as in Andersson et al. (1998), that the cumulative demand perceived by a single retailer can be modeled as a nondecreasing continuous stochastic process, with stationary and independent increments. In this case the inventory position at each retailer will be uniformly distributed over the interval Ri ; Ri Qi , see Browne and Zipkin (1991) and Zheng (1992). Later, we will focus on the special case when the cumulative customer demand follows a Wiener process with drift. A new feature of this problem formulation compared to the related problem investigated in Andersson et al. (1998) is that we allow each retailer to use an individual order quantity. This seemingly minor generalization signi®cantly enhances the practical value of the model but also makes the mathematical analysis more intricate. 2.2. Cost functions in the exact and approximate problems The expected cost for the entire system can be expressed in the following schematic way:
TCE C0
N X i1
487
CiE ;
1
where TCE is the expected total system cost per time unit, CiE the expected cost per time unit at retailer i and C0 is the expected warehouse cost per time unit. We also need to de®ne what will be denoted as the approximate problem or the approximate model for the remainder of this paper. In the exact model above the replenishment lead-time for retailer i, Li , is a stochastic variable. In the approximate model these stochastic lead-times (Li ; i 1; 2; . . . ; N are replaced by their expected values, Li ; i 1; 2; . . . ; N . The total cost in the approximate model can be expressed as follows: TCA C0
N X i1
CiA ;
2
where TCA is the expected total system cost per time unit in the approximate model and CiA is the expected cost per time unit at retailer i in the approximate model. 2.3. The retailer cost function Traditionally the inventory cost at an installation is divided into ordering costs, inventory holding costs, and some sort of shortage or backorder costs, see for example Hadley and Whitin (1963). Since the ordering cost is unaected by the choice of ordering point, Ri , we exclude this component from the retailer cost function. This leaves us with an expression evaluating the inventory holding costs and the backorder costs. For a certain choice of ordering point at the warehouse, R0 , the replenishment lead-time for retailer i in the approximate model (Li
R0 ) is constant. The expected cost per time unit is then given by (3) (see for example Zheng, 1992): CiA
Ri jLi
R0 h
1 Qi
Z
Ri Qi
Ri
EDi
Li
hi
y ÿ Di
Li pi
Di
Li ÿ y
i
dy;
3
488
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
where
x max
x; 0, hi the holding cost per unit and time unit at retailer i, pi the shortage cost per unit and time unit at retailer i, or, equivalently, according to LittleÕs formula, per average number of backorders, and Di
t is the customer demand at retailer i during the time period t, (s.v.). It is worth stressing that the expected leadtimes, Li , are dierent for dierent retailers. When modeling a system with non-identical retailers this property becomes crucial and we deal with this issue both in Appendix A and in Section 5. In the exact model where the replenishment lead-time for retailer i, Li , is stochastic, we can obtain the expected cost by conditioning on the lead-time. In practice this expression is dicult to evaluate since the distribution of Li is hard to obtain. 2 1 CiE
Ri jLi
R0 ELi
R0 4 Qi
Z
Ri Qi
Ri
EDi
Li
3 hi
y ÿ Di
Li pi
Di
Li ÿ y jLi dy 5:
4
Note that expression (4) is only valid for exogenously generated lead-times, that is, when R0 Pÿ 1 (see Andersson et al., 1998). Also note that expression (4) holds because the warehouse only allows for deliveries of complete batches, Qi , to retailer i.
2.4. The cost function at the central warehouse The fact that we allow each retailer to have dierent order quantities, Qi , together with the delivery policy of only shipping complete retailer batches from the warehouse, leads to the occurrence of reserved units. A reserved unit is ordered by a retailer and available at the warehouse but it is not yet shipped. The reason for this is that there is not enough inventory on hand at the warehouse to ®ll the entire retailer order in question, i.e., the reserved units must wait for the arrival of deliveries from the external supplier before they can be shipped. Due to the existence
of reserved subbatches at the warehouse, the inventory position ( inventory on hand + outstanding orders ) backorders) is not uniformly distributed between R0 1 and R0 Q0 . To handle this complication we utilize an idea used in Lee and Moinzadeh (1987) and treat the reserved units separately. This is done by de®ning a modi®ed inventory position, y0 inventory on hand + outstanding orders ) backorders ) reserved units, which is uniformly distributed over the interval R0 ; R0 Q0 . The cost function at the central warehouse C0 can then be expressed as follows: C0
R0
R0 Q0 h0 Q X ED0
L0
y0 ÿ D0
L0 Q0 y R 1 0
0
h0 QEBr0 h0 Q
EI0 EBr0 ;
5
where y0 is the modi®ed inventory position at the warehouse expressed in units of Q, h0 the holding cost per unit and time unit at the warehouse, D0
t the retailer demand at the warehouse during the time period t expressed in units of Q, Br0 the number of reserved subbatches at the warehouse in steady state, and I0 is the inventory on hand at the central warehouse in steady state, expressed in units of Q, excluding the reserved subbatches Br0 . Note that the only cost component considered at the warehouse is the inventory holding cost. From the systems perspective shortage costs only occur when customer demand is backordered at a retailer, not when a retailer, order is delayed at the warehouse.
3. Decomposition and coordination In this section we will discuss how to solve the approximate problem by using a decomposition technique together with an iterative coordination procedure. The approach that we use is based on the one in Andersson et al. (1998), but it is modi®ed to handle our situation with non-identical retailers using individual order quantities and complete deliveries from the warehouse.
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
489
3.1. Decomposition of the approximate problem We would like to transform the approximate problem, which is a complicated multi-level inventory problem, into N 1 conceptually simple single-level problems coordinated by using a limited amount of information. The basic idea is that each installation must use a cost function, which re¯ects the impact that a certain choice of its reorder point has on the total system cost. Obviously, the retailer cost function, CiA , ful®lls these requirements in its present form. Consequently we de®ne the N retailer problems in the following way: min CiA
Ri jLi ; Ri
i 1; 2; . . . ; N :
6
The optimal solution to (6), given a certain value of Li , will be denoted Ri . Note that since Ri is a function of Li the proper denotation would be Ri
Li ), for notational convenience we disregard this when there is no loss of clarity. Turning to the situation at the central warehouse, we can conclude that a certain choice of reorder point, R0 , will aect the cost at the retailer level, and thereby the total cost through the expected lead-times, Li . We capture this mechanism by including the marginal cost for lead-time change in the cost function, C~0
R0 , used by the warehouse (see Eq. (7)). CiA
Ri jLi bi
li
the minimum cost for retailer i in the approximate model given Li , shortage cost per unit and time unit, for backlogged units at the warehouse ordered by retailer i, bi
dCiA
Ri jLi =dLi
1=li , expected demand per time unit at retailer i, expressed in number of units.
min C~0
R0 R0
min C0
R0 R0
min C0
R0 R0
N X dCiA
Ri jLi
Li
R0 ÿ li dLi i1
N X bi li
Li
R0 ÿ li : i1
7
Fig. 2. The structure of the decomposed approximate problem.
Note, in Eq. (7), Li
R0 is a function of R0 while Li is a ®xed parameter. The interaction between the warehouse problem and the N retailer problems is illustrated in Fig. 2. We can conclude that the coordination of the warehouse problem and the N retailer problems is facilitated through the information conveyed by the parameters bi and Li (i 1; 2; . . . ; N ). We can interpret bi as a transfer cost, which redistributes the total shortage cost between the warehouse and the retailers according to the principle that each installation should carry its own costs. 3.2. The coordination procedure ± general case To ®nd candidate solutions to the decomposed problem, de®ned in the previous section, we can apply a simple iterative procedure, which solves the warehouse problem and the N retailer problems in a sequential manner. The procedure was ®rst presented in Andersson et al. (1998) and is easily described from Fig. 2. First, set the expected lead-times, Li
i 1; 2; . . . ; N to some initial values in the correct intervals li ; li L0 . Given these expected lead-times all the retailer problems can easily be solved independently of each other, rendering us a set of shortage costs b fb1 ; b2 ; . . . ; bN g. Using these shortage costs, it is fairly easy to solve the warehouse problem (7). The new value of R0 will then determine a new set of expected lead-times for which the retailer problems can be resolved and so on. The successive updates of the warehouse and retailer problems continue until a stationary solution (or equivalently a Nash equilibrium) is found, provided one exists. A stationary solution for the decomposed problem (Rs0 , Rs fRs1 ; Rs2 ; . . . ; RsN g) is de®ned as a solution, which does not change during two successive iterations. From a managerial
490
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
point of view the coordination procedure can be interpreted as a negotiation process, where the warehouse will reimburse each retailer for the cost it suers due to late deliveries. The negotiations and successive updates continue until a stationary solution is found. The only information that has to be conveyed from a certain retailer i to the central warehouse is the current shortage penalty cost for late deliveries, bi . A weakness with the suggested procedure is that for a general demand process satisfying the conditions discussed in Section 2, we cannot be sure that any stationary solution exists. Furthermore, even if one does exist there is no guarantee that the procedure will ®nd it, cycling could very well occur. Another diculty is that even if we ®nd a stationary solution, this is not necessarily the optimal solution to the decomposed problem.
retical problems will diminish when the probability of negative demand is close to zero. That is, when li t is relatively large compared to ri t1=2 . Now, if the cumulative lead-time demand is normally distributed we can express the cost function at retailer i in terms of the standard normal density function u and the standard normal cumulative distribution function U, see Andersson et al. (1998) or Silver and Peterson (1985): Qi Ri ÿ li Li
hi pi CiA
Ri jLi hi 2 " ! !# r2i Li Ri ÿ li Li Ri ÿ li Li Qi H ÿH ; 1=2 1=2 2Qi ri Li ri Li
8 where H
v
v2 1
1 ÿ U
v ÿ vu
v:
3.3. The coordination procedure ± the case of normally distributed demand As we have seen above, we cannot guarantee the usefulness of the coordination procedure for ®nding the optimal solution to the approximate problem in the general case. Fortunately, there exist at least one special case where we can show that the procedure will enable us to ®nd the optimal solution we are looking for. This occurs when the cumulative lead-time demand Di (t) at every retailer i is normally distributed with mean li t and standard deviation ri t1=2 . A nice property worth stressing is that the entire class of demand processes de®ned in Section 2, will render a cumulative lead-time demand which will be approximately normally distributed, provided that the lead-time is long enough. This is a direct consequence of the central limit theorem, see also Andersson et al. (1998). However, a drawback with the normal distribution is that it allows for negative demand to occur. This is discouraging since one of the assumptions made in Section 2 was that the demand process should be non-negative. The consequences are that the retailer inventory position is no longer exactly uniformly distributed over Ri ; Ri Qi , and that the lead-time distribution derived in Appendix A is approximate. However, these theo-
9
The ®rst order optimality condition for the retailer problem (6) given a certain expected lead-time, Li , can be expressed as follows: oCiA
Ri jLi hi ÿ
hi pi oRi " ! !# 1=2 ri Li Ri ÿ li Li Ri ÿ li Li Qi G ÿG 0; 1=2 1=2 Qi ri Li ri Li
10 where G
v
Z
1 v
x ÿ vu
x dx
u
v ÿ v
1 ÿ U
v:
11
By using the optimality condition above we can deduce the expression for the derivative of the minimum cost at retailer i with respect to the expected lead-time. dCiA
Ri jLi
hi pi dLi " ! !# r2i Ri ÿ li Li Qi Ri ÿ li Li U ÿU : 1=2 1=2 2Qi ri Li ri Li
12
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
The key property, which assures convergence of the coordination procedure in the case of normally distributed demand, is the concavity of CiA
Ri jLi . A necessary but not very restricting condition for this property to hold is that the unit costs at retailer i must satisfy; pi P hi , see Andersson et al. (1998). Proposition 1. Given that pi P hi , CiA
Ri jLi is a concave function in Li . A complete analysis of the relationship between the stationary solutions and the optimal solution to the problem in question, together with a thorough investigation of the behavior of the coordination procedure, can be found in Andersson et al. (1998). We will here only summarize the key observations. First of all, in the decomposed model the warehouse minimizes a cost function, which is an upper bound to the total cost in the approximate model. This follows from the expressions below together with the concavity of CiA
Ri jLi . Remember that Ri is a function of Li . De®ne C~iA
Ri jLi
R0 C A
R jLi
Rs i
i
i
i
0
dC A
R jL
Rs i i si 0
Li
R0 ÿ Li
Rs0 dLi
R0 A P C
R jLi
R0 ; ~ A C0
R0 TC
N X 1
C~iA
Li
R0 P TCA :
13
14
~ A will render the same Note that minimizing TC optimal value of R0 as minimizing C~0 (see (7)), since CiA
Ri jLi
Rs0 is a constant in (13). We can also see that in a stationary solution where ~ A is equal to TCA . Based on these R0 Rs0 , TC observations, Proposition 2 can be derived, see Andersson et al. (1998). Proposition 2. The optimal solution to the approximate problem must be a stationary solution to the decomposed problem.
491
The set of stationary solutions can easily be determined by using the coordination procedure outlined above within a larger framework. The basic logic of this framework rests on two fairly easily validated observations concerning the dynamic relationships between the reorder point at the warehouse, R0 , and the variables bi and Li for i 1; 2; . . . ; N . From the expressions for Li in Appendix A, it can be shown that Li
i 1; 2; . . . ; N are non-increasing functions in R0 . With this in mind, we can see from Eq. (7) that R0 is a non-decreasing function in
b1 ; . . . ; bN . Now, suppose that all the expected lead-times, Li , are initially set to their smallest values, which means that Li li for i 1; 2; . . . ; N . Due to the concavity of CiA
Ri jLi and the fact that R0 is a non-decreasing function in bi , the coordination procedure will render us a stationary solution, (Ru0 ; Rl ), where Ru0 is an upper bound for all stationary values of R0 . At the same time the vector Rl represents a lower bound for the reordering point at each retailer. The procedure can then be restarted with the initial lead-times set to their largest values; Li li L0 for all i 1; 2; . . . ; N . The iterative procedure will this time present us with a stationary solution (Rl0 ; Ru ) where Rl0 constiu l tutes a lower bound for RA 0 . If R0 R0 then the optimal solution to the approximate problem is found. If this is not the case, we need to investigate the ®nite number of solutions in the interval Rl0 ; Ru0 . Remember that each value of R0 , through the expected lead-times Li
R0 , uniquely determines the optimal retailer reorder points Ri
Li
R0 for all i. An interesting perspective, which emphasizes the usefulness of our method for decentralized control, arises if we focus our attention on the shortage penalty cost bi . It is clear that if we know the optimal values of bi (for all i), it is easy to calculate the optimal solution to the approximate problem. In a practical situation, where each retailer minimizes its cost according to (6) and the prime objective at the warehouse is to minimize (7), applying the optimal bi Õs will force the system to operate at the optimal solution to the approximate model. In order to achieve a `fair' sharing of costs, in the sense that all parties will be satis®ed, the warehouse must physically reimburse each retailer for late deliveries according to bi . The actual
492
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
cost at thePwarehouse per time unit will then be N A C0
RA cost at 0 1 bi li
Li
R0 ÿ li and the P N ÿ retailer i amounts to CiA
Ri jLi
RA 0 1 bi li A
Li
R0 ÿ li . A similar transfer payment scheme is also suggested in Lee and Whang (1994). The incentive for the involved parties to participate and accept this cost-sharing scheme is the knowledge that it will lead to a near optimal solution for the entire system. Consequently, we assume that all installations are unsel®sh and without any inclination to try and gain any personal advantages by gaming. At ®rst glance this might seem as an unrealistic assumption. However, in a supply chain where all actors are committed to a long-term relationship, possibly as the only mean to survive, cheating can be very costly. We therefore argue that the assumption of a system where the main objective for all installations is the well being of the entire system is not too far-fetched. Our model should therefore be a useful tool for a supply chain manager whose purpose is to ®nd ways to improve the cooperation and coordination between the dierent installations in the chain. 3.4. An alternative optimization procedure A shortcoming with the optimization procedure discussed in the previous section is that if the gap between Ru0 and Rl0 is large, we basically have to solve the problem by enumeration. It is worth mentioning that we have not encountered any such situation while running test problems, still from a theoretical point of view it might very well occur. In this section we will therefore present an alternative way of ®nding the optimal solution to the approximate problem with better convergence properties. The drawbacks are that this method is conceptually more complex and also requires more information to be conveyed from the retailers to the warehouse. The basic idea is to capitalize on the concavity of CiA
Ri jLi , and successively generate a price schedule for the shortage penalty cost at the warehouse related to a certain retailer. This means that we approximate CiA
Ri jLi with a piecewise linear function, C~iA
Ri jLi , instead of just a linear function as before, see (13). Subsequently, in each
iteration the shortage penalty cost bi is no longer just one constant but a descending staircase function over the interval li 6 Li 6 li L0 . By using Fig. 3 we can give a more explicit description of how the algorithm works. In the ®rst step when we consider the N retailer problems we only know the extreme values of the replenishment lead-times for each retailer, i.e. li and li L0 . By evaluating the retailer cost for these two lead-times, respectively, we can calculate the ®rst shortage penalty cost as follows (see Fig. 3 for illustration): ÿ ÿ CiA Ri jli L0 ÿ CiA Ri jli 1 ; bi L0 li
15 l i 6 L i 6 li L 0 : Using this function bi we can solve the warehouse problem and obtain a corresponding set of expected lead-times L1
L11 ; . . . ; L1N . Based on this new information the retailer problems can be resolved and the minimum cost for retailer i, CiA
Ri jL1i , is then used in order to determine the new function bi (see Fig. 3 for illustration): 8 ÿ A 1 > C R j L ÿ CiA Ri jli 1 > i i i > > > b1i ; > > li L1i ÿ li > > < 1 li 6 Li 6 Li ;
16 bi ÿ > > CiA Ri jli L0 ÿ CiA Ri jL1i > 1 > > ; b2i > > li > li L0 ÿ L1i > : 1 Li < Li 6 li L0 :
Fig. 3. Illustration of how CiA
Ri jLi is used to successively generate and improve the accuracy of the shortage cost function bi . In iteration 1 the function corresponds to the slope bi and in iteration 2 it consists of the two slopes b1i and b2i .
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
This new penalty cost function can be used to resolve the warehouse problem etc. The algorithm stops when the solution does not change in two consecutive iterations. Before we show that the algorithm is guaranteed to ®nd the optimum solution for the apA proximate problem (RA 0 ; R ) we need to give a general mathematical description of the cost functions involved. Assume that bi consists of K steps, i.e., bi
b1i ; b2i ; . . . ; bKi , where b1i is only valid over the interval L0i li ; L1i and bKi is only valid over ; LKi li L0 etc. When Linÿ1 6 Li 6 Lni ; LKÿ1 i n 1; 2; . . . K, it follows that ( nÿ1 X ÿ A A ~ ~ bj Lji ÿ Ljÿ1 C R jLi C R jli li i i
i
i
i
j1
bni Li ÿ Lnÿ1 i
)
i
6 CiA Ri jLi ;
493
~ A TC ~ A
RA TCA
RA min TCA : min TC 0 0 The last equality follows from the fact that ~ A
R0 constitutes a lower bound to TCA (R0 ) for TC every R0 , and that this lower bound is made tighter in every iteration when bi for i 1; . . . ; N is updated. Since R0 is a discrete variable the algorithm will ®nd the optimum solution within a ®nite number of steps. It is rather complicated to determine a `fair' physical reimbursement from the warehouse to each retailer using the staircase function bi . For practical purposes we therefore recommend that the optimization algorithm discussed in this section is used only for ®nding the optimal solution to the approximate problem. We can then apply the shortage penalty cost de®ned in Section 3.3 to determine an ecient cost-sharing scheme for the system.
17
C~0
R0 C0
R0
N X i1
bni
(
li
nÿ1 X j1
) nÿ1 Li ÿ Li ;
~ A
R0 C0
R0 TC
N X i1
bji Lji ÿ Ljÿ1 i
4. Error bounds
18
C~iA Ri jLi
R0 6 TCA
R0 :
19
From (17)±(19) we can see to that minimizing the warehouse cost function C~0
R0 is equivalent to minimizing the total cost function in the decom~ A
R0 . It also follows that both posed model TC ~ ~ C0
R0 and TCA
R0 for each R0 represent lower bounds to the total cost in the approximate model TCA (R0 ). An important observation concerning the convergence properties of the algorithm is that if two successive iterations produce the same lead-time vector L this means that C~iA
Ri jLi CiA
Ri jLi for all i 1; . . . ; N . Consequently, we can conclude that
In this section we derive a performance ratio for the approximate problem, which is an upper bound on the maximum approximation error. The bound is valid when the cumulative demand at each retailer follows a non-decreasing stochastic process with stationary and independent increments, as discussed in Section 2. The approach we are using is mainly based on the theoretical results presented in Andersson et al. (1998). However, by using the lead-time distribution derived in Appendix A we are able to get a much tighter bound. When the demand process is modeled as a Wiener process with drift, the performance ratio is no longer a bound but a reasonable quality measurement, provided that the probability of negative demand is small. An interesting interpretation of the error bound is that it re¯ects the relative cost of reduced information availability. In our case this means the maximum cost of using the average lead-time instead of the entire lead-time distribution when deciding on the optimal policy parameters. An important property of the retailer cost function in the approximate model is that it is
494
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
convex in the expected lead-time for ®xed values of the reorder point. Proposition 3. CiA
Ri jLi is a convex function in Li for every given value of Ri . We omit the proof and refer to Andersson et al. (1998). Proposition 3 holds for all stationary demand processes with independent and non-negative increments. The convexity of CiA
Ri jLi enables us to relate the total cost in the approximate model to the total cost for the system. The results are summarized in Propositions 4 and 5 below. However, before we look at these ®ndings we need to de®ne some additional notation. RE i
R0
RA i
R0
ÿ CiA RA i
R0
ÿ CiE RE i
R0
true optimal reorder point for retailer i given a certain reorder point R0 at the warehouse, RE
R0 E
RE 1
R0 ; . . . ; RN
R0 , optimal reorder point for retailer i in the approximate model given a certain reorder point R0 at the warehouse, A RA
R0
RA 1
R0 ; . . . ; RN
R0 , the minimum cost at retailer i in the approximate model given a certain warehouse reorder point, R0 , ( CiA
Ri jLi
R0 in previous notation), the minimum cost at retailer i in the exact model given a certain warehouse reorder point R0 .
ÿ ÿ E E Proposition 4. CiA RA i
R0 6 Ci Ri
R0 : Using Proposition 4 it is fairly easy to obtain the following. Proposition 5. ÿ ÿ E E A A TCA RA 0 ; R
R0 6 TCE R0 ; R
R0 : The performance ratio, r, relates the minimum total system cost when the optimal solution to the
approximate problems is used, to the minimum total cost for the exact model. This means that r can be expressed in the following way: ÿ ÿ E E E A A r TCE RA 0 ; R
R0 =TCE R0 ; R
R0 :
20 The expression for r is not very practical since the denominator involves the true optimal solution E
RE 0 ; R , which is unknown to us. However, by using Proposition 5 it is easy to construct an upper bound for r, which can be evaluated with the available information. Proposition 6. The performance ratio r is bounded from above by the following expression: r 6 ^r
C0
RA 0
PN
i1
ÿ A A ELi
RA CiA RA i
R0 jLi
R0 0
A A TCA
RA 0 ; R
R0
:
21 Proof. The result follows directly from Proposition 5 together with the de®nition of TCE : In order to evaluate the bound on the performance ratio we must know the distribution of Li
RA 0 . An approximate method for obtaining this rather elusive distribution is presented in Appendix A.
5. Computational aspects In this section we will discuss the optimization of the decomposed approximate problem in more detail. We will also introduce a simple and intuitive approximate expression for the expected leadtime, Li . From a computational point of view this approximation is much simpler than the method described in Appendix A. Finally, we will present some numerical results, which illustrate the performance of the dierent approximations compared to simulated results.
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
5.1. Optimization of the decomposed approximate problem The structure of the decomposed approximate problem is illustrated in Fig. 2. We will here investigate how the subproblems can be evaluated when the cumulative demand at each retailer is normally distributed. We will focus our attention on the sub-problems related to the optimization procedure discussed in Section 3.3 and only brie¯y comment what minor changes must be done to handle the alternative procedure presented in Section 3.4. Consider the retailer problem (6) for an arbitrary retailer i given a certain lead-time, Li ; we know that the cost function CiA
Ri jLi is convex in Ri (see Zheng, 1992). Consequently, the retailer problem is eciently solved by a simple one-dimensional search procedure. When the optimal reorder point, for the current value of Li , Ri
Li is found, we can easily obtain the corresponding value of bi
dCiA
Ri jLi =dLi
1=li from expression (12). If the alternative optimization procedure is used the staircase function bi is determined as described in Section 3.4. Turning to the warehouse problem (7) we want ~ 0 with respect to to minimize the cost function C
R ~ R0 . To evaluate C
R0 we need to compute the number of reserved subbatches at the warehouse, EBr0 . Through LittleÕs formula EBr0 can be expressed as a function of the mean lead-times, Li
R0 (for i 1; 2; . . . ; N ), and the expected number of backordered subbatches at the warehouse, EB0 : N X li
Li ÿ li ÿ EB0 ; E Br0 Q i1
EB0
R0 Q0 1 X ED0
L0
D0
L0 ÿ y0 : Q0 y R 1 0
22
~ 0 given The optimal R0 , which minimizes C
R a set of shortage costs (b1 ; . . . ; bN ), is denoted by ~ 0 is that R0 . A complication when optimizing C
R it is not necessarily convex in R0 . However, it does possess a certain degree of regularity, which can be capitalized on to restrict the number of values of R0 that need to be evaluated in search ~ 0 of R0 . The idea is to use the fact that C
R consists of three dierent components EI0
R0 , EB0
R0 and EBr0
R0 (see (5), (7) and (22)). By using what we know about the behavior of the ®rst two components, and by bounding the in¯uence of the last one, we are able to ®nd conditions that de®ne dynamic upper and lower bounds on R0 . Lemma 1. R0 6 Ru0 , where Ru0 is the smallest value of R0 satisfying the conditions h0
EI0
Ru0 1 ÿ EI0
Ru0 max
bi
EB0
Ru0 1 ÿ EB0
Ru0 P 0; i
24 ~ 0 : ~ u ÿ Q
h0 max
bi EBr
Ru P min C
R C
R 0 0 0 u i
0
To compute the expected lead-time for retailer i, Li
R0 , we can use the method in Appendix A. We also need to ®nd the distribution of D0
L0 by convoluting the distributions of the warehouse demand emanating from each retailer.
R0 6 R0
25
Proof. De®ne DI0
k E I0
Ru0 k ÿ E I0
Ru0 ; DB0
k E B0
Ru0 k ÿ E B0
Ru0 ; DBr0
k E Br0
Ru0 k ÿ E Br0
Ru0 ; DLi
k Li
Ru k ÿ Li
Ru : 0
23
495
0
It is well known that EI0
R0 is an increasing convex function and that EB0
R0 is a decreasing convex function of R0 , see Zheng (1992) and Zipkin (1986). Consequently, DI0 (k) > 0 and DB0 (k) < 0. Furthermore, from the expressions in Appendix A it can be shown that Li
R0 is a nonincreasing function of R0 . Using these properties together with (22) and the fact that EBr0
R0 is a non-negative function of R0 it follows that
496
J. Andersson, J. Marklund / European Journal of Operational Research 127 (2000) 483±506
~ lb ÿ Q
h0 min
bi EBr
Rlb P min C
R ~ 0 : C
R 0 0 0
~ u k ÿ C
R ~ u C
R 0 0 ÿ
h0 Q DI0
k DBr0
k
N X i1
i
bi li DLi
k
28
N X ÿ P h0 Q DI0
k DBr0
k max
bi li DLi
k i
Q h0 DI0
k max
bi DB0
k
i1
i
Q h0 max
bi DBr0
k i
P Q h0 DI0
k max
bi DB0
k
R0
i
P kQ h0 DI0
1 max
bi DB0
1 i
ÿ Q h0 max
bi E Br0
Ru0 i
Pÿ Q h0 max
bi E Br0
Ru0 for all k P 0; i
26 where the last inequality follows from condition (24). We can conclude that when (25) is satis®ed, ~ 0 : R0 is the solution to minR0 6 Ru0 C
R It can be shown that Lemma 1 also holds for the alternative optimization procedure when ~ 0 is de®ned by (18). The only dierence is that C
R bi is replaced by bi
li , which denotes the value of the function bi for Li li . In the same way as Lemma 1 provides us with two conditions, which can be used to identify an upper limit for the optimal value of R0 , Lemma 2 below allow us to determine a lower bound for R0 . Lemma 2 can be proven using the same technique as in the proof of Lemma 1. lb Lemma 2. R0 P Rlb 0 , where R0 is the largest value of R0 satisfying the conditions: lb h0
EI0
Rlb 0 ÿ 1 ÿ EI0
R0 lb min
bi
EB0
Rlb 0 ÿ 1 ÿ EB0
R0 P 0;
For the alternative optimization algorithm in ~ 0 is de®ned by (18), Lemma Section 3.4, where C
R 2 will still hold provided that bi in (27) and (28) is replaced by bi
li L0 . Applying Lemma 1 and Lemma 2 we can device an ecient method for ®nding R0 based on a successive search procedure originating from a suitable starting value, R^0 . A reasonable starting value is for example the optimal solution to the convex problem: ^ 0 Q h0 EI0 min
bi EB0 : min C
R
i
ÿ Q h0 max
bi E Br0
Ru0
i
Rlb
