Policies for inventory/distribution systems: The effect of centralization vs. decentralization

UNCORRECTED PROOF Int. J. Production Economics ](]]]])]]]–]]] Policies for inventory/distribution systems: the effect of centralization vs. decentralization B. Abdul-Jalbar a , J. Guti! errez a , J. Puerto b , J. Sicilia a, * a Dpto. de Estad ! istica, Facultad de matematicas, I.O. y Computaci! on. Universidad de La Laguna, Avenida Astrofisico F. Sanchez, s/n, La Laguna, Tenerife 38271, Spain b Dpto. de Estad ! istica e Investigaci! on Operativa. Universidad de Sevilla, Sevilla, Spain Abstract This paper concerns with a multi-echelon inventory/distribution system considering one-warehouse and N-retailers. The retailers are replenished from the warehouse. We assume that the demand rate at each retailer is known. The problem consists of determining the optimal reorder policy which minimizes the overall cost, that is, the sum of the holding and replenishment costs. Shortages are not allowed and lead times are negligible. We study two situations: when the retailers make decisions independently and when the retailers are branches of the same firm. Solution methods to determine near-optimal policies in both cases are provided. Computational results on several randomly generated problems are reported. r2002 Published by Elsevier Science B.V. JEL 90B05; 90B30 Keywords: Inventory control; Inventory/distribution systems; Multi-echelon systems 1. Introduction The multi-echelon inventory/distribution systems represent a special category of inventories encountered in practice where several installations are involved. Due to their applicability in realworld situations, the multi-echelon systems have caught the researchers’ attention. A special type of such inventory systems deals with one-warehouse and N-retailers (e.g., a chain of stores supplied by a single regional warehouse). In this problem, the warehouse is the sole supplier of Nretailers. Customer demand occurs at each retailer at a constant rate. This demand must be met as it occurs over an infinite horizon without either shortages or backlogging. Orders placed by retailers generate demands at the warehouse. There is a holding cost rate per unit stored per unit time and a fixed charge for each order placed at the warehouse and at each retailer. The demand rates, holding unit costs, and setup costs are stationary and facility dependent. Delivery of orders is assumed to be instantaneous, that is, lead times are assumed to be zero. The goal is to find a policy with minimum or near-minimum long-run average cost. ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 3B2v7:51c GML4:3:1PROECO : 2593 Prod:Type:COM pp:1213ðcol:fig::NILÞ ED:JayashreeSanyasi PAGN: bmprakash SCAN: nil *Corresponding author. Tel.: +34-22-319190; fax: +34-22- 319202. E-mail address: [email protected] (J. Sicilia). 0925-5273/02/$ - see front matter r2002 Published by Elsevier Science B.V. PII: S 0925-5273(02)00361-4 UNCORRECTED PROOF This one-warehouse and N-retailers system was examined by Schwarz (1973) and he showed that the form of the optimal policy can be very complex; in particular, it requires that the order quantity at one or more of the locations varies with time even though all relevant demand and cost factors are time invariant. Thus, he considered the possibility of restricting the class of strategies, where the order quantity at each location does not change with time and he determined the necessary conditions of an optimal policy. Moreover, he provided a solution method for the one-warehouse and Nidentical retailers problem and suggested heuristic solutions for the general case. Schwarz (1973) proved that an optimal policy can be found in the set of ‘‘basic’’ policies. A basic policy is any feasible policy where deliveries are made to the warehouse only when the warehouse has zero inventory and, at least one retailer has zero inventory. Moreover, deliveries are made to any given retailer only when that retailer has zero inventory. In addition, all deliveries made to any given retailer between successive deliveries to the warehouse are of equal size. In particular, Schwarz (1973) introduced two classes of basic policies: myopic and single cycle policies and he also tested the near optimality of these policies using three lower bounds. A myopic policy is one which optimizes a given objective function with respect to any two stages and it ignores multi-stage interaction effects. Accordingly, the system one-warehouse and N-retailers is viewed as None-warehouse and one-retailer systems. A single cycle policy is one that is stationary and nested. A policy is said to be stationary if each facility always orders the same quantity at equally spaced points in time. A nested policy is one in which each time any stage orders, all of its successors also order. Graves and Schwarz (1977) performed a similar analysis for arborescent systems in which each stage obtains its supply from an unique immediate predecessor and supplies its output to a set of immediate successors. They reduced the class of admissible policies for stationary continuous-time infinite-horizon multi-stage production/inventory problems to find a good approximation to optimal policies, presenting a branch-and-bound algorithm to determine optimal single cycle policies for arborescent systems. They also examined the near-optimality of the myopic policies. Roundy (1985) showed that nested policies can have very low effectiveness in the worst case and he defined new classes of policies for the onewarehouse N-retailers problem: q-optimal integerratio and optimal power-of-two policies. He proved that for any data set, the effectiveness of q-optimal integer-ratio and optimal power-of-two policies is at least 94% and 98%, respectively. In this paper, we introduce near-optimal policies for inventory/distribution systems with one-ware- house and N-retailers considering an instantaneous demand pattern at the warehouse. We study two cases: if the warehouse and the retailers belong to the same firm (centralization), or if the warehouse and retailers belong to different firms (decentralization). Outside customer demand rates are assumed known and constant. Shortages and lead times are not allowed. At each stage, a fixed-order cost which is independent of the lot size and a holding unit cost are considered. The goal consists of determining the optimal policy with minimum overall cost both when there exists dependence and when not. We introduce a solution method to obtain the near-optimal plan in the case of independence or decentralization. This method allows us to know in advance the number of periods of the demand vector at the warehouse. Once this number is calculated, either the Wagner and Whitin (1958) algorithm or the Wagelmans et al. (1992) procedure for inventory systems with time-varying demand can be applied. On the other hand, when the Nretailers are branches of the same firm (centralization), we deal with the class of single cycle policies and we propose a branch and bound algorithm to determine the near-optimal plan. The outline of the remaining of this paper is divided into seven sections. In Section 2, we introduce the notation and terminology required to state the problem. Section 3 is devoted to the one-warehouse and N-retailers problem assuming that the retailers are independent of the warehouse. In such a situation, the problem becomes a ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 B. Abdul-Jalbar et al. / Int. J. Production Economics ](]]]])]]]–]]]2 PROECO : 2593 UNCORRECTED PROOF time-varying demand inventory system and a procedure to determine the number of periods at the warehouse is provided. Section 4 deals with the centralized situation, that is, when the retailers and the warehouse belong to the same firm. In this case, two different policies are suggested: the retailers can place their orders at a common replenishment time or at different replenishment times. In the former case, the solution can be obtained directly using an analytical approach. In the latter case, a solution method based on a branch and bound scheme is proposed. Section 5 presents a numerical example which is analyzed assuming that there is both centralization and decentralization among the warehouse and the retailers. Computational results are reported in Section 6. Finally, in Section 7, we present our conclusions and final remarks. 2. Terminology and problem statement Consider a multi-echelon inventory/distribution system where a warehouse supplies Nretailers. Assume that customer demand occurs at each retailer at a constant rate. This demand must be met as it occurs without shortages. Orders placed by retailers generate demands at the warehouse. There is a holding cost per unit stored per unit time and a fixed charge for each order placed at the warehouse and at each retailer. The demand rates, holding unit costs, and replenishment costs are stationary and facility dependent. Deliveries of orders are assumed to be instantaneous. Hereafter we use the following notation: Djdemand per unit time at retailer j;j¼ 1;y;N Dwdemand vector at the warehouse (for decentralized decisions) Dwdemand per unit time at the warehouse (for centralized decisions) kjfixed ordering cost of a replenishment at retailer j;j¼1;y;N kwfixed ordering cost of a replenishment at the warehouse hjunit carrying cost at retailer j;j¼ 1;y;N hwunit carrying cost at the warehouse tjtime interval between replenishments at retailer j;j¼1;y;N twvector that contains the time instants where the retailers place their orders to the warehouse (for decentralized decisions) twtime horizon at the warehouse (for decentralized decisions) twtime interval between replenishments at the warehouse (for centralized decisions) Qjorder quantity at retailer j;j¼1;y;N Qworder quantities vector at the warehouse (for decentralized decisions) Qworder quantity at the warehouse (for centralized decisions) Cjtotal cost at retailer j;j¼1;y;N Cwtotal cost at the warehouse Coverall cost of the firm. The aim consists of minimizing the overall cost, that is, the holding and replenishment costs at the warehouse and at the retailers. In general, the cost function is C¼CwþX N j¼1 Cj ¼CwþX N j¼1 kj Dj Qj þhj Qj 2  :ð1Þ Depending on whether there exists dependence or not among the warehouse and the retailers, the cost function at the warehouse is formulated in a different way. From this point on, we propose a procedure which determines near-optimal solutions for the decentralized case. 3. Decentralized case Suppose that there exists independence among the retailers and the warehouse. In such a situation, it is assumed that each installation belongs to different firms. For this reason, each retailer is interested in minimizing its own cost independently. ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 B. Abdul-Jalbar et al. / Int. J. Production Economics ](]]]])]]]–]]] 3 PROECO : 2593 UNCORRECTED PROOF Let CjðQjÞbe the cost function at retailer j; CjðQjÞ¼hjQj=2þkjDj=Qj:Since the previous formula stands for the cost function for a EOQ system, we can determine the optimal lot size, Qn j; the optimal planning time, tn j;and the optimal cost, Cn j;using the following classical expressions, that is, Qn j¼ffiffiffiffiffiffiffiffiffiffiffiffi 2Djkj hj s;tn j¼Qn j Dj and Cn j¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2Djkjhj pfor j¼1;y;N: Since each retailer places orders according to an EOQ pattern, the planning times are not related. Therefore, the warehouse behaves as an inventory system with time-varying demand. When the demand rate varies with time, we can no longer assume that the best strategy is to always order the same replenishment quantity. In fact, this will seldom be the case. Hence, the warehouse does not follow the classical saw-teeth pattern of the EOQ model. Indeed, we now have to use the demand information at the retailers, over a finite planning horizon, to determine the appropriate replenishment quantities at the warehouse. Following Schwarz (1973), deliveries are made to the warehouse only when the warehouse and at least one retailer have zero inventory. Note that the optimal planning times for each retailer are real values. Therefore, we cannot assure that a point in time exists where all the retailers order simultaneously. In this case, the number of periods of the demand vector at the warehouse is not finite and, the problem cannot be solved by the Wagelmans et al. algorithm (1992). Under this assumption, we propose an approach to overcome this problem. The idea consists of either truncating or rounding up to rational times the real planning times. It is clear that the solution provided by this method is not the real optimal plan but it is quite a good approximation. Furthermore, in practice, it does not make sense to work with irrational times. Let Bbe the set of rational times where any retailer orders to the warehouse, that is, B¼ftAQ:t¼nti;for some nANand iAð1;2;y;NÞg;where each ti¼ai=bi;i¼ 1;2;y;N;is obtained by rounding or truncating the optimal planning time at each retailer. Moreover, following the characterization of the ‘‘basic’’ policies stated by Schwarz (1973), each value in B represents a candidate instant where the warehouse can place an order. Since the optimal planning times have been transformed into rational values, a set S¼ fn1;n2;y;nNgof integer values can always be found such that n1t1¼n2t2¼?¼nNtN¼tw;or, in other words n1 a1 b1 ¼n2 a2 b2 ¼?¼nN aN bN ¼tw:ð2Þ Recall that twor an integer multiple of tw represents the planning time for the warehouse. Note that (2) represents a linear equations system with nvariables and n1 equations. In order to assure the integrality of the ni’s, set nN¼bNaN1aN2?a2a1:ð3Þ Therefore, the remaining integer values in (2) are obtained by ni¼nN aN bN bi ai ;i¼1;2;y;N1:ð4Þ Finally, each ni’s is divided by the m.c.d.(n1;n2;y;nNÞ:Then, the values thus obtained are considered as the new ni’s values and tw can be calculated by (2). Also, these values can be used to determine the number Pof different instants in time over twwhere the warehouse receives an order from some retailer. First of all, the values ni’s must be clustered in the following way. Those nj’s that are powers of some nivalue are included in a cluster. That is, nj¼nk i;for some kinteger. If there are not nj’s values that are powers of some ni;then this cluster contains only the nivalue. Let Rbe the number of clusters. For each cluster i;we choose the highest power value n0 i as the representative element. That is, n0 i¼nk i being kthe highest power. Then, set mi¼n0 i1 for i¼1;2;y;R:The integer mirepresents the number of equidistant points over twneeded to get n0 iintervals. The theorem below states when orders are placed to the warehouse. The proof of Theorem 2 requires the following lemma. Lemma 1. Let t1and t2be two rational numbers and let n1and n2be integer numbers such that n1t1¼n2t2¼tw:Then,the number of points in ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 B. Abdul-Jalbar et al. / Int. J. Production Economics ](]]]])]]]–]]]4 PROECO : 2593 UNCORRECTED PROOF ð0;twÞwhere it1¼jt2for i ¼1;2;y;n1and j ¼ 1;2;y;n2is given by the m.c.d.ðn1;n2Þ1: The proof of this lemma is straightforward. Theorem 2. The number P of different instants in time where the warehouse receives an order from some retailer is P¼X R i¼1 miX R1 i¼1X R j¼iþ1 ðm:c:d:ðn0 i;n0 jÞ1Þ:ð5Þ Proof. By Lemma 1, the double summation in (5) represents the points in ð0;twÞwhich have been considered more than once in the first summation. Therefore, Pstands for the number of different instants in ð0;twÞwhere the warehouse receives an order from some retailer. & Once the number of points Pis obtained, we can generate the demand vector at the warehouse of dimension Pþ1 or a multiple of Pþ1:Since the planning times have been rounded the order quantity at each retailer, Qn j;has changed to be Qj¼tjDj:Let Jjbe the set of retailers ordering from the warehouse in period j:This set can be used to determine the quantity to be satisfied by the warehouse in period j;j¼0;1;y;P;in the following way Dw½j¼PiAJjQi:This demand vector represents the quantities that the warehouse has to supply. To solve this problem, the Wagelmans et al. algorithm (1992) can be used. Below, we present a numerical example with five retailers and one warehouse where the planning times at each retailer are Retailer 1 Retailer 2 Retailer 3 Retailer 4 Retailer 5 t1¼5t2¼5=2t3¼5=3t4¼ 10=3 t5¼ 10=9 Then, using the method shown above, the values in Sare n1¼2;n2¼4;n3¼6;n4¼3;n5¼9 and tw¼10: The next step consists of clustering these values including into a cluster all the nj’s values that are powers of some nivalue in S:Hence, the representative elements of each cluster are: n0 1¼ 4;n0 2¼9;n0 3¼6 and, therefore, m1¼3;m2¼8; m3¼5:Then, according to Theorem 2, Pis equal to 13 and the number of periods at the warehouse is 14. Now, we have to determine the demand ordered from the warehouse in each interval, that is, Dw; and then we apply the Wagelmans et al. algorithm (1992). See the numerical example presented in Section 5 for more details. The following section is devoted to the centralized case. Under this assumption, we study different policies. 4. Centralized case In this case, the warehouse and the retailers belong to the same firm. Therefore, the firm should pay all the costs, and the goal is to minimize (1), that is, the cost at the warehouse plus the costs at the retailers. Taking into account that the firm has to make decisions about the stock control, it can force the retailers to place their orders at the same time or to place an order either at different instants of time or independently. The latter case was already studied in the previous section. 4.1. Assuming common replenishment time To coordinate the replenishments, the firm can force the retailers to place their orders at the same time, say every ttime units. Then, the cost at each retailer j;j¼1;y;N;is Cj¼hj Djt 2þkj t: Let Dbe the sum of the demands at the retailers, that is, D¼PN j¼1Dj:Since all retailers place an order at the same time, the one-warehouse N- retailers problem can be viewed as a one-ware- house one-retailer problem where the demand per unit time at the warehouse is Dw¼D:Besides, the new retailer orders the sum of the quantities ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 B. Abdul-Jalbar et al. / Int. J. Production Economics ](]]]])]]]–]]] 5 PROECO : 2593 UNCORRECTED PROOF ordered by the retailers, that is, Q¼PN j¼1Qjevery ttime units. For that reason, the order quantity Qwat the warehouse can be determined according to the integer-ratio policy. Crowston et al. (1973) and Williams (1982) proved the optimality of the integer-ratio policy for two-echelon systems. Therefore, in our problem, we can follow this integer-ratio policy and set Qw¼nQ;where nis a positive integer. Then, the cost at the warehouse, assuming instantaneous demand pattern, is Cw¼ hwððn1Þ=2ÞtD þkw=nt: The aim consists of minimizing the sum of total holding cost plus ordering cost at the warehouse and at the retailers, that is, Cðt;nÞ¼t 2X N j¼1 hjDjþhwðn1ÞD ! þ1 tX N j¼1 kjþkw n ! : Note that the overall cost depends on tand n only. To calculate the optimal solution ðtn;nnÞwe need the following Lemma. Lemma 3. If hwohj;j¼1;y;N;and n is a continuous variable,then Cðt;nÞis convex over the region:fR:0onoN;0otpBðnÞg;and has its global minimum at ðtn;nnÞ;where BðnÞ¼1 n 2kw hwD21þnPN j¼1kj k0 ! 1=2 1 2 43 5 2 43 5 1=2 and tn¼ 2PN j¼1kjþkw n  PN j¼1hjDjþhwðn1ÞD 2 6 6 43 7 7 5 1=2 ;ð6Þ nn¼ kwPN j¼1hjDjhwD  hwDPN j¼1kj 2 43 5 1=2 :ð7Þ Proof. Assuming that nis a continuous variable and setting the first partial derivatives of Cðt;nÞ equal to zero, we obtain tnby (6) and nnby (7). It is easy to see that the Hessian is positive definite at t¼tnand n¼nn;therefore, Cðt;nÞhas a local minimum at ðtn;nnÞ: The Hessian matrix is non-negative definite for any nand tin the region: fR:0onoN;0otpBðnÞg:Also, ðtn;nnÞAR:Thus, Cðt;nÞis convex on Rwith the global minimum at ðtn;nnÞ:& From the value tn;we can obtain the optimal order quantities for each retailer, that is, Qn j¼Djtn;j¼1;y;Nð8Þ and Qn w¼nX N j¼1 Qn j;ð9Þ where nis the nearest integer to nn: Summarizing, if the firm forces the retailers to place their orders at the same time, the optimal solution is given by the formulae in Table 1. However, due to some reasons such as logistics problems, it could be preferable to satisfy the demand at the retailers at different time instants. Hence, in the following section, we develop the case where the retailers can place orders at different instants of time. 4.2. Assuming different replenishment times The firm can allow the retailers to place their orders at different instants of time tj;j¼ 1;2;y;N:This case concerns the class of single cycle policies, and hence, the unique condition that must be verified is that there must exist n1;n2;y;nNAN;such that, n1t1¼n2t2¼?¼ nNtN¼tw: Schwarz (1973) was the first who considered this class of policy. He provided an optimal solution for the one-warehouse and Nidentical retailers problem (transforming the system into a onewarehouse one-retailer system), and suggested a heuristic solution for the general one-warehouse N-retailers problem. However, this heuristic does not always provide good solutions. Graves and Schwarz (1977) proposed a solution method to get optimal single cycle policies for this problem. ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 B. Abdul-Jalbar et al. / Int. J. Production Economics ](]]]])]]]–]]]6 PROECO : 2593 UNCORRECTED PROOF Roundy (1985) focused on the special class of single cycle policies known as power-of-two policies. He proved that the effectiveness of power-of-two policies with fixed base planning period, is at least 94%. That is, when we restrict ourselves to such policies, we can guarantee a solution whose cost is at most 6% above the cost of an optimal policy. Furthermore, if the base planning period is assumed to be variable, the power-of-two policies are at least 98% effective. We propose a procedure which combines the relaxation of the integrality constraint of the ni’s, along with a branch and bound scheme. This approach runs with lower computational effort than the Graves and Schwarz’s method (1977). Moreover, as it is shown in Section 6, this procedure generates better single cycle policies than those provided by the Roundy’s method (1985) when stationary and nested policies are considered. The new approach assumes that, in period tw; retailer jhas to order njtimes and it holds njDjt2 j=2¼twtjDj=2 units of item. Therefore, the cost at retailer jis as follows Cj¼ 1=twðhjðtwtjDj=2ÞþkjnjÞ¼hjtjDj=2þkj=tj: On the other hand, the warehouse only places an order once, and it holds twPN j¼1DjðtwtjÞ=2 units of item. Thus, the cost at the warehouse is given by Cw¼1 tw hwtwX N j¼1 DjðtwtjÞ 2þkw ! ¼hwX N j¼1 DjðtwtjÞ 2þkw tw : Therefore, to find the optimal single cycle policy we have to solve minCðtw;t1;t2;y;tNÞ ¼kw tw þhw twPN j¼1Dj 2 þX N j¼1 kj tj þðhjhwÞDjtj 2  ð10Þ s:t:niti¼njtj¼tw;i;j¼1;2;y;N;ð11Þ njX1;integer;j¼1;2;y;N: The first step to solve (10) consists of relaxing the integrality constraint of the nj’s. Then, the optimal replenishment times that minimize (10) are tw¼½2kw=hwD1=2;being D¼PN j¼1Dj;and tj¼ ½2kj=ðhjhwÞDj1=2;j¼1;y;N: Taking into account (11), the optimal nj’s values can be calculated as nj¼tw tj ¼kwðhjhwÞDj kjhwD  1=2 : Unfortunately, in general, these nj’s are not integers. However, we propose a solution method based on a branch and bound scheme to obtain near-optimal integer nj’s from the real values. We start sorting the retailers so that retailer iis smaller than retailer j;iif nionj:We can assume, without loss of generality, that n1on2o?onN: Then, we proceed to find the near-optimal integers by generating an initial feasible solution setting njequals to the nearest integer value, or nj¼1ifnjo1;j¼1;2;y;N:This feasible solution provides an upper bound, UB;for the total ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 Table 1 Time Quantity Retailer 1 t1¼tn¼2ðPN j¼1kjþkw=nÞ ðPN j¼1hjDjþhwðn1ÞDÞ "# 1=2Qn 1¼D1tn Retailer 2 t2¼tnQn 2¼D2tn ^^ ^ Retailer NtN¼tnQn N¼DNtn Warehouse tw¼ntnQn w¼nPN j¼1Qn j B. Abdul-Jalbar et al. / Int. J. Production Economics ](]]]])]]]–]]] 7 PROECO : 2593 UNCORRECTED PROOF cost which allows us to ignore worse solutions than the UB: Afterward, the procedure generates an enumeration tree with Nlevels where each level corresponds to a different nj;j¼1;2;y;N:At level iþ1;each nj;j¼1;2;y;iis fixed and only nk’s, k¼iþ1;y;N;have to be determined. Note that if nj’s, j¼1;y;i;are known, each reorder time tjhas changed to satisfy tj¼njtw: Thus, the total cost can be reformulated as follows: Cðtw;tiþ1;y;tNÞ ¼kw tw þhw twD 2 þX i j¼1 kj nj tw þðhjhwÞDj 2 tw nj  þX N j¼iþ1 kj tj þðhjhwÞDjtj 2  ¼1 tw kwþX i j¼1 kjnj ! þtw 2hwDþX i j¼1 ðhjhwÞDj nj ! þX N j¼iþ1 kj tj þðhjhwÞDjtj 2  : Let ti wdenote the optimal reorder time at the warehouse assuming that nj’s, j¼1;y;i;are known, that is, ti w¼2ðkwþPi j¼1kjnjÞ hwDþPi j¼1ðhjhwÞDj=nj "# 1=2 : Once we know ti wand taking into account (11), we can calculate the new optimal niþ1as niþ1¼ti w tiþ1 :ð12Þ Thus, considering that nj’s, j¼1;2;y;iare known, the minimum cost given by the above procedure is Cðtw;tiþ1;y;tNÞ:This cost represents a lower bound LB for the subproblem where the nj’s, j¼1;2;y;i;are known and integer-valued. If this lower bound exceeds the upper bound UB, the subproblem does not need to be examined. In the opposite case, if Cðtw;tiþ1;y;tNÞdoes not exceed the upper bound UB, then, the subproblem is branched at level iþ1 generating two new subproblems. The first corresponds to set niþ1¼ Iniþ1mand the second corresponds to set niþ1¼ Iniþ1mþ1;where niþ1is the real value determined from (12). For each subproblem the previous procedure is applied. When the cost associated with a feasible solution at level Nis lower than the current upper bound UB, we update UB to be the new cost which has been calculated and the procedure continues looking for a better solution. Finally, when the branch and bound stops, we can assure that each njis an integer value and the replenishment time at the warehouse is given by tN w¼2ðkwþPN j¼1kjnjÞ hwDþPN j¼1ðhjhwÞDj=nj "# 1=2 : Once we know n1;n2;y;nNand tN w;the replenishment time at each retailer is computed using (11). Given the tj’s, we can calculate the quantity ordered by retailer jas Qj¼Djtj:Finally, it is easy to see that the order quantity at the warehouse is Qw¼PN j¼1njQj: The computational experience shows that the procedure is quite fast since the lower bound for each subproblem allows us to ignore a lot of possible branches in the enumeration tree. The following section illustrates the different solution methods for both decentralized and centralized cases. 5. Numerical example Consider a numerical example with threeretailers and one-warehouse with the input data (Table 2). Now we proceed to calculate the optimal costs provided by the three policies introduced in the previous sections. ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 B. Abdul-Jalbar et al. / Int. J. Production Economics ](]]]])]]]–]]]8 PROECO : 2593 UNCORRECTED PROOF 5.1. Assuming decentralization Using the classical EOQ expressions, we can calculate the optimal order quantities and planning times (Table 3). As you can see, the planning times are not rational numbers. For that reason, we round the tn i’s to obtain the following values: t1¼0:2¼2 10; t2¼0:3¼3 10 and t3¼0:1¼1 10:Now, the ni’s values can be calculated using (3) and (4) to give n1¼60 1 10 10 2¼30;n2¼60 1 10 10 3¼20 and n3¼ 10 32¼60: Then, we divide the ni’s values by the m.c.d.ðn1;n2;n3Þ¼10 obtaining the following results: n1¼3;n2¼2andn3¼6:After that, the different clusters are calculated. In this case there are three clusters, one for each nj:Hence, n0 j¼nj; j¼1;2;3: Using the new planning times, the order quantities and the costs at each retailer are given in Table 4. The planning time is tw¼niti¼0:6:The number Pof instants where the warehouse receives an order is P3 i¼1miP31 i¼1P3 j¼iþ1 (m.c.d.ðn0 i;n0 jÞ1Þ¼5 and the time vector twis 0:00:10:20:30:40:5 The demand vector at the warehouse Dwis given by 48:49:724:733:424:79:7 Once the demand vector is obtained, the Wagelmans et al. algorithm (1992) provides the optimal order planning for the warehouse. That is, Qw¼ 58.1 0.0 58.1 0.0 34.4 0.0 The cost at the warehouse is 255.4 $/time unit. The overall cost including the costs at the retailers and at the warehouse is 1939.7833 $/time unit. 5.2. Centralization with common replenishment time In this case, the retailers place their orders at the same time. Using (6) and (7), we have tn¼0:2004 time units and nn¼0:9482 and, therefore, n¼1: Thus, the retailers and the warehouse place their orders once every tn¼0:2004 time units. The order quantities at the retailers are calculated using (8). Accordingly, Qn 1¼15:03 units of item, Qn 2¼15:83 units of item and Qn 3¼19:44 units of item. Then, the order quantity at the warehouse can be computed from (9) to give Qn w¼50:30 units of item. Following this policy the overall cost is 2065.2947 $/time unit. ARTICLE IN PRESS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 Table 2 Dikihi Retailer 1 75 42 48 Retailer 2 79 100 21 Retailer 3 97 28 52 Warehouse 37 8 Table 3 Qn itn i Retailer 1 ffiffiffiffiffiffiffiffiffiffiffi 27542 48 qC11:4564 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 27542=48 p75 C0:1527 Retailer 2 ffiffiffiffiffiffiffiffiffiffiffiffi 279100 21 qC27:4295 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 279100=21 p79 C0:3472 Retailer 3 ffiffiffiffiffiffiffiffiffiffiffi 29728 52 qC10:2206 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 29728=52 p97 C0:1053 Table 4 QiCi Retailer 1 15:0 570:0000 Retailer 2 23:7 582:1833 Retailer 3 9:7 532:2000 B. Abdul-Jalbar et al. / Int. J. Production Economics ](]]]])]]]–]]] 9 PROECO : 2593