L O W E R B O U N D S F O R P R O D U C T I O N / I N V E N T O R Y P R O B L E M S B Y C O S T A L L O C A T I O N By P A U L O M O L E W A I Y O G U N B.Sc. (Petroleum Engineering). University of lbadan, 1978 M.Eng. (Industrial Engineering), University of Toronto, 1983 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T OF T H E R E Q U I R E M E N T S FOR T H E D E G R E E OF D O C T O R O F PHILOSOPHY in T H E F A C U L T Y OF G R A D U A T E STUDIES (Commerce and Business Administration) We accept this thesis as conforming to the required standard T H E UNIVERSITY O F BRITISH C O L U M B I A © Paul Omolewa Iyogun, 1987 July 1987 In p resen t i ng this thesis in part ial fu l f i lment of the requ i remen ts for an a d v a n c e d d e g r e e at the Univers i ty o f Br i t ish C o l u m b i a , I agree that the Library shal l m a k e it f reely avai lable for re fe rence and s tudy . I fur ther agree that pe rm iss ion for ex tens i ve c o p y i n g o f this thesis for scho la r l y p u r p o s e s may be g ran ted by the h e a d o f m y depa r tmen t o r by his o r her representa t i ves . It is u n d e r s t o o d that c o p y i n g o r pub l i ca t i on of this thesis fo r f inanc ia l ga in shal l no t b e a l l o w e d w i t h o u t m y wr i t t en p e r m i s s i o n . D e p a r t m e n t of Cocewe*ce a^4 Business fVc\m(n\sWaVon T h e Un ivers i t y o f Bri t ish C o l u m b i a 1956 M a i n M a l l V a n c o u v e r , C a n a d a V 6 T 1Y3 D a t e DE-6(3/81) A B S T R A C T This thesis presents a cost allocation method for deriving lower bounds on costs of feasible policies for a class of production/inventory problems. Consider the joint replenishment problem where a group of items is replenished together or individually. A sequence of reorders for any particular item wil l incur holding, backorder and set-up costs specific to the item, l n addition whenever any item is replenished a joint cost is incurred. What is required of the total problem is the minimizat ion of a cost function of the replenishment sequence or policy. The cost allocation method consists of decomposing the total problem into sub-problems, one for each item, by allocating the joint cost amongst the items in such a way that every item in the group receives a positive allocation or none. The result is that, for an arbitrary feasible cost allocation, the sum of the min imum costs for the subproblems is a lower bound on the cost of any feasible policy to the total problem. The results for the joint replenishment problem follows: For the constant and continuous demand case we reproduce the lower bound of Jackson, Maxwel l and Muckstadt more easily than they did. For the mult i- i tem dy-namic lot-size problem, we generalize Si lver -Meal and part-period balancing heuristics, and derive a cost allocation bound wi th little extra work. For the 'can-order' system, we use periodic policies derived from the cost allocation method and show that they are superior to the more complex (s,c,S) policies. The cost allocation method is eas-ily generalized to pure distribution problems where joint replenishment decisions are taken at several facilities. For example, for the one-warehouse multi-retailer problem, we reproduce Roundy's bound more easily than he did. For the multi-facility joint replenishment problem (a pure distr ibution system with an arbitrary number of ware-houses), we give a lower bound algorithm whose complexity is dr\ogr where d is the maximum number of facilities which replenish a particular i tem and r is the number of items. n C ontents A B S T R A C T ii A C K N O W L E D G E M E N T ix I N T R O D U C T I O N 1 C H A P T E R O N E 5 The Joint Replenishment Problem: Literature Review 5 Introduction 5 1.2 Deterministic T ime-Vary ing Demand 7 1.2.1 ZangwilPs Algor i thm 10 1.2.2 Kao's Algor i thm . . . 13 1.2.3 Leopoulos-Proth 's Algor i thm 16 1.2.4 Veinott 's A lgor i thm 18 1.3 Deterministic Stationary Demand Case 18 1.3.1 Goyal's Method 21 1.3.2 Silver's Method 24 1.3.3 Jackson-Maxwell-Muckstadt 's Me thod 26 1.4 Random Demand Case 28 1.5 Other Related Models 30 i i i C H A P T E R T W O 32 A Lower B o u n d on a Class of Production/Inventory Problems 32 Introduction 32 2.2 The Joint Replenishment Problem 37 2.2.1 Deterministic, Continuous-Time Stationary Demand 37 2.2.2 The Cost Al locat ion Method 38 2.2.3 The Lower Bound Problem 39 2.2.4 The Mul t ip roduc t Dynamic Lotsize Problem 42 2.2.5 'Can Order ' Policies 42 2.3 The One-Warehouse Mul t i -Reta i le r Prob lem 43 2.3.1 Cost Al locat ion and the Lower Bound 45 2.4 Concluding Remarks 49 C H A P T E R T H R E E 50 The Mult i -Faci l i ty Joint Replenishment Problem 50 Introduction 50 3.2 Problem Definition and Notation 53 3.3 Cost Allocat ion and the Lower Bound 54 3.3.1 The Lower Bound Problem 56 3.3.2 ' The Facilities-in-Series Problem 63 3.4 Solution to the General Problem 68 3.4.1 The Algor i thm 70 3.4.2 Example 3.1 75 C H A P T E R F O U R 81 The Mul t i -Produc t Dynamic Lot-Size Problem 81 iv 4.2 The Lower Bound 84 4.3 Generalized Silver-Meal Heuristic 85 4.4 Computat ional Experience 89 4.5 Other Heuristics 91 4.5.1 P P B and G P P B Heuristics 91 4.5.2 B M Y and G B M Y heuristics 93 4.6 Conclusion 94 C H A P T E R F I V E 95 P e r i o d i c V e r s u s ' C a n - O r d e r ' P o l i c i e s 95 Introduction 95 5.2 Mode l Assumptions 97 5.3 'Can-Order ' Policies 98 5.4 The Lower Bound 98 5.5 The Periodic Policies 99 5.6 Computat ional Results 100 5.7 Concluding Remarks 105 C H A P T E R S I X 108 C o n c l u s i o n 108 B I B L I O G R A P H Y 108 A P P E N D I X A 119 v List o f Tables 4.1 Heuristic Performance 90 5.1 Data and Typica l Results 101 5.2 Results wi th no Time-weighted Backlogging Cost 103 5.3 Results with only Time-weighted Backlogging Cost 104 5.4 Same as F i g . 5.3 with Higher Holding Cost 105 5.5 Results wi th Different Lead Times and Demands 106 vi List of Figures 2.1 A Mul t i -Fac i l i ty Joint Replenishment Problem 35 2.2 Cost Allocat ion for F i g . 2.1 36 3.1 A Typica l Solution for a Given Cost Al locat ion 61 3.2 'Rounded ' Power-of-two Solution for Figure 3.1 62 3.3 Op t imum Clusters for Example 3.1 80 v i i This thesis is dedicated to my mother, A n i m a Ebe Iyogun. v i i i A C K N O W L E D G E M E N T I would like to thank Professor Derek Atk ins , my research supervisor, for introducing me to this area of research, for supporting me both morally and financially and for guiding me throughout the period of this research. His help was invaluable in preparing this document. M y thanks also go to Professors Shelby Brumelle and Daniel Granot, members of my research committee, and Maurice Queyranne who were very helpful in correcting my mistakes and for their moral support. I would also like to thank Professors M a r t i n Puterman and Piet de Jong for giving me an opportunity to earn some money when 1 needed it most, and the Natural Science and Engineering Research Counci l of Canada and the Faculty of Commerce for their financial support throughout the period of this research. F ina l ly I must thank my wife Amanele, and my sons Onose and Odalo for their patience and understanding when I could not be with them most of the time because of this research. ix I N T R O D U C T I O N This dissertation presents a cost allocation method for deriving lower bounds on costs of feasible policies to joint replenishment problems in inventory management. Con-sider a group of items whose replenishment generally requires a common process such as having a common supplier or a common production unit, or a common mode of transportation. Replenishment of one or more items in the group involves a major set-up cost resulting from init iating the order or production process. In addition to the major set-up cost, each item to be included in the replenishment group has an as-sociated cost which depends only on the item. This item-dependent cost may include a set-up cost, to be referred to as the minor set-up cost, and a purchase cost for the item. There is also an inventory related cost rate which depends on the amount of stock and the demand for each item. The particular nature of this cost depends on the context but in general wi l l involve the cost of holding excess inventory in stock when it is not needed or a penalty cost for not having enough stock to meet the immediate demands. The demand process can be either deterministic (constant or time varying, discrete or continuous) or stochastic. Each of these processes gives rise to a complex problem in joint replenishment inventory management. The methods of solution are quite different, and wi l l therefore be treated in separate sections. The problem is to schedule replenishment of each item so as to minimize the total 1 set-up and inventory related costs or the average of these costs per unit time over a known horizon. One obvious solution to this problem is to treat each item separately and schedule replenishments using the sum of the item-dependent set-up cost and the major set-up cost as the set-up cost for each item. The solution obtained by this method is feasible and hence its cost is an upper bound on all reasonable solutions. This upper bound is found to be very loose in most practical problems, indicating that there is ample room for improved solutions. Unfortunately, the computational requirements for obtaining an opt imum solution to a joint replenishment problem wi th only a few items are extraordinarily heavy. Moreover the form of the opt imum policy, if known, may be very complex and therefore not implementable in practice. These two issues have forced researchers to seek simple solutions to the joint replenishment problem. A solution wil l be referred to as easy or simple when the parameters specifying the replenishment schedule are easy to compute and the policy induced by these parameters is easy to implement. If also the easy solution results in a substantial cost saving when compared to the upper bound, the solution is "good". Efforts are made to balance computational simplicity and solution quality. The greater part of this dissertation wi l l discuss simple techniques that give very good solutions - generally better than 105% of a lower bound. The major motivation for this research is a lower bound for a general class of inventory problems, which has a particularly simple form for the joint replenishment problem. Its derivation also gives some useful insight into possible feasible policies which turn out to be very good. The dissertation is organized into six chapters. In Chapter one, we survey the literature on the joint replenishment problem and discuss some existing solution tech-niques. In Chapter two, we introduce a new method referred to as the cost allocation method of deriving lower bounds for a class of inventory/ production problems which require coordinating the replenishment of more than one item. This cost allocation 2 method is used to work out in detail the lower bounds for the joint replenishment prob-lem and the one-warehouse, multi-retailer problem both under deterministic, constant and continuous demands. Other problems to which the cost allocation method can be applied are also discussed. In Chapter three we introduce the multi-facility joint replenishment problem which is a pure distribution problem requiring joint replenish-ment decisions at various facilities. Although the discussion is long, the algorithm for determining the lower bound for this problem is very simple. Again the form of the lower bound is obtained from the cost allocation method. In Chapter four, we discuss the mult i - i tem dynamic lot size problem. The cost allocation method provides a simple lower bound for this problem. This lower bound gives a new insight into the problem which helps in generalizing some of the single i tem dynamic lot sizing heuristics to the mult i- i tem environment, without losing the quality of the heuristics. For exam-ple a series of computational results shows that the generalized Silver-Meal heuristic performs equally well in the multi-i tem environment as the original heuristic in the single product environment. It is also demonstrated that the effectiveness ratios of the part period balancing heuristic and a variant of it are unchanged when generalized to the mult i- i tem environment. These generalized heuristics can be applied quite easily to the joint replenishment problem with an arbitrary number of products. This is in contrast to the existing heuristics which, because of their complexity, could not be used for problems wi th more than a few items. In Chapter five, we demonstrate through computational examples that the simple periodic policy obtained using a method de-rived from the cost allocation bound, performs better than the much written-about s,c,S policy. Final ly, Chapter six is a summary and a discussion of topics for further research. In summary, this thesis presents a new and very general method - the cost allocation method, and demonstrates its use in determining lower bounds; which in turn can be used to develop new solutions to a wide class of production/inventory problems that 3 require coordinating the replenishment of more than one item. 4 C H A P T E R O N E T h e J o i n t R e p l e n i s h m e n t P r o b l e m : L i t e r a t u r e R e v i e w Introduction Consider an inventory control manager faced with the problem of scheduling the pro-duction or procurement of N different items over a known horizon, so that the demands for each product or item over the horizon are met, subject to constraints on backlog-ging. If there is no restriction on the total amount that can be backlogged at any time, any procurement or production policy that satisfies all demands over the horizon is feasible. Whatever constraints there are on the problem, it is likely that there are an infinite number of, or very many feasible solutions to the problem. The problem is to choose among all the feasible solutions, that policy whose implementation results in the overall min imum cost. The cost of a. policy consists of a replenishment cost and an inventory related cost. The replenishment cost consists of a major set-up cost which must be paid whenever one or more items are replenished and a minor set-up cost associated with each item, which must be paid whenever an item is included in a joint order. 5 The inventory related cost depends on the current inventory and the demand until the next decision point. There is a holding cost rate charged for excess stock and a backlogging cost rate, when backlogging is allowed, which is charged for each unit of demand not met directly from stock, except in the s.c.S model discussed in Chapter 5 where a cost which depends on the length of a stockout is also charged. Other costs parameters w i l l be introduced as needed. The demand pattern of each item is important in determining the method of so-lution to this problem. In most reasonable cases, the computational requirements for finding an opt imum solution is prohibitive. Moreover, the form of the policy that is opt imal , if known, is usually complex and difficult to implement. Because of these problems, researchers have concentrated more effort on the development of reasonable heuristics. Unfortunately, these heuristics were evaluated using very simple examples because there was no known good lower bound for this problem. There is now available a good lower bound which wil l be discussed in Chapter 2. This lower bound is useful in that it facilitates the process of developing heuristics. Very simple heuristics can now be tested quite easily as is done in chapters 4 and 5. For the deterministic demand case, the pattern is usually either the time-varying and periodic demand [78,86,87] or stationary and continuous time demand, see for example [28,27,26,29,30,36,52,53,66,63]. For the stochastic case the pattern is usu-ally either stationary and periodic demand or stationary and continuous time de-mands. Tan [74] characterized an opt imum policy for a two-product problem with periodic demands. For stationary and continuous time demands, see for example [75,69,65,23,39,38,82]. Veinott [76] treated the case of non-stationary demands but no joint set-up cost. The next sections are devoted to specifying the joint replenishment problem induced by each of the demand patterns above, and discussing some of the associated existing solution methods. 6 1.2 Deterministic Time-Varying Demand Demands for the items are known in each period over the horizon but vary from one period to the other. In this finite horizon is always assumed. Whenever a replenishment is made, a major set-up cost AQ is paid, independent of the number of items in the joint order. In addition, a minor set-up cost Ai is paid if i tem i is included in the joint order. The unit variable cost of producing or purchasing each of the items is assumed constant for each item. The case w i th non-constant unit variable cost is not considered here. W i t h this assumption, the total variable purchase or production cost for each i tem is constant for all feasible solutions which have no shortage, or excess stock at the end of the planning horizon. Since the models of this chapter do not permit shortages or excess stock at the end of the planning horizon, the unit variable procurement or production cost wi l l be ignored in all subsequent analysis. A t the end of each period, a holding cost is charged at the rate of hi per unit, if there is excess stock of item i. A more general version of this problem has been addressed. For example, Zang-wi l l [86], and Ka lymon [40] considered the case with a generalized procurement plus inventory cost; Veinott [78], K a o [41] and Leopoulos et al . [44] considered the case wi th seperable but concave procurement and inventory cost functions. The restricted version described here where the set-up costs are constant, is most common in practice and has been addressed by Silver [68]. There are many algorithms which find the opt imum solution to this problem [40,41,68,78,86]. The common problem wi th these solution methods is that their com-putational requirements are enormous. The algorithms of Zangwill [86], K a o [41], Silver [68] and Leopoulos et al . [44] are exponential in the number of products, while those by Veinott [78] and K a l y m o n [40] are exponential in the number of time periods. None of these methods can be used for a problem wi th a moderate to large number of items and a long planning horizon. 7 A brief description of some of the solution methods wi l l now be given. Some Notations: Kit = demand for product i in period t Xlt = replenishment quantity of item i in period t X1 = (Xlt, X2t, xNt) inventory level of item i at the end of period t h = {ht, ht, lm) N = number of items H — number of periods in horizon Model Assumptions: 1. The unit variable acquisition cost of any item is constant and therefore disre-garded. 2. There is no backlogging of any item. 3. There is no capacity constraint. 4. Lead time is zero. The single item problem with these assumptions has been studied extensively. Wagner and W h i t i n [80] were the first to give a dynamic programming solution to the problem. Thei r basic model has been expanded, sometimes to relax some of the assumptions above and sometimes to derive new solution properties for the basic problem and for a more general class of problems. For example Zabel [85] introduced planning horizon theorems which reduce the computational requirements of the Wagner-Whit in model. Some properties of opt imum solutions derived for the single item case have been extended to the mult i- i tem problem; examples of such extensions can be seen in [66,86]. 8 The most important of these properties which have been exploited in deriving the solution to the joint replenishment problem are given below. P r o p e r t y 1: Xit — YJj=t^xj t <n< H: n integer and n < a rgmin{/ : (/ — tf)/i,-7r„ > Ao + A,} P r o p e r t y 2: Xit > 0 implies Iit_1 < 0; Iit > 0. Property 1 says that when any item is replenished, the replenishment quantity must be equal to the sum of demands for an integer number of periods. Also, it is not desirable to purchase the requirement of period n in period t, I < n, if the cost to hold this requirement from period t to period n is greater than the total set-up cost. Property 2 says that a replenishment for any item takes place only when that item has zero inventory, and that the replenishment quantity must be sufficient to cover the demand of the period in which the replenishment takes place. The condition on n can also be treated as a property. It is the planning horizon concept which reduces the solution space to consider in searching for an optimum solution. Let A ( / t - i ) = [X\.XL...,XlN). where X\ is a feasible sequence of replenishments of item i from period t to the end of the planning horizon given that the starting inventory of the item in period t is Iu-i-If Xn satisfies properties 1 and 2 above, Dt{It-\) is known as the dominant set for period t if the starting inventory in period t is It-i, Zangwill [86]. This dominant set is simply the set of feasible replenishment schedules, given the starting inventory, which satisfy properties I and 2 above and by implication contain an optimum schedule. The construction of an opt imum solution to the joint replenishment problem uses dynamic programming, efficiently exploit ing the fact that an opt imum replenishment schedule is contained in the dominant set. This idea was introduced by Zangwill [86] in the 9 context of a more general problem. The methods of Zangwill , Kao , Leopoulos et al and Veinott , used for obtaining an optimum solution wi l l be described in the next four subsections. 1 .2 .1 Zangwill's Algorithm Zangwil l devised a dynamic programming method for determining an opt imum replen-ishment schedule from the dominant set of a general class of multi-i tem, multi-stage inventory problems. The algorithm specializes easily to the joint replenishment prob-lem, and wil l be described in the context of this chapter. Let N 1=1 N Ht(Xl) = *£hiXit A t any time t, let t=i and n,-i = mdx{k\Y,*ij = lit-i} i=t Iit-i = 0 implies n t j = t — 1 Thus nt] is the time when the current inventory for item i w i l l be fully consumed. For every i, define rii2 by Xit = ^2 iTij-, ni2 > ntl; ni2 integer. J=n,-i + l «1 = ("-11,^21, •••,ttjVl) n2 = (n12,n22,...,nN2) H = an A r -dimensional vector of H 10 From the above definition, n^2 is the time when the current replenishment of item i, if any, wi l l be fully consumed. The cost incurred in any period t can now be written as N Pt{nun2) = A06{At) + + h%{X« + ltl^ - Tr,-,)) (1.1) t = i where 6(x) — 0 if x < 0 and 6(x) = 1 if x > 0. Let F t(nx) be the min imum replenish-ment plus inventory cost from period i to period H given that in period t, the starting inventory wi l l meet the demands from period t to periods n^. (Recall that ni is a vector). It can be shown that Ft(-) satisfies the following recursion. F,(ni) = mm _(Pt(nun2) + Ft+1{n2)) F„(H) = 0. When backlogging is not allowed as in this case, t — 1 < n,-i < H • for every i Although this algorithm produces an opt imum solution, the state space required is very large. For example the maximum number of ways of selecting raj is HN. For large H and N, this algorithm is clearly impractical. Example Let N = 2 , H=3 , / i x = h2 = 1. = 5 TTil = 3 7T2] = 4 Ax = 2 7T12 = 5 = 3 A2 = 3 7Tl3 = 1 7T23 = 4 11 The relevant calculations are shown below. F 3 (3 ,3 ) = P 3 [(3,3) ,(3,3)] = 0 F3{3,2) = P 3 [(3,2),(3,3)] = 8 F 3 (2 ,3 ) = P 3 [(2,3),(3,3)] = 7 F 3 (2 ,2 ) = P 3 [(2,2),(3,3)] = 10 F2{2,3) = min(P 2 [(2,3) , (2,3)] + F 3 (2 ,3 ) ;P 2 f (2 ,3 ) , (3 ,3 ) ] + F 3 (3 ,3) ) = 11 n 2 = ( 2 , 3 ) . continuing in this way, the other values are:-F2 (3,2) = 9 wi th n 2 -- (3,2) F2 (2,2) = 10 wi th n2 = (2,2) F2 (1,2) = 15 with n2 = (3,3) F2 (2,1) = 15 wi th n2 = (3,3) F2 (1,3) = 12 wi th n2 (3,3) F2 (3,1) = 13 wi th n2 (3,3) F2 (1,1) = 15 wi th n2 (3,3) Fx (o,i) = 15 with n2 (3,3) Fx (i,o) = 15 with n2 (3,3) Fx (0,0) = 25 wi th n-2 (1,1) The solution is to order both items for the first period only, and to order again at the beginning of the second period for the second and third periods. The total cost is 25. One weakness of this algorithm is that it does not fully utilize property 2 which all opt imum solutions have. The state space of the dynamic program is the vector of periods when the entry inventory levels w i l l be fully consumed. Stages are the periods. Property 2 says that no replenishment is needed in time t, if all components of rii are strictly greater than t; that is if entry inventories for all items are all strictly positive. Thus, at stage t, it is only necessary to consider states where the vector of 12 entry inventory contains at least one zero, or equivalently, at least one component of rii is t — 1, except when t = H. If this fact is incorporated in the algorithm,the states needed wi l l be considerably less. For example, for the problem above it is not necessary to calculate F 2 ( 3 , 3 ) , F 2 ( 2 , 3 ) , F 2 (3 ,2 ) , F2{2.2) and Kao [41] noticed this fact and incorporated it into his network algorithm. Apar t from the fact that Kao's method uses a network approach, it is the same as Zangwill 's algorithm plus property 2 on page 9. A brief description of Kao's method now follows. 1.2.2. Kao's A l g o r i t h m As was indicated in the last subsection, Kao's algorithm is an efficient implementation of Zangwill 's algori thm. It uses property 2 of opt imal solution to reduce the state space at every stage, and formulated the problem as a network problem. Let M denote the node set of the network and Mt denote the node set that can be generated at stage t. The nodes and arc sets are defined as follows. Any element n x of Mt satisfies the following; ni = {^11,^21, ••• ,nN1} nil ~ {n\t ~~ 1 5: n < H} and riji = t — 1, for some j. and there is a directed arc from rii £ M , to n2 G Mt> if and only if n2 > nj and t' > t. The length of an arc from n x to n 2 at stage i , is given by P t ( n i 5 n 2 ) a s defined in 1.1. W i t h these nodes and arc set, the joint replenishment problem is to find the shortest part through the network, starting from the node which represents the init ial inventory to the terminal node which is a vector of N components, with each element l o equal to H. The problem, can thus be stated as follows. min _ { P t ( n ! n 2 ) + Ft{n2)} Standard solution techniques for this problem can be found in basic texts on networks such as [34]. Al though, this method involves a smaller state space than Zangwills method, it is st i l l exponential in the number of products. One solution to the example in section 6 using this method wi l l involve all the steps in Zangwill 's algorithm except that F 2 ( 3 , 3 ) , F 2 ( 3 , 2 ) , ^ ( 2 , 3 ) , F 2 (2 ,2) and F i ( l , l ) , w i l l not be evaluated. Kao also proposed a heuristic which performs very well on some test examples. Kao's heuristic The heuristic is best described using a two product example, say product 1 and product 2. I n i t i a l i z e : Set R to an A 7-dimenesional vector of zeroes. I <— 1 S t e p 1: Choose item 1 and define the set-up cost as: otherwise S t e p 2: Use Wagner-Whi t in ' s algorithm for item 1 using a\t as set-up cost. Let R[ = {t j Xit > 0} If R[ = R[~2, S T O P ; otherwise /<—/ + ! and go to step 3. S t e p 3: Select product 2 and augment the set-up cost as follows: 14 Use Wagner-Whi t in ' s algorithm for product 2 wi th a'2t as set-up cost. Let R[ = {t\X2t > 0}. If R2 = R2~2 S T O P . Otherwise /•*—/ + 1. R Rl2, and go to step 1. For more than two products the order of product pairs has to be determined before step 1. For an N-product problem, a typical choice can be (1.2), ( 2 , 3 ) , . . . , (N — l,N), (7V,1). This algori thm can be improved wi th better starting values for R . One such starting value is described in Variant 1 below [41]. Variant 1 Let JV JV a = A0 + = At; -Kt = *ithit i=l i=l Use Wagner-Whi t in ' s algorithm with a as set-up cost, 7rt as the demand in period t, and unit holding cost per item per period. Let R = {t\Xt > 0}. This is then used as ini t ial value for R in step 0 of the heuristic. Variant 2 Use every item as starting point in the heuristic in conjunction with variant 1. Select the min imum cost solution. Al though, this heuristic is reported to perform well , it is not satisfactory for a problem with a large number of items, considering the number of Wagner -Whi t in type 15 problems to be solved. Wagner-Whi t in ' s algorithm is typically not used in practice even in the single item case. Some good heuristics, independent of Wagner-Whit in 's algorithm wi l l be discussed in Chapter 4. Another algorithm which is similar to that of Zangwil l is that of Loupoulos and Pro th , which wi l l be discussed next. 1.2.3 Leopoulos—Proth's Algorithm The algorithm by Leopoulos and Proth [44] is similar to Zangwill 's algorithm in being exponential in the number of products. Let Ft[h-i] be the min imum cost from period t to the end of the horizon given that the starting inventory in period i is It-i, Ft(-) satisfies the following recursive equation. Ftih-x) = min {A06{&t) + Yl{AAXt)+hi{Xit + lu^-ixlt) + Ft+l{Xt + It-i-*t)} This dynamic program can be shown to be identical to that of Zangwil l , and therefore requires a larger state space than that of Kao . Leopoulos and Proth also gave a heuristic algorithm which depends on the following argument: For simplicity assume there are only two products. Suppose X = (X^X^) is an optimum schedule with a given initial starting inventory I0. The value of Xx which minimizes Ft{Ia\X2) is X\. Leopoulos-Proth's Heuristic I n i t i a l i z e : set k *— 0; / 0 X° = some feasible policy for product 1. Step 1: Define the set-up cost as follows: x£D,(I,-i)FH^(-) = 0. otherwise 16 Use Wagner-Whi t in ' s algorithm for item 2 using a'2t as set-up cost, to obtain X2 If Xl2 = Xlf1 S T O P , otherwise go to step 2. Step 2: k *- A; -f 1 and let Use Wagner-Whi t in ' s algorithm for product 1 with a'lt as set-up cost, to obtain If = X f - 1 S T O P , otherwise l-*— I + 1 and go to 1. This algorithm is applied using different starting values of X ° , randomly generated. The heuristic policy is the policy which gives the minimum cost. This heuristic is similar to Kao 's heuristic. The only noticeable difference is that K a o uses a systematic method to generate a starting feasible solution while Leopoulos-Pro th randomly generates the starting solution. Since at least one of the randomly generated starting solutions wi l l correspond to an optimum set-up times as the number of trials go to infinity, Leopoulos-Proth 's method wil l eventually find an optimum solution. However there is no reason to believe that Kao's method of generating ini t ial set-up times wil l give an opt imum solution even for large number of trials. The algorithms described thus far are based on Zangwill 's method and therefore exponential in the number of products. In practice, the number of products involved in a joint replenishment problem is large while the number of periods may be small . This is partly due to the fact that demand forecasts far into the future are not very reliable. Veinott gave this as a justification for proposing a different solution to the joint replenishment problem which is exponential in the number of time periods and linear in the number of products. otherwise 17 1.2.4 V e i n o t t ' s A l g o r i t h m The algori thm is based on the fact that in any period, there is either a major set-up or there is none. A l l possible major set-up patterns can therefore be enumerated. The opt imum replenishment schedule must correspond to at least on of these patterns. The algorithm is simply to generate a major set-up pattern, and determine using Wagner-Whi t in ' s algorithm for each item an opt imum replenishment schedule wi th in the major set-up pattern. The cost for a pattern is the sum of the costs for all the items. The replenishment schedule for each item, corresponding to the pattern that gives the min imum total cost is the opt imum replenishment policy. This algorithm is simple, but enumerating all the possible set-up patterns, which are at most 2 H _ 1 patterns is obviously not an attractive thing to do in practice, unless the number of periods, H is less than about 15. Veinott also showed that when the minor set-up cost for each item is zero for all items, the replenishment schedule satisfies: N hi-i(*}2,Xit) = 0 for every i and t i This means that no item is ordered unless the total inventory level is zero; all items are out of stock simultaneously. 1.3 Deterministic Stationary Demand Case We now turn to continuous time models. The problem parameters are constant and stationary in time. Specifically, the demand rate for item i is TT, per period, which for convenience wi l l be taken as one year. The holding cost rate per unit of item per unit of time is No backlogging of demand is allowed for any item. The major and minor set-up costs are as specified in the previous section. The problem is to determine an ordering policy which minimizes the average set-up plus inventory holding cost per unit t ime over the infinite horizon. This problem arises when a number of items, each of 18 which has a constant demand per period, can benefit from a centralized replenishment policy. Such is the case if the items share a common production unit or if they have a common supplier or a common mode of transportation. The amount of each item to replenish each time a major replenishment process is initiated becomes important, as well as the average number of replenishments to be made per unit time. A number of authors [20,26,28,27,36,46,53,64,66] have addressed this problem. The common denominator of their solution methods is that they use equally spaced replen-ishment epochs. These policies are not necessarily optimal as is argued in [5]. The opt imum referred to in all these papers where 'opt imum' is specifically mentioned should be qualified by the word 'periodic' . It is s t i l l an open problem what problem parameters ensure the existence of periodic opt imum policies, except two cases. The first case is obvious and this is the case when all items have equal parameter values. This fact is easily seen from the lower bound for this class of problems, to be discussed in the next chapter. The second case which is slightly different from the model in this chapter has item-dependent set-up costs but with a fixed saving when all items are replenished together. For this problem Andres and Emmons [4] showed that an opt imum policy has equally spaced replenishments epochs for each item. Even the problem of finding optimal periodic policies is not a t r ivial task, [27,66]. Because of this, researchers have focussed mainly on developing approximate methods for finding good periodic policies. Recently efforts at finding good solutions to this problem have shifted to specific periodic policies such as the power-of-two policies, introduced by Roundy [57] and also used in [36]. In this class of policies, it is assumed that a base period exists for operational reasons or otherwise, or that a convenient one can be found by optimization methods. A l l replenishments are then restricted to 2l of this base period, with / > 0, a positive integer. This approach is interesting because it gen-erally yields good solutions and in any case, has a worst case performance of less than 6% above the unknown opt imum cost. In the next subsections, two methods, Silver 19 [66] and Goyal [27] which give good periodic policies and another one by Jackson et al [36] for finding optimum power-of-two policy wi l l be discussed. Assumptions and Notations: Let 9i Ti To Ni No Ni kt Note that if the period is 1 year, T0 71 i hi ~ 2 ~ reorder interval in years for product i the major replenishment interval in years. the number of replenishments per year for item i the number of major replenishments per year. replenishment quantity per replenishment epoch for item iVo Ni 1 A T 1 — and i , = — NQ Ni Problem Formulation. This formulation assumes equally spaced replenishments. Let C(N0,N) denote the cost per year given A70 and A ; = (JVi, N2, •••, NN) N C(N0,N) = AoN0 + J2(A>N> + Jf) i = l 1 No A N A-= + S K ^ F T " + Togtki) J-0 1 = i J 0 « i Let t ing k = {ko, /cj, . . . , k^}. equation 1.3 can be written as i=0 * 0 J = 0 (1.2) (1.3) (1.4) (1.5) 20 and equation 1.4 can be written as C(T 0 , fc) = £ ( 7 ^ + 9 ^ 0 ) (1.6) where /CQ = 1 and go = 0. The problem is to determine No and k, which minimize 1.5 or equivalently T 0 and ki which minimize 1.6 with A;,- restricted to the positive integers for every i. 1.3.1 Goyal's Method Goyal 's approach is to choose N0 and A:, for every i, to minimize the cost function expressed 1.5. Define the natural cost of an item as the single item cost, if replenishment could be made at the minor set-up cost. For every i tem i, let n z = natural order frequency for item i C — the natural cost for item i Cl is given by: & = Atnl+*r and this is minimized when: - - ar Let Ci(N0,ki) denote the cost of replenishing i tem i independently of all other items, given the major replenishment frequency is NQ. n (\r L.\ A I N ° _ L D I K I M 7^ Ci[No,ki) = — — + — (1.7) ki IVQ For a given A 7 0 let ki(N0) minimize 1.7. 21 Since A;,-(JV0) must be an integer, it must satisfy: Ci(N0,k{N0)) < Ci{N0,k{N0) + l) and (1.8) Ci{N0,k{N0)) < Ci{N0,k{N0)-l) (1.9) Equations 1.8 and 1.9 are respectively equivalent to < M^oMM^o) +1] (1.10) and N*At 9i which both imply: < M/VoMW.) - 1 ] (l .n). n'MNo^kiiNo) - 1] < N0 < n'M^MNo) + l] (1.12) A simple justification of 1.12 is given in [81]. For any value of 7V0, it is easy to determine ki(No) from 1.12. Thus a search over all reasonable values of TVo wi l l give the desired result from the point of view of minimizing the cost function given in 1.5. Goyal [27] used the following two conditions to restrict the range of N0 values to search. Let L = arg max,- n\ = {i\ max, n\ = n'L}. Condition one: No < NL This condition states that the major replenishment frequency cannot be greater than the natural replenishment frequency of the item with the largest replenishment fre-quency. 22 Andres and Emmons [5] pointed out that this condition is not true in general. It is only true when the policy space is restricted to the class of policies for which the major set-ups are equally spaced. Because of this and the fact that ki(N0) are restricted to integers, the 'opt imum' found by Goyal can at best be optimum in this class of policies. Condition Two: Set ki = 1 for every i. This implies that all items are ordered at every major set-up. Let N0 denote the ordering frequency under this rule. The best value of N'Q can be found from 1.6, since the cost function is a convex function of iVo- The value is: A necessary condition for A7o to be optimum is that: J V 0 > 7 V 0 Goyal's Algorithm S t e p 1: F i n d n'L and N'0 from 1.12 and 1.13 respectively. Arrange all the items in descending order by the value of n\. S t e p 2: F ind 0, > 0 for every i such that kiiNo + Bi) = fc,-(X) + l . Let JV : ' = : A R ' + 0,-. Because of step 1, A R , ' < A r j for every j > i, with the restriction that A^Q + Oi < n'L for every i. Let m be the number of distinct N\. S t e p 3: For A^o in each range, N'0 - h\, N[ - N!2,. .., -n'L, determine an opt imum value of ki for every i. and the associated cost using 1.5. Let k* be the value of ki which gives the overall min imum cost after searching all the ranges. 23 S t e p 4: Determine an opt imum major replenishment frequency by A7, 0 £ £ o ( A / * , - ) This algorithm obviously requires a lot of computations. Roundy [57], used an al-gori thm similar to this, but restricted attention only to power-of-two policies, and showed that the computational requirement not only reduces considerably, but the so-lution found wi th in the class of power-of-two policies is at most 2% above the unknown opt imum. Silver devised a rather simple but relatively good heuristic for this problem. 1.3.2 Silver's M e t h o d Silver [66] gave a very simple closed form equation for selecting values of / c , for every i, and To which give close to the minimum value of the average replenishment plus inventory holding cost given in equation 1.6 Consider 1.6 1 A ' Ax N C{To, k) = — J2 IT + To Yl 9iki J 0 , - = 0 K{ t - = 0 with k0 — 1 and go = 0. For a given k, the cost is convex in To- Min imiz ing with respect to T0 gives and C(T0,k) = 2 fax1) (1.15) \t=0 1 i=0 ) The problem is to select / c , for every i to minimize 1.15. The approach used in [66] is first to ignore the constraint that every / c , be restricted to the positive integers, and minimize 1.15 with respect to k. This is done by taking the partial derivatives wi th 24 respect to each /ct and setting the result equal to zero. This gives A N N A ~ -dY,9ik + 9iY,T = 0 ' 1 = 1 , 2 , . . . , ^ (1.16) Ki 7 = 1 i=0 K i As is shown in Schweitzer and Silver [63] this system has no solution when A0 > 0. To show this multiply 1.16 by kl and sum over all i to obtain JV t'=l which implies that A 0 = 0. Cal l the item whose A,-/ft is min imum over all i item 1. Despite the fact that system 1.16 does not have a solution, if the constraint k\ = 1 is added to the system, the solution obtained by this method gives the correct relative values of the k\s. Solving system 1.16 wi th this restriction gives; (AV2 k3 = M c ; j = 2,---,N (1.17) v 9, ki = 1 w here 2 t = l ki9i Yli=0 A-ij k% * = \ ^ = 1 7 n . 1 (1-18) From 1.17 JV / TV \ ] / 2 k<9t = 9i + c I A9, (1-19) »'=] Vi = 2 / and 1/2 N 4 {T.i-iA.gX E r = (1-20) t=l Substituting 1.19 and 1.20 into 1.18 gives 1/2 From which 25 11/2 J = 2,...,N. (1.22) The kj obtained wil l not necessarily be integer. Simply rounding to the nearest integer is found to be satisfactory, although a search routine can be used. Goya) and Belton |29] suggested a modification to this method. They pointed out that the item to be denoted as item 1 should be that item wi th the min imum value of (An + Ai)/gi. Computat ional results with this modification show some improvement over Silver's basic method which is ideal for the case wi th A0 = 0. Silver's method is simple and performs relatively well when compared to Goyal 's method. Silver showed that for the case wi th two items, the algorithm gives a solution that is always better than 1% above the opt imum. Attent ion has recently shifted to a special class of periodic policies, called power-of-two policies. The next subsection wil l describe the method of Jackson et al for computing an opt imum power-of-two policy for the joint replenishment problem. 1.3.3 Jackson-Maxwell-Muckstadt's Method The method of Jackson-Maxwell-Muckstadt [36] is to determine an opt imum power-of-two policy for a given base planning period. The basic cost equation used is similar to equation 1.6. The problem is to minimize the average cost given by: wi th the restriction that; k, e {?; i = 0,1,.:.},?; = 0,1,2,•••,*/. and k{ > k0 26 In this formulation To is assumed fixed for operational reasons or otherwise. If the second constraint is relaxed and k0 is fixed, the problem becomes separable, and an opt imum k'{s are given by: k- = 21' ; for every i where l\ is a non-negative integer that minimizes-Ai 7,-2'To 2'-T 0 If the min imum is unique, /t- is the smallest integer that satisfies: This is equivalent to: 2'' >~ teV'! '0 Take log to base 2 of both sides to obtain, Ai 1^/2 l'i = log-2 L z f t J d j 2 where [ x j 2 is the smallest integer power of two greater than or equal to x. If the min imum is not unique, the other minimizing value of /, is the above quantity plus 1. The Algorithm, Step 1: Sort items in ascending order of Aljgi. Let H = {0,1, •••,*"} where T.)=o Aj Ai .,. > — lor i < i and 27 for i > i" Step 2: ( ) 1/2 k0 = 2 " = 2T 0 £ V = 0 ^ 2 Step 3: Set kj — ko', for j € H and fcj = 1/2 for > 0 K. 2 This algorithm is accomplished in 0(N log A7) time and is proved to have a worst case performance of at most 6% above the unknown opt imum. The mathematical justification for this algorithm, and especially for step 2 is some-what complex as given by the authors. A very simple method for justifying step 2 wi l l be given in Chapter 2. 1.4 Random Demand Case The joint replenishment problem under random demands has been studied by many authors, [6,11,38,39.65,69,23,76]. Not much is known about opt imum policies for the joint replenishment problem with both major and minor set-up costs. Tan [74] char-acterized the optimum policy for a two-product problem under random demands and periodic review. Jn some cases, for example when there is no major set-up cost, Veinott [76] showed that an optimum policy is of the (s, S) type. When there is a major set-up cost but no minor set-up cost, Johnson [38] and K a l i n [39] have shown that an optimum policy is of the (a, S) type, where a is a subset, referred to as the 'do-not-order' set, of the possible inventory position of the system, when an order is not desirable. The characterization of the set o is complex and poses computational problems, rendering the (a, S) policy impractical . In the face of these difficulties, researchers have tended to focus on heuristic policies like the ( s , c ,5 ) policy where an i tem i is ordered whenever 28 its inventory position reaches its 'must-order' point s,, and any other i tem j whose inventory position is at or below its 'can-order' point c ; , is also ordered. The amount ordered in either case is enough to raise the inventory level of the item i (resp., j) to its 'order-up-to' point 5,- (resp., Sj). This policy was proposed by Balintfy [6]. Silver and other authors have developed good procedures for computing the values of the control parameters s, c and S [23,65,68,69,75]. The (s,c,S) policy is not an optimal policy, as was shown by Ignall [35] but it is judged to be a reasonable policy and has been shown empirically to give cost savings of sometimes up to 20% below the cost of an uncoordinated policy. The uncoordinated policy uses the major set-up plus the item-dependent set-up cost as the set-up cost for each item. The demand patterns used in evaluating the s,c,S policy have so far been Poisson demands [65,68] and compound Poisson demands [75,69,23]. Assumptions common to all the papers are that the opportunities for an item to be ordered at its 'can-order' point are indepen-dently distributed according to the Poisson process wi th rate equal to the expected number of major replenishments per period that are not caused by the item and that the demands are uncorrelated. These assumptions simplify the required mathematics and the solution still shows considerable cost savings over the independent policy. The basic method used consists of a decomposition procedure and an iterative routine. Silver [65] developed a simple sequential method of determining the values of s, S that solve a single item problem under Poisson demand. The values of c for the items are then selected iteratively until convergence in the cost is achieved. Thompstone and Silver [75] also developed a method for compound Poisson demands. The paper by Federgruen et al [23] differs from previous work in one essential aspect: the method for solving the decomposed problem, that is, the single item problem, is a specialized policy iteration method. Other interesting work in this area include those of Mil tenburg and Silver [48,49]. They determined the probabili ty distribution of the residual stock of items jointly 29 replenished at the time of replenishment by modelling the inventory process as a dif-fusion process in both periodic and continuous review environments. Heuristics were then developed for ordering policies which take proper account of residual stock. They showed that these heuristics perform better than the I B M ' s I M P A C T inventory control package. Naddor [52] compared different policies e.g, periodic, s,S and other policies for single item problem and developed a simple method of determining good periodic policies for the joint replenishment problem. 1.5 O t h e r R e l a t e d M o d e l s Clark [15] gave a general survey of multi-echelon inventory models. A n interesting survey of general physical distribution problems in inventory management is given by Schwarz [61]. A particular model of interest is the dynamic multi-location inventory model. In this model there are many locations supplied by a central warehouse that may or may not hold stock. When the warehouse does not hold stock, it acts merely as a distr ibution center. For this problem where the emphasis is on the distribution of a fixed amount of stock to minimize inventory cost, Simpson [70] showed that when the penalty costs are equal across locations, the opt imum rule is to distribute the stock so as to equalize the probability of shortage in all locations. When the penalty costs are different the distribution rule is to equalize the weighted probability of shortage across locations, the weights being the penalty costs. Other early studies of this problem can be found in [3]. Recently Eppen [21] showed the exact effect of centralization on the expected inventory cost for a one-period model. Eppen and Schrage [22] later consid-ered centralized ordering wi th lead time in a multi-period setting with norma] demand distr ibution. Following this lead, Federgruen and Zipkin [24,25] developed good ap-proximate allocation rules by aggregating demands across locations and over time. They used normal, exponential and gamma demand distributions all wi th constant 30 coefficients of variations. When the warehouse can hold stock, the problem becomes a one-warehouse mult i -retailer problem. This problem and the generalization has been studied widely. Veinott [78] and K a l y m o n [40] gave exponential running time algorithms for this problem with discrete and deterministic demand under periodic review. Schwarz [60] gave some properties which any opt imum solution of the deterministic demand, continuous review version of this problem must possess. Roundy [57] exploited these properties along wi th restricting the policy to power-of-two policies and found an algorithm which runs in N\ogN t ime, if there are N end facilities called retailers, and showed that such a solution has effectiveness of 98% in the worst case. This result in part motivates the research reported in this thesis. A 98% effective power-of-two solution for the general multi-stage, multi-facility production/inventory problem under continuous review, wi th a fixed set-up cost de-pending on the group of items replenished at a facility has also been given by Roundy [59]. This result was generalized by Queyranne [55] to include submodular set-up cost functions. Other multi-echelon inventory models include the assembly systems in M R P setting. Ear ly work in this area include Crowston et al [17,18], Schwarz and Schrage [62] Graves i31] and Blackburn and Mi l l en [9j. Others can be found in [56]. Recently Afentakis et al [l] used a Langragean relaxation method to develop a lower bound on the cost for an assembly system under periodic review and used a branch and bound integer programming method for solution. Roundy [56] developed a 94% effective power-of-two solution to the assembly problem under continuous review in the infinite horizon. 31 C H A P T E R T W O A Lower Bound on a Class of Production /Inventory Problems Introduction A cost allocation method is presented for determining lower bounds for a class of production/inventory problems. We have N products which are replenished together or individually. A sequence of reorders for any particular item wil l incur holding, backorder and set-up costs specific to the item. In addition whenever any i tem is replenished a joint cost Ao is incurred. For instance, if several items are replenished simultaneously, the joint cost is incurred. But if only one item is replenished, the joint cost is also incurred. What is required of the total problem is to minimize a cost function of the replen-ishment sequence. This might be a long run average or a total cost function. It should be clear that any feasible replenishment sequence for the total problem would also give a feasible replenishment sequence to each item individually. If, at any instance of joint replenishment, the joint cost A Q is shared amongst all items so that each i tem i gets a 32 fraction c t , A 0 of the cost, and N Y, * = 1; a,- > 0 (2.1) i = ] then the sum of the costs implied by each feasible replenishment sequence on each item wi l l not be greater than the cost of the total problem. Thus the sum of the minimum costs incurred for each item after reallocating the joint cost wi l l be a lower bound on the min imum cost for the total problem. This is true for any allocation which satisfies 2.1 above and is true in particular if we maximize the lower bound wi th respect to a = (<*!,.. .,aN). In the sequel we show how to use this cost allocation method to derive lower bounds on the costs of any feasible replenishment policy for each of the following problems: 1. The (single facility) joint replenishment problem 2. The one-warehouse multi-retailer problem 3. The multi-facility joint replenishment problem. For the one-warehouse multi-retailer problem the item reorder which is relevant in applying the cost allocation method is the reorder at the warehouse. Also for the multi-facility joint replenishment problem, the relevant item reorders are the reorders at facilities which distribute more than one item. The one-warehouse multi-retailer problem is the production/inventory problem where a warehouse supplies an item to many retailers. The (single facility) joint replen-ishment problem is a special case of the one-warehouse multi-retailer problem. In the joint replenishment problem the warehouse does not hold any stock. The multi-facility joint replenishment problem is a problem wi th an arbitrary number of warehouses such that a warehouse has a unique immediate predecessor. A warehouse supplies an ar-bitrary number of products to warehouses or retailers in the set of its immediate successors and so on until the products get to the retailers. 33 One common feature of these problems is that a warehouse or retailer has a unique immediate predecessor but may have any number of successors. We shall sometimes refer to a warehouse or retailer simply as a facility. Another feature of these three groups of problems is that a group of items shares a common replenishment or pro-duction set-up cost, which must be paid whenever one or more items in the group is replenished or produced. This joint cost is referred to as a major set-up cost at the facility where the joint replenishment takes place. The group of items that shares this major set-up cost includes all the items supplied by the end facilities that are also successors of the 'major' facility. Each item has a 'minor ' or ' l ine' set-up cost which is paid when a particular item is withdrawn by an end facility, that is, a retailer. There is also an inventory cost at each facility which depends on the stock level and the stock withdrawal pattern at the facility. The specific nature of this cost depends on the problem structure and wi l l be described as each example is introduced. The problem is generally to schedule replenishments of the various items at each facility so as to minimize the total cost or average cost per unit time of ordering and holding inventory at each facility over a given horizon, subject to a given set of constraints. The effectiveness of a feasible solution is the ratio of the best available lower bound on the cost of any feasible solution to the cost of that feasible solution. One use of lower bounds is in evaluating the effectiveness of heuristic solutions to difficult problems. 94% and 98% effective solution methods exist respectively for the joint replenishment problem [36,57] and the one-warehouse multi-retailer problem [57]; both with stationary, deterministic and continuous-time demands. Another major use of lower bounds is apparent from the methods of obtaining the 94% and 98% effective solutions for the above problems: that of deriving feasible solutions from the bound. The bound introduced here is derived by using a general principle of allocating the set-up cost of a facility amongst all the items that are replenished at the facility. The total of all allocated fractions of cost is required to be unity for feasibility. W i t h this 34 allocation scheme, we can decompose the problem into N facilities-in-series problems, if there are N end facilities, as illustrated in figures 2.1 and 2.2 below. ^ 8 Figure 2.1: A Mul t i -Fac i l i ty Joint Replenishment Problem The decomposed problem corresponding to figure 2.1 is shown in figure 2.2 below. It is required that « 1 8 + « 2 8 + « 3 8 + "48 + « 5 8 = 1 #16 + "26 + "36 = 1 "47 + « 5 7 = 1 The major result of this cost allocation method is that: the sum of the minimum costs of the feasible solutions to the subproblems, for every allocation scheme such that the total fractional cost allocation at each facility is unity, is a lower bound on the cost of any feasible solution to the original problem. Because it is usually easier to solve a facilities-in-series problem, the bound is easy to derive for every cost allocation scheme. The only problem is to determine a cost allocation scheme which gives a 'good' bound. 35 8)a 5 g^8 Figure 2.2: Cost Al locat ion for F i g . 2.1 The major part of this chapter wi l l be devoted to determining good bounds for the joint replenishment and the one-warehouse multi-retailer problems, using the cost allocation method. The application of this general bound to the multi-facility joint replenishment problem wi l l be deferred to the next chapter. These bounds w i l l , hence-forth, be referred to as the cost allocation bounds. The cost allocation bound, for each of the problems, coincides wi th the bounds in [36] for the joint relenishment problem, and in [57] for the one-warehouse TV-retailer problem. One further advantage of the bound, apart from the simplicity of deriving it, is its very intuitive base, which renders it very general. The cost allocation bound, is determined and proved for the joint replenishment problem in the next section, while the same is done for the one-warehouse multi-retailer problem in section 3. 36 2.2 T h e J o i n t R e p l e n i s h m e n t P r o b l e m In genera] there is a major set-up cost Ao which is paid whenever a replenishment is made, and a minor set-up cost Ai also paid whenever item i is replenished. The joint replenishment problem can generally be categorized according to the demand patterns of the items involved, because the methods of solution are similar for similar demand patterns. Three cases wil l be considered. 2.2.1 Deterministic, Continuous-Time Stationary Demand It is desired to schedule the replenishment or production of N items over the infinite horizon. Each i tem experiences a known constant and continuous demand per period. The inventory related cost consists of a linear echelon holding cost rate per unit of stock per unit time. The concept of echelon holding cost reflects the value added to an item as it moves from a facility to the successor facility. In the joint replenishment problem, a major assumption is that no value is added in moving items from the warehouse to the retailer, so the echelon holding cost at the retailer is zero. The warehouse and the retailers are in fact the same physical facility. The individual unit variable procurement cost is assumed constant throughout the horizon, and need not be considered since backlogging is not allowed. The to-tal accumulated cost of procurement wi l l clearly not depend on any specific feasible replenishment policy wi th no excess stock at the end of the horizon. We consider the class of feasible policies consisting of all policies which replenish an item only when the inventory of the item is zero, that is an i tem is replenished only at the last minute. It is easy to check that this class of policies dominate any other class of policies in the sense that it contains the opt imum replenishment schedule. Let a particular feasible policy in this class be specified by VP. ty w i l l be uniquely defined 37 by • the replenishment epochs of item i denoted by T ° . • the replenishment quantities of item i, Qi(T®) at the epochs T f . Let ty, be the replenishment schedule induced on item i by . We see that V&j is feasible for item i when viewed alone. We can then say that \1> consists of ^ 2 for all i in the group, and hence write * = ( * 1 , * 2 , . . . , * j V ) and Z(ty) as the average cost of policy 2.2.2 The Cost Allocation Method The cost allocation method requires that a set-up cost that is common to a group of items be shared amongst the items in the group. In the joint replenishment problem, the major set-up cost is shared amongst all the items that can be joint ly replenished. Let a,- be the fractional allocation of the major set-up cost to item i. It is required that the total of all fractional allocations derived from this major set-up cost be unity. By this allocation, the problem decomposes to N two stage facilities-in-series prob-lems. Let Z,-(Vl/t-, a;) be the cost for the ith facilities-in-series problem if the allocation to item i is a, and the policy is vf/,-. The pattern of inventory levels for i tem i resulting from using \I/ for the general problem is exactly the same as that resulting from using SI*, for the ith facilities-in-series system. Thus the inventory holding costs are equal in both cases. Let us now examine the set-up costs. Let r be a member of some T,°. This means that at time r , there is a minor set-up and therefore also a major set-up. Let ET be the set of items that are replenished at time r. The total minor set-up cost at time T is the same using policy or the individual facilities-in-series, that is using individually. The major set up cost using ^ for the general problem is AQ. Using the 38 individual policies the total major set-up costs incurred at time r is the quantity given below: Sum of the major set-up costs at time r — Ao{^2 a 0 — Ao-We have thus shown that the sum of the set-up costs for all the facilities-in-series problems is always bounded above by the total set-up cost for the original problem, and the patterns of inventories in the system are identical in both cases. Therefore >J2Zi(*i,«i)- (2-2) Thus the cost allocation method gives a lower bound on the cost of all feasible policies to the joint replenishment problem. The result applies to any demand pattern at the retailers and with backorders, including random demands, since it applies verbatim to each sample path if the items are distinct so that there is no risk pooling. 2.2.3 The Lower Bound Problem Let PZi(a.i) : Zi(a.i) = min Zt(*,-, a,-). The echelon holding cost at the retailer is zero in the joint replenishment problem. Because of this, in any feasible solution to the ilh facilities-in-series problem we must have that the replenishment epochs of the warehouse in the facilities-in-series coincide with that at the retailer. The ith facilities-in-series problem is thus equivalent to a simple Economic Order Quantity ( E O Q ) problem with a set-up cost a ,Ao + A and a holding cost rate of h,. Without loss of generality, we assume for the rest of the analysis that delivery lead time is zero, and that demands occur at a constant rate of 2 per unit time. This latter assumption was first used by Roundy [57]. We also assume that there is no backlogging of demands. W i t h these assumptions we can write Zi(at) explici t ly as 39 . TV Zi(cti) = 2 y ( a ^ o + -A,-)/i,- and Z(a) = ^ Zi{a.i). Let N Z ( Q V ) = m&x{Z(a)\Ya. — 1; a J 0} We have pointed out that the lower bound in equation 2.2 is true for any given feasible vector a. In particular > Z{a) The desired lower bound is given by Z(a) wri t ten below. N N Z[OL) = 2 { m a x ^ yJ(ctiA0 + = 1; a, > 0} (2.3) i=l i=l Because Z , , is strictly concave and continuously differentiable in c^, the Kuhn-Tucker necessary conditions are also sufficient for optimality. Thus, after introducing the Lagrange multiplier A, and letting prime denote the first derivative, the relevant K — T conditions can be writ ten as: = M A J 1 / 2 (XiA0 + A{ < A (2.4) a,- > 0 Z?(a,-) = A (2.5) N £ « . • = 1 (2.6) i=i The first two conditions imply that N is partitioned into two sets of items K] and N 2 , such that: . i e Ni = £ • ct, > 0 Note that K 2 can be empty. From condition 2.5, it can be deduced that: • R W , <*JAQ + A, A 0 2 2 (E =^> = constant = (-7-) rti A 40 Combin in ing this wi th condition 2.6 and solving for a,, i <E Nj, gives; a, = - ^ 6 K ' ' (2.7) AQ The problem is to parti t ion the items into the sets and N 2 , such that a, defined above is non-negative. The parti t ioning problem is solved in [36]. We give a similar algori thm which is consistent wi th the spirit of our lower bound. The algorithm s tep 0 Initialize Let c «— a big number, = A,/hi for all i. Rank all ti in ascending order and assume for simplici ty that ti < t2 • • • < tn; set k <— 1, N 2 <— { 1 , 2 , . . . , N}, Ni <— 0 a <— A Q , ft 0. s tep 1 Al loca t ion If c > tk, do the following: a <— a + A ^ , ft A: +— A; + 1, and go to step 1; otherwise the problem is solved the current partition is opt imum, go to step 2. s tep 2 Calculate a- using equation 2.7 for all i G K x and let a\ < — 0 for all i 6 N 2 The cost given by the algorithm is then 2 , / U o + E E M +2 E which coincides wi th the lower bound in [36]. A close look at the set Hj reveals that the 'run-out ' times (the cycle times in this case) for each i G K i is A / A 0 , and these are the items wi th a, > 0, while the 'run-out' times for each i £ K 2 is greater than 41 X/AQ, and these are the items with = 0. Thus we can say that the allocation is done to equalize the 'run-out' times as much as possible, or equivalently to maximize the minimum 'run-out' time. 2.2.4 The Multiproduct Dynamic Lotsize Problem K a o [41] and Silver [68] amongst others have studied a finite horizon deterministic production planning problem without backlogging or other constraints with a major (joint) set-up cost A0 and minor (product) set-up cost Ai. In this case the problem PZi(cxi) becomes a version of the dynamic lot size model for which much computational experience has been accumulated and for which efficient routines exist (e.g., Wagner and Whi t i n [80]). However here the choice of optimal a* is by no means obvious. Of coursesany feasible choice wi l l still provide a bound. As is demonstrated in Chapter 4, a heuristic choice of a, to make 'run-out' times as equal as possible without ai becbming negative gives a bound which is close enough to the optimal to be useful. Further research is needed on optimal choices of c^. 2.2.5 'Can Order' Policies Take the joint replenishment problem but now with the demand process as stochastic. W i t h Ai = 0 we know, given other assumptions, that a (CT, S) type policy is optimal, Johnson [38] and K a l i n [39], where a is a 'do-not-order' subset of the possible inventory states. However few properties are known about a and wi th Ai > 0 interest has focused more on (s.c,S) heuristics, [68,23,65,69,75]. Here an item i is ordered up to Si if its inventory position drops to and at that time any other item j below its 'can order' point Cj is also ordered up to Sj. Ignall [35] has demonstrated that such policies are not opt imal , however the suspicion remains that they are fairly good and of course are relatively easy to implement once the parameters (s.c,S) have been calculated. A g a i n , many authors have studied this problem, in particular Silver [69], 42 and Federgruen et al [23]. Different authors have taken different distributions, although all are independent between products, and alternative service level constraints have been tried. Concentrating on shortage costs to control service level rather than explicit constraints, the problem PZi{cti) is now a single product with a fixed cost of aiA0 + At. The lower bound also holds in this case. Again much is known about the optimality of (s.S) type policies for such problems and considerable computational experience has been accumulated [76,77,79]. A n exploration of a choice of a; to equalize expected 'run-out' times as much as possible using periodic policies rather than (s,c, S) policies has been made with very encouraging results, shown in Chapter 5 where it is also shown that even this heuristic choice of CK , wi th in a periodic policy, outperforms the (s,c, S) policies on a wide range of examples. 2.3 The One-Warehouse Multi-Retailer Problem Consider the production/inventory problem where a warehouse acts as the sole distrib-utor to many retailers. The warehouse gets its supply from an external source. Because there is no constraint on capacity, the warehouse can order any positive amount of any item at any time. Each retailer gets its supply from the warehouse and demands are deterministic. There is a fixed charge A0 which must be paid whenever the warehouse replenishes any item, independent of the number or nature of the items replenished. A retailer also incurs a set-up cost Ai whenever retailer i replenishes. There is an echelon holding cost rate at the warehouse for each item and a strictly positive echelon holding cost rate at each retailer for the corresponding item. This distinguishes the one-warehouse multi-retailer problem from the joint replenishment problem where the echelon holding cost rate at the retailers are all zeros. Since the demand on each retailer is deterministic, the amount ordered by the 43 warehouse at any time is determined on the basis of the needs of the different retailers over a specific time interval. The part of the order meant for a particular retailer is predetermined at the time of order. This initial allocation does not change, because of the deterministic nature of the demand patterns. The warehouse can be imagined as consisting of N slots, if there are Ar retailers, one slot per retailer. When the warehouse's replenishment is received, the amount is shared amongst the slots, with each slot receiving the preassigned amount for the corresponding retailer. W i t h this interpretation, each retailer can be thought of as representing a distinct i tem, and the replenishment problem at the warehouse is a joint replenishment problem. This joint replenishment problem is characterized by a fixed cost to be paid whenever one or more items are ordered. A n item-dependent minor set-up cost is paid only when the item is wi thdrawn from the warehouse. Thus the one-warehouse multi-retailer problem can be thought of as a special case of the multi-facility joint replenishment problem to be discussed in Chapter 3. The problem is to schedule replenishments of all items at the warehouse and each item at the corresponding retailer so as to minimize the average set-up plus inventory holding cost in the infinite horizon. As in the joint replenishment problem, we restrict attention to the class of feasible policies characterized by 'last minute' orders for each item. Tha t is, an item is ordered (at the warehouse or retailer) only when the inventory level of the item at the facility is zero. Let a particular feasible policy in this class be ty. Such a policy is characterized by: • the replenishment epochs of item i at the warehouse denoted by T° and at the retailer i denoted by Tn'.-• the corresponding order quantities Q°(T°) at the warehouse and Q;(T\,) at the retailer. 44 Let tyt denote the policy induced on item i by ty. We can then write * = {tyuty2,...,tyN) and Z(ty) the cost of policy ty. 2.3.1 Cost Allocation and the Lower Bound The procedure for deriving the lower bound is exactly the same as for the joint replen-ishment problem. However, the lower bound result is no longer true when demands are random because of the possibility of risk pooling at the warehouse. Let Z(tyi,oti) be the cost of the ith facilities-in-series problem if the fractional allocation of the ware-house set-up cost to item i is a,. For the rest of the analysis, we assume that demands occur at a constant and continuous rate of 2 per unit time for each retailer, and the delivery lead time is zero. PZi{at): Zi{ai) =TCun{Zi{tyi,OLi) and i = l Schwarz [60] has shown that the opt imum policy to this serial problem is periodic with constant cycle times. Thus for any feasible fractional allocations, PZ^) : £•(«,•) = m i n { ^ + ^ • + + M j (2-8) t'!,ti ti subject to t°{ = ra,£,; m,- > 1, integer; for every i (2-9) Relax the integrality constraint 2.9 to *i > ti'i for every i 45 and call the objective function of this later problem S,(aj). Let JV Sia) = Y S'iai) i We note here that since St(a,-) is a lower bound on Zi(at), S(a) is also a lower bound on Z(a) for any feasible a. The value of 5,-(o;,-) depends on a, as follows: ti'A • When ft,- > A n d when a, < f 0 = f . / O i ^ O + A i V Siicti) = 2yJ{aiA0 + Ai){h° + hi) For any feasible choice of a, we can then partition the items into the two sets, Kj and K 2 3 below. h°A-hiA0 and write <S'(a) in terms of these two sets as follows: S{a) =2{Y1 vWo + Ai){h? + K) + Yl \fidAoh? + \ /AA)} (2.10) and the desired cost allocation bound is jv S(a') = m a x { 5 ( a ) | ^ a i = l , a , > 0,V?'} 46 which can be solved to determine a ' . The value of a: which solves this maximization problem can be determined as follows. Firs t note that 5 (a ) is concave in a. After introducing the Lagrange multiplier A, the K — T conditions are: S'Aai) < A (2.11) at > 0=>S'i{ai) = \ (2.12) £ > = 1 (2.13) «=i The first two conditions imply that there are two sets of items, ((Ki U N 2 3 ) \ N 3 ) and N 3 such that: i E ((Hj U N 2 3 ) \ N 3 ) =>• ^ > 0 and i ' e K 3 = > a, = 0. F r o m the definition of the set K l 5 the intersection of Kj and K 3 is empty, since a, > 0 for i 6 K x if all holding cost and set-up costs are strictly positive. Let N 2 = N 2 3 \ N 3 . F rom 2.11 and 2.12, it can be deduced that; i e N l = > ( ^ ) = A 2 (2.14) ai : £ K . => ( A „ ) ! ( ^ ^ ) < A ! (2.16) Ai From 2.14 and 2.15, it is found that: alA0 + Ai (AgOi def . , Observe that c is the square of the replenishment cycle time at the warehouse for those items with at > 0. That is — yjc for i e N] U N 2 which can be determined from 2.17 using the fact that the sum of the fractional allocations must be unity. The value of c is: _ AQ + Ai 47 (2.18) Substi tut ing for c in 2.17 the values of a* are obtained and are given below: c(/i° +_hi) - At A-A\ a} = 0 i e K 3 (2.21) «? = ^ T ; r ^ i (2.19) j < = ^ (2.20) It can be verified that the set H 3 satisfies: Three sets are now clearly identified in terms of c. K, = {,•!«>£} The problem of determining a is equivalent to the problem of partit ioning the items into these three sets. Once the parti t ioning problem is solved c is obtained from 2.18, while the values of o are obtained from 2.19 - 2.21. Substituting a for a in 2.10, the cost allocation bound is obtained as given below. S{a) = 2 {Ao + E Ai)(H2 + Hx) + E + M + E \lAihi {V « e N 2 t€« 3 ieN, J where #2 = E(/i« + /i°) a n d Hi = E ^ -The cost allocation bound above coincides wi th the lower bound in Roundy [57] where also an 0(N log N) algorithm for parti t ioning the items into the three sets is given. 48 2.4 Concluding Remarks In this chapter we have proposed an extremely simple lower bound for a fairly general class of cost minimization problems in production and inventory control. Two examples have been worked out in detail giving much easier derivations of bounds than in the original papers. We believe these papers [57,36] are pivotal in their respective fields in the sense that, they solve their respective problems for practical purposes. Our approach however has much wider generality. This fact is demonstrated in Chapter 3. 49 C H A P T E R T H R E E T h e M u l t i - F a c i l i t y J o i n t R e p l e n i s h m e n t P r o b l e m Introduction The multi-facility joint replenishment problem is a multi-facility production/inventory problem where the facilities (warehouses or production facilities) are arranged as a directed tree network. Each facility is a sole distributor to one or more facilities, called the successor facilities. A facility without successor facilities is a sole distributor of only one item to meet external demand for that item. A characteristic of this problem which needs emphasis is that a facility, except for the root facility, gets all its supplies from only one facility, referred to as the immediate predecessor; that is, a facility has a unique immediate predecessor in the facilities configuration. The root facility is the unique facility without a predecessor. A facility may have any number of successors. A particular system that fits this description is a distribution network which con-sists of a national warehouse, regional warehouses, branch warehouses and retail out-lets. A retail outlet gets all its supplies from a branch warehouse, while a branch warehouse gets all its supplies from a regional warehouse which in turn gets all its 50 supplies from the national warehouse. A retail outlet may stock any number of items, provided that these items are obtained from one source. We consider the problem with this configuration of facilities, where the facilities without successor facilities, referred to as end facilities, each faces a constant and continuous time demand over the infinite horizon. Each facility has a major set-up cost which must be paid at each replenishment regardless of the number of items replenished. W i t h this cost structure, the generalization to the mult i- i tem case does not complicate the problem because a retailer wi th j items is equivalent to a warehouse that is a sole distributor of an item each to j retailers. Each retailer in this case wil l have the demand and cost character-istics of the corresponding item. Also the conventional holding cost of an item at the retailer-turned warehouse wil l be equal to the conventional holding cost of the item at the corresponding retailer, that is, the echelon holding cost at the retailer is zero. This implies that it is irrelevant where the stock is kept, either at the warehouse or at the retailer. It can be assumed therefore that the warehouse, representing a retailer wi th many items, does not hold any item in stock. Because of this relationship, 'items' and 'retailers' wi l l be used interchangeably. A facility without successors distributes exactly one item. The number of items distributed by a facility with more than one successor facility is the number of its successors which are end facilities, since each such end facility distributes exactly one item. The problem is a joint replenishment problem because a distributor facility incurs a fixed set-up cost whenever it orders or produces at least one of the items it distributes. This replenishment cost is sometimes referred to as the joint or major set-up cost. This cost, as in the conventional joint replenishment problem, is independent of the nature or the number of items replenished. This implies that a distributor facility has some incentive to coordinate the replenishment of all the items it distributes. A minor set-up cost at the distributor facility is the cost incurred by a successor facility when the successor facility withdraws items from the distributor. This minor set-up 51 cost at a distributor facility is a joint or a major set-up cost at the successor facility, when the successor facility has successors of its own. The simplest case of this problem is the one warehouse multi-retailer problem where, as pointed out in Chapter 2, there is only one joint replenishment facility, the warehouse. A more general case of this problem where a facility may have any number of successors and predecessors has been considered in the literature, [57,86] The solution algorithms are generally complex. Recently Roundy [57] developed an algorithm which solves this general multi-facility product ion/ inventory problem by solving a series of min-cut max-flow problems. Al though the solution therein is guaranteed to be 98% effective in the class of all feasible policies, the complexity of the algorithm is 0($4), where $ is the number of paths that can be drawn from an end facility through all its predecessors. In the special case of a directed network of facilities, each with a unique predecessor facility, $ is of the order of the total number of end facilities. The algorithm for the general multi-facility problem, when the policy space is restricted to nested policies, has a complexity of / log / when there are / facilities in the network [57]. Included in this class is the one warehouse multi-retailer and multi- i tem problem [51]. A solution method is proposed here for the multi-facilities joint replenishment prob-lem which is guaranteed to be 98% effective in the class of all feasible policies, in the worst case. The complexity of the solution method is 0(dr log r) where r is the number of end facilities and d is the maximum number of predecessors of any one facility. This coincides with the r log r algorithm for the one-warehouse multi-retailer problem. The facility wi th the maximum number of predecessors is obviously an end facility. The method derives naturally from a lower bound on the cost of all feasible solutions to the problem. The lower bound is new and belongs to the general class of the cost allocation bounds introduced in chapter 2. The remainder of this chapter is organized as follows: the next section introduces 52 the notation. Section 3 gives the cost allocation method and the lower bound, while section 4 discusses the solution to, and gives an algorithm for solving, the lower bound problem to the multi-facility joint replenishment problem. 3.2 Problem Definition and Notation Let the set F of facilities be numbered from 1 to / , where / = \F\, (\F\ denotes the cardinality of F), such that the number assigned to a facility is greater than the number assigned to any of its successors. In addition the facilities without successors wi l l be numbered consecutively from 1 to r = \R\, where R is the set of the facilities without successors. Each facility i £ i? faces a constant deterministic demand for an item replenishes only this item, also numbered item i. A facility may have any number of successors but only one predecessor. Facili ty / is the only facility without a predecessor, and is called the root facility. Because a facility has a unique predecessor, the path from any facility to any of its predecessors is unique. Let p3 and Sj denote the immediate predecessor (a single facility) and the set of immediate successors of facility j respectively, while Pj and Sj are the set of all predecessors plus facility j, and the set of all successors plus facility j , respectively. It is important to note that each of Pj and Sj includes facility j. We shall use Rj to denote the intersection of R and Sj, that is, the set of retailers or items that are replenished from facility 'j. Let A , be the set-up cost associated with facility j, and htj the echelon holding cost of item i at facility j , for each item i £ Rj. The concept of echelon holding cost was discussed in Chapter 2. A facility with no predecessor either is a production facility, or replenishes from an outside supplier. In the multi-facility joint replenishment problem considered here, there is only one facility, / , without a predecessor. The set-up cost associated with a facility must be paid whenever a replenishment or production takes place at the 53 facility. The echelon holding cost, hij, is the cost rate per unit time per unit of echelon stock of i tem i at the facility j. The individual unit variable cost is assumed to be constant throughout the horizon, and need not be considered since backlogging is not allowed. The average procurement cost should therefore not depend on any particular policy. The problem is to schedule replenishments of all items at all the facilities so as to minimize the average set-up plus inventory holding cost over the infinite horizon. Let ty be a feasible policy defined by • the replenishment times of i tem i at facility j denoted by the sequence TV,-, for every i £ Rj and every j . • the corresponding order quantities Q , J ( T , J ) of i tem i at facility j, at times in IV,, % e Rj. Let tyt denote the replenishment schedule induced by ty on item i. We can then write Let Z{ty) be the average cost of policy ty. 3.3 C o s t A l l o c a t i o n a n d t h e L o w e r B o u n d The set-up cost of facility j is allocated amongst all the items it produces or replenishes, that is, all i £ Rj. Let a t J be the fractional allocation from facility j to item i, i £ Rj. It is required that the sum of all fractional allocations, derived from a single facility be unity. The tree network of facilities is now decomposed into r facilities-in-series such that the facilities-in-series corresponding to each i £ R, consists only of P, . The holding cost rates for an i tem at the facilities-in-series are the same as the holding cost rates 54 for the i tem at the corresponding facilities before the allocation scheme. The set-up cost at facility j in the facilities-in-series corresponding to item i is a^Aj. Each facilities-in-series represents an inventory problem of its own; that is, to determine a feasible replenishment policy at each facility in the facilities-in-series which minimizes the average set-up plus inventory holding cost over the infinite horizon. Let a = (<*!,-••,«,.) where a t = [aij\j e Pi)-The allocation vector a is admissible if ctij = 1; ctij > 0 V j £ F and i e R, (3.1) ieii-, Using the policy Vl> for the r fa.cilities-in-series, we observe that the replenishment times associated with the ith facilities-in-series problem, \J/;, are feasible for this problem. Let the cost of this facilities-in-series problem be denoted by Z , ( ^ j , a , ) , if a, is the fractional allocation vector to i tem i. Firs t note that the sequence of orders implied by ^ is the same as the sequences implied by applied to the ith facilities-in-series problem. So the inventory patterns are the same, and hence the inventory holding costs are also equal in both cases. Suppose T is a. replenishment time of a particular facility, say j. The set-up cost of facility j, Aj is paid at time T when \F/ is applied to the general problem. Let E(T) be the set of items in Rs that are replenished at time r by facility j. When ty,- is applied individually to each facilities-in-series problem i, i £ Rj, the total set-up cost incurred at facility j is given by: Ai av — Ai A'3 = Ai i£E(r) iC II, 55 It follows that, for all admissible cost allocation vectors a,, Z(V) > £ £ , ( * , - , « , ) (3.2) Thus the cost allocation method gives a lower bound on the average cost of all feasible policies to the multi-facility joint replenishment problem. Let Z-'(ai) = mjii Zi{tyi,cti) (3.3) This is the minimum average cost over all feasible policies to the ith facilities-in-series problem. We remark that a lower bound on the general problem would be obtained if only the set-up cost of any one facility is allocated. However, allocating the set-up costs of all facilities as is done here decomposes the problem to units that can be solved. We can rewrite this section by replacing the word 'average' wherever it occurs by the word ' total ' , and 'infinite' by 'finite', and the result is stil l true. That is, the lower bound holds true for both finite and infinite horizon problems wi th any deterministic demand pattern. It also applies to non-deterministic demands if items are all distinct. 3.3.1 The Lower Bound Problem A policy is product-nested if each item must be replenished at a facility whenever the immediate predecessor of the facility replenishes the same item. Product-nested policies should be distinguished carefully from the nested policies in the literature, which we might call facility-nested and require that a facility replenishes whenever its predecessor replenishes. Facility-nestedness implies product-nestedness but not vice versa. Consider periodic policies where the intervals between replenishments at a facility, and for each item are constant. The replenishment times for item i at facility j w i l l be, for example, of the form T J J {0, Cjy, 2c,j, • • •} 56 The replenishment cycle time of item i at facility j in this case is c%r We consider periodic and product-nested policies. Power-of-two policies [57,36] which require that the ratio of the replenishment cycle time of an item at a facility to the replenishment cycle time of the same item at a successor facility be an integer power of two, are special cases of the periodic and product-nested policies. The lower bound.problem is developed by first restricting attention to only periodic and product-nestedipolicies. In this class of policies, each facility j has a fixed cycle time of Tj, and a fixed replenishment cycle time T±j for each item i £ Rj. The minimum cost equation is developed for this class of policies. It is then shown that when the integrality requirement of product-nestedness is relaxed, a lower bound on the cost of all feasible policies is obtained. Let s(i, j) = Pi n Sj, that is, the immediate successor of facility j which is also a predecessor of i. Let P be the following problem: P : ZP = m\n{J2(^+ E f k j T a ) } (3.4) subject to Ttj = rn,ijTi<,(ij); rriij > 1, integer; V j £ F, and i £ Rj (3-5) Tij > T3 > 0 ; V j , and i € R3 (3.6) This problem P is the multi-facility joint replenishment problem restricted to product-nested policies. Constraint 3.5 is the product-nested constraint. Replace 3.5 by the following relaxation: Tj > Tis(itj) > 0 V j , and i£ Rj (3.7) This relaxes the integrality requirement of product-nestedness. Denote this relaxed problem by RP and its objective function by Z^p. Because constraint 3.7 is a re-laxation of 3.5, we have Zp > Zpp. The right hand side of equation 3.4, that is the 57 objective function of this problem, can be re-written as jeF iERj i£Rj ieBjEP, L1 Note that, this function is independent of a whenever a is admissible, that is a satisfies equation 3.1. Because T t J > Tj, and Tj is only in the denominator of the objective function of RP, we can get a lower bound on RP by replacing Tj in 3.8 by Tj and deleting the constraint 3.6. Let the resulting problem be denoted by RRP{a), which is stated below. ^ Q . . . RRP(a) : Z R R P [ a ) = min ]T ^ [ - ^r 1 + hi3Ti3'] ieftjeP, v subject to 3.7 This problem is clearly dependent on a. We can now write down the following rela-tionships. Zp > ZpP > ZRRP(a) (3.9) Let RSi(ai) be defined as: RSi(cti) : ZRS,(a) = min ]T 1 + -Ti3•] (3.10) subject to Tij > Tit[iJ) > 0; je Pi. (3.11) W i t h this definition, ZRRP(a) = Z~L ZRSi\<*i)-The notation RSi(cti) is meant to remind us that i25,(a,) is a relaxation of the following periodic facilities-in-series problem: 5,-(at-) : ZSi(a) = min E [-^T- 1 + ^ T i j ] ( 3 - 1 2 ) j£P, J i ' i subject to T^ = mijTis(itj) > 0; m , ; > 1,integer, j G P j . (3.13) 58 The relaxation stems from the fact that 3.11 is a relaxation of 3.13. The desired result is stated after the following proposition. P r o p o s i t i o n 3.1 ZRS,[O,) < Z-{a{) where Z{ (a,-) is defined in 3.3. P r o o f : In [56] Roundy showed that when the integrality requirements on the set of constraints 3.13 are relaxed for the pure assembly system, the resulting problem provides a lower bound on the cost of all feasible solutions to the assembly problem. The facilities-in-series problem is a special case of the pure assembly system. So, that result holds for facilities-in-series problem. That is Z-{cxi) > Z H S x ( a , ) . The following relationship is an obvious consequence of the definitions of P, RP, RRP(a) and proposition 3.1. Yl ZHai) > ZRRP(A) = Yl ZRSi(ai)- (3-14) The above relationship is true for any admissible vector a, that is ZRRP^ is a lower bound on the cost of any feasible solution to the original problem, and also on problem RP, for any admissible a. In particular the maximum of ZRRP^ over all admissible a satisfying 3.1 is our desired lower bound. RRP • ZRRP(A*) = m z x Z R R P ( A ) (3.15) subject to J~] ctij = 1; a,j > 0 V j and i £ Rj ieRj 59 In section 4 we provide an algorithm for this problem which gives T and a such that the following holds. a.ij = 1; ctij > 0. (3.16) {t'|iSifj,T,j=min/t Denote by a:', the particular a which satisfies equation 3.16. First we establish that ZRRP^ = ZRP = ZRRP(0*) and then discusss how a\ or equivalently a' can be determined. Theorem 3.2 Suppose a' satisfies equation 8.16, then any solution to problem RRP(a') ts feasible for problem RP and ZRRP^I) = ZRP = ZRRP(0-) where a is defined in S.15. Thus ZRP is a lower bound on the cost of any feasible solution to the original problem. Proof Let V be a solution of RRP(a'). Let T\ = \mnk{Vki\k £ Rj). The cycle times T" satisfy equations 3.6 and 3.7 and are therefore feasible for problem RP. So we have ZnRp(a>) = ZRR. But as shown in equation 3.9, ZRRP^) < ZRP for any admissible a. The maximum of ZRRP^ over all admissible a cannot be greater than ZRP. Thus ZR.Rp.(a') — ZRRP(a*y The last statement of the theorem follows since ZRRP^^ is a lower bound on the cost of any feasible solution to the original problem. • The implication is that if we solve the lower bound problem and hence can de-termine the optimal values of a, we wi l l have solved problem RP. We now consider the implication of this theorem in the context of the solution procedure we shall pro-pose for providing a' and by implication solving the lower bound problem and RP. Purely as a. motivational device and anticipating somewhat the results below, we shall consider RRP(a) further in the context of 3.16. We know from the above that the solution to RSi(oti) for any particular i £ R of the r facilities-in-series problems gives a lower bound on the cost of an opt imum policy for the facilities-in-series problem. 60 The policy however, may not be feasible. In [57] Roundy has shown that when the constant cycle times T I J 7 are rounded to a multiple of 2 of some common base period, then the cost penalty incurred is less than 6%, or less than 2% if the base period is optimized, of the cost of the optimum policy. In addition the resulting power-of-two policy is feasible. If we take the problem of figure 2.1 and create the facilities-in-series problems as in figure 2.2 for the values of a shown, we could get the solution shown in figure 3.1 below. The numbers to the right of each facility-in-series are the values of the fractional cost allocations from the corresponding facility, while the the numbers to the left are the unrounded cycle times or solution to each RSi(ai), i £ R. If these cycle times are rounded to a common base period, say 2, then we could have the picture shown in figure 3.2. . 8 ( 8 ) 0.3 5 . 1 ® 0.2 4 . 5 ® 0.1 6 . 5 ® 0.15 7 . 5 ® 0.25 2 ( f ) 2.4(6) 0.2 4.6(6) 0.5 4.1(6) 0.3 i !5.1(7) 0.6 4.6(7) 0.4 2 . 4 ® 3.9(3J 3.5(4) 3.7(5 Figure 3.1: A Typical Solution for a Given Cost Al locat ion Although this is a feasible solution, the accounting of set-up costs is not done 61 4.0(8) 0.3 4.0(8) 0.2 4.0® 0.1 8 . 0 ® 0.15 8 . 0 ® J0.25 2.0(6) 0.2 4.0(6 0.5 4.0(6) : 0.3 •o® 4.0(3 4.0(7) 0.6 4.0(4 1.0® L O ® 0.4: Figure 3.2: 'Rounded ' Power-of-two Solution for Figure 3.1 correctly. For example, consider the second replenishment that takes place at time 4.0, after the init ial replenishment at time 0 at facility 8, the total set-up cost incurred at the facility is 0.6Ag, which does not correctly account for the actual set-up cost of A$. What we need for proper accounting is that those facilities-in-series that drive the joint facility cycle times have their values of a that sum to 1, and hence account correctly for the facility set-up cost. Accounting correctly for the set-up cost is exactly the statement of equation 3.16. For example suppose Q 1 8 = 0.5, a2$ = 0.3 and a 3 8 = 0.2, the full set-up cost of facility 8 wil l always be paid whenever a set-up cost takes place at the facility. This correctly accounts for the set-up cost at facility 8. l n the sequel we shall provide an algorithm for choosing a which gives correct accounting, and simultaneously solves 725, (a t ) , for all i £ R. Such a solution ensures that al l facilities-in-series that share a common facility j and have a non-zero allocation > 0, i £ Rj, 62 wil l have an identical cycle time. Wri t ten formally, we shall have that: T,j > Tkj imples a,^ = 0. (3-17) This is obviously equivalent to 3.16 and implies the following: Tij — Tkj whenever atj > 0 and akj > 0 . (3.18) A n y such choice of a wi l l be termed correctly accountable. The main objective of this chapter is to provide an algorithm which solves PS,-(a,), i <E R and simultaneously provides correctly accountable a. Before describing this algorithm, we shall give some useful properties of any opt imum solution to a facilities-in-series problem. 3.3.2 T h e F a c i l i t i e s - i n - S e r i e s P r o b l e m One algorithm which gives the opt imum solution to a facilities-in-series problem is the min imum violators algorithm [56], described in Appendix A . Let j be the topmost facility, that is, the facility without a predecessor and let n £ Sj n P j . Facility n is the immediate successor of j in this series system. Suppose the set-up cost OL{nAn of facility n in the ith facilities-in-series is strictly positive, that is ain > 0 and An > 0. Let ctij = 0- In the opt imum solution provided by the minimum violators algorithm, facility n and j have the same cycle time. Suppose we wish to solve this ith facilities-in-series problem such that the max imum index with a positive set-up cost is n. The set-up cost for a facility k k £ Sj fl P, is alkAk. Let this problem be called P S j ( n , j). The algorithm results in a partition of the set of facilities in the series system into series clusters. The topmost cluster for problem F S , ( n , n ) is CL(i,n,n) while it is CL(i,n,j) for PSi(n,j). The clusters for P 5 , ( n , j ) consists of CL(i,m,m) where m £ P,• n Sn and ra is the root of the cluster CL[i,m,m), and a topmost cluster CL[i,n,j). Note that CL(i,n,j) is different from CL(i,n,n); the former being the topmost cluster for problem PSi(n,j) and the latter being the topmost cluster for 63 problem PSi(n,n). The optimality conditions for these clusters are given in Roundy [56], and repeated here. For any subset B, define T\B\ = ^ J & B AIJ^J The necessary and sufficient conditions for optimality are: 1. T\CL{i,m,m)\ > T\CL(i,k,k)}, implies m > k Also T\CL(i, n.j)] > T\CL(i, m, m)] for m 6 Sn \ CL(i, n,j). 2. T\CL(i,m,m) n Sk] > T\CL(i,m,m)], for any k E CL(i,m,m). These two conditions wi l l be referred to as the optimum series conditions. The follow-ing is a direct consequence of the second opt imum series condition. 3. If / e Sn n Pu T\CL{i,l,l)} < T\CL{i,n,j)\ implies that / £ CL{i,n,j). Another condition that can be deduced from the first two conditions above is: 4. I N £ CL{i,n,j): then CL{i,l,l) C CL(i,n,j) We now show the implications of these conditions in the context of the solution pro-cedure for the lower bound problem. Suppose we wish to solve problem PSi(j,j) parametrically as follows. We first assume that a t ; is set equal to zero, that is the set-up cost at facility j is zero. Thus we have problem PSi(n,j). (Recall n 6 Sj D Pi). The algorithm, for problem PSi(n,j), gives us the topmost cluster CL(i,n,j), with T\CL(i,n,j)) = g ^ ( ' ^ ) \ W > «inAn + 0 d g ^ ( 3 j g ) Z-'keCL(i,n,j)\{nj} aik + "in + nij For I e SnD CL(i,n,j) let . JJ _ T,keCL{i,l,l) aikAk HkeCL((i,i,i) ha* Note that Ui = T[CL(i,l,l)]. Suppose we decide to raise the set-up cost of facility j from its zero level by increasing a,j to a positive value. This process is referred to 64 as allocation in the sequel, and it is the general step in both the algorithms for the facilities-in-series described in this section and for the general problem in the next section. Because facility j is now assigned a set-up cost OHJAJ, the resulting optimal topmost cluster is no longer CL(i.n.j) but CL(i.j.j). Let this new cluster be referred to as the current cluster. To determine membership of this current cluster, replace the zero in the numerator of 3.19 by a^A2 and examine the relationship of T\CL(i,j, j)] and Ui, I £ Sn P , CL(i,n,j). So long as the new value of T\CL(i,j,j)] is less than or equal to the minimum of Ut, I £ Sn D CL(i,n,j), all the facilities in CL(i,n,j) wil l remain in the new cluster CL(i,j,j) and the opt imum series conditions are sat-isfied. Suppose, on the other hand, the value of T\CL(i,j,j)\ is greater than some Ui. This violates the thi rd condition above and by implication the second opt imum series condi t ion. To rectify this situation, we detach CL(i,l,l) from CL(i,j,j). Be-cause of condition 4 above, if CL(i,l,l) is the first such cluster to be deleted, then CL(i,l,l) = Si n CL(i,n,j). By this detachment, the feasible clusters become the clusters obtained when solving P S , ( / , / ) , plus the new cluster CL(i,j,j). The detach-ment also preserves the opt imum series conditions because if T\CL(i, n, j)} was greater than T\CL(i,k,k)\ for some k £ Sn, the new cluster CL(i,j,j) has a cycle time at least as large as T\CL(i,n,j)\, and then also larger than T[CL(i,k,k)}. The detached cluster CL(i,l,l) and the newly created cluster CL(i,j,j) clearly satisfy condition 1 of the opt imum series conditions. The second condition is also satisfied because as the set-up cost Aj is being allocated, any violation of the second condition is immediately rectified by detaching the portion of the cluster causing the violat ion. We can now call Ui, I £ Sn n CL(i,n,j), the upper point and CL(i,l,l) the upper cluster of facility I, which is also the topmost cluster for problem P, (1,1), when allocating the set-up cost of facility j . The upper point is the point at which facility / wi th the upper cluster CL(i,l,l) drops out of the current cluster and the opt imum clusters of P S , ( / , / ) become members of the opt imum clusters for PSi(j,j). We also refer to Ln as the lower point 65 and CL(i,n,j) as the lower cluster of facility n. The lower point is thus the point at which we can begin to consider facility n wi th the lower cluster of n as a member of the current cluster: in this case cluster CL(i, j, j), when the amount of set-up cost allocated from facility j is raised just above zero. The main point to note here is that when allocating the set-up cost Aj the immediate successor of j . that is, n in this case has two sets of clusters associated with it, the lower cluster CL(i,n,j) and the upper cluster CL(i,n,n) while each facility / £ S„ n CL(i,n,j) has one cluster associated wi th i t , that is, the upper cluster CL(i,l,l). The lower cluster must always contain j . This also implies that whenever the set-up cost of a facility is being allocated, the cluster that can be added to the current cluster must contain the immediate successor of the facility whose set-up cost is being allocated, and the cluster that can be deleted must have been a member of the current cluster, that is, the cluster which contains the current facility (the one whose cost is being allocated). A n algorithm based on this allocation method can be used to solve the general facilities-in-series problem if we choose the sequence of subproblems to solve in the correct order. In particular if we have a facilities-in-series problem from i to / , once the problem from i to / is solved wi th the set-up cost of / temporarily set to zero, the final solution is obtained by allocating the set-up cost ctifAj. 66 An Algorithm for the Facilities-in-Series Problem Statement of the Algorithm for P S , - ( / , / ) Initialize: j —^ pt-: / -e— i Step 1: Solve P S , w i t h set-up cost of all P ; temporarily set to zero. Allocate anA\ to topmost cluster CL(i,l,j). to determine the new set of opt imum clusters for PSi(l,j). I *— pi. Repeat step 1 until / =- j. Step 2: j' <— pj\ I <— i. G o to step 1 if j < f. The algorithm for the general problem determines how much of each set-up cost to allocate to each facilities-in-series, so that series by series, the optimum series condi-tions are satisfied and also the allocated fractions are correctly accountable. That is, all those receiving an allocation must have the min imum cycle time before allocation and equal cycle time after allocation. This would suggest that if we only allocate enough to the cluster that has the min imum cycle time to bring its cycle time up to that of the next minimum, then allocate again to all those at this minimum until their cycle time becomes equal to the next, and repeat until no more allocation can be made, then we would have satisfied the criterion of correct accontability. Also using the allocation method described earlier in this section, the allocation satisfies the optimum series conditions for each series. By theorem 3.2, the problem is then solved. We now consider the problem of simultaneously allocating set-up cost to more than one serial cluster, so that the opt imum series conditions are not violated and the allocation is correctly accountable. As an example, suppose after allocating the set-up 67 cost An to four facilities-in-series, we have the lower clusters CL(l,n,j), CL(2,n,j), CL(3,k,j), CL(4,l,j), wi th k and / in Sn. Suppose we have T[CL{4,l,j)} > T\CL{l,n,j)\ = T[CL(2,n,j)} = T\CL(3,k.j)}. This situation implies that a i n > 0, a2n > 0, a 3 n = aAn = 0. For a cluster CL(3,k,j) to be a lower or topmost cluster, the set-up cost of the predecessors of k including n are zeroes. We say that CX(3, k, j) has no allocation from n. Notice that although CL(3,k,j) has no allocation from facility n , it has the same cycle time as the facilities that do receive an allocation. This is a special case when, after allocating the set-up cost of facility n , the resulting cycle time coincides with the cycle time of a series without any allocation. We now wish to allocate A2- to these four lower series clusters so that the opt imum series conditions are satisfied and the resulting allocation is correctly accountable. We start by allocating to a lower cluster wi th minimum cycle t ime. In this case there is a tie; CL(l,n,j), CL(2,n,j) and CL(3,k,j). Because of this, whenever an allocation is made to any one of these clusters, we can always share this allocation amongst the relevant clusters wi th the same cycle time so that their resulting cycle times after the allocation are all equal. This condition wi l l be referred to as keeping the clusters with the same cycle time in balance. Suppose we allocate enough of the set-up cost Aj to the three clusters to raise their cycle time to that of CL(4,l,j). A t this point all the four clusters are in balance and wil l remain so in any further allocation. Further the clusters are now CL(l,j,j), CL(2,j,j), CL(3,j,j) and CL(4,j,j). We wi l l at any point take note of any upper cluster to delete as our allocation gets past the cycle time of the cluster. Because all clusters with an allocation are kept in balance, the fractional allocations to the clusters are correctly accountable, since the clusters receiving allocation have all the min imum cycle time. This is equivalent to correct accountability as in 3.16. Suppose the maximum index of a facility whose set-up cost has been allocated is /. Let us say that those serial clusters that have received an allocation from Ai are similar 68 because they have equal cycle time by our allocation regime. Thus cluster CL(i,l,j) and cluster CL(m,l, j) are similar if T\CL(i,l,j)\ = T\CL(m,/,j)] = Tj. Similar clusters are those clusters whose cycle times are equal and must, by necessity, be kept in balance during any later allocation. If this is the case we loose no information if we combine all similar serial clusters before making any allocation. We can now formally define a combination of serial clusters: Let CL{l,j) = u{CL(i,l,j)\i £ RhT\CL(iJ,j)} = Ti}. Any reference to a cluster, without qualification, in the subsequent discussion is a reference to a combination of similar serial clusters. 3.4 Solution to the General Problem We shall solve the general problem by solving subproblems defined on subtrees of the original problem. Let the path from facility i to facility j consist of facilities in (P.-DS,-). Let TInj be the subtree wi th root node n plus a path from n to j, j £ Pn. For the subtree Tlnj, the set-up cost of all facilities on the path from pn to j are temporarily set to zero, while the set-up costs at all facilities k,k £ Sn are unchanged. The echelon holding costs of items i,i £ Rn at facility n are also temporarily replaced by h'in, defined below. Kn= E bk- (3-20) keP„nS3-The reason for replacing the echelon holding cost at facility n by h'in when solving the problem on Tlnj wi l l become clear in what follows. The cost allocation method applied to Ylnj defines \Rn \ facilities-in-series problems. The problem on the subtree Tlnj is said to be 'solved' when we have partitioned each of its facilities-in-series problems into serial clusters which, series by series, satisfy the optimum series conditions and we have allocated the set-up cost of all facilities k £ Sn 69 between series such that the a's are correctly accountable. Ult imately, we wish to 'solve' the tree 11//. Thus we consider the equivalent \Rn\ series problem from i to n with the echelon holding cost at facility n in the iih facilities-in-series replaced by h'in. A formal definition of problem RPn„j on J\nj is as follows: RPnHj: m i n £ £ \^HL + htmTim] (3.21) subject to Tim > Ti.,(,- im); V m e l l n ; & i e Rm\ (3.22) T .m > T m > 0 ; V m e n n j & i G 7? m . (3.23). A n d a formal statement of the desired solution is as follows: find clusters which par-t i t ion the \Rn\ facilities-in-series and a feasible allocation <*ik > 0; Y aik = i ; 1 ^ Rn, k e Sn such that the optimal series conditions hold, and the allocation is is correctly account-able, condition 3.16 is satisfied. Theorem 3.2 tells us that an opt imum solution to this problem does in fact possess these properties. Recall that correct accountability is defined by: Tkm > Ttm implies a k m = 0 We can deduce from these that whenever correct accountability is achieved, the fol-lowing must also be satisfied: Tkm =miny Tj,„ } aim. 2: a t m > 0 and a k m > 0 imply Tim = Tkm. We know by Theorem 3.2 that the above conditions, that is, correct accountability and the opt imum series conditions, are sufficient for the optimali ty of any a. The algorithm below is designed such that at each allocation step, the opt imum series conditions are 70 satisfied and moreover the a's resulting from the allocation are correctly accountable. The algori thm ensures that the relevant information is available when allocating Af. 3.4.1 The Algorithm This algorithm provides correctly accountable ct's which also satisfy the opt imum series conditions for each subtree Tlnj in 0(dn\Rn\ log \Rn\) time, where dn is the number of facilities on the longest path from an item to root facility, which in this case is facility n . The algorithm is constructive. It consists of solving a sequence of problems on subtrees Jlnj, j £ Pn- The set-up cost An is allocated sequentially to the lower clusters to raise the min imum cycle time as much as possible. If at any time during the allocation, the cycle time of the current cluster becomes greater than that of an upper cluster which is a subset of the current cluster, that upper cluster is deleted from the current cluster. This allocation rule is justified on the ground that series-by-series, it preserves the opt imum series conditions and the resulting fractional allocations are correctly accountable since all clusters wi th the same cycle time before allocation are kept in balance during allocation. B y Theorem 3.2 this allocation rule solves RP\-\nj. A simple way to carry out this allocation procedure is to rank and merge all the existing lower clusters CL(l,j) where / £ Sn and the upper clusters, that is those clusters whose roots are in CL(l,j), and to perform the allocation step to be described later in this section. Initially the current cluster CL(n,j) only consists of facilities (Pn\Pj)l) {j}. A list of the the relevant lower and upper clusters, ranked in ascending order of their cycle times, is kept in the list of unchecked clusters denoted by UP(n,j). The set-up cost An is allocated first to the unchecked cluster with the smallest cycle t ime. Members of this cluster are added to cluster CL(n,j). The set-up cost associated wi th this cluster is 71 added to the set-up cost An to determine the new set-up cost of CL(n,j). The holding cost of the new cluster is the holding cost of the old cluster. Let r n j denote T\CL(n,j)\. The resulting r n j is then compared with the next point on the list UP(n,j). If rnj is greater than or equal to the next point and the point is a lower point, the cluster associated wi th it. is added to the current cluster, if it is strictly greater and the point is an upper point, the cluster associated with the point is deleted from the current cluster. In either case rn] is updated. Deletion of a cluster consists of simply removing the set-up cost and the holding cost of the cluster to be deleted from the set-up cost and holding cost respectively of the current cluster, while addition of a cluster consists of adding the set-up cost and the holding cost of the cluster to be added to the set-up cost and holding cost respectively of the current cluster. When allocating, a record of all the upper clusters deleted from the current cluster, that is the clusters in the immediate successor set of the current cluster, is kept in a list known as the active points AP(n,j). It wi l l be seen that AP(l.j) I (E Sn is a record of the feasible clusters for Tlnj. The algorithm consists of two major steps. S t e p 1: Determination of the unchecked points. S t e p 2: Al locat ion of the set-up cost to determine the active points, while simultane-ously updating the unchecked points. Let UP(k,j) be the ordered list of unchecked points, representing the clusters when solving the problem on Tik] and when allocating Ak. The points are quadruples. The first element is the cycle time of the cluster, the second element is the first index of the cluster, that is, the root of the cluster, and the third element is the second index of the cluster. The fourth element is an indicator variable indicating whether the point (cluster) is a lower or an upper point (cluster). D e t e r m i n a t i o n o f u n c h e c k e d p o i n t s : 72 Let © be a notation for 'rank and merge'. The following are the formulae for deter-mining the unchecked points relevant to problem Tlkj. A A-UP{i,j) = (( —L,i,j.lower); upper)): i £ R; j = p{; UP{i,j) = {^~,i,j.lower): i£R j > pt UP{n,j) = ®{UP{k,j); k e sn) © {AP{n,l);n(t R, l e Sj n Pn} since Sj n Pn — 0 for n = j UP(n,n) = ®UP(k,n); k 6 sn. A l l o c a t i o n of s e t - u p cost An to UP(n,j), n ^ R: Initially set rnj to a very large number. Compare it wi th the first element of the next point in the ordered list UP(n,j). Let a point whose second and th i rd elements are / and k repectively be denoted by Let the next point in the ordered list of points of UP(n,j) be C/ i f c. B and E are init ial ly zero. If r n j > rlk, and it is a lower point, do the following: Bnj < — An + Bik, Enj <— Enj + Eik, CL(n,j) <— CL(n,j) U CL(l,k) otherwise if it is an upper point, and the inequality is strict do the following: Bnj <- Bnj - Btk, Enj *- Enj - Elk, CL(n,j) <- CL(n,j) \ CL(l,k), AP{n,j) AP{n,j)(j{Ulk}. In either case UP{n,j) +- {UP{n,j)\Ulk). Let rnj <- | j and T( <— r n j for all / £ CL(n.j). Compare rnj with the next unchecked point of UP(n,j) and repeat the above update unti l rnj < rlk, where Uik is the next unchecked point of UP(n,j). The current point is denoted by Unj- Include the current point in UP(n,j) as the first unchecked lower point. If n = j , after the above update, check all remaining unchecked points in UP(n, n). If the next unchecked point is a lower point, include it in AP(n,n) as an upper point and delete it from UP(n,n). If the point is an upper point, simply delete it from UP(n,n). Repeat unti l UP(n,n) is empty. 73 This later step is necessary to ensure that all serial clusters of the CL(i,l,n) I G sn become CL(i,n,n) after allocating the set-up cost An even for those without an allocation. S t a t e m e n t o f the A l g o r i t h m I n i t i a l i z e : Eij <— h\- and Bi3 <— A , ; Mj and i G Rj UP{n,j)+-Q, A P ( n , j ) < - 0 , CL{n,j) <- {n}, n $ R-J £ Pn AP{i,i) <-0, i e R Determine UP(i,j), and set CL(i,j) {i}, i G R, j' G P,-. M a i n S t e p : For ra = | P | + 1 step 1 unti l n = f Determine UP(n,j); j G P n . Allocate A n to determine AP(n,j) and update ,-UP(n,j). The cycle times from the algorithm are given by k£F To get a policy which is 94% effective, we simply choose a base period and round the cycle times to the nearest power-of-two of the base period in such a way that the order of the cycle times are preserved. That is if T'k > T{, then the cycle times should be rounded such that if Tk denotes the rounded cycle time of facility k then Tk > 7}. To obtain a solution which is 98% effective, we optimize over the base period. Details of this are in Roundy (57]. 74 Complexity of the Algorithm For illustrative purpose we assume a symmetric tree. If. the number of facilities in P,-is d for i G R, we say there are d, stages in the facilities network. Let Fk be the set of facilities in stage k and let the number of successors for each facility in Fk be nk. W i t h this notation Fx = R and n r f n d _ 1 . . . n 2 = r. For each j £ F 2 , the ranking done to determine unchecked points is ra2logre2. This is done for the n d ra d _]. . .n 3 facilities in F2. The required amount of work for this ini t ial ranking is thus n d n r f_j . . . n 3 n 2 log n2 = r log n2 The amount of computational work involved is r which is no more than in ranking as long as n2 > 1. The ranking is done d — 1 times. So the total amount of work in ranking involving j G P 2 is (d - l ) r \ogn2 For j G P 3 we need to merge already ranked points of F2. The amount of work for the merging operation for each j G P 3 is n3n2 log n3 Again the amount of computational work is no more than the ranking as long as ra3 > 1. The ranking is done for the n^nd-i•••nA facilities in P 3 , (d — 2) times in a l l . The total amount of work involved is thus (d - 2)n d n r f _]. .n 2 log n 3 = {d - 2 ) r l o g n 3 In general the amount of ranking for facilities in stage k is (d - k + l ) r logn,t The computational work is again, no more than the ranking as long as. nk > 1. The total amount of work involved in ranking for the algorithm is thus d E (d — + l ) r log nk < dr log r k=2 • 75 The complexity of the algorithm is therefore 0(dr log r ) . The case where some or all = 1, k = 2,..., d, is rather too special to be of general interest here. 3.4.2 Example 3.1 Let Ax = 4, A2 = 5, A3 = 7, A4 = 2, A 5 = 20, A6 = 8, A 7 = 6 and A 8 = 10. h n = .14 ^16 = .16 his = .05 .25 h2& - .20 h2s = .10 ^33 = .15 h3& = .10 hzs = .05 h44 = .30 h47 = .20 h4S = .15 ^55 = .20 h57 = .15 hw = .10 Initialize A * wi l l be used to denote a lower point. t /P( l ,6 ) = {4/.14 (1,1): 4/ .3* (1.6)} rjp(2,6) = {5/.25(2,2); 5/.45 * (2,6)} £/P(3,6) = {7/.15 (3,3); 7/.25 * (3,6)} UP{4,7) '= {2/.30(4,4); 2/.50 * (4,7)} f/P(5,7) '= (20/.20(5,5); 20/. 35* (5,7)} l/P(l,8) = {4/.35* (1,8)} £/P(2,8) = • {5/.55* (2,8)} £/P(3,8) = {7/.30* (3,8)} £/P(4,8) = {2/.65* (4,8)} C/P(5,8) =' {20/.45 * (5,8)} 76 Set CL(n,j) n for all relevant n and j. t /P (6 ,6 ) = t / P ( l , 6 ) © t /P(2 ,6) © t /P(3 ,6) = 5 / .45* (2,6); 4/.3 * (1,6); 5/ .25(2,2); 7/.25 •• (3,6); 4 / . 14 (1,1); 7/.15 (3,3). Allocate As = 8 to obtain AP(6,6) = (5 / .25(2 ,2) ; 12/ .5(6,6); 7/ .25(3,6)} C L ( 6 , 6 ) = {6,1} C/P(6,8) = £ / P ( l , 8 ) © C / P ( 2 , 8 ) © t / P ( 3 , 8 ) © A P ( 6 , 6 ) = {5 / .55* (2,8); 4/.35 * (1,8); 5/ .25(2,2); 7 / . 3 * (3,8); 12/ .5(6,6) ; 7 / .25(3 ,6)} Allocate A& = 8 to obtain A P ( 6 , 8 ) = 0 t /P (6 ,8 ) = { 1 7 / . 9 * (6,8); 5/ .25(2,2); 7/.3 * (3,8); 12/ .5(6,6) ; 7/ .25(3,6)} C L ( 6 , 8 ) = {6,1,2} \UP{1.1) = UP{4,7) © C / P ( 5 , 7 ) { 2 / . 5 * (4,7); 2/ .3(4,4) ; 20/.35 * (5,7); 20/.2 (5 Allocate A-i = 6 to obtain A P ( 7 , 7 ) = {2/ .3(4 ,4) ; 6 / .2(7,7) ; 20/.35 (5,7)} C X ( 7 , 7 ) = { 7 } 77 E/P(7,8) = r j P ( 4 , 8 ) © l / P ( 5 , 8 ) © v l P ( 7 , 7 ) = {2/.6S* (4,8); 2/.3(4,4); 6/.2(7,7); 20/.35(5,7); 20/.45 * (5,8) } Allocate A 7 = 6 to obtain A P ( 7 , 8 ) = {2/.3(4,4)> t/P(7,8) = {6/.35* (7,8); 6/.2(7,7); 20/.45 * (5,8); 20/.35 (5,7) } CL(7,8) = {7} UP{8,8) = UP{6,8) © t / P ( 7 , 8 ) = {6/.35* (7,8); 17/.90 * (6,8); 5/.25(2,2); 7/.3* (3,8); 12/.50(6,6); 7/.25(3,6); 6/.20(7,7); 20/.45 * (5,8); 20/.35(5,7); } Allocate As — 10 to obtain A P ( 8 , 8 ) = {5/.25(2,2); 12/.50(6,6); 7/.25(3,6); 16/.55(8,8); 20/.45 (5, 8) } _ CL(8,8) = {8,7} The resulting clusters and their cycle times are recorded in AP(6,8) , AP(7,8) and AP(8,8) . The clusters are obtained starting from the 'topmost' that is facility 8, and working down through the facility network, such that a facility is examined only after 78 its predecessors have been examined. Thus AP(8,8) C L U S T E R facilities in Cluster Cycle Time CL(2 ,2 ) CL(6 ,6 ) CL(3 ,6 ) CL(8 ,8 ) C L ( 5 , 8 ) 2 yJb/0.25 = 4.47 1,6 ^12/0.50 = 4.90 ^7/0.25 = 5.29 7,8 ^16/0.55 = 5.39 5 ^20/0.45 = 6.67 AP(7 ,8 ) CL(4 ,4 ) 4 2.58 A P ( 6 , 8 ) The cycle times at each facility and for each item at a facility are obtained directly from the table above. TU = r1 6 = r2 6 = rj = r6 = 4.90 r 2 2 = T2 = 4.47 T 3 3 = r3 6 = r3 = 5.29 7^44 = 7^ 4 — 2.58 T 5 5 = T 5 7 = T 5 8 = 6.67 TiS — T 2 8 = T 3 8 = T4S = T47 = T 7 = Tg — 5.39 The determination of the fractional allocation is not a necessary part of the algorithm but it can be done as an illustration to check that the solution obtained corresponds to correctly accountable cost allocation and also satisfies the opt imum series conditions. We can determine the cost allocations as follows. Allocation at facility 6 79 Firs t note that a 3 6 = 0 since T 3 6 > T&. The following gives a 1 6 and a26 a 20, A6 h2e and a 1 6 -f a2G = 1. This gives us a ] 6 = 0.4 and a2a — 0.6. Allocation at facility 7 Since T57 > T7 a 5 7 = 0 and hence 0:47 = 1. Allocation at facility 8 Since T 5 8 > T 8 , c*58 = 0- The other allocations can be obtained using the equations below. W i t h these two equations we have a 1 8 = 0.145, a2S = 0.290, a3S = 0.145, and a 4 8 = It can be checked from figure 3.3 that -these allocations (on the right of circles) are correctly accountable and that the cycle times (on the left of circles) satisfy the op t imum series conditions. ^ 1 8 ^ 8 ^18 CX28^8 _ a 3 8 ^ 8 h2s h3s A7 + O J 4 8 A 8 /147 + /148 and "18 + « 2 8 + "38 + 0>48 = 1 0.420. 80 5.39(8)0.145 5.39(8) 0.29 5.39(8)0.145 5.39(8) 0.420 ! 4 .9(6) 0.4 4 . 9 ( 6 ) 0.6 4 . 9 ® 5.29(6) 0. i !5.39(7) 1.0 . 4 7 © 5.29 (3 ! . 5 8 ( t ) Figure 3.3: O p t i m u m Clusters for Example 3.1 81 C H A P T E R F O U R The Multi-Product Dynamic Lot-Size Problem Introduction This chapter considers the determination of lot sizes in a multiple product environ-ment. A fixed set-up or order cost Ao is incurred whenever any product is ordered or produced, independently of the number or type of products; and an extra cost A , is added if product i is included in the joint order. The demand for each item is discrete in time and known over a given time horizon H. Linear holding costs are charged on the end of period inventories and backlogging is not permitted. It is assumed that the variable purchase cost for each product is constant through out the horizon, so that the total purchase cost of any item for total demand in the horizon is a constant independent of the replenishment policy since backlogging is not permitted at the end of the horizon. Quantity discounts are not considered here. The problem is to schedule the replenishment of each item so that the total set-up and inventory holding cost is minimized over the horizon. This problem has been studied very widely in the literature with several optimal solutions proposed. The dynamic programming solutions for this problem are complex. The solutions by Zangwill and Veinott described in Chapter 1 are generalizations of this 82 problem. When specialized to this problem Zangwill 's method (86] is exponential in the number of products, while Veinott 's [78] and Kalymon's [40] solutions are exponential in the number of time periods. Solutions which are exponential in the number of products have also been proposed by K a o [41] and Silver [66]. These solutions are not useful for practical problems which usually involve many items and many time periods. Efforts have therefore shifted to the development of heuristic solutions. Unfortunately, though these heuristics are relatively simple when compared to the opt imum solutions they still have two major disadvantages. Firs t , they generally depend on the Wagner-W h i t i n dynamic programming solution to the single item dynamic lot size problem. Second, it is not known how good these heuristics are. Some of these heuristics are described in Chapter 1. Silver [67] reports on a simple one-pass heuristic with a three product example. Because a typical practical problem involves many items, and managers find it difficult to understand dynamic programmin solutions, these heuristics are not desirable from a practical standpoint. The a im of this chapter is to present heuristics which overcome the two disadvantages of earlier heuristics. We introduce a new lower bound (the cost allocation bound) whose computational complexity varies as the square of the number of time periods and linearly as the number of products. In addition we present generalizations of some of the very simple heuristics for the one product dynamic lot size problem. Thus for any data set we can establish easily a bound on how far the opt imum is from the heuristic solution. The heuristics that we generalize are; the Silver-Meal [54], the part-period balanc-ing ( P P B ) and a variant of it proposed by Bi t r an , Magnant i and Yanasse [8] which we denote as B M Y heuristic. It is known that the Silver-Meal heuristic is arbitrarily bad in the worst case but performs very well in practical problems. We show by a series of examples that the generalization we propose also performs very well. It is, of course, not questionable that this generalization can also be arbitrarily bad in the worst case. The Si lver-Meal heuristic is known to be widely used in practice [54] because of its 83 simplicity and the very highly intuitive base. So, we hope that this generalization wi l l also capture the attention of practitioners who have joint replenishment problems to solve. The part-period balancing heuristic is known to perform well in practice and it is simple, but it has an effectiveness ratio of 1 /3. That is the ratio of the cost of an opt imum solution to the cost of the heuristic solution cannot be less than 1/3 in the worst case. We shall show that when this heuristic is generalized to the multi-product dynamic lot size problem, the effectiveness of the generalized heuristic cannot be less than 1/3 either. The other heuristic ( B M Y ) reported in [8] which is a simple variant of the part-period balancing heuristic is shown to have an effectiveness ratio of 1/2. We show that when this heuristic is generalized, the generalization does not affect its effectiveness. These generalized heuristics are simple one pass heuristics, which are linear in the number of products and the length of the horizon. The lower bound run time is linear in the number of products and the same as the Wagner-Whit in algorithm in the number of time periods. We thus have heuristics and also a posteriori guarantee of the heuristics' performances on all data set. In two cases, the genaralized part period balancing and a variant of it, the B M Y heuristic, we in fact have the effectiveness ratios. For the generalized Silver-Meal heuristic we report results over a wide variety of cost and demand scenarios for a thirty product, twenty-four period problem, which is a much larger problem than any reported result in the literature. We emphasize that the heuristics can be used very easily for any number of products. The heuristic is usually between 95% and 100% of the lower bound and hence maybe even closer to the opt imum. This chapter is divided into four sections. In section 2, we formally define the problem and describe the lower bound. In section 3, we describe the Silver-Meal heuristic and the generalization. The result on a series of examples are also presented. 84 In section 4, we present the two other heuristics, the generalized P P B ( G P P B ) and the generalized B M Y ( G B M Y ) , and establish their effectiveness ratios. 4.2 The Lower Bound Let N be the number of items and H the time horizon. There is a. linear inventory holding cost hi per unit per period for item i. Backlogging is not allowed. The major reorder cost is A0 while the item-specific reorder cost is Ai for item i. Let du, Xtt and lit be the demand, order quantity and end of period inventory respectively for item i in period t. The holding cost rate can be allowed to vary from period to period but it is assumed constant for expository simplicity. Let 6(x) = 0 if x = 0 and 6(x) = 1 if x > 0. The problem of minimizing the total order cost plus inventory holding cost over the horizon can be stated as follows: H r N N P: ZP = niin^ I Ao6[J2 Xit]+ Yl\Ai6{Xit)+hiIit] t=l l i=l i=l subject to -Xlt + lit-i - dit - In = 0; Vt" and £ = 1 ,2 , . . . , IT (4.1) Xit > 0, Iu > 0, du > 0. (4.2) Without loss of generality, we can assume that IiQ = 0. Let us say that the fractional allocation a is admissible if £ > * = 1; ait>0; V / Let ai — (ail,aI2,... , atH) For any admissible cost allocation we can write the follow-ing single item dynamic lot-size problem: Pi{ai) : ZP.(ai) = mm{(aitA0 +Ai)6(Xit) + hJit} subject to 4.1 and 4.2 85 Since it, must be true that A' Zp >Y Zp,(a,) i = 1 Note that JliLi Zpi(a,) i s the objective function value of a decomposition problem, P{cx), of problem P. The lower bound expressed in equation 4.2 is true for any admissi-ble a. It is reasonable therefore to choose the a which maximizes Zp(ay The problem of making such a choice is st i l l rather complex. The problem Pi(at) is a single item dynamic lot size problem. Many heuristics exist for solving this problem. In Chapter 2, it was observed in the case of continuous review, infinite horizon stationary de-mands and cost parameters, and minimizat ion of long run avearge cost problem, that the choice of a was made so that the min imum cycle time was as large as possible. We use a similar strategy for choosing a in this case. We select a such that when each problem P,-(a,-) is solved then in any interval, the minimum 'run-out' time for any i tem is as large as possible. Having chosen a we can then determine Zp^ai) using the Wagner-Whit in 's algorithm for the dynamic lot size problem. In the following sections, we describe heuristics solutions to the multi- i tem dynamic lot-size problem and the corresponding methods of choosing the fractional allocations. 4.3 Generalized Silver-Meal Heuristic Firs t we review the Silver-Meal heuristic for the single item dynamic lot size problem. Let SMit(Ai) = A + hi T,'j=Li{j - Li)d%} t - U + 1 where Li is the time of the last set-up for item i. The heuristic recommends a set-up at time t if t is the first time after Ll such that SMit(Ai) > SMit~i(Ai) 86 Multiple Items The following is the Silver-Meal heuristic generalized to the multiple item environment. Let T be a set-up epoch. A t any time t > T, products are in one of two sets, set R contains all items for which it has already been decided to include in the joint replenishment at time T, that is we have L , = T. Set C , the 'continuation' set contains all other items, that is those for which L , < T. For the products not in R, we have the choice of reordering them at time T, or continuing to satisfy demands from the previous set-up. The total cost of continuing to satisfy demand between T and t > T from the previous set-up Li is given by t while the cost of ordering at time T and continuing to t > T is t -. j=T So these products would rather not join the reorder set unti l i hi{T - Li) Yl dij > A (4.3) The Heuristic I n i t i a l i z e : Put all items in R and let C be the empty set. Let T = t = 1. Step 1 Calculate SMit(Ai) for each i 6 C. If SMtt(At) > SMu-^Ai) and the condition of equation 4.3 holds, move i from C to R and set L t <— T. Step 2: Calculate SMit(Ai) for each i £ R. If SMit(At) > SMit-i(Ai), we allocate as much of the major set-up cost A0 to i tem i to equalize the two quantities. The allocation, A,-, necessary to do this is given by SMit(Ai + Ai) = SMit_1(Al + A,-) (4.4) 87 Set t <— t + 1 and repeat steps 1 and 2 unti l £2; A ; > A0. In this case go to step 3. Step 3 Set T t and reorder at time T. Let 7? = {z| A , > 0 } and L , = T if i (E R. Return to step 1 until i = B. This algorithm is easy to program and clearly runs in time proportional to TV and H. An Example Three items and five periods problem wi th the following parameter values. Ao = 39, Ai = A-2 = As = 20, hi = h-2 = h-s = 1. The demands are shown in the table below. Time 1 1 3 4 5 item 1 10 6 20 10 10 item 2 5 4 12 16 10 item 3 10 10 6 2 7 The Algorithm Initially R = {1 ,2 ,3}: C = 0; U = L2 = L3 = 1. T ime t = 1 S M „ = 20 SM-n = 20 S M S 1 = 20 A i = 0 A 2 = 0 A 3 = 0 Time t = 2 SMV1 = 13 SM22 = 12 SM32 = 15 A i = 0 A 2 = 0 A 3 = 0 Time t = 3 SMiS = 22 SM23 = 16 SM3S = 14 A ] = 54 A 2 = 24 A 3 = 0 This is because SJWi 2 (20 + 54) = 5 M 1 3 ( 2 0 + 54) = 40 and 5 M 2 2 ( 2 0 + 24) = 5 M 2 3 ( 2 0 + 24) = 24 88 As A ] + A 2 > 39 a reorder is scheduled at T = 3 and we reset L\ — L2 — 3 and P = { l , 2 } , C = {3}. T ime 4 : S M ] 4 = 15 SMU = 18 SMM = 12 • A ] = 0 A 2 = 0 A 3 = 0 T ime 5: SM^ > SM-i4 and (3 - 1)(6 + 2 + 7) > 20 so item 3 joins R, is reordered at T = 3. and set L3 = 3. S M 1 5 = 50/3 5 M 2 5 = 56/3 5 M 3 5 = 12 A 3 = 10 A 2 = 4 A 3 = 6 No reorder is scheduled at time 5 because the major set-up cost is not exhausted, that is A ] + A 2 + A 3 = 20 < 39 = A0 So the heuristic gives a reorder schedule of Time 1 2 3 4 5 item 1 16 0 40 0 0 item 2 9 0 38 0 0 item 3 20 0 15 0 0 and a total cost of 2(39) + 6(20) + 1(102) = 300. The lower bound We left the lower bound without specifying a choice of att. From the heuristic, at a period when we decide to reorder we have allocated A 2 > 0 to i' £ R and A , = 0 to i £ C. Let A t-a u = T A " 89 for each i 6 R and for each period t, from the period immediately following the last joint reorder period to period T. If the last joint reorder is in period 1, then an is as above from t = 1 to t = T. The logic behind this rule is that this allocation lengthens the joint reorder interval as much as possible. When A , = 0, which may be the case when t = H, we simply allocate Ao equally amongst all the items. Returning to the example we have the values of an. Time 1 2 3 4 5 item 1 54/78 54/78 54/78 10/20 10/20 item 2 54/78 24/78 54/78 4/20 4/20 item 3 0 0 0 6/20 6/20 The Wagner-Whit in solution to each in turn is Time Cost 1 2 3 4 5 item 1 16 0 40 0 0 130 item 2 9 0 38 0 0 104 item 3 20 0 15 0 0 66 which gives a total cost of 300. The heuristic gives the opt imum solution in this case. We now present the results for realistically sized problems. 4.4 Computational Experience We take the following problem. Horizon=24 periods and the number of items equals 30. Wi thout loss of generality we take / i , = 1 for all items. The item-specific set-up costs A% are uniformly distributed on [30,50]. The demand is uniformly distributed on [a, b] as shown in Table 4.1. Each cell of the table gives the average performance for 90 Ao demand 0 100 200 300 400 [20,20] 0 0 0 0 0.2 [20, 30] 0.3 0.2 0.1 0.2 0.4 [15,25] 0.5 0.6 0.9 1.8 2.5 [15,30] 1.3 0.6 1.0 1.4 3.0 [10,20] 3.8 3.5 3.5 2.4 2.4 [5,10] 1.5 2.7 2.8 2.8 3.3 [5,15] 4.0 2.7 3.3 5.2 6.4 [10,30] 4.4 2.7 3.0 4.3 5.3 Table 4.1: Heuristic Performance five different runs. The performance measure used is heuristic cost — lower bound cost - — x 100 lower bound cost The first row is for a constant demand. The first column is essentially the Silver-M e a l heuristic, although the possibility of the rule in equation 4.3 changes things slightly. We see that over a wide data set, seldom is the heuristic more than 5% away from the lower bound and hence closer to the unknown opt imum. We see however that when the demand variability is proportionally high, that is (b — a)/a = 2, as in the last two rows and the joint cost Ao is high, the performance of either the heuristic or the bound or both deteriorates. We have presented a simple heuristic, easy to code and calculate, which is essentially an extension of the Silver-Meal heuristic for single products. The key importance of this heuristic compared with other heuristics is that a posteriori performance guarantee is given for the particular data set being considered. A variety of experiments on 91 varied data sets indicate performance of usually better than a 5% error. In view of the inaccuracies of demand and cost data typically available to the production planner, a 5% gap from the lower bound but not, necessarily from the opt imum is a relatively small price to pay for the simplicity of the algorithm. 4.5 Other Heuristics The heuristics to be generalized in this section are the part period balancing heuristic and a variant of it introduced in Bi t ran et al . [8] to be referred to as B M Y heuristic. The main purpose of this section is to show that the effectiveness ratios of these generalized heuristics are the same as the effectiveness ratios of the corresponding single item heuristics. 4.5.1 P P B a n d G P P B H e u r i s t i c s The part period balancing heuristic minimizes the absolute difference between the set-up cost and the inventory holding cost unti l the next set-up. Let Hi(Li,t) be the cummulative inventory holding cost from period L ; to /. — 1 given that a set-up occurs at period L , . Let t' be the smallest time greater than L t such that Ht(Li,t') — Ai > 0. The part period balancing heuristic sets up in period t' if Hi(tt,t') - A < A - Hi{ti,t' - 1) (4.5) and in period t' - 1 otherwise. Proposit ion 4.1 The effectiveness of the PPB heuristic is at least l/S. Proof The proof of this proposition is given in [8] and is repeated here. The maximum inventory holding cost between any two set-ups is 2,4,. So the max imum total cost 92 incurred from one set-up to the period before the next set-up is 3At. If the two consecutive set-ups of the heuristic are and t\ the cost incurred in an optimum policy between £, and t\ cannot be less than A,-, being either a set-up cost or inventory holding cost. Thus if C# is the cost of the heuristic solution and C 0 is the cost of the opt imum solution, the effectiveness of the P P B heuristic is given by 9°. > A = I CH ~ ZAi 3 • For the G P P B heuristic, let L , be the last time item i was ordered. Let Gt be defined as the set of items each of whose accumulated holding cost at t ime t exceeds its item-dependent set-up cost, that is Gt = {i\Hi(Li,t) > A,} and let t' be the first time after L, such that the following holds •Y,{Hi{Li,t')-Ai)-A0>0 (4.6) ieG,, A set-up is made at /,' if E {ffi(Li,t') - A{) - A 0 < E (Ai ~ Hi{Li,t' - 1)) + A0 i€Gt, ieG,, and at time t' — 1 otherwise. The items reordered are those in Gt>. P r o p o s i t i o n 4.2 The effectiveness of the GPPB heuristic is at least l/S. P r o o f Suppose two consecutive set-ups are in periods t' and t". The max imum cost incurred for those items ordered at t" between periods t' + 1 and / " inc lus ive is the set-up cost at period t", which consists of A0 plus the the set-up cost of the items ordered at time t"; and the inventory holding cost in these periods. But the inventory cost cannot be 93 greater than twice the set-up cost at period t". Thus if we denote the set-up cost by A" and the cost given by the heuristic in the interval by C"H C"H < 3A" + Inventory cost of items not ordered at t" If the opt imum cost in this interval is CQ then Co > A" + Inventory cost of items not ordered at t" Note that the minimum cost for all those items ordered by the heuristic at t" is A". If an item not ordered by the heuristic is ordered in the opt imum solution, the set-up cost incurred for that item is greater than the holding cost for the item in this interval. Also if an opt imum set-up occurs between the last heuristic set-up and the end of the horizon, the cost incurred due to this set-up cannot be less than the holding cost incurred by the heuristic. Thus the effectiveness of the heuristic is given by CQ ^ A" + Inventory cost of items not ordered att" A" 1 C'H ~ ZA" + Inventory cost of items not ordered at t" ~ SA" 3 • 4.5.2 B M Y and G B M Y heuristics B M Y requires a set-up to be made at time t' — 1 if Hi(ti,t') > A{ and #,•(*,-,*' - l ) < At where t' is as defined in 4.5. P r o p o s i t i o n 4.3 The effectiveness of the BMY heuristic is at least 1/2. P r o o f The proof is similar to the proof of proposition 4.1. Here the inventory holding cost between two consecutive replenishments is bounded by the set-up cost. 94 For the G B M Y heuristic, a set-up is made in period t' — 1 where t' is as defined in 4.6 above. Proposition 4.4 The effectiveness of the GBMY heuristic is at least 1/2. Proof The proof is similar to that of proposition 4.2. The inventory holding cost between two consecutive replenishments is bounded by the cost of the second set-up in the interval. • 4.6 Conclusion We have presented very simple heuristics which are easy to implement and easy to code. The first is a generalization of S i lver -Meal heuristic. This heuristic is shown to perform very well on a series of examples. The second is a generalization of the part period balancing while the third is also a generalization of a variant of the part period balancing first presented in [8]. The effectiveness ratios of these latter heuristics are shown .to be the same as for their corresponding single item heuristics. It is also simple to derive lower bounds for these heuristics. The major contribution of this chapter, therefore, is that it gives simple heuristics with posteriori guarantees of performance. 95 C H A P T E R F I V E Periodic Versus 'Can-Order' Policies Introduction In this chapter we consider the problem of the coordination of replenishment orders for groups of items in a mult i - i tem inventory system. A single fixed cost is incurred whenever any item is replenished and an individual fixed cost is incurred for each item included in the joint replenishment. The latter is often referred to as a 'line i tem' cost on a joint reorder. Demands are generated by independent Poisson Processes. Excess demands are backlogged and there is a constant delivery lead time for each item. The full model details are described in section 2. Here we discuss the motivation and the main results of this chapter. Al though in practice periodic replenishment policies may perhaps be more preva-lent, the literature has tended to concentrate an (s.c,S) or can-order systems. Such a policy operates as follows. When any item's inventory drops to its reorder point s,-a reorder is scheduled. Other items j are inspected and any at or below their can-order point Cj are also included in the reorder. Items i (resp., j) are reordered up to Si (resp., Sj). Such policies were proposed by Balintfy [6] and have been investigated in a series of papers by Silver [65,68,69], Thompstone and Silver (75] and recently by Fed-96 ergruen et al . [23], and have been shown to be considerably better than uncoordinated policies, often with savings around 20%. We know 'can-order' policies are not opt imal , e.g., Ignall [35]. However, their performance on small problems (two products) has been good, Silver and Peterson [54, page 450]. The question arises as to how good they are for realistically sized problems. The cost allocation bound described in Chapter 2 also applies to this problem but, used as a lower bound, it is 'a long way' below the 'can-order' policy. B y a 'long way' we mean varying from nothing when the joint cost is zero, that is no coordination opportunities, to up to 50% for subtantial joint costs. This raises the question whether the bound is weak or whether can-order policies can be considerably improved or both. These results were obtained on a 12-item example. In order to answer this question, an alternative heuristic is proposed which is very easy to calculate and implement. A n obvious choice would be a. heuristic wi th opportunity for coordination. One such heuristic is an (R.T) periodic review policy where every T periods the inventory of item i is raised to i2t-. (R.T) policies are common in practice as they tend to lower set-up cost because the process of setting up for replenishment becomes a routine periodic operation. To achieve coordination, all periods T are integral multiples of a base period. This policy was tested on a range of problems and performed consistently better than 'can-order' policies except for small values of the joint cost. We would expect poor performance for small values of the joint cost because, for example, when the joint cost is zero, we are simply comparing periodic review with continuous review models. What was surprising was the much better performance for significant values of the joint cost, where the gap between the lower bound and the can-order policy was typically halved, a saving of often 20%. Encouraged by this result we also replaced the (R,T) policy by a simple heuristic. In this heuristic the T : periods were calculated from essentially an Economic Order Quantity and then rounded to a multiple of the 97 base period. This heuristic which is very easy to calculate performed only slightly worse than the (R, T) policy, and still much better than the 'can-order' policy. Thus the main result of this chapter is that periodic review policies can outperform 'can-order' policies for coordinated replenishment inventory systems, and can do it with considerably simpler calculations. The remaining part of this chapter is organized as follows: section 2 describes the model assumptions, section 3 presents s , c , 5 and independent policies tested, section 4 gives a brief description of the lower bound, section 5 describes the periodic heuristics, section 6 gives details of the numerical results-, while section 7 concludes wi th a discussion of topics for further research. 5.2 Model Assumptions The TV-item inventory system is subject to a continuous review and demands are generated by independent Poisson processes wi th rate A, for item i. The possibility of continuous review is required by 'can-order' policies even though only periodic review wi l l be required for the periodic policies. Excess demands are backlogged and each replenishment needs a constant lead time /,-. The joint cost is A0 and the ' l ine' cost is At. Holding costs are charged at a rate fo, on every item of inventory. Two types of shortage costs are used, 0, for every item i unable to be filled immediately on request, and a rate p, for every unit of backlogging outstanding. Thus p, is a 'time-weighted' shortage charge. These shortage and holding costs are linear. The criterion is to minimize the long run average cost per unit time. Which of these assumptions can be readily generalized wi l l be discussed in section 7. 98 5.3 'Can-Order' Policies The method of calculation used for the parameters (s, c, S) is that given by Federgruen et a l . [23]. We used only simple, not compound, Poisson demands and did not include service level constraints. The two types of shortage costs were used alternatively, not together. Further details on the (s.c.S) policies and the method of calculation are in Federgruen et al [23]. The calculations for the (s,c,S) policy are not quite exact because of the assumption of independence needed for item reorders. A g a i n , details on the extent of this exactness are given in the above paper. In addition, we calculated the 'independent 1 policy, where item i incurs the full cost Ao + A , whenever it is reordered. The optimal (s,S) policies for this were calculated using the methodology, used in Federgruen et al.[23, page 352]. 5.4 The Lower Bound The cost allocation method decomposes the problem into N single item problems, if there are N items, as in the joint replenishment problem in Chapter 2. The key here is that the 'opt imum' policy for the single item problem is known. The set-up cost for item i after the cost allocation is a , A 0 + A , . The choice of the best a's to use is difficult in this case. Recall that any feasible values of a w i l l give a lower bound. However, we use a heuristic method to determine the allocations for the lower bound. For the joint replenishment problem wi th constant and continuous demands discussed in Chapter 2, the choice of a, was made as follows: first calculate the run-out times for each item init ial ly with a,- = 0 for all i. We then allocate the set-up cost to raise the minimum cycle time to equal the next higher cycle time and repeat the allocation until there is no more set-up cost to allocate. We use the same procedure here with mean demand used for calculating the run-out times. The min imum run-out time achieved after the allocation is termed the base period and all items i with a,- > 0 the base set, B. If 99 Ci(cii) is the min imum cost for i tem i wi th allocation a,-, the lower bound is LB = J£Ci{ai) + YtCi(0) iEB i£B We note here that 'better' lower bounds are clearly available with more calculations. 5.5 The Periodic Policies The (R, T) policy is one that orders the inventory position up to R every T periods. We use-the Poisson demand distribution and the equations for calculating the average cost of an (R,T) model for each item below are taken from Hadley and Whi t in [33, page 260], equations 5.65-67 inclusine. Let P\q\nx\iT\ be the probability that the demand in a review interval of length riiT is at least q. Let Average backorders per period for item i under (J2j,n,-T) policy Average unit years of shortage for item i under (i2,-,n t-T) policy Average on-hand inventory per period for item i under (Ri,n.,T) policy The average cost is given by Ai -I- a,-A0 (P[l;nt-A,-r]) + hiDi(R,,n,T) + n,T) + piB(Ri,nlT) The expressions for Dt, E% and Bi are given below. B(Rl,n,T) AplirUli + ntT)2P[R, - 1; A.-ft + mT)] - llP\Ri - 1;A,-/,-]} riil A ^ ( 2 A + + ' 1 5 K [ h + H l T ) ] " + 1 5 U ] } + niT)P[Ri; A,- (/, + n t T) ] - / 4 P [ P , ; A,/,]}] 100 E(Rx,n%T) At7,-P[P,- — •i + n,-r)P[J2,- - 1; A,-(/,- + n,T)} - P , P | P , ; A,-(/,• + n,T)] l ; A , / t ] + /2,-Pfi2,-;A.-/i]} D(Ri,n,T) — Rj — Hi T -- + B{R„ntT) Three versions of this policy were tried. The first, we shall call simply [R,T). For this, all items used the same period P,that is, n, = 1 for all i. A single variable search was used to determine T. For the second, which we shall term (R,nT), a single search over T was also performed but any item could have a period of any n , T where n,t is a positive integer. The values of n, were determined in the following way. For each value of T and for each i, n, was increased from 1 unti l the resulting cost no longer decreased. F ina l ly a simple alternative was tried, motivated by the lower bound in section 4. For items in the base set, i £ B, T was taken as the common base period. A l l other items i B (or rather their deterministic equivalents) have run-out times greater than T. This is because of the way the G ; were defined. Each of these items i is given a period n t P nearest to the runout time, where again nt is a positive integer. This heuristic wi l l be termed PH, for periodic heuristic. For all three options P , is chosen to minimize expected carrying and shortage costs during lt + P,. It should be recalled that for periodic policies, if an order is placed now, then another chance to place an order wi l l not occur unti l Pj later and that wi l l not result in products being available unti l a further time /,-. Hence current decisions must face the uncertainty of demand over a t ime /, + TJ. 5.6 C o m p u t a t i o n a l R e s u l t s Twelve products are listed in Table 5.1, along wi th values for Aj, A, and /,-. The products have been ranked by the value of A;/A, which means that the base set B occurs first and is actually products 1 to 6 inclusive. 101 D A T A Results P rod . A A / LB PH (R,T) ( s,c,S) Indep. (s,S,T) (R,T) T=0.8 s,S 1 10 40 0.2 11 39 0.65 41 0.65 46 8 34 46 10 58 2 10 35 0.5 22 47 0.65 47 0.65 52 17 43 54 20 66 3 20 40 0.2 11 39 0.65 41 0.65 46 8 32 49 10 59 4 20 40 0.1 6 34 0.65 36 0.65 42 4 27 44 5 54 5 40 40 0.2 11 39 0.65 41 0.65 46 8 29 53 10 62 6 20 20 1.5 35 52 0.65 50 0.65 53 23 46 58 32 70 7 40 20 1 24 43 0.82 40 0.65 42 14 33 50 21 60 8 40 20 1 24 43 0.82 40 0.65 42 14 o o oo 50 21 60 9 60 28 1 33 60 0.85 54 0.65 58 25 44 69 30 78 10 60 208 1 23 46 1 50 1.3 42 13 32 53 21 62 11 80 20 1 23 49 1.15 50 1.3 42 12 31 55 21 64 12 80 20 1 23 49 1.15 50 1.3 42 12 31 55 21 64 C O S T 2047 2291 2322 2620 3357 C O S T / L B 100 112 113 128 164 Table 5.1: Data and Typica l Results (A0 — 150, cf> = 30, p = 0, h = 6) 102 N O T E S : LB = Lower Bound PH = Periodic heuristic, using T from the lower bound to the nearest multiple. (R,T) = Periodic policy with common cycle length T. (s.c.S) — 'can-order 'policy. The (R,nT) results are identical to the PH results up to the last digit or two and are omitted for clarity. For different experiments Ao varies from 20 to 250. A l l the p,, (0,-) are identical and equal to 30 or zero alternately. A l l the hi are identical and equal to either 2 or 6. Experiments were run with different and nonidentical values of / i , - , p^, (</>,) but no essentially different results were obtained. Neither did varying the range of Xi, At and hi affect the qualitative impact of the results, although of course the actual numbers varied considerably. In terms of relative performance the most sensitive factor is Ao-Examples of some of these results for varying A, and /, are shown in Table 5.5 Table 5.1 gives details of a run with AQ — 150, h = 6 and using the non-time weighted shortage cost <f> = 30. Under LB are given the values of s, S and the 'runout' times as described in section 4. Notice that the base set have identical times, the base period of 0.65. Notice under PH that products 6 through 9 have been 'rounded down' to the base period and 10 through 12 'rounded up ' to twice the base period. The minimiz ing value of T found with (R, T) was T = 0.8. Only a coarse grid search with interval 0.05 was used. Smaller grids were not worthwhile, achieving only very small improvements. The savings of the (s,c,S) policy over the independent policy are consistent with previous work, see [23]. Note that the c o s t / L B ratio is to be interpreted in the light that the bound LB might st i l l be quite weak. The simple PH policy is seen to perform well in comparison wi th others. 103 LB PH (R,T) [s,c,S) Indep. 50 999 1135 1183 1172 1349 (114) (118) (117) (135) 100 1051 1195 1223 1327 1643 (114) (116) (126) (156) 150 1096 1244 1262 1459 1886 (114) (115) (133) (172) 200 1137 1289 1299 1571 2052 (113) (114) (138) (180) 250 1175 1329 1334 1676 2239 (113) (114) (143) (191) Table 5.2: tfi = 30, p = 0,h = 2 The first main experiment is given in Table 5.2. Everything is identical to the previous experiment except h = 2. The ratio of c o s t / L B is given underneath each figure in parentheses, in percentage points Again the improvement of (s,c,S) over independent is consistent wi th previous findings. The performance of the periodic compared wi th the (s,c,S) policy improves as A0 increases and is quite pronounced, reaching a 20% improvement for high values of Ao. Interestingly the ratio of P H / L B seems independent of Ao- We know however that for small values of A0 the periodic policy wi l l begin to behave poorly compared wi th (s, c, S) policies. We can see this in Table 5.3. Here the data is identical to Table 5.2 except that we use the time-weighted shortage cost and A0 has been extended to the value of 20. We see that with Ao = 20, the (s,c,S) policies are better, but Ao = 20 is a rather small cost for this data set and the whole value of coordination is becoming marginal. 104 LB PH (R,T) [s,c,S) Indep. 20 815 907 961 922 975 (111) (118) (110) (120) 50 851 944 984 1114 1189 (111) (116) (131) (140) 100 901 1005 1023 1243 1476 (112) (114) (138) (164) 150 945 1046 1059 1350 1713 (111) (112) (143) (183) 200 981 1088 1095 1443 1908 (111) (112) (147) (194) Table 5.3: </> = 0, p = 30, h = 2 A n extra, run with Ao — 0 confirmed what we already know. For this LB, (s,c,S) and Indep. were all identical and the periodic solutions more costly. A final run is shown in Table 5.4, identical to Table 5.3 except that h = 6, and with a smaller range of AQ. To demonstrate the robust nature of these results some rather different experiments were performed. The base case for these experiments, example 1 in Table 5.5, had the following parameters. Eight identical products, Ai = 20 A0 = 150 A, = 40 / = 0.2 h = 6 4> = 30 p = 0 Only the values for the lower bound, the independent policy, the 'can-order' and periodic heuristic are shown. In experiments 1-3 the lead times are lengthened and the biggest change is in the 105 LB PH (R,T) [s,c,S) Indep. 100 1493 1676 1673 1898 2362 (112) (U2) (127) (158) 150 1562 1733 1743 2054 2738 (111) (112) (131) (175) 200 1626 1803 1798 2193 3069 (111) (111) (135) (189) Table 5.4: 4> = 0,p = 30, h = 6 lower bound thereby improving the relative measure of performance of both heuristics. It needs to be emphasized that the actual performance need not be improving; only our estimate using the lower bound did. A caution needs also to be made with respect to the periodic heuristic. The heuristic solution was calculated in the tradit ional way, assuming a very low chance of more than one outstanding order per i tem. As lead times lengthen this assumption becomes suspect. See [33] for more on this. Experiments 4 and 5 changed the demand and the number of products without changing the aggregate demand. Again the relative performance was little affected. 5.7 C o n c l u d i n g R e m a r k s For the model studied here simple periodic policies seem to show considerable promise over more complex 'can-order' system. Periodic policies were studied by Naddor [52] but without a bound or computational comparison with 'can-order' systems. Natural extensions to this work are to compound Poisson demands, systems under service level constraints and lost sales case. Alternatively the discrete nature of demand can be 106 Example Description LB PH [s,c,S) Indep. 1 Base case 1357 1559 1929 2490 2 Base case except lead times have increased to 0.4 1451 1615 1991 2563 3 Base case except lead times have increased to 0.6 1523 1664 2043 2618 4 Base case except demand has changed to 4 products with A, = 20, and 4 products wi th A, = 60 1348 1543 1869 2405 5 Base case except only 4 products with A,- = 80 1348 1543 1869 2405 Table 5.5: Summary of Results wi th Different Lead Times and Demands 107 dropped in favour e.g., of normal distribution of demands. M o r e profound extensions would raise the following questions. Can this bound be sharpened? We noted in Section 4 that we are not using the values of a, that would maximize the lower bound as was the case with deterministic demands in previous chapters. A second question is, can the heuristic be improved? A th i rd and most interesting question is, can a guaranteed performance be given for a heuristic compared to the bound? One last comment which could have implications for extensions is the observation that although ( s , c ,5 ) policies require independence for their computation, nowhere is independence needed for either the lower bound or the periodic heuristic. 108 C H A P T E R SIX Conclusion Lower bounds for some production/inventory problems were derived using a cost allo-cation method. The generality of this method is demonstrated in its use for the joint replenishment problem with constant and time-varying demands, the one-warehouse multi-retailer problem, the multi-facility joint replenishment problem, the multi-item dynamic lot-size problem and the (s,c,S) or 'can-order' model. This work can be extended in various directions. For example, we could relax the assumption on back-logging or use more complex cost structures for the joint replenishment problem with constant and continuous demands and the mult i- i tem dynamic lot-size problem. Back-logging of demand could also be allowed in the one-warehouse multi-retailer problem. For the 'can-order' system some possible extensions include: using alternative demand distributions, like compound Poisson distribution; allowing lost sales and no backlog-ging; incorporating service level constraints and using alternative heuristics. For the lower bound itself, research into better ways of choosing the cost allocations in the multi-product dynamic lot-size and the 'can-order' systems is needed. Better choices of the cost allocations wil l help in extablishing better performances for the heuristics introduced here and possibly give ideas about other heuristics. 109 B ibliography [l] Afentakis, P., B . Gavish and U . Karmarkar . "Computationally Effecient Op-t imal Solutions to the Lot-Sizing Problem in Mult i -Stage Assembly Systems." Management Sci., 30 (1984), 222-239. [2] Agnihot r i , S., U . Karmarkar and P. Kuba t . "Stochastic Al locat ion Rules." Oper. Res., 30 (1982), 545-555. [3] A l l en , G . S. "Redistribution of Total Stock Over Several User Locations." Nav. Res. Log. Quart., 5 (1958), 337-345. [4] Andres, F . M . and H . Emmons. " A Mult i -product Inventory System wi th Inter-active Setup Costs." Management Sci., 21 (1975), 1055-1063. [5] Andres, F . M . and H . Emmons. "On the Opt imal Packaging Frequency of Prod-ucts Jointly Replenished." Management Sci., 22 (1976), 1165-1166. [6] Balintfy, J . L . "On a Basic Class of Mul t i - I tem Inventory Problem." Management Sci., 10 (1964), 287-297. [7] Bensoussan, A . and J . M . Pro th . "Economical Ordering Quantities for the Two Products Problem wi th Joint Production Costs." A P I 1 , Systemes de production. 19 (1985) 509-521. 110 [8] B i t r a n G . R . and T. L . Magnant i and H . H . Yanasse. "Approx imat ion Methods for the Uncapacitated Dynamic Lot Size Problem." Management Sci., 30(1984), 1121-1141. [9] Blackburn , J , D . and R. A . Mi l l en . "Improved Heuristics for Multi-Stage Re-quirement Planning Systems." Management Sci., 28 (1982), 44-56. [10] Bomberger, E . " A Dynamic Programming Approach to a Lot Size Scheduling Problem." Management Sci., 12 (1966), 778-784. [ l l ] Brown, R . G . Decision Rules for Inventory Management. Hol t , Rinehart, and Wins ton , N Y , 1967. [12] Cahen, J . F . "Stock Policy in Case of Simultaneous Ordering." Int. J. Prod. Res., 10 (1972), 301-312. [13] Chakravarty, A . K . "Mult i - I tem Inventory Aggregation into Groups." J. Opl Res., 22 (1981), 19-26. [14] Chakravarty, A . K . , J. B . Or l i n and U . G . Rothblum. " A Part i t ioning Problem wi th Addi t ive Objective wi th an Appl ica t ion to Opt imal Inventory Grouping for Joint Replenishment." Oper. Res., 30 (1982), 1018-1022. [15] Clark , A . " A n informal Survey of Mul t i -Echelon Inventory Theory." Nav. Res. Log. Quart., 19 (1972), 621-650. [16] Clark , A . J . and H . Scarf. "Opt imal Policies for a Mul t i -Echelon Inventory Prob-lem", Management Sci., 6 (i960), 475-490. [17] Crowston, W . B . , M . H . Wagner and A . Henshaw. " A Comparison of Exact and Heuristic Routines for Lot-Size Determination in Mult i -Stage Assembly Sys-tems." AIIE Transactions, 4 (1972), 313-317. I l l [18] Crowston, W . B . , M . H . Wagner and J . F . Wi l l i ams . "Economic Lot Size De-termination in Multi-Stage Assembly Systems." Management Sci., 19 (1973), 517-527. 119] Das C . "Supply and Redistribution Rules for Two-Locat ion Inventory Systems: One-Period Analysis ." Management Sci., 21 (1975), 765-776. [20] D o l l , C . L . and D . C . Whybark " A n Iterative Procedure for the Single-Machine Mul t i -P roduc t Lot Scheduling Problem." Management Sci., 20 (1973), 50-55. [21] Eppen , G . D . "Effects of Centralization on Expected Costs in a Mul t i -Loca t ion Newsboy Problem." Management Set., 25 (1979), 498-501. [22] Eppen , G . and L . Schrage. "Centalized Ordering Policies in a Mult iware-house System with Leadtimes and Random Demand." in Multi-Level Produc-tion/Inventory Control Systems Theory and Practice. Schwarz. L . , E d . , North Hol land, Amsterdam. (1981), 51-69. [23] Federgruen, A . , H . Groenevelt and H . C . Ti jms. "Coordinated replenishment in a mult i- i tem inventory system wi th compound Poisson Demands." Management Sci., 30(1984), 344-357. [24] Federgruen, A . and P. Z ipk in . "Approximations of Dynamic , Mul t i loca t ion Pro-duction and Inventory Problems." Management Sci., 30 (1984), 69-84. [25] Federgruen, A . and P. Z ipk in . "Al locat ion Policies and Cost Approximations for Mul t i loca t ion Inventory Systems." Nav. Res. Log. Quart., 31(1984), 97-129. [26] Goya l , S. K . "Determination of Economic Packaging Frequency for Items Jointly Replenished." Management Sci., 20 (1973), 232-235. [27] Goya l , S. K . "Determination of Opt imum Packaging Frequency of Items Jointly Replenished." Management Sci., 21 (1974), 436-443. 112 [28] Goya l , S. K . "Opt imum Ordering Policy for a M u l t i Item, Single Supplier Sys-tem." Oper. Res. Quart.., 25 (1974), 293-298. [29] Goyal , S. K . and A . S. Bel ton. "On ; A Simple Method of Determining Order Quantities in Joint Replenishments Under Deterministic Demand' ." Manage-ment Sci., 26 (1979), 604. [30] Graves, S. C . "On the Deterministic-Demand Mul t i -P roduc t Single-Machine Lot Scheduling Problem." Oper. Res., 25 (1979), 276-280. [31] Graves, S. C . "Multi-stage Lot-Sizing: A n Iterative Procedure." in Multi-Level Production/Inventory Control Systems: Theory and Practice. Schwarz, L . B . (Ed.) , North Hol land. [32] Graves, S. C . and L . B . Schwarz. "Single Cycle Continuous Review Policies for Arborescent/Inventory Systems." Management Sci., 23 (1977), 529-540. [33] Hadley, G . and T . M . W h i t i n . Analysis of Inventory Systems. Prentice Hal l , 1963. [34] H u , T . C . Combinatorial Algorithms. Addison-Wesley, 1982. [35] Ignall, E . "Opt imal Continuous Review Policies for the Two Product Inventory Systems wi th Joint Setup Costs." Management Sci., 15(1969), 277-279. [36] Jackson, P., W . Maxwel l and J . Muckstadt . "The Joint Replenishment Problem with a Powers-of-Two Restrict ion." HE Transactions, 17 (1985), 25-32. [37] Jensen, P. A . and H . A . K h a n . "Scheduling in a Mult istage Production System wi th Set-up and Inventory Costs." AIIE Transactions, 4 (1972), 126-133. [38] Johnson, E . L . "Opt imal i ty and Computat ion of [o, S) Policies in the Mul t i - i t em Infinite Horizon Inventory Problem." Management Sci., 13 (1967), 475-491. [39] K a l i n D . "On the Optimali ty of (o,S) Policies." Management Set., 5 (1980), 293-307. [40] K a l y m o n , A . B . " A Decomposition Algor i thm for Arborescence Inventory Sys-tems." Oper. Res., 20 (1970), 860-873. [41] K a o , E . P. C . " A Mul t i -P roduc t Dynamic Lot-Size Mode l with Individual and Joint Set-Up Costs." Oper. Res., 27 (1979), 279-289. [42] Karmarkar , U . "Equalizat ion of Runout Times." Oper. Res., 29 (1981), 757-752. [43] Lambrecht, M . and J . Eecken Vander. " A Facilities in Series Capacity Con-strained Dynamic Lot-Sized Model . " European J. Oper. Res., 2 (1978), 42-49. [44] Leopoulos, V . I. and J . M . Proth . "The General Mul t i -Produc ts Dynamic Lot Size Mode l with Individual Inventory Costs and Joint Production Costs." RAIRO APII, 19 (1985), 117-130. (45] Love, S. " A Facilities in Series Inventory Model wi th Nested Schedules." Man-agement Sci., 18 (1972), 327-338. [46] Madigan , J . G . "Scheduling a. Mul t i -Produc t Single Machine System for an In-finite Planning Period." Management Sci., 14 (1968), 713-719. [47] Mendelson,H. , J . Pl iskin and U . Yechial i . " A Stochastic Al loca t ion Problem." Oper. Res., 28 (1980), 687-693. [48] Mil tenburg , G . J . and E . A . Silver. "Accounting for Residual Stock in Continuous Coordinated Control of a Family of Items." Int. J. Prod. Res., 22 (1984), 607-628. 114 [49] Mil tenburg , G . J . and E . A . Silver. "The Diffusion Process and Residual Stock in Periodic Review Coordinated Control of Families of Items." Int. J. Prod. Res.. 22 (1984), 629-646. [50] Moi ly , J . A . "Opt imal and Heuristic Procedures for Component Lot-Spl i t t ing in Mult i-Stage Manufacturing Systems." Management Sci., 32 (1986), 113-125. [51] Muckstadt , J . A . and R . O. Roundy. "Mult i - I tem, One-Warehouse, M u l t i -Retailer Dis t r ibut ion Systems. Technical Report No . 646, 1985. Dept. of Industr. Eng . , Cornell University, Ithaca. [52] Naddor, E . "Opt imal and Heuristic Decisions in Single and Mul t i - I t em Inventory Systems." Management Sci., 21(1975), 1234-1249. [53] Nocturne, D . J . "Economic Ordering Frequency for Several Items Jointly Re-plenished." Management Sci., 19 (1973), 1093-1096. [54] Peterson R. and E . A . Silver. Decision Systems for Inventory Management and Production Planning. Wiley, New York , 1985. [55] Queyranne, M . " A Polynomial -Time, Submodular Extension to Roundy 's 98%-Effective Heuristic for Production/Inventory Systems." Tecnichnical Report No. 1136, 1985. Faculty of Commerce and Bus. A d m i n . , University of Br i t i sh Columbia , Vancouver. [56] Roundy, R . "94%i-Effective Lot-Sizing in Mult i -Stage Assembly Systems." Tech-nical Report No. 647. (1983), Dept of Indust. Eng . , Cornell University, Ithaca. [57] Roundy, R. O. "98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Mul t i -Reta i ler Systems." Management Sci., 31 (1985), 1416-1430. 115 [58] Roundy, R. "Efficient, Effective Lot-Sizing For Mul t i -Produc t Mult i-Stage Pro-duct ion/Dis t r ibut ion Systems with Correlated Demands." Tecnhnical Report No . 671. (1985), Dept of Industr. Eng . , Cornell University, Ithaca. [59] Roundy R. " A 98%-Effective Lot-Sizing Rule for a Mul t i -Produc t , Multi-Stage Production/Inventory System." Maths, of OR., 11 (1986), 699-727. [60] Schwarz, L . B . " A Simple Continuous Review Deterministic One-Warehouse N-Retailer Inventory Problem." Management Sci., 19 (1973), 555-566. [61] Schwarz, L . B . "Physical Distr ibut ion: The Analysis of Inventory and Location." A HE Transactions, 13 (1981), 138-150. [62] Schwarz, L . B . and L . Schrage. "Opt imal and System-Myopic Policies for M u l t i -Echelon Production/Inventory Assembly Systems." Management Sci., 21 (1975), 1285-1294. [63] Schweitzer, P. J . and E . A . Silver. "Mathematical Pitfalls in the One Machine Mul t ip roduc t Economic Lot Scheduling Problem." Oper. Res., 31 (1983), 401-405. [64] Shu, F . T . "Economic Ordering Frequency for Two Items Jointly Replenished." Management Sci., 17 (1971), B-406-410. [65] Silver, E . A . " A Control System for Coordinated Inventory Replenishment." Int. J. Prod. Res., 12 (1974), 647-671. [66] Silver, E . A . " A Simple Method of Determining Order Quantities in Joint Re-plenishment Under Deterministic Demand." Management Set., 22 (1976), 1351-1361. 116 [67] Silver, E . A . "Some thoughts on Extension of Lot-Sizing Procedures Under De-terministic Time-Varying Demand." Working Paper No. 104, 1976. Dept of M a n -agement Science, U . of Waterloo. [68] Silver, E . A . "Coordinated Replenishments of Items Under Time Varying De-mand: Dynamic Programming Formulation." Nav. Res. Log. Quart., 26 (1979), 141-151. [69] Silver, E . A . "Establishing Reorder Points in the (S,c,s) Coordinated Control System under Compound Poisson Demand." Internat. J. of Prod Res., 9 (1981), 743-750. (70] Simpson, F . K . J r . " A Theory of Al locat ion of Stocks to Warehouses." Oper. Res., 7 (1959), 797-805. [71] Steinberg, E . and H . A . Napier. "Opt imal Mul t i -Leve l Lot-Siz ing for Require-ments Planning Systems." Management Sci., 26 (1980), 1258-1271. [72] Szendrovits, A . Z. "Manufacturing Cycle Time Determination for a Multi-Stage Economic Production Quantity Mode l . " Management Sci., 22 (1975), 298-308. [73] Taha, H . A . and R. W . Skieth. "The Economic Lot Sizes in Multi-Stage Pro-duction Systems." AIIE Transactions, 2 (1970), 157-162. [74] Tan, K . F . "Opt imal Policies for a. Mul t i -Eche lon Inventory Problem with Peri-odic Ordering." 20 (1974), 1104-1111. [75] Thompstone. R. and E . A . Silver. "A Coordinated Inventory Control System for Compound Poisson Demand and Zero Lead Time." Int. J. Prod. Res., 13 (1975), 581-602. [76] Veinott , A . F . "Opt imal Policy for a Mul t i -product , Dynamic , Non-stationar Inventory Problem." Management Sci., 12 (1965), 206-222. 117 [77] Veinott , A . F . " O n the Optimali ty of (s, S) Inventory Policies. New Conditions and a New Proof." SIAM J. Appl Math., 14 (1966), 1067-1083. [78] Veinott , A. F . " M i n i m u m Concave-Cost Solution of Leontief Substitution Models of Mult i faci l i ty Inventory Systems." Oper. Res., 17 (1969), 262-291. [79] Veinott , A . F . , Jr . and H . M . Wagner. "Computing Opt imal [s,S) Inventory Policies." Management Set., 11 (1965), 525-552. [80] Wagner, H . M . and T . W h i t i n . "Dynamic Version of the Economic Lot Size M o d e l " , Management Sci., 5 (1958), 89-96. [81] Washburn, A . " A Note on Integer Maximiza t ion of Unimodular Functions." - Oper. Res., 23 (1975), 358-360. [82] Wheeler, A . "Mult iproduct Inventory Models wi th Set-up." Technical Report No. 106, 1968. Oper. Res. Dept. Stanford University, Stanford. [83] Wi l l i ams , J . F . "Heuristic Techniques for Simultaneous Scheduling of Production and Dist r ibut ion in Mul t i -Echelon Structures: Theory and Empir ica l Compar-isons." Management Sci., 27 (1981), 336-352. [84] Wi l l i ams , J . F . " A Hybr id Algor i thm for Simultaneous Scheduling of Product ion and Distr ibut ion in Mul t i -Eche lon Structures. Management Sci., 29 (1983), 77-105. [85] Zabel, E . "Some Generalization of an Inventory Planning Horizon Theorem." Management Sci., 10 (1964), 465-471. [86] Zangwil l , W . I. " A Deterministic Mul t iproduct Mul t i fac i l i ty Product ion and Inventory Mode l . " Oper. Res., 14 (1966) 486-507. 118 [87] Zangwil l , W . I. " A Backlogging Model and a Mul t i -Echelon Mode l of a Dynamic Economic Lot Size Product ion System—A Network Approach." Management Sci., 19 (1969), 506-527. [88] Zipkin , P. "Simple Ranking Methods for Allocation of One Resourse." Manage-ment Sci., 26 (1980), 34-43. [89] Z ipk in , P. "On the Imbalance of Inventories in Mul t i -Echelon Systems." Maths, of Oper. Res., 9 (1984), 402-423. 119 A P P E N D I X A The Minimum Violators Algorithm for a Facilities-in-Series Problem Initialize Let the root facility be j and let Ak <— 0 temporarily, A; <E (Pn U Sj) \ {n} Let am a i m A m , em <- h i m , rn < n, en +- h'tn; where Kn= E ^ keP,.nSj FAC (Pi \ (Pn \ {n}), CL(i, m , m) +- {m}, m < n; CL(i, n) <— P „ , s m <— max{A; m l m G FAC1 }. cm <- s{ <- 0, F A C l <- J M C . Step 1: Whi le FAC1 # 0 repeat / <- argmin{c f c | /c £ F A C l } If = 0 or c ( > c „ , F A C T F A C l \ {/}. If FAC\ — 0, S T O P , the current clusters are optimum; otherwise go to step 2. Step 2: CL(iJ,l) <- CL(i,l,l) U CZ/(t',s t); a, <- a/ + a,,, e( <- e, + e,,, ci *- fj-, F A C FAC\{Sl}, st ^ ssl, Set Ttfc = Q for all k £ CL(iJ,l). FACl <- FAC. Repeat step 1. 120
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Lower bounds for production/inventory problems by cost...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Lower bounds for production/inventory problems by cost allocation Iyogun, Paul Omolewa 1987
pdf
Page Metadata
Item Metadata
Title | Lower bounds for production/inventory problems by cost allocation |
Creator |
Iyogun, Paul Omolewa |
Publisher | University of British Columbia |
Date Issued | 1987 |
Description | This thesis presents a cost allocation method for deriving lower bounds on costs of feasible policies for a class of production/inventory problems. Consider the joint replenishment problem where a group of items is replenished together or individually. A sequence of reorders for any particular item will incur holding, backorder and set-up costs specific to the item, in addition whenever any item is replenished a joint cost is incurred. What is required of the total problem is the minimization of a cost function of the replenishment sequence or policy. The cost allocation method consists of decomposing the total problem into sub-problems, one for each item, by allocating the joint cost amongst the items in such a way that every item in the group receives a positive allocation or none. The result is that, for an arbitrary feasible cost allocation, the sum of the minimum costs for the subproblems is a lower bound on the cost of any feasible policy to the total problem. The results for the joint replenishment problem follows: For the constant and continuous demand case we reproduce the lower bound of Jackson, Maxwell and Muckstadt more easily than they did. For the multi-item dynamic lot-size problem, we generalize Silver-Meal and part-period balancing heuristics, and derive a cost allocation bound with little extra work. For the 'can-order' system, we use periodic policies derived from the cost allocation method and show that they are superior to the more complex (s,c,S) policies. The cost allocation method is easily generalized to pure distribution problems where joint replenishment decisions are taken at several facilities. For example, for the one-warehouse multi-retailer problem, we reproduce Roundy's bound more easily than he did. For the multi-facility joint replenishment problem (a pure distribution system with an arbitrary number of warehouses), we give a lower bound algorithm whose complexity is dr log r where d is the maximum number of facilities which replenish a particular item and r is the number of items. |
Subject |
Cost accounting Inventory control -- Mathematical models Production control -- Mathematical models |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-08-13 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0097386 |
URI | http://hdl.handle.net/2429/27323 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1987_A1 I96.pdf [ 5.87MB ]
- Metadata
- JSON: 831-1.0097386.json
- JSON-LD: 831-1.0097386-ld.json
- RDF/XML (Pretty): 831-1.0097386-rdf.xml
- RDF/JSON: 831-1.0097386-rdf.json
- Turtle: 831-1.0097386-turtle.txt
- N-Triples: 831-1.0097386-rdf-ntriples.txt
- Original Record: 831-1.0097386-source.json
- Full Text
- 831-1.0097386-fulltext.txt
- Citation
- 831-1.0097386.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0097386/manifest