S T R U C T U R E D POLICIES F O R C O M P L E X P R O D U C T I O N A N D I N V E N T O R Y M O D E L S By Daning Sun B. Sc. (Mathematics) Fudan University M . Eng. (Decision Science & Computer Science) Shanghai Jiao-Tong University A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F D O C T O R O F P H I L O S O P H Y in T H E F A C U L T Y O F G R A D U A T E S T U D I E S F A C U L T Y O F C O M M E R C E A N D B U S I N E S S A D M I N S T R A T I O N We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A August 1990 © Daning Sun, 1990 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Faculty of Commerce and Business Adminstration The University of British Columbia 6224 Agricultural Road Vancouver, Canada V6T 1W5 Date: Abstract For inventory models minimizing the long-run average cost over an infinite horizon, the existence of optimal policies was an open question for a long time. Consider a deterministic, continuous time inventory system satisfies the following conditions: the production network is acyclic, the joint setup cost function is monotone, the holding cost and the backlogging cost rates are nonnegative, the demand rates are constant over time, the production rates are infinite or finite non-increasing, and backlogging may be allowed or not. For this very general extension of the Wilson-Harris E O Q model, we prove the existence of optimal policies. Very few properties of optimal policies have been discovered since the 1950's. Restricting the above inventory model to infinite production rates, we present some new properties of optimal policies, such as the Latest Ordering Property, and explicit expressions for echelon inventories and order quantities in terms of ordering instants. An assembly production system with n facilities has a constant external demand oc-curring at the end facility. Production rates at each facility are finite and non-increasing along any path in the assembly network. Associated with each facility are a set-up cost and positive echelon holding cost rate. The formulation of the lot-sizing problem is developed in terms of integer-ratio lot size policies. This formulation provides a unifica-tion of the integer-split policies formulation of Schwarz and Schrage [34] (1975) and the integer-multiple policies formulation of Moily [20] (1986), allowing either assumption to be operative at any point in the system. A relaxed solution to this unified formulation provides a lower bound to the cost of any feasible policy. The derivation of this Lower Bound Theorem is novel and relies on the notion of path holding costs, a generalization of n echelon holding costs. An optimal power-of-two lot size policy is found by an 0(n3 log n) algorithm and its cost is within 2% of the optimum in the worst case. Mitchell [18] (1987) extended Roundy's 98%-efFectiveness results for one-warehouse multi-retailer inventory systems with backlogging. We extend this 98%-effectiveness re-sult for series inventory systems with backlogging. The nearly-integer-ratio policies still work. The continuous relaxation provides a lower bound on the long-run average cost of any feasible policy. The backlogging model is also reduced in 0{n) time to an equivalent model without backlogging. Roundy's results [27] (1983) are then applied for finding a 98%-effective backlogging policy in O(nlogn) time. In an EOQ model with n products, joint setup costs provide incentives for joint replenishment. These joint setup costs may be modelled as a positive, nondecreasing, submodular set function. A grouping heuristic partitions the n products into groups, and all products in the same group are always jointly replenished. Each group is then considered as a single "aggregate product" being replenished independently of the other groups, and therefore according to the EOQ formula. As a result, possible savings when several groups are simultaneously replenished are simply ignored. Our main result is that the cost of the best such grouping solution cannot be worse than 44.8% above the optimum cost. Known examples show that it can be as bad as 22.4% above the optimum cost. These results contrast with earlier results for power-of-two policies, the best of which never being worse than about 2% above the optimum cost. i n Table of Contents Abstract ii List of Tables vii List of Figures viii Acknowledgement x 1 Introduction and Summary 1 1.1 Optimal Inventory Policies 2 1.2 Generalization of Previous Work 3 1.3 Performance Bounds on the Cost of Grouping Policies 6 1.4 Joint Replenishment with Subadditive Joint Setup Costs: a Bad Example for Power-of-Two policies 7 2 Optimal Inventory Policies 11 2.1 Introduction 11 2.2 Inventory Models 12 2.3 Existence of Optimal Policies 17 2.4 Properties of Optimal Inventory Policies 28 2.5 Conclusions . . 56 2.6 Appendix to Chapter 2 57 2.6.1 A n Inventory Problem That Has no Optimal Policy 57 2.6.2 Some misunderstanding of the properties of optimal policies . . . 58 iv 2.6.3 A proof of lemma 2.3.4 by using a "remove" Algorithm 61 2.6.4 Calculating Hu. An Example 62 2.6.5 Notation and Definitions 64 L o t S i z i n g Pol ic ies for F i n i t e P r o d u c t i o n R a t e A s s e m b l y Sys t ems 75 3.1 Introduction 75 3.2 Notation . . . . 78 3.3 Properties of Finite Horizon Optimal Policies 81 3.4 Integer-Ratio Lot Size Policies 82 3.5 Lower Bound Theorem 88 3.6 Effectiveness of Integer-Ratio and Power-of-Two Lot Size Policies . . . . 98 3.7 Finding Optimal Power-of-Two Lot Size Policies 99 3.8 Conclusions 106 3.9 Appendix to Chapter 3 107 3.9.1 Effectiveness of Integer-Multiple and Integer-Split Lot Size Policies 107 3.9.2 Constructing a Production Schedule from Integer-Ratio Lot Size Policies I l l Series Sys t ems W i t h B a c k l o g g i n g 116 4.1 Introduction 116 4.2 Best Integer Frequency Policies 118 4.3 Lower Bound Theorem 132 4.4 Reduction to an Equivalent No-Backlog Problem and Scheduling Algorithml38 4.5 Conclusions 140 T h e P e r f o r m a n c e R a t i o of G r o u p i n g Pol ic ies for the J o i n t R e p l e n i s h -ment P r o b l e m 142 5.1 Introduction 142 5.2 Lower Bound on the Average Cost of All Feasible Policies 146 5.3 Grouping Policies and Performance Ratio 152 5.4 Upper Bound on the Worst Case Performance Ratio of Grouping Policies 158 5.5 Lower Bound on the worst Case Performance Ratio and Bad Examples . 166 5.6 Conclusions 169 5.7 Appendix to Chapter 5 171 5.7.1 The Proofs of Lemmas in the Text 171 5.7.2 Notation 185 5.7.3 Performance Ratios of Power-of-/? Policies 189 Bibliography 190 v i List of Tables 2.1 Expressing 0r3,0rt,0rs,0r6 in terms of t3,t4 42 2.2 Values of functions 0rj(t) and Trj(t) 43 2.3 Definition of routes 62 2.4 Holding costs /i; and hjT 62 2.5 Xr and Atj 63 2.6 Echelon inventory Er and actual route inventory Ir 63 2.7 Node inventory 7t and actual route inventory Ir 63 2.8 Holding cost rate h\ and echelon holding cost rate hj 63 3.1 Slopes of the path echelon inventory level 89 3.2 Production starting instants and lot sizes 113 5.1 Values of pp, Wp and r* 166 5.2 Performance Ratios of Power-of-/3 Policies 189 vii List of Figures 1.1 A cyclic heuristic for three products 9 2.1 Time intervals Tm, rm and r ' 21 2.2 The non-uniqueness of route ordering quantities 31 2.3 Modification Step A(i,t', t", lfp~) and how it may introduce new non-zero-inventory ordering instants at predecessor node j £ p(i) 33 2.4 The Latest Ordering Property and the Zero Inventory Ordering Property do not imply each other 36 2.5 Order instants 6T and TT 39 2.6 The echelon inventory level E\ is a function of time t 44 2.7 Decomposing all the routes passing through node i 49 2.8 Predecessor Modification Step AR(J, 9", 0'r,x) 52 2.9 Example showing that no optimal policy exists 58 2.10 The order instants at warehouse do not coincide with the order instants at retailers 60 2.11 Algorithm Remove t) 61 2.12 The production network of six products 62 2.13 The correspondence between the two inventory systems 66 3.1 Example of an assembly system 79 3.2 Path (u,v) 83 3.3 Cumulated Path Echelon Inventory on path (u,v) 84 3.4 Route (u,l) is divided into path (u,i) and route (s(i),l) 87 viii 3.5 Illustrating the proof of Lemma 3.5.1 — facility u produces four lots over the time interval [0,T) 90 3.6 Illustrating the proof of Lemma 3.5.2 — decomposition of the path echelon holding cost on (u,v) 92 3.7 Path (u,v) is divided into path (u,i) and path (s(i),v) 93 3.8 Illustrating the proof of Lemma 3.5.4 — assembly system G(N, A) is par-titioned into leaf-routes 96 3.9 Graph C7(7V, A) 103 3.10 Graph G(N', A') 103 3.11 Graph G(7Vi, A i ) , which is embedded in graph G(N2, A2) 104 3.12 Graph G{N2,A2) = G(N, A) x G(N',A') 105 3.13 Three facilities in series 107 3.14 Network corresponding to the constraints of the 3-facility problem . . . . 108 3.15 Scheduling Algorithm 113 3.16 Procedure Schedule(t, v) 113 3.17 Six facilities in series 114 3.18 Echelon inventories E1^^ for the example in section 3.9.2 115 4.1 The Actual Inventory and Echelon Inventory Level for Series System with backlogging 119 4.2 The Power-of-Two Frequency Policy 141 5.1 Grouping Heuristic 161 i x Acknowledgement I wish to express my deepest indebtedness to my co-supervisor, Professor Maurice Queyranne, for introducing this research area to me, guiding the research and improving every aspect of my dissertation. Without his invaluable input, wisdom, encouragement, and financial support during my Ph.D. studies in the Management Science Division, my dissertation would never have taken its present form. I am indebted to my co-supervisor, Professor Derek Atkins, for calling the problems to my attention, for directing my research and for reading and checking every version of my dissertation. His insights, encouragement and personal support have been invaluable to me. I express my thanks to Professor Robin Roundy of Cornell University for agreeing to be the external examiner for this dissertation. I also thank him for suggesting the improved algorithm for finding a best power-of-two policy for a finite production rate assembly system. Thanks are also due to my committee members Professors Thomas McCormick, Daniel Granot and Tae Oum for their careful reading of my dissertation and their valuable suggestions. Throughout the period of my Ph.D. program I was supported by the Government of Canada through the Canadian International Development Agency. I would like to express my profound gratitude to them for the opportunity they have given me. Finally I must thank my wife Yanyun Zeng and my son James Sun for their patience and understanding when I could not be with them most of the time because of this research. x Chapter 1 Introduction and Summary There is no doubt about the importance of production planning and inventory control for the manufacturing and distribution industries. Billions of dollars in Canada alone have been invested in inventories. A significant proportion of the workload for computers in manufacturing companies is spent for updating and maintaining production and inventory records. Dozens of production and inventory control packages are commercially available ranging from a small system costing a few hundred dollars to large implementations costing close to one million dollars. The costs of all these activities are not just measured in terms of the current assets tied up, software and hardware costs and the costs of personnel, but also in the loss of national and international competitiveness engendered by poor delivery and service. Thus, a small percentage savings in inventory costs means millions of dollars and better service, and enhances chances of survival in the fiercely competitive world of the 1990's. Since the classic Economic Order Quantity (EOQ) model was investigated by Harris in 1915, thousands of articles have been published in the production and inventory area. Most of the serious works has been done since the 1950's. It could be claimed that the most significant progress has been made in the 1980's. The EOQ model elegantly solves the one product inventory problem. The EOQ solution is optimal among not only periodic policies but also all feasible policies. To extend this model to finite production rates and allowing backlogging is straightforward. However, it is a completely different story for multi-product inventory systems: the 1 Chapter 1. Introduction and Summary 2 optimal policy is so difficult to get (except for few very simple cases) that we may even doubt the existence of an optimal policy. The difficulties result from the fact that the production decisions are dependent on each other: decisions for one product may depend on decisions made for other products. Although many M R P software packages claim to handle complex bills of materials, in fact most treat each component or product as an isolated single facility. Perhaps the most significant step forward in our ability to sensibly model multiechelon inventory systems was made by Roundy in his two papers [28] (1985) and [30] (1986). Most of my thesis is dedicated to making extensions to the theory that has been built up on his initial work. Because these extensions, both in this thesis and by others prior to this thesis, depend crucially on a clear understanding of properties of optimal policies including even the existence of optimal policies, the first part of the thesis is devoted to a careful understanding and development of such properties. These two aspects of the thesis are now discussed in more detail. 1.1 Optimal Inventory Policies Even though it is difficult to get an optimal policy, it is natural to ask whether an optimal policy exists and what the properties of such an optimal policy might be. The first question was an open question up until now. Inspired by the work of Hassin and Megiddo [12] (1989), we prove the existence of the optimal policies in Chapter 2. Turning now to properties of an optimal policy, investigation of such properties was started by Wagner and Whitin [38] (1958). They demonstrated that an optimal policy has the Zero Inventory Ordering Property, i.e., each product orders only at the zero inventory level. Besides the Zero Inventory Ordering Property, Schwarz [33] (1973) proved that two other properties of an optimal policy also hold for one-warehouse n-retailer inventory systems: (1) Nestedness Property, i.e., the warehouse orders only when at least one Chapter 1. Introduction and Summary 3 retailer orders, and (2) Stationary Property, i.e., order quantities at any retailer between successive orders at warehouse are of equal size. Zheng [39] (1987) extended the Zero Inventory Ordering Property to general acyclic inventory systems with submodular setup cost function (see Chapter 2 herein for details), and the Nestedness Property (which he called the Last Minute Ordering Property) to general acyclic inventory systems but with a separable setup cost function. Zheng also demonstrated that the echelon inventories in an inventory system without backlogging may be expressed as a linear function of the ordering instants. In Chapter 2, we expand this list of properties further. We prove that there is an optimal policy which satisfies the Latest Ordering Property, i.e., every product is ordered as late as possible. We also show that if policy satisfies the optimality properties mentioned above, the echelon inventories as well as order quantities can be explicitly expressed as functions of the ordering instants even for an inventory system with backlogging. These quantitative relationships are very useful in deriving the formulation for specific policies. For example, in Chapter 4 we use them to calculate the total holding cost of any feasible policy for an inventory system with backlogging. 1.2 G e n e r a l i z a t i o n of P r e v i o u s W o r k Because optimal policies are difficult to find and have properties that are so general as to make implementation of them an impossibly complex task, it is not surprising that most research has been restricted to some special classes of policies. For a long time, nested policies (i.e., when the warehouse orders, each retailer also has to order) have been implicitly assumed to be near optimal for 1-warehouse n-retailer systems. Unfortunately, it turned out that these policies could be arbitrarily bad, (see Roundy [27] (1983)). Other authors concentrated on designing ingenious and sophisticated heuristics. They then compared their heuristics with others demonstrating improvements by either examples Chapter 1. Introduction and Summary 4 or simulation. The optimal solutions were just not available for comparison. As a result, nothing was known of the worst case performance of such heuristics. In his two papers [28] (1985) and [30] (1986), Roundy cleverly avoided this comparison difficulty by comparing with a lower bound to the (unknown) optimum. The lower bound is obtained by solving a continuous relaxation associated with a class of heuristics known as power-of-two policies. He proved that the long-run average cost given by a power-of-two heuristic is within 2% of this lower bound in the worst case. This means that the lower bound is really very close to the optimal value. If the production network is a one-warehouse n-retailer system, an O(nlogn) algorithm gives the optimal power-of-two solution. In short, from the theoretical and practical point of view, this problem is essentially solved as data accuracy is unlikely to justify closing that 2% gap. Since then, a variety of extensions to his basic work have been studied. For ease of discussion, we classify inventory systems in terms of infinite production rate or finite production rate, and without backlogging or with backlogging. Most extensions to the basic work were for infinite production rate inventory systems without backlogging. For example, Queyranne [24] (1985) first extended the result to a submodular setup cost function. Zheng [39] (1987) extended the results to a general acyclic production network with a submodular setup cost function. These results prob-ably reach the "boundary" of possible extensions for power-of-two heuristics for infinite production rate inventory systems. As evidence for this view, we have constructed an example in Section 1.4 of this chapter showing that if the setup cost function is not sub-modular but rather subadditive, the continuous relaxation of power-of-two heuristics is no longer a lower bound on the average cost of inventory systems. For inventory systems in this category, Roundy [23] (1988) summarized several important reasons for using re-order intervals, that is, the time between placement of orders, rather than lot sizes to formulate these inventory models. Chapter 1. Introduction and Summary 5 For the finite production rate inventory systems without backlogging, there were no such results prior to this thesis. Several papers proposed heuristics for inventory models with finite production rates, but none of them attempted to find provable performance bounds. For example, for finite production rate assembly systems, Crowston, Wagner, and Henshaw [6] (1972), and Schwarz and Schrage [34] (1975) studied integer-multiple lot size policies, wherein the lot size at each facility is an integer-multiple of its successor's lot size. Moily [20] (1986) investigated integer-split lot size policies, wherein the lot size at each facility is an integer-split (divisor) of its successor's lot size. Neither integer-multiple lot size policies nor integer-split lot size policies dominate each other. As shown in Chapter 3, both integer-multiple and integer-split lot size policies may be simultaneously arbitrarily bad. In Chapter 3, we propose an integer-ratio lot size policy and show that the average cost given by the best power-of-two lot size policy is within 2% of the optimal value of the assembly inventory system. As summarized in Chapter 3, we find that using lot sizes rather than reorder intervals to formulate the inventory model is more effective in the finite production rate case. For the case of infinite production rate inventory model with backlogging, except for one paper by Mitchell [18] (1987) for the one-warehouse n-retailer backlogged problem, no generalizations to include backlogging appear to have been made. In Chapter 4, we show that the worst case performance results can be extended to series systems. For inventory systems in this category, it is not near-optimal to use constant reorder intervals. Following Mitchell [18] (1987), we formulate the problem in terms of the reciprocal of (long-run average) order frequencies, i.e., allowing reorder intervals to vary. Thus the original work of Roundy used power-of-two order intervals, the "finite production rate" results in this thesis use power-of-two lot sizes, and the "backlogging" results in this thesis use power-of-two order frequencies. Chapter 1. Introduction and Summary 6 1.3 Performance Bounds on the Cost of Grouping Policies Until now, all known performance bounds on inventory systems were for the integer ratio or power-of-two type replenishment policies. In fact, other policies, such as grouping policies, are also attractive and interesting in real world applications. A grouping pol-icy partitions the products into groups, and all products in the same group are always jointly replenished. Each group is then considered as a single "aggregate product" being replenished independently of the other groups, and therefore the EOQ formula is applica-ble. As a result, possible savings when several groups are simultaneously replenished are simply ignored. The grouping policies are easy to implement and are potentially more appropriate when inventory is a subproblem, such as inventory problems combined with vehicle routing problems (Anily [2] (1986)). Grouping policies sometimes outperform power-of-two policies. For example, if two products are independent of each other and have the reorder intervals of 1 and y/2, respectively, then the (trivial) grouping policy gives the optimal solution, but the power-of-two policy will never be optimal. A two-products example in Chapter 5 shows that a best grouping policy can be much worse than a power-of-two policy. Therefore, a natural question to ask is whether best group-ing policies have provable performance bounds or could be arbitrarily bad. In Chapter 5, we prove that grouping policies do have a provable performance bound, that is, the cost of the best such grouping solution cannot be worse than 44.8% above the optimum cost. As the subsequent chapters in this thesis are relatively independent, a detailed liter-ature review is found at the beginning of each chapter. Chapter 1. Introduction and Summary 7 1.4 Joint Replenishment with Subadditive Joint Setup Costs: a Bad Exam-ple for Power—of—Two policies For the joint replenishment inventory problem with a submodular setup cost function (see the definition in Chapter 2), the continuous relaxation of the problem of finding optimal power-of-two policies yields a lower bound for all feasible policies. However, the following example shows that when the setup cost function is subadditive (see the definition in Chapter 2) but not submodular, the continuous relaxation of this problem no longer yields a lower bound for all feasible policies. Example. The joint replenishment inventory model has three products. Setup costs Ks, holding cost rates hi and demand rates e?, are given below: where setup cost Ks means all products in set S are replenished at the same time. Note that Ks is subadditive but not submodular. As the setup cost for replenishing two products is the same as for replenishing one product, we will always replenish at least two products at the same time. By symmetry, there are only two different power-of-two policies, where ti is the replenishment cycle of product i: (1) Products 1 and 2 are replenished at the same time, and product 3 is replenished less frequently. The following nonlinear integer programming solves this problem. K, = K2 = K3 = Kl2 = K13 = K23 = l , K123 = 2, h1 — h2 = h3 = 1, d\ = d2 = dz = 2, Zl POT mm 12 + K s.t. t3>ti, h = 2mn0, t3 = 2mn0 Chapter 1. Introduction and Summary 8 where t0 is the base period. The solution to the continuous relaxation of the problem above is tx = t2 = —j=, £3 = 1, and Z P O T = 2 + 2\/2 = 4.82843 (2) Products 1, 2 and 3 are replenished at the same time. Zp0T = min + 3£3 = ^ - + 3 i 3 s.t. t3 > 0, * 3 = 2"13 No-where t0 is the base period. The solution to the continuous relaxation of the problem above is tx = t2 = t3 = y - , and Z P O T = 2 ^ = 4.89898. Therefore, the power-of-two lower bound is ZPOT = mm{ZPOT, ZpOT) = 2 + 2y/2 = 4.82843. However, the following cyclic heuristic defines a feasible policy with an average cost less than the Power-of-Two lower bound ZPOT- Let t be the cycle period of the heuristic. At equal time intervals t/3, we replenish two products at the same time in the cyclic sequence {1,2}, {1,3}, {2,3}, {1,2}, • • • as shown in Figure 1.1. The total setup costs in any time interval t is K12 + Kl3 + I<23 = 3, and the holding costs for product i (i = 1, 2 and 3) in the same time period is (k / A 2 dj_ /2t^ 2' 2 \3J 2 V3 9 Chapter 1. Introduction and Summary Figure 1.1: A cyclic heuristic for three products products: 1,2 1 n 3 2,3 1,2 1 3 2,3 1,2 1 3 2,3 P time time time time Therefore, the average cost for cyclic heuristic is CW - § + §,. 3 For t* = —j= = 1.34164, the average cost is C(t*) = 2\/5 = 4.47214. Note that c ( r ) = 0.92621, ZPOT 2(1 + v^) i.e., the average cost for this cyclic heuristic is less than 93% of the Power-of-Two bound. Chapter 1. Introduction and Summary 10 In fact, this cyclic heuristic can easily be extended to the following n-product problem: 0, |5 | = 0, 1, |5 | = l , 2 , - - - , n - l , 2, \S\ = n, Ks \S\ n - 1 hi - 1, di - 2, Vi G N, where N = {1,2, • • •, n}. It is not difficult to find that the Power-of-Two lower bound is Zpor = 2(1 -\-\fn — 1). The average cost given by the cyclic heuristic is C(t*) = 2y/n + 2 with t* = y/^T^In. For n = 10, C(t*)/ZPOT = V3/2 = 0.8660, i.e., the average cost for this cyclic heuristic is less than 87% of the Power-of-Two lower bound. Chapter 2 Optimal Inventory Policies 2.1 Introduction Lots of the work in production and inventory area has dealt with the case of minimization of the long-run average cost for infinite horizon problems. In this case, the existence of optimal policies was an open question. In Section 2.6.1 of this chapter, we show that an inventory problem could have no optimal policy. This means that the existence of optimal policies is a meaningful problem. The first objective of this chapter is to prove the existence of optimal policies for very general inventory systems. Our proof is inspired by the work of Hassin and Megiddo [12] (1989). We correct a deficiency in their proof, and extend their result to a more considerably general setting. An immediate consequence of this theorem is that the qualifying phrase "if there exists an optimal policy", found (or which ought to be found) in many theorems about inventory systems with long-run average cost criterion, may now be dropped. Various properties of optimal inventory policies have been investigated since the late 1950's. The classic Wagner-Whitin [38] (1958) paper was one of the first works dis-cussing such properties. But very few new properties have been discovered since the early 1960's. Schwarz [33] (1973) and Zheng [39] (1987) summarized the known prop-erties. These properties seem simple and easy to accept, but they may also be very easily misunderstood. See concrete examples in section 2.6.2. To alleviate the potential for confusion, we associate these properties with different inventory models. A l l known 11 Chapter 2. Optimal Inventory Policies 12 properties of optimal policies will be expressed in term of this classification. In addition, some properties not discussed before, such as those related to route inventories, will also be presented. These properties reveal some deeper insights into the structure of inventory systems. The structure of this chapter is as follows. In Section 2.2, we provide a taxonomy of deterministic inventory models. In Section 2.3, we prove the existence of optimal policies. In Section 2.4, properties of optimal policies for various inventory systems are listed. 2.2 Inventory Models In this thesis, we deal with different inventory models. We use five parameters — network, setup cost function, holding and backlogging cost, production rate, backlogging — to describe these inventory models. This makes it easy to rigorously specify the models and their properties. In the following, we first describe these five parameters, then introduce inventory models. The production network G(N, A) is an acyclic directed graph, where iV = { l , 2 , • • •, n} is the node set and A is the arc set. The nodes are indexed such that i > j if (i,j) G A. Each node represents a particular product, at a particular location and/or production stage. A directed arc G A from node i to node j repre-sents the fact that the output of location or operation i directly supplies location or operation j. We say that i is an immediate predecessor of j, and that j is an im-mediate successor of i, whenever are (i,j) G A. Let p(i) be the set of all immediate predecessors of product i, and s(i) be the set of all immediate successors of node i. Let Djy = {i G N\s(i) = 0} be the set of all nodes without successor. Without loss of generality, we may assume that = {i G N\ node i has external demand} — the external demand set of G(N,A). See the details why we may make such an Chapter 2. Optimal Inventory Policies 13 assumption in section 2.6.5. Let Xij be the number of units of product i required to produce 1 unit of product j. We use the following symbols to denote different types of networks: G - General acyclic network: there is no directed cycle in network G(N,A). A - Assembly Systems (a special case of G): each node has exactly one successor in the network G(N,A), except for one node, which has no successor and is called the root node. D - Distribution Systems (a special case of G): each node has exactly one prede-cessor in the network G(N, A), except for one node, which has no predecessor. S - Series Systems (the intersection of A and D): each node has exactly one suc-cessor and one predecessor in the network G(N, A), except for two nodes, one with only a successor and the other one with only a predecessor. 0 - One-warehouse Multi-retailer Systems (a special case of D): one node, termed the warehouse, has successors but no predecessor in network G(N,A), and all other nodes, the retailers, have no successor and exactly one predecessor, the warehouse. 1 - Isolated nodes (a special case of G): A — 0. The setup (or joint replenishment) cost function is a real-valued set function IC : 2N h-• R+ such that for all S C N, K(S) is the cost associated with replenishing all the products i 6 S at the same instant t. Without loss of generality, it is assumed that #*(0) = 0, and K\S) > 0, VS ^ 0, S C N. In this thesis, we will assume, for simplicity, that setup costs are stationary, that is Kt(S) = K(S) for all t,S. Let ki be a real number associated with each node i 6 N. The following symbols are used to denote different properties of the setup cost function: Chapter 2. Optimal Inventory Policies 14 M T - Monotonicity: K(S) < K(T), V 5 C T C J V . SA - Monotonicity and Subadditivity: K(S\JT) < K(S) + K(T), VS, T C N. S M - Monotonicity and Submodularity: K(S\JT) + K(S f l T ) < K(S) + K(T), VS, T C TV. M D - Modularity or First Order Interaction (a special case of SM): K{$) = 0, K(S) = K0 + k" VS ^ 0, S C TV, where K0 > 0 is a fixed constant. ies SP - Separability (a special case of MD): K(S) = ^^t-, VS C N. Backlogging: The following symbols are used to denote different assumptions about backlogging. G B - General Backlogging: Backlogging may be allowed for some or all external demands, but is not allowed for any internal (induced) demand. B - Always backlogging (a special case of GB): Backlogging is allowed for every external demand. N B - No backlogging (a special case of GB) : There is no backlogging at any place. Holding and Backlogging Costs are inventory related cost, charged in terms of the units of products stored and backlogged and the length of time it is stored and backlogged, respectively. Let h'* (resp. bj) be the holding (resp. backlogging) cost rate of product i at instant t: it is the cost of holding (resp. backlogging) one unit of product i for one unit of time at instant t. Let h\ — h'l — ^ Kjh-j he the echelon holding cost rate of node i at instant t: it is the "added" holding cost rate for product i. Let I\ be the actual (node) inventory level of product i at instant t, I\~ = l i m / f be the inventory level just before instant t, I\+ = l im/ , ' be the inventory level just after instant t. Let /• = max(//,0) be the physical inventory Chapter 2. Optimal Inventory Policies 15 level of product i at instant t and 7' = max(—7,-,0), be the backlogged inventory level of product i at instant t. Let the total holding and backlogging cost rate at instant t be Hl — + £\b\) which is the total holding and backlogging i=l cost in one unit of time at instant t. The total holding and backlogging cost: A fT CH(T) = / H* dt is the total holding and backlogging cost accrued over time Jo interval [0, T). The following symbols are used to denote different types of holding and backlogging cost functions: N N - Nonnegative Holding and backlogging cost rates: h'* > 0 and b\ > 0 for each i 6 N. Thus holding and backlogging costs are increasing functions of the number of units stored and backlogged in the holding and backlogging duration. C T - Constant holding and backlogging cost rates (a special case of NN): h'l = h\ > 0 and b\ = 6,- > 0, which are independent of time t for each product i. N E - Nonnegative Echelon holding cost rates (a special case of CT): hi > 0 and constant. Production Rate: Let production rate 7r,- be the number of units that can be produced at node i per time unit. The following symbols are used to denote different types of production rates: F - Finite production rate: the production rate 7r,- is finite for each node in N. It is assumed that production at node i can only be turned on, at rate 7r;, or off, at rate 0. Every turn on in this production status incurs a setup cost, as described above. Chapter 2. Optimal Inventory Policies 16 F F - Fast finite production rate (a special case of F): the production rate 7r,- of each node i £ N is fast enough that its output could supply the total demands from all its immediate successors without the need for building inventory be-forehand: 7T,- > ^2 A J J7TJ , for all i G N. Recall that s(i) is the set of all immediate successors of node i. IF - Infinite production rate: the production rate 7r,- of each node is infinite. This corresponds to "instantaneous" or negligible production times, and to deliv-eries in distribution networks. Let "C" mean "is a special case of" . Because "a property holds for a general case" implies that "it also holds for the special case", the following relationships are worth noticing. For the network types, S C. A C. G, S Q D C. G and O C D, I C G; for the setup cost functions: SP C MD C SM C SA C MT; for backlogging: B C GB and NB C GB; for the holding and backlogging cost functions: NE C CT C NN; for the production rates: FF C F. Now we can use these parameters to define our inventory model by IM(network, setup cost function, holding and backlogging cost, production rate, backlogging). When we don't care about the assumptions on some of the parameters, sometimes we will use "•" to represent the situation. Note that because we always assume that the external demand rates are constant, demand is not a parameter in our models. We also assume that the transfer of a lot is instantaneous, and that, supplies arrive at nodes without predecessor instantaneously and in batch. Our objective is to minimize the long-run average cost over an infinite horizon (see definition in next section). As an example, inventory model I M ( G , M T , N E , F F , G B ) means: 1. The production network G(N,A) is a general acyclic network. Chapter 2. Optimal Inventory Policies 17 2. The setup cost function satisfies the monotonicity property: K(S) < K(T), VS C TCN. 3. The echelon holding cost rates are constant and non-negative. The backlogging cost rates are also constant. 4. The production rate at any node is finite and fast enough such that its output could supply the total demands from all its successors without building inventory beforehand. This requirement means that 7r,- > ^ 7Tj, for each node i £ N. 5. The external demand has to be satisfied and backlogging some of the external demands is allowed. As another example inventory model I M ( G , M T , N E , F F , N B ) is the same as inventory model I M ( G , M T , N E , F F , G B ) except that backlogging is not allowed anywhere in the network. 2.3 Existence of Optimal Policies Even though the results in this chapter are not difficult to be extended to more gen-eral inventory models, we derive them only for simple and important inventory models IM(G,MT,NN, IF ,GB) and I M ( G , M T , N N , F F , N B ) . In this section, we prove that an optimal policy exists for these two inventory systems. For this, we need a few concepts about policies and costs. We use two assumptions: the Zero Initial Inventory Assumption and the Nonpositive Ending Inventory Assumption. They are important because they guarantee that an infinite horizon policy constructed from a series of finite horizon policies is feasible, i.e., satisfies all constraints. This construction will be used in the proof of the existence of optimal policies. Based on these prerequisites, we proceed to proving.the existence of optimal policies. Chapter 2. Optimal Inventory Policies 18 1,2,- - - , n A replenishment policy P = (tp,Qp) is a specification of ordering instants tP and order quantities Qp for all products over a planning horizon. That is, tp — (tip,t2p,-• • ,tnp), Qp — {QIP, Q2P1 • • •, Qn,p) 1 tiP — (t}pi ^ iPi •" " j tiPi ''') ) 0 < t}P < t2iP < • • • < tkiP < • • • Qip = {Q}P,Q1P,---,Q^P,---)>O, _ where n is the number of products, quantity Q\P is the amount of product i ordered at instant t^P. Sometimes we use Q\P to represent the amount ordered for product i at instant t, and if t = tkiP the quantity Q\P may be replaced by QkP, whenever it is convenient. Note that for the finite product rate case the ordering instant t is the production starting time. When replenishment policy P is not emphasized, subscript P in t and Q may be dropped without risk of confusion. An infinite/finite horizon policy: If the planning horizon is infinite (resp. finite), the policy P is called an infinite (resp. a finite) horizon policy. If P is an infinite horizon policy, the restriction of P to a finite horizon [0, T) is a finite horizon policy, which is also called policy P for simplicity. A feasible policy P is a policy which satisfies all the requirements of the model under consideration. These requirements include satisfying external demands for specified products, without backlogging if it is prohibited. We consider different costs incurred in an inventory system by this replenishment pol-icy P: The total cost Cp{T) of policy P over finite horizon [0,T) is the sum of total setup or ordering cost Csp{T) and total holding and backlogging cost Cjjp(T) over horizon Chapter 2. Optimal Inventory Policies 19 [0,T), that is, CP(T) = CSp(T) + CHP(T). Note that we exclude the ordering cost at instant T. This means that backlogging may exist at instant T. Thus if we concatenate two policies together, the ordering cost of the first policy at ending instant will be taken into consideration by the second policy at the initial instant. Over a finite horizon, the objective is to minimize the total cost Cp(T) over all feasible policies P. Assuming all setup costs are positive (except for the empty set) and that a feasible policy with finite cost exists, we are only interested in policies with a finite number of replenishments over finite horizon [0,T). The long-run average cost Cp of an infinite horizon policy P is defined by CP= l i m s u p ^ C p ( T ) . (2.1) X-+oo i The optimal average cost C over all feasible policies is defined by C" = inf CP. (2.2) all feasible P Sometimes, we are also interested in the relationship between two policies. Domination is one of the simplest relationship between two policies. Dominate: Policy P' dominates policy P over interval [0,T), if Cp>(t) < Cp(t), Vt G [0,T). To construct a feasible infinite horizon policy from a series of finite horizon poli-cies, we need the Zero Initial Inventory Assumption and Nonpositive Ending Inventory Assumption defined below. Zero Initial Inventory Assumption: The initial inventory of each product is zero and all the products are replenished at the initial instant 0. Chapter 2. Optimal Inventory Policies 20 Nonpositive Ending Inventory Policy: A finite horizon feasible policy P over [0, T) is a Nonpositive Ending Inventory policy if the inventory level of each product is nonpositive at instant T. When backlogging is not allowed, a Nonpositive Ending Inventory policy is a Zero Ending Inventory policy. Nonpositive Ending Inventory Assumption: For any feasible policy P over finite horizon [0,T) there exists a Nonpositive Ending Inventory policy P', which domi-nates policy P. When backlogging is not allowed, the Nonpositive Ending Inventory Assumption reduces to the Zero Ending Inventory Assumption. As the total cost over any finite horizon has no effect on the long-run average cost, without loss of generality we assume that the Zero Initial Inventory Assumption holds for inventory models IM(G,MT,NN,IF ,GB) and I M ( G , M T , N N , F F , N B ) . In Lemma 2.3.4, we can show that the Nonpositive Ending Inventory Assumption also holds for both inventory models. Given a sequence of finite Nonpositive Ending Inventory policies Pm over time interval [0,T m ) , satisfying the Zero Initial Inventory Assumption, the concatenation method CM constructs an infinite horizon policy P = (P1P2 • • •) as follows. For all m, let policy Pm = (tPm,Qpm) be defined by 0 < t\pm < •• <t .Jim. iPm <T7 m > 1 = 1,2, ••• n Let T0 t 0, m A m = 0,1,2,---T, m Chapter 2. Optimal Inventory Policies 21 Figure 2.1: Time intervals Tm, rm and r ' T\ Ti ... Tm Tm+1 time 0 T l T2 ••• T m_x T m Tl T T m + 1 ro—1 For index k = I + Jt„ with 1 < £ < j , m , let policy P = (tp, Q p ) be defined by u=l ik _ _ i _ xt LiP — Tm-1 I ''ipm, and . ^ J Qjpm — I{pm , if 1 = 1 , [ QiP^i if ^ = 2, •••,jim where is the ending inventory of product z under policy P m . Recall that lipm1 < 0 by the Nonpositive Ending Inventory Assumption. That is, policy P = (P1P2 • • •) over interval ( T V ^ ! , - ^ ) is identical to replenishment policy Pm over (0 ,T m ) , shifted forward r m _ 1 time units. Lemma 2.3.1 (Property of Infinite Horizon Policy P) Consider inventory models IM(G,MT,NN,IF, GB) and IM(G,MT,NN,FF,NB). Suppose Pm satisfies the Zero Initial Inventory and the Nonpositive Ending Inventory Assump-tions for each m. Suppose r € [ r m , r m + i ) and r' = r — T m (see the Figure 2.1). Then policy P = (P1P2 • • •) constructed by concatenation method C M is feasible, and its total cost over interval [0,r) is m Cp(T) = Cp(TM) + CPm+1(T') = YlCP'(T*) + C P ^ ( T ' ) - (2-3) 8 = 1 Chapter 2. Optimal Inventory Policies 22 Proof. For the inventory model IM(G,MT,NN,FF ,NB) , the Zero Initial Inventory Assumption and the Nonpositive Ending Inventory Assumption ensure that the initial inventory and ending inventory of each product under each finite horizon policy Pm is zero. Therefore, policy P is feasible. For the inventory model IM(G,MT,NN, IF ,GB) , the initial inventory of each product is zero, each product is ordered at the initial instant, and the ending inventory of each product is nonpositive. To make policy P feasible, we only need to include the backlogged quantities into the order quantities of policy P at all instants r m , as defined above. Thus feasibility obtains. The total cost equations follow directly by the construction. • Theorem 2.3.2 (Existence of an Optimal Policy) If the Zero Initial Inventory and the Nonpositive Ending Inventory Assumptions hold for the inventory models IM(G,MT,NN,IF ,GB) and I M ( G , M T , N N , F F , N B ) , then there exists an optimal infinite horizon policy P*, i.e., satisfying CP* = C*. (2.4) Proof. By definition of (T, there exists a sequence of infinite horizon policies {P1,P2,---,Pm,---} such that Cpm < CT + J ^ , V m = l , 2 , . . . . (2.5) By definition of Cpm, there exists T'm > 0 such that i c p m ( T ) < Cpm + ^ , V T ^ T ; , m = l , 2 , - . . . (2.6) Chapter 2. Optimal Inventory Policies 23 Let Cm = Cpm{Vm). (2.7) Recursively define { m-1 |^ rm, 3j2Ti, 2m+1Cm+1j. (2.8) (Note that the third argument in the maximization is expressed in time units, because in inequality (2.6), the term ( l / 2 m + 1 ) has the units of a cost rate: dollars per time unit.) Using the concatenation method C M given above, we may define a feasible policy P* = [PlP2 • • •). By Lemma 2.3.1, the total cost of policy P* over interval [0,T) is m i=l In the following, we show that the infinite horizon policy P* defined above is an optimal policy. First, let's estimate the total cost of policy P* over [0,r m ): Cp*(Tm) = Y2Cpi(Ti) i=l m / _ 1 \ < £ Ti (Cp. + - ^ j (by inequality (2.6)) < E r i ( ? + )^ (by inequality (2.5)) m rp + £ 4 (by d e f m i t i o n of r-) (2-9) l—l The following inequality is proved by induction: 2* 1 < —T. (2.10) For m = 1, it follows from the definition T\ = T\. Chapter 2. Optimal Inventory Policies 24 Suppose that the inequality (2.10) holds for m. For m + 1, we have ro+1 Ti Ti y =4 y -Oi Ol i-1 i=l + r m+l m+l m+1 E Ti E Ti i=l 1=1 m rp Y-Ol ^m+1 m < ' '= i " + 2 m + 1 1 < 4 En «'=1 1 1 + 1 (by definition of T m +i in (2.8)) (by induction) This completes the proof of inequality (2.10). From inequalities (2.9) and (2.10), —<?P*(Tm) < ^ + ^ T T , form = 1,2, Then -Cp*(r) = -Cp*(Tm) H—Cpm+i(r') r r r There are two cases to consider: Case 1. If T' < T m + 1 , then CPm+l(T') < Cpm+l(T^ + 1 ) — Cm+1 T (by Lemma 2.3.1) (by inequality (2.11)) < 2m+l (by definition of C m + i m (2-7)) (by definition of Tm in (2.8)) By inequality (2.12), 1 T 2>n+l (2.11) (2.12) Chapter 2. Optimal Inventory Policies 25 < C* + - — - + -—— (from rm < T and Tm < r ) — 2 m — om+i v m — "* — ' Case 2. If r ' > T m + 1 , then Cpm+i (r') < T ' (cPm+, + ~r^j (by inequality (2.6)) < (r — r m ) ^ C * + 2^+i) inequality (2.5) and definition of r') By inequality (2.12), 2 m — i 2m+i < r + 1 )m-2 In summary, ^CP*(T) < C* + -^z^, V T € [ r m , r m + 1 ) , m = 1,2, That is, Cp* = lim sup —Cp*(r) < 0*. T—too T The proof is completed by recalling that Cp* > C . • Remark : This proof extends and corrects a proof by Hassin and Megiddo [12] (1989) for a related inventory problem. The original proof in Hassin and Megiddo established results only for all t = r m , but not for other values of r, which invalidates the result. Our proof corrects this by lengthening the times during which policies Pm are used (equation (2.8) ) so as to achieve the result for all t > 0. Chapter 2. Optimal Inventory Policies 26 Note that the proof of this theorem does not require the existence of an optimal finite horizon policy, although this is easy to prove for the models under consideration. Sometimes, we are not only interested in the existence of an optimal infinite horizon policy, but also in properties satisfied by an optimal policy such as the Nonpositive Inventory Ordering Property and the Latest Ordering Property (defined in the next section). The following corollary gives us a vehicle to extend the properties satisfied by finite horizon policies to an optimal infinite horizon policy. Corollary 2.3.3 (Existence of Optimal Solutions Satisfying Property V) Suppose that the Zero Initial Inventory and the Nonpositive Ending Inventory Assump-tions hold for inventory models IM(G,MT,NN,IF ,GB) and I M ( G , M T , N N , F F , N B ) . Con-sider a property V satisfying the following conditions: 1. (Nonpositive Ending Inventory under Property V) For any finite horizon [0,T) and any feasible policy P over this horizon, there exists a feasible policy P' satisfying: 1.1. property V; 1.2. Nonpositive Ending Inventory Assumption; and 1.3. P' dominates P. 2. (Stability of property V) If all finite horizon feasible policies P1, P2, • • • satisfy property V, then the infinite horizon policy P = (P1P2 • • •) defined by concatenation method C M also satisfies property V. Then there exists an optimal policy satisfying property V. Proof Follows immediately from the previous proof by assuming that all the compo-nents Pm satisfy property V. • Chapter 2. Optimal Inventory Policies 27 Remark : Condition 2, the Stability Condition is satisfied by many useful properties, such as "Zero Inventory Ordering" property, as we shall see later in this thesis. It is not satisfied, however, by some other desirable properties of optimal policies such as that of being periodic. Every finite horizon policy is periodic, with period at most the length of the horizon. Yet, this does not imply that infinite horizon policies need to be periodic (consider for instance the case of two unrelated products, where one E O Q frequency is an irrational multiple of the other). The question of finding sufficient properties for the existence of an optimal policy which is periodic is a very interesting one, but it is beyond the scope of this thesis (See Hassin and Megiddo [12] (1989) for one such example). We conclude this section by proving a lemma mentioned earlier. L e m m a 2.3.4 For the inventory models IM(G,MT,NN,IF ,GB) and I M ( G , M T , N N , F F , N B ) the Nonpos-itive Ending Inventory Assumption holds. Proof. Whenever there is a positive actual inventory level If of product i at the ending instant T, this "extra" inventory if may be removed as well as all the inventories of i's predecessors, which supplies the "extra" inventory If. By doing so, the actual inventory level of each node at any instant does not increase, and neither does the total holding cost. The monotonicity of the setup cost function K ensures that the total setup cost does not increase. Therefore, the total inventory cost does not increase either. This shows that the Zero Ending Inventory Assumption holds. (For a more detailed proof based on the "Remove" algorithm see section 2.6.3.) D Chapter 2. Optimal Inventory Policies 28 2.4 Properties of Optimal Inventory Policies As the behaviour of inventory models is quite different when the production rate is finite or infinite, for simplicity we consider only the infinite production rate inventory model in this section. We demonstrate that for the inventory model IM(G,MT,NN, IF ,GB) , there exists an optimal infinite horizon policy which satisfies the following three properties: Nonposi-tive Inventory Ordering, Latest Ordering and Nonnegative Filling. Therefore, from the perspective of minimizing the long-run average cost, we may restrict ourselves to poli-cies satisfying these properties. For a replenishment policy satisfying the Nonpositive Inventory Ordering Property and the Latest Ordering Property, we show that there is an explicit expression of echelon inventory levels and route order quantities in terms of ordering instants. This formulation implies that the ordering instants uniquely determine the order quantities. Therefore, the replenishment policy needs only be described by the ordering instants tp. The definitions of these concepts appear below. We first introduce network-related concepts, such as paths, routes, and inventory-related concepts, such as actual inventory levels and echelon inventory levels. We then present properties of optimal inventory policies. Path r = (ii,Z2,«3, • • • , i m - i , « m ) is a sequence of nodes z a, z-2, • • • ,im £ N such that all arcs i2)> («2» &3)5 •'" > (?'m-i) «m) £ A. The first node of r is fr = i l 5 the second node of r is sr = i2, a n d the last node of r is £r = im. Set i2, • • •, im} is called the node set of path r, and i £ r means that node i £ {21,^2, • • • ,im}- Let \r\ = m denote the length of path r. Whenever convenient, we also say that arc belongs to path r, for all j — 1, • • •, m — 1. Route r = 13, • • •, im-i, im) is a path terminating at a node im £ Djy. If there is no further specification, r generally denotes a route instead of a path. Say Chapter 2. Optimal Inventory Policies 29 r' = (ij, • • •, im) with j £ {1, • • •, m} is a sub-route of r, denoted by r' C r. Let r \ / r = (^2, • • • ,im) be the immediate sub-route of r. Ptt- is the set of all routes r starting at node i £ iV, i.e., such that fr = i. R = \J Ri is the set of all routes r in G(N, A). ieN Xij is the number of units of product i required to produce 1 unit of product j, for (i,j) € A. A,. = < if IH = 1, is the number of units of product / r re-s ^hi2^i2i3 ''' i^m-it'm> if l r l — 2 quired to produce 1 unit of product £ r through path r. dr = A r ^ r is the induced route demand rate at node fr from route r. = ^ dr is the induced (node) demand rate of node i. Note that dr is the "long-run average" demand rate of node fr from route r, as is induced demand rate di. The "actual" induced route demand at an internal node fr Djy is generated by the orders from its immediate successor on route r and varies over time. The "actual" induced demand at node i is the sum of the orders from "all" its successors. A Route Order Quant i ty Qfr is that part of order quantity Q\ at node i and ordering instant t which is used to satisfy the (induced) demand from node £ r along route r. By definition, Q\= £ Q\. Ir is the actual route inventory at node fr for route r at instant t. By definition, I{ Y I\ for all t. Similarly, P~ = l i m / ' and /*+ = l i m / ' . z - ; r r t</t r T t'\t r E\ is the echelon inventory on route r at instant t. It is the total inventory of good fr Chapter 2. Optimal Inventory Policies 30 on route r, defined as follows: where routes r' are subroutes of r having the same last node. Similarly, E\~ = l imE* ' and E1+ = l im£*' . t>/t T T t'\t r Given a replenishment policy P = (tp, Qp), the actual (node) inventories are uniquely defined by policy P. However, the actual route order quantities Q\ with r £ R{ are not uniquely defined by Q\, neither are the actual route inventories Ilr nor the echelon inventories E\. See the example in Figure 2.2 on page 31. Nonpositive Inventory Ordering Property: If a replenishment policy P orders quan-tity Q\ > 0 at node i and ordering instant t with actual inventory level l\~ < 0, it is said that policy P satisfies the Nonpositive Inventory Ordering Property for node i at instant t. . Note that if node i does not allow backlogging, then the Nonpositive Inventory Ordering Property reduces to the well-known Zero Inventory Ordering Property, that is, policy P orders positive quantities at node i only at instants t where l\~ = 0. This is the case for all internal nodes under either GB, B or NB model. If policy P satisfies the Nonpositive Inventory Ordering Property for every node i £ iV at every ordering instant, then policy P is said to satisfy the Nonpositive Inventory Ordering Property. The concepts defined below are used in the proofs of the following lemmas. Node—instant point (i,t) is a pair of node i and ordering instant t. Over any finite horizon [0,T), if i < j or, if i = j and t < u, we say that node-instant point (i,t) is less than node-ihstant point (j,u), written as (i,t) < (j,u). (This is the usual lexicographic order on 7Y x [0,T).) Chapter 2. Optimal Inventory Policies Figure 2.2: The non-uniqueness of route ordering quantities. P time time time C A S E 1 { 7(3,i) n p i(3,2) time time P time C A S E 2 { P J(3,2) time Chapter 2. Optimal Inventory Policies 32 QvjP> Modification Step: Given a replenishment policy P, policy P' = (tP,QPi) is defined by applying the following Modification Step A(i,t',t",x), which reduces the order quantity at node i and instant t' by quantity x and increases that at instant t" by the same quantity x, that is, Qt'p — x if j = i and v = t', QIP + x if j = i and v = t", Q'JP otherwise. See Figure 2.3 on page 33. Lemma 2.4.1 (Property of the Modification Step) Given a feasible policy P for the inventory model IM(G,MT,NE, IF ,GB) . Let P be a feasi-ble policy such that lfp~ > 0 at ordering instant t". Let t' = max {v\QviP > 0, 0 < v < t"} be the last ordering instant before t" at node i and x = m i n { / ' P _ , Qfp} > 0. Then policy P' generated from policy P by executing of the Modification Step A(i,t', t", x) is feasi-ble and dominates policy P. Besides, the only inventory levels affected by this change are those of i and its immediate predecessors, and these changes are restricted to time interval (t', t"). Proof. First, observe that, by definition of t' and x, one has I\P > I\P~ > 0 for all t e {t',t"). Thus for policy P\ I\P, > Ij'P~ - x > 0 for all t £ (t',t"). If i is an internal node, all orders from i's successors during time interval (t', t") may still be satisfied. Thus, the only nodes affected by the Modification Step are i itself and its predecessors. Each immediate predecessor j £ p(i) has a quantity at least \ijQ\P > x available at instant t'', so the only change is an increase in its inventory level during time interval (t',t"). Therefore, the non-immediate predecessors of i are not affected by the Modification Step. The total holding and backlogging costs Cnp(t) and CHP'{t) of policies P and P ' , Chapter 2. Optimal Inventory Policies 33 Figure 2.3: Modification Step A(i,t',t",IlP ) and how it may introduce new non-zero-inventory ordering instants at predecessor node j 6 p(i) I © © I Before executing A(i,t',t",IiP ) Q V n i t I S t Q t" iP Q f iP Tt»-xip t I t t bad point After executing A(i,t',t", IiP ) time time I © © I I L 1 S f" bad point QiP' — {Qtp - rip-) time QiP' — (QfP + i*p-) t' t" time Chapter 2. Optimal Inventory Policies 34 respectively, during time interval [0,/) satisfy, for all t G [0,T]: rimn{t,t"} ( , , \ C„P(t) - CHP,(t) = x h? - J2 dt *' V J6p(i) / (where f(t)dt = 0, if a > 6). The only change in setup costs occurs at node i and instant t', and only if x = Q}'p. Because of the monotonicity assumption MT, total setup costs will satisfy Csp(t) > Csp'it) for all t G [0,T). This completes the proof of the lemma. • Note that this Lemma, and the next two results, requires both the monotonicity as-sumption MT on setup costs and the nonnegativity assumption NE on echelon inventory costs. The Nonpositive Inventory Ordering Property is probably one of the best known properties of optimal policies. We prove it below for a rather general model. Proposition 2.4.2 (Finite Horizon Nonpositive Inventory Ordering Property) For any finite cost, feasible replenishment policy P = (tp,Qp) over a finite horizon [0, T) for the inventory model I M ( G , M T , N E , I F , G B ) ; there exists a replenishment policy P' = (tp,Qp>), which satisfies the Nonpositive Inventory Ordering Property and domi-nates policy P. Proof. If node i violates the Nonpositive Inventory Ordering Property at instant t, then we call node-instant point (i,t) a bad point. Let (i,t") be the (lexicographically) smallest bad point of policy P, then Ql"p > 0 and P-p- > 0. Let t' = max{v\Qvp > 0,0 < v < t"} as defined in Lemma 2.4.1. (Note that t' exists, as Q^P > 0 ) Because t' is not a bad point, we have l\f = 0. Because there are no positive order quantities for node i in time interval (t',t"), the order quantity Q\P must satisfy all the demands to node i in time interval [t1, t") and leave the actual inventory Chapter 2. Optimal Inventory Policies 35 level T\'P~ > 0 at instant t". Hence, the Modification Step A(i,t',t",llP~) generates a feasible replenishment policy P' from P , and it reduces the inventory level I\P~ > 0 to zero, that is, point (i,t") is not a bad point of policy P'. By Lemma 2.4.1, policy P' dominates policy P . Note however that the Modification Step may generate new bad points (j,s) for node j £ p(i), i.e., j > i, therefore, (j,s) > (i,t"), see also Figure 2.3 on page 33. In other words, the smallest bad point of policy P ' is strictly greater than the smallest bad point of policy P . As there are only a finite number of node-instant points in the finite horizon [0,T), all the bad points in [0,T) will be removed by a finite number of Modification Steps. This produces a policy which has no bad point and dominates policy P . • Note that, for the purpose of studying infinite horizon policies, we need not prove the existence of an optimal policy for finite horizon. This result, however, follows easily. Corollary 2.4.3 (Infinite Horizon Nonpositive Inventory Ordering Property) Given the inventory model IM(G,MT,NE, IF ,GB) , there exists an optimal infinite horizon policy satisfying the Nonpositive Inventory Ordering Property. Proof Let property V be the Nonpositive Inventory Ordering Property. From the previous Proposition, it follows that all the conditions in Corollary 2.3.3 hold. Applying Corollary 2.3.3 completes the proof. • Latest Ordering Property: A replenishment policy P = (t, Q) satisfies the Latest Ordering Property, if the following holds for every node i and every ordering instant t = tk: the order quantity Q\ is positive iff there exists a positive order quantity > 0 of some node j € s(i) at some ordering instant u € [tk,tk+1). Chapter 2. Optimal Inventory Policies 36 Figure 2.4: The Latest Ordering Property and the Zero Inventory Ordering Property do not imply each other time P t6 not zero time not latest ordering inventory ordering Latest Ordering means that the positive quantity ordered at the possible ordering instants (given by the replenishment policy) are delayed as late as possible. This does not mean that the corresponding ordering instants have to coincide with ordering instants of the successors. See the example in Figure 2.10 on page 60 of section 2.6.2, where warehouse 3 orders product 2 at the instants at which retailer 2 does not order. Note that in this definition, the Latest Ordering Property and the Nonpositive In-ventory Ordering Property do not imply each other. See the example in Figure 2.4 on page 36. In this figure, t\, - • • ,t% are all the possible ordering instants of policy P at node 2. At ordering instant t\, policy P satisfies the Zero Inventory Ordering Property, but does not satisfy the Latest Ordering Property. At ordering instant t\, policy P satisfies the Latest Ordering Property, but does not satisfy the Zero Inventory Ordering Property. Chapter 2. Optimal Inventory Policies 37 Proposition 2.4.4 (Finite Horizon Latest Ordering Property) For any finite cost, feasible replenishment policy P = (t, Q) over a finite horizon [0, T) for an inventory model IM(G,MT,NE, IF ,GB) , there exists a finite horizon replenishment policy P' = (t,Q'), such that P' satisfies the Latest Ordering Property and dominates policy P. Proof. The proof is similar to that for Proposition 2.4.2. If node i violates the Latest Ordering Property at instant t, then we call the node-instant point (i,t) a bad point. Let node-instant point (i,f) be the (lexicographically) smallest bad point. Then QiP > 0. Let ordering instant t" be the next ordering instant at node i after t'. Because (i,f) is a bad point, there is no demand from any node j G s(i) during time interval [t',t"). The Modification Step A(i,t',t",Ql'P), which shifts the order quantity Q\'P for ordering instant t' to ordering instant t", generates a feasible policy P' without order quantity at instant t', i.e., is not a bad point for policy P'. Therefore, policy P' has a larger smallest bad point than policy P and dominates policy P. By executing such Modification Step a finite number of times produces a policy which has no bad point and dominates policy P. D Corollary 2.4.5 (Infinite Horizon Latest Ordering Property) For inventory model IM(G,MT,NE, IF ,GB) , there exists an optimal infinite horizon policy satisfying the Latest Ordering Property. Proof. The proof is similar to that for Corollary 2.4.3. • The following concepts related to ordering instants are useful in expressing echelon inventories and order quantities in terms of ordering instants. Below, the ordering in-stants 9r are related to the first node fr of route r, and the ordering instants TT are Chapter 2. Optimal Inventory Policies 38 related to the last node £T of route r. Note that these ordering instants depend not only on nodes, such as fr and £ T, but also on route r. Given all the possible ordering instants t\ of a policy P , 9T and r r are recursively defined by tk along route r. The parameter t in the following definition reflects the relationship between any instant t (not necessarily an ordering instant) and the original ordering instant. To ease the illustration, we may assume that policy P satisfies Nonpositive Ending Inventory and Latest Ordering Prop-erties, even though the following concepts do not rely on these properties. To simplify indexing, we assume that Q\ > 0 at every ordering instant tk if i £ Djy. To understand the following four concepts, it is better to refer to the example shown in Figure 2.5 on p. 39 at the same time. et > k = 1,2, max{t%\t%<ekAfr, £=1,2,-..}, if |r| > 2 is the latest ordering instant at node fr, at which the order quantity can be used to satisfy the demand from node £T at instant tkr through route r. If policy P satisfies Nonpositive Ending Inventory and Latest Ordering Properties, then route order quantity Qk is positive only at these ordering instants 0k. For simplicity, we say that latest ordering instant 9k of node fr corresponds to latest ordering instant 9kr at node £T through route r. Consider the example in Figure 2.5. By definition 6k = tk for all k. Therefore, we have PTi = max{*£ < 0^ } = max{*£ < t\) = 4} and 0*3 = max{4 < 0* } = max have the same value. Because of this, the following concept is introduced to eliminate the duplicated indices. 0 r = ^Qk\k = 1, 2, • • •} is the latest ordering instant set at node fr for route r. Because some of the instants 9k may coincide, we let Qr = = 1,2, • • •, j where 6\ < Q2T < • • • < 6lT < • • • are all the distinct values of the elements in O r . For example, Chapter 2. Optimal Inventory Policies 0—&-Figure 2.5: Order instants 9r and r r . Part I, Actual Inventory Levels .(T)— dx ri = 1, r 2 = 2, r 3 = (3,1), r 4 = (3, 2) ^ © — ^ 2 r 5 = (4,3,1), r 6 = (4,3,2), time time time time time el e6r ri . . . i . i i ^ 6 time time -time Chapter 2. Optimal Inventory Policies 40 Figure 2.5: Order instants 6r and r r . Part II, Echelon Inventory Levels E{ Chapter 2. Optimal Inventory Policies 41 in Figure 2.5, we have Q\ =t\ = 6% = 64T3 Based on these ordering instants, we may establish two functions of any instant t. The value of 6r(t) is taken from 0 r , which is the subset of the ordering instants at first node fT of route r, and the value of r r ( i ) is on the set of the ordering instants at last node £T of route r. 9r(t)= m i n { ^ | ^ > t , k = 1,2,- • •}, for any t > 0, is the first node earliest ordering instant after instant i , i.e., the earliest ordering instant of first node /,. of route r after instant t. For example, in Figure 2.5, if t <E (0?3,6P], then we have 9T3(t) = ^ = t\. Tr(t) = < for any t > 0, i T p U p(0 p(*)), if | r|>2 is the last node earliest ordering instant for instant t, which is the earliest ordering instant of the last node £ r of route r after instant t. For example, in Figure 2.5, if t G (6>r23,0r33], then we have r P 3(t) = r r i(0 r 3(<)) = T n ( ^ 3 ) = 0rM) = *f In the following, we list the all the values of 6r and TT in terms of t\ for the example in Figure 2.5. As 1^ 1 = \r2\ = 1, we have 0* = ^ and 0 P 2 = t*. The four tables in Table 2.1 show how to express #p in terms of t^r for \r\ > 2. And the six tables in Table 2.2 show that 0T{t) and rr(t) as the functions of t. Recall that dr = Kder is the induced demand on route r, and is the actual inventory at instant rr{t) used for external demand of node £T. If a policy satisfies the Nonpositive Inventory Ordering Property, then I(ff < 0, with equality if backlogging is not allowed. The next Proposition shows that the route echelon inventory of an optimal policy can be explicitly expressed in terms of ordering instants and inventory levels at the end products only. Chapter 2. Optimal Inventory Policies 42 Table 2.1: Expressing 9r3,9ri,9rs,9re in terms oi t3,t4 0k O3 t\ t4 4 4 4 »k ^3 91 o% K ok 9 2r 9 3r 91 ok 4 4 4 4 4 ok K O3 ot 91 T± ok ok ol ot TS Ols Ots t\ tl tt t6 tl 4 ol 91 r 5 Ok Ot TS Ok 0? TS Ok Ok ol o3 T(, Ok 01 T6 ek t\ 4 t\ t\ t6 4 ok o% ot T6 ol T§ Ok ok of T6 ok er 2. Optimal Inventory Policies Table 2.2: Values of functions 0rj(t) and Trj(t) t G (*!,*?] (4,4} (4,4) (4,4} (4,4} 9ri{t) = 4 *? 4 ti tl *? ti tt ti 4 t G (i 1 t2] \L2i ' '2. (4, ^2] (^25 ^2. (t4 t5] V.fc2> t 2 J (^2>^2] (t6 t7] \l2i L2\ (t7 t8] \L2il2\ (^2> ^2] M * ) = t2 l2 • 4 l 2 /5 l 2 l2 4 t8 L2 t9 L2 *Va(<) = t2 l 2 s 2 l 2 t6 l2 4 t8 l2 t9 l2 t G KX3] M * ) = 4 t4 4 4 4 Tri(t) = 4 t5 4 4 4 t e V I M ( K M eTi{t) = 4 4 4 4 4 4 Tr<(t) = 4 4 4 4 4 4 t G (05 06 1 V^rs) "rsl M * ) = t3 L4 4 4 4 t8 l4 Trs(t) = t2 4 4 4 t8 t G (e1 e2 1 (G3 04 1 \ur6i "rel (0r6>0r6] (05 06 1 9r6(t) = t2 t3 l4 t5 l4 t6 L4 t8 L4 Tre(t) = t2 t3 l2 t4 L2 t6 l2 t9 L2 Chapter 2. Optimal Inventory Policies 44 Figure 2.6: The echelon inventory level El is a function of time t Proposition 2.4.6 (Echelon Inventory) Suppose that replenishment policy P for inventory model LM(G,-,-,IF,GB) satisfies the Nonpositive Inventory Ordering Property and the Latest Ordering Property, then the echelon inventory for each route r can be represented as 1 El (^(t)-t) + —Ier TT(t) Vr£i?. (2.13) For the non-backlogging case, the formula simplifies to El = dT [rr(t) — t]. Proof. By induction on the length of route r: (i) For \r\ = 1, we have r = £r, dT = dtT, and 9T{t) — Tr(t). Therefore, EI = ii = der(er(t)-t) + ie/ (t) = < J ( T r ( t ) _ t ) + -lrM«> der See Figure 2.6 on page 44. (ii) Suppose that equation 2.13 holds for \r\ = ra. Let \r\ — m + 1 > 2 and t\ = 8r(t). Then product fr orders positive quantity for route r at instant tl. Recall that for the Chapter 2. Optimal Inventory Policies 45 internal demands we do not allow backlogging. The Nonpositive Inventory Ordering Property thus reduces to the Zero Inventory Ordering Property. Therefore, the route inventory level it1 = 0. Note that | r \ / r | = m, £r = £r\fri ^frsrdr\fr — dr, and Tr\fr(ti) = Tr\fr(Qr(t)) = Tr(t). We have Kx~ = E v / r ' r r ' C r = E r ' C r \ / r - XfrSrK\fr = ^frsrdr\fr (rr\fM-h) + ~ ^ , A t l ) d(r (by definition) (because J ' 1 - = 0) (by definition) (by induction) = dr 1 -Tr(0 Because there is no order during time interval [£,<i), we have Et = ( h - ^ d r + E^ dr (Tr(t)-t) + —lZ This completes the proof. M*) • Note that Proposition 2.4.6 extends the Lemma 5.8 on p. 154 in Zheng's Thesis [39] (1987) to the backlogging case. By previous lemmas, there exist optimal policies satisfying the Nonpositive Inven-tory Ordering and the Latest Ordering Properties. The following Proposition also holds for such optimal policies. This new result reveals the relationship between route order quantities for such policies. Proposition 2.4.7 (Route Order Quantities) Suppose that replenishment policy P = (t, Q) for the inventory model IM(G,MT,NE, IF ,GB) Chapter 2. Optimal Inventory Policies 46 satisfies the Nonpositive Inventory Ordering Property and the Latest Ordering Property. Then for any route r £ R order quantity Ql satisfies: A / r S r £ Qsr\fr, i f | r | > 2 , •e[*Jr..«JP+1) ^ if < = *fcf IT o, otherwise (2.14) (2.15) where Ijr = 7j r (Wc? Ijr = Ijr resp.) is the inventory level of node fr at instant t = tJjr (and just before t — t°jr resp.) for j = k,k + 1. (b) Ql > 0 iff t G e r . (2.16) Proof. (a) Note that |r| = 1 implies r = fr and the first part of equation (2.14) is simply the inventory balance equations. Suppose that |r| > 2. From the inventory balance equation, if t = tf and r £ R{, we have Qr = A / r S r £ QSr\fT + Ir+1~ - Ir~•> -6[*jr.*jr) By definition, both order quantities and a r e positive. Because node i (fc DN, no backlogging is allowed at node i. By the Nonpositive Inventory Ordering Property, which reduces the Zero Inventory Ordering Property, we have lf~ = lf+1~ — 0. Therefore, I*~ — l£+1~ = 0. This completes the proof of part (a). (b) We prove part (b) by induction on the length of route r. For \r\ = 1, it is true by the definition of 6>P. Suppose (b) holds for |r| = m. For \r\ = m + 1, we have to show two implications. Case 1: Suppose Ql > 0, let t = t^. From equation (2.14), we know that there exists s £ [t^,^1) such that Qsr\fr > 0. By induction, s £ 0/ r, i.e., s = ¥JT for some I. Therefore, by definition, t = 9er, i.e., t £ O r . That is, Ql > 0 implies t £ 0 P . Chapter 2. Optimal Inventory Policies 47 Case 2: Suppose t 6 0 r , let t = tkr — 9^ for some £. By the definition of 8^, we know that 5 = 0yr G [ ty^t^ 1 ) . By induction, Qsfr > 0. From equation (2.14), we know that Q)r > 0. That is, t € © r implies Q* > 0. Therefore, by induction, (b) holds for any route. • Suppose that replenishment policy P — (t,Q) for the inventory model IM(G,MT,NE, IF ,GB) satisfies the Nonpositive Inventory Ordering and the Latest Or-dering Properties. We make the following observations: Observation 1. The route demand induced by route r at node fr £ DN come from the orders of its sub-route r\fr. They are instantaneous, and occur at discrete points in time. Case (a) in Proposition 2.4.7 implies that every induced route demand at node fr is satisfied by "one" order of node fr from its predecessor. Therefore, the number of orders at node fr for route r is always no greater than the number of orders at node sr for its sub-route r\fr over any finite horizon. Observation 2. Case (b) in Proposition 2.4.7 implies that the Latest Ordering Property holds not only for nodes but also for "routes". That is, we order each product for a route as late as possible: the Latest Ordering instant t = 9* of node fr is the only ordering instant at which the route order quantity Qk = Q\ is positive. And each route order quantity Qk is satisfied by only one route order quantity Qk, of any its super-route r' = (p r , r) . Observation 3. For the inventory model IM(G,MT,NE, IF ,NB) , a special case of the above where backlogging is not allowed, the order quantities are uniquely defined by the ordering instants. Observation 4. If Qkr > 0, it is still possible that Qk = 0, for some route r with IH > 2. Chapter 2. Optimal Inventory Policies 48 Observation 5. Note that Proposition 2.5 (p.37) in Zheng [39] (1987) is an imme-diate result of this Proposition: There exists an optimal power-of-two policy T, where T = (Ti, • • •, Tn) is the replenishment cycle time vector for a power-of-two policy, with Last Minute Ordering Property, which means node nested property in our thesis, see definition later: If di — 0 (i.e., if i is not an end-product), then Ti > min{Tj : j G S(i)}. In the following, we express the holding and backlogging cost rates in terms of echelon inventory levels instead of actual inventory levels. Recall that fr denotes the first node of route r, and R is the set of all routes in graph G(N, A). Proposition 2.4.8 (First Expression of HL) For the inventory model IM(G,- ,NN,IF,GB), the total holding and backlogging cost rate at any instant t is given by: H1 = £ KM + E m + *?)• r£R ieDN Proof. By induction on the maximum length from initial nodes (the node without predecessors) to node i, we verify that the following equation holds: h? = h\ + E A * * ? = E Kh)r1 (2.17) where Gi is the set of all "paths" which start from a node j G P(i)\J{i} and end at node i. Note that / ' = l\ — JJ, = + JJ and P\ = 0 if node i £ DN, then we have: H* - E < j W + m + E w ieDN i£N\DN = E [tftf+lSvM+ *?)]+ E M i&DN i€N\DN ieN i€DN and E M = E ieN i^N E A p 1 *0 (E V E E E M,^) ieNrxeGi r'eRi Chapter 2. Optimal Inventory Policies 49 Figure 2.7: Decomposing all the routes passing through node i Gil fr Gi / o-}Ri Ri For any route r = (fr, • • • ,£r) £ R, let z £ r, r x = (/ r , • • •, i) and r' = (i, • • • ,£r). Then r-i £ Gi, r' £ i?t- and A n = \r/Xri. Rearrange the summation in the previous equation by first going through all the routes r £ R, then collecting all terms with i £ r symbolically, and reassigning to subroutes: EE E = ££ = ££• ieN r i € G , r'eRi reRier reRr'Cr See Figure 2.7. Therefore, This completes the proof. • Consider inventory model IM(G,- ,CT,IF,GB), where the holding and backlogging cost rates are constant. If a replenishment policy satisfies the Nonpositive Inventory Ordering and the Latest Ordering Properties, we obtain an explicit expression of holding and backlogging cost rates in terms of ordering instants. Chapter 2. Optimal Inventory Policies 50 Corollary 2.4.9 (Second Expression of Hl) Suppose that replenishment policy P for inventory model IM(G,- ,CT,IF,GB) satisfies the Nonpositive Inventory Ordering and the Latest Ordering Properties. Then the total hold-ing and backlogging cost rate at instant t is given by 1 H* = ^ h f r d r reR ( T T ( t ) - t ) + —ll M*) ieDN where for i G -di (6i(t) -t) + 0, > 0, if di(6i(t) -t) < otherwise. Proof. By definition, for i G D^, we have P\ = max {—d,- {ji(t) — t) — Ij'^\ 0 J . By Nonpositive Inventory Ordering Property, we have Ij'^ < 0. Applying Propositions 2.4.8 and 2.4.6, completes the proof. O Nonnegative Filling Property: Given replenishment policy P for inventory model IM(G,-,• ,IF,GB), if order quantity Qj at node i G DN and ordering instant t re-duces the actual route inventory to a non-negative level (i.e., 7T-+ > 0), then the Nonnegative Filling Property holds for node i at ordering instant t. If the Nonneg-ative Filling Property holds at every node in DN and every ordering instant, then replenishment policy P satisfies the Nonnegative Filling Property. The following Proposition matches the intuition that optimal policies should satisfy the Nonnegative Filling Property. However, the proof is not trivial for a general inventory system. This property was implicitly assumed in Mitchell's paper [18] (1987), when he calculated the inventory level of the inventory system, without proof. This result is also used in Chapter 4 of this thesis for the backlogging case. Chapter 2. Optimal Inventory Policies 51 We will use the following notation in Proposition 2.4.10: consider a replenishment policy P and node-instant point (j,0j), where node j £ DN and 6'j is a latest ordering instant. For any route r 3 j (including node j itself), let t = 9'r be the latest ordering instant of node fT incurred by the instant 9'- of node j through route r. Let Q\p be the corresponding route order quantity. (Refer to the definition of 0k.) Then define Q'rP and I'TP as follows: Q'rP^Qlp, I'rP^Kp, i f* = C for r3j (including r = j). Similarly, let the latest ordering instant 9" be the next latest ordering instant at node j after 9'j. Define Q"P and I"p as follows: Q';P = QTP, I'r'p = lip, if* = C f o r r ^ j (including r = j). Proposition 2.4.10 (Finite Horizon Nonnegative Filling Property) For any finite-cost, feasible replenishment policy P = (ip,Qp) for an inventory model IM(G,MT,CT,IF,GB) over a finite interval [0,T), there exists a replenishment policy P' = (tp,Qpi) which satisfies the Nonnegative Filling Property, and dominates policy P over interval [0,T). Proof. Based on Proposition 2.4.2 and Proposition 2.4.4, it may be assumed that replenishment policy P satisfies the Nonpositive Inventory Ordering and the Latest Or-dering Properties. If node j £ DN violates the Nonnegative Filling Property at ordering instant t, we call node-instant point (j, t) a bad point. Let (j, 9'f) be a bad point under policy P. Then l'fp < 0 and Q'jp > 0. Let 6" be the next latest ordering instant of node j after ordering instant 9j, that is, Q"P > 0, which is defined as the same as Q'jP. See Figure 2.8 on page 52. Chapter 2. Optimal Inventory Policies 52 Figure 2.8: Predecessor Modification Step Aji(j,6",0'r,x) r = (/r,sr,j), n = (sr,j) Chapter 2. Optimal Inventory Policies 53 For each route r 3 j , let 9'r and 6" be the latest ordering instants of node /,. corre-sponding to latest ordering instants 6j and 9" through route r, respectively. Let Q'rP and Q"P be the corresponding route order quantities. Policy P' = (tp,Qpi) is defined by applying the following Predecessor Modification Step An(j,9",9'r,x) as follows: Q'rp + \rx, if t = 9'T QIP> = I Q'rP — XrX, if t QIPI Vr 9 j (including r — j), otherwise; and Q\p> = HQIP', f o r a l H e / V . r9« By Proposition 2.4.7, we have Q'rP > A/ r S r<5' r\ / r, and Q"rP > XfTsrQr\fT- Therefore, policy P' resulting from the application of Predecessor Modification Step Ap(j,9",9r,x) is feasible for any x £ [—Q'JP, Q"p\- However, if x < 1-% , the only backlogging cost to be changed is that at node j. Therefore, we require x £ [ — Q'jp, min | I-~p ,<5JP|]-Note that the holding cost of every node i £ P(j) may be changed. Recall that bj is the backorder cost rate of node j. The total change of holding and backlogging cost is CHP'{T) — CHP{T) — a X x, where a rBj, r^j is a constant independent of x as long as x £ [—Q'jp, min{|/ J-p|, Q"p}] • Let ' -Q'j if a > 0, min{|/;p|,Q?p} if a < 0 , and let policy P' result from policy P by application of Predecessor Modification Step AR{j, 9", Q'r,x*)- T n u s CHp'(T) < CHp(T). We claim that policy P' has fewer bad points x = Chapter 2. Optimal Inventory Policies 54 than policy P in either case: If a > 0, then there is no order for j at instant 0', i.e., (ji, 6j) is not a bad point. If a < 0, we have two sub-cases to consider. First, if |7-p| > Qjp, then x* = Q"p, and there is no order for j at instant 0". Note that (j,0j) must also be a bad point of policy P, but is not a bad point of policy P'. Second, if \Ijp\ < Q'jp, then x* = |7-p| and (j,0j) is no longer a bad point of policy P' Because of the monotonicity of the set-up cost function, the total set-up cost cannot increase, i.e., CSp>{T) < CSp(T). Therefore, CP,(T) < CP(T). In summary, policy P' dominates policy P and has fewer bad points over finite horizon [0,T). By executing Predecessor Modification Step Ap,(j,0",0'r,x*) a finite number of times, we construct a policy P' without any bad point and dominating policy P. The proof of Proposition 2.4.10 is completed by repeating this construct a finite number of times, until all bad points are eliminated. • C o r o l l a r y 2.4.11 (Infinite H o r i z o n N o n n e g a t i v e F i l l i n g P r o p e r t y ) For inventory model IM(G,MT,NE, IF ,GB) there exists an optimal infinite horizon policy satisfying the Nonnegative Filling Property. Proof. By applying Corollary 2.3.3 and the previous Proposition, it is easy to verify this Corollary. • N o d e Nestedness P r o p e r t y : A replenishment policy P is said to satisfy the Node Nested Property, if every node i £ N orders only at instants which coincide with an ordering instant of one of its successors. E v e r y N o d e Nestedness P r o p e r t y : A replenishment policy P is said to satisfy the Every Node Nested Property, if every node i £ TV orders only at instants which Chapter 2. Optimal Inventory Policies 55 coincide with an ordering instant of every of its successors. If policy P satisfies Every Node Nestedness Property, we may say that P is a nested policy. Note that Node Nestedness Property sometimes is called "Last Minute Ordering", as in Zheng's thesis [39] (1987). He demonstrates that Node Nestedness Property holds for inventory model with general acyclic network (G) and separable setup cost function (SP) in Theorem 2.2, p.26 of his thesis [39] (1987). We demonstrate it in an extended form, i.e., allowing backlogging, without proof. Theorem 2.4.12 (Node Nestedness Property for Separable Setup Function) For inventory model IM(G,SP,CT,IF,GB) there exists an optimal policy satisfies Node Nested Property. On pp.28-30 of his thesis [39] (1987), Zheng showed that Node Nestedness Property does not hold for inventory model with non-separable setup cost by an inventory model of only three nodes. If an optimal policy could be a nested policy, it is easier to deal with such as in Chapter 4. Therefore, it is interested to known for which inventory model there is an optimal nested policy. Lemma 2.4.13 below specifies a sufficient condition for it. Lemma 2.4.13 (Optimal Nested Policy for Assembly Systems) For inventory model IM(A,SP,CT,IF,GB) there exists an optimal nested policy. Proof. This follows from the fact that there is only one successor and Theorem 2.4.12. • Chapter 2. Optimal Inventory Policies 56 2.5 Conclusions In this chapter, we prove the existence of an optimal policy for a large class of inventory models. This had been a open question for a long time. We also present properties of optimal policies in this chapter. For simplicity, we only consider inventory models with infinite production rate. In fact, these properties may be extended to inventory models with finite production rates. As an example, we present some of the properties for the assembly systems in Chapter 3. These properties of optimal policies are useful in probing optimal policies per se. They are also useful for special classes of policies, such as power-of-two policies, under which we may further simplify the average cost formulation. For example, in Chapter 4, we consider a series inventory model with backlogging, for which an optimal policy is nested. If we consider integer frequency policies, the expression of holding and backlogging cost is further simplified. Based on this formulation, we derive heuristic and a lower bound. These developments rely in part on properties of optimal policies. Chapter 2. Optimal Inventory Policies 57 2.6 Appendix to Chapter 2 2.6.1 An Inventory Problem That Has no Optimal Policy The following example illustrates that an inventory problem could have no optimal policy. Example. A two-product joint replenishment inventory problem over finite hori-zon [0,2) does not allow backlogging. Suppose its initial inventory levels 1,(0) = 0, holding cost rates h{ = 1, demand rates di = 2, {i = 1,2) and the joint setup cost function is Because no backlogging is allowed, any feasible policy has to replenish both products 1 and 2 at instant 0, therefore incurring an initial setup cost of 3. Taking this into account and using the setup cost allocation of Atkins-Iyogum [3] (1987), it can be shown that a lower bound on the total cost is 9. This lower bound could only be achieved if both product were jointly replenished at instants 0 and 1, but the joint replenishment at instant 1 increases the total cost to 10. Consider the following sequence of policies depending on parameter e satisfying 0 < e < 1: Product 1 is replenished at instants 0 and 1, and product 2 is replenished at instants 0 and 1 — e (see Figure 2.9). The total setup cost over [0,2) is 3 + 2 = 5, the total holding cost over [0,2) is 2 + (1 - e)2 + (1 + e)2 = 4 + 2e2, and the total cost over [0,2) is Ct = 9 + 2e2. K(S) = 1, i f | 5 | = l , 3, if \S\ = 2. Therefore, l im Cc = 9, but no policy can achieve a total cost of 9. • Chapter 2. Optimal Inventory Policies 58 Figure 2.9: Example showing that no optimal policy exists 2.6.2 Some misunderstanding of the properties of optimal policies Various properties of optimal inventory policies have been investigated since the late 1950's. The classic Wagner-Whitin [38] (1958) paper was one of the first works dis-cussing such properties. But very few new properties have been discovered since the early 1960's. Schwarz [33] (1973) and Zheng [39] (1987) summarized the known proper-ties. These properties seem simple and easy to accept, but they may also be very easily misunderstood. For example, for 1-warehouse n-retailer systems, nested policies (i.e., such that when the warehouse orders, each retailer also has to order) have long been implicitly assumed to be near optimal. Unfortunately, nested policies may be arbitrarily bad, as Roundy [27] (1983) pointed out. Another example is in Mitchell's [18] (1987) paper. He considered 1-warehouse n-retailer systems with backlogging. He misinterpreted the last minute ordering property as follows: "By last minute ordering (see Schwarz 1973) we know that retailer i will also Chapter 2. Optimal Inventory Policies 59 order at those instants when the warehouse orders products iv. In fact, this interpreta-tion is wrong. It is possible that the warehouse orders product "z" at an instant that the retailer " i " does not. See the example in Figure 2.10 on page 60, where warehouse 3 orders product 2 at the instant that retailer 2 does not order. This misinterpretation, however, does not invalidate his Lower Bound Theorem, but the latter needs a correc-tion. This correction uses the latest ordering property demonstrated in this chapter. (1) Because of the Observation 1 of Proposition 2.4.7, the number of orders at warehouse for product i is no greater than the number of orders at retailer i. Therefore, the in-equality in Mitchell's [18] (1987) still holds. (2) It requires to consider an additional simple case where the warehouse orders product i at an instant when the retailer i does not: in Figure 2.10, we know that the ordering instants of retailer 2 do not coincide with the warehouse 3. As each retailer order will be satisfied by one warehouse order, the warehouse may delay this ordering instant to match the corresponding ordering instant of the retailer. This will reduce the holding and backlogging cost. As the setup cost function is separable, we do not change the setup costs of warehouse and the retailers. This modification will generate a lower bound for the policy, although it is not necessarily a feasible policy. Chapter 2. Optimal Inventory Policies Figure 2.10: The order instants at warehouse do not coincide with the order instants at retailers. r 1 = l , r 2 = 2, r 3 = (3,l), r 4 = (3,2) time time time time Chapter 2. Optimal Inventory Policies 61 2.6.3 A proof of lemma 2.3.4 by using a "remove" Algorithm Lemma 2.3.4 For the inventory models IM(G,MT,IN,IF,GB) and IM(G,MT, IN,FF ,NB) the Nonposi-tive Ending Inventory Assumption holds. Proof. We only show that the result holds for the inventory model IM(G,MT,IN, IF ,GB) . The proof for the other model is similar. The following algorithm "Remove(I,i,t)" in Figure 2.11 removes the "extra" inventory amount I at node i and instant t, as well as all the inventories of i's predecessors which supply the "extra" inventory I. The proof is completed by calling algorithm "Remove(J, i, X1)" for each node i £ N at ending instant T. D Figure 2.11: Algorithm Remove (I,i,t) Input: I, i , t, Q; Output: Q. begin if 7 > 0 then begin / * find the instant u of the order which supplies inventory / . */ u <- max{v < t\Qv > 0,} ; if Qf > I then begin / * reduce the order quantity at node i and instant u by amount I. */ Qi^Qi-T, /<-0; / * increase the inventory at node j G p(i)- */ for all j E p(i) do Remove(Ajt7,j, u); end else/* <I */ begin for all j e p(i) do Remove(Aj,(5",i, u); I<-I-Q?; Q ? ^ C J ; / * extra inventory I is not reduced to zero, */ /* call the remove algorithm again */ Remove(J, i , t); end end end. Chapter 2. Optimal Inventory Policies 2.6.4 Calculating W: An Example Figure 2.12: The production network of six products K5,K Kuh[ Table 2.3: Definition of routes ri r2 ^3 ^5 re r7 r8 r9 7*10 1 2 (3,1) (3,2) (4,2) (5,3,1) (5,3,2) (6,3,1) (6,3,2) (6,4,2) Table 2.4: Holding costs hi and hjr J r 3 hfri hfr Jr6 hfr hfr hi h2 h3 hs /14 hb h5 h6 h6 h6 Chapter 2. Optimal Inventory Policies Table 2.5: A r and A ; , A n A r 2 K3 A r s A r 6 A r 7 A r g A j - i o 1 1 A31 A32 A 4 2 A53A31 A53A32 ^63^31 ^63^32 A 6 4 A 4 2 Table 2.6: Echelon inventory Er and actual route inventory Ir E r i E T 2 E T 3 E T i E r s Er6 E r ? Erg Er10 Iri Ir2 IT3 + I r i + Ir5 + Ir6 + Ir7 + •i"re + Ir9 + Irio A3I Ir! A32 Ir2 A 4 2 - ^ r 2 A 53-^7-3+ A 531^ + ^63^3 + ^63^4 + A64-^r5 + ^53^31^7-1 ^53^32^2 A63A31-^ 7-1 A63A32 -^7-2 A 6 4 A 4 2 / r 2 Table 2.7: Node inventory 7t and actual route inventory IT h h h h h h IT2 Irs ~\~ Ir4 Ir& 1re ~T~ ^-v? Irs Irg ~T Ir\o Table 2.8: Holding cost rate h\ and echelon holding cost rate hj K K K K K K h! + h2+ A3l/i3 + A32^3 + h3+ A42^4 + h4+ ^53^31^5 + ^53^32^5 + A 5 3 / i 5 + h5 ^63^31 he A63A32^6 + ^4X42^ A63^6 A64^6 h6 Chapter 2. Optimal Inventory Policies 64 H* = J2Kit • i = l = (h + A 3 1 f t 3 + A 5 3 A 3 1/i5 + A 6 3 A 3 1 / i 6 ) / r i + (^ 2 + A 32/l 3 + A42/I4 + A53A32/i5 + A6 3A 32^6 + ^ 64-^42ra6)7r2 +(h3 + \53h5 + A 6 3 f e 6 ) ( / 1 . 3 + 7 r J + ( / i 4 + A 6 4 / i 6 ) / r 5 + / i 5 ( / r 6 + J r r) + h6(Irs + Irg + Iri0) = h\ITl + /l2-^r 2 + (X3\ITl + IT3)h3 + ( A 3 2 / r 2 + ITi)h3 + ^ 42-^2 + -^r 5) r t4 + (^r 6 + A 5 3 / r 3 + ASSASJ/J-J ) « 5 + (7 r ? + A 5 3 / R 4 + A53A32-/j.2)/l5 + (^r 8 + ^63-^r 3 + ^63^31 ^n)^6 + (-^ rg + ^63-^T-4 + A 6 3 A 3 2 / r 2 )^6 ~K^ no + ^64^7-5 + ^64-^42 ^ 2)^6 10 2.6.5 Notation and Definitions In this section, all the notation and definitions are collected for reference. A - Assembly Systems (a special case of G): each node has exactly one successor in the network G(N, A), except for one node, which has no successor and is called the root node. B - Always backlogging (a special case of G B ) : Backlogging is allowed for every external demand. b\ is the backlogging cost rate of product i at instant t: it is the cost of backlogging one unit of product i for one unit of time at instant t. A fT CH(T) = / Hl dt is the total holding and backlogging cost accrued during the time interval [0, T ) . C T - Constant holding and backlogging cost rates (a special case of NN): h? = h'{>0 and b\ = 6t- > 0, which are independent of time t for each product i. Chapter 2. Optimal Inventory Policies 65 D - Distribution Systems (a special case of G): each node has exactly one predecessor in the network G(N,A), except for one node, which has no predecessor. reRi DN = {i £ iV|s(i) = 0} is the set of all nodes without successor. Without loss of gen-erality, we may assume that = {i ' € N\ node i has external demand} — the external demand set of G(N,A). Otherwise, if node i in an inventory model has both "external demand" di and "internal demand" induced by its successors, we may construct a new inventory model from the original inventory model by adding a pseudo node ie, arc (i, z'e), moving the external demand di from node i to node ie and letting setup cost Kie = 0, K(S\Jie) = K(S), actual holding cost rate h'{ = h'^ backlogging cost rate 6t-e = 6, and not allowing backlogging at node i. It is easy to establish a correspondence between feasible policies for these two inventory sys-tems, preserving total cost. For example, given any feasible policy for the original inventory model, we may construct a feasible policy for the new inventory model by immediately delivering all the inventories at node i for external demand di to node ie (see the example in Figure 2.13 on page 66). It is easy to check that the total cost of the policy for the new inventory model is exactly the same as the original one. For the reverse, given any feasible policy for the new inventory model, construct a policy for the original inventory system by merging the inventory at node i and ie for the new inventory model. This gives a feasible policy for the original inventory model, which has the same total cost as the new inventory model unless the following situation arises: node i has positive inventory and node ie has negative inventory (backlogging). However, such a policy is dominated in the new inventory model, because shifting (pushing) the product demand rate of node i. Chapter 2. Optimal Inventory Policies 66 Figure 2.13: The correspondence between the two inventory systems. di Original Inventory System time (0,AJ) / New Inventory System P time Chapter 2. Optimal Inventory Policies 67 from i to ie incurs no additional setup cost and has the same holding cost, but eliminates the backlogging cost. Dominate: Policy P' dominates policy P over interval [0,T), if Cp>(t) < Cp{t), Vt £ [ o , r ) . dr = \rder is the induced route demand rate at node fr from route r. Every Node Nestedness Property: A replenishment policy P is said to satisfy the Every Node Nested Property, if every node i £ T V orders only at instants which coincide with an ordering instant of every of its successors. If policy P satisfies Every Node Nestedness Property, we may say that P is a nested policy. E\ is the echelon inventory on route r at instant t. It is the total inventory of good fr on route r, defined as follows: where routes r' are subroutes of r having the same last node. Et- = ]imEl'. Er+ = l i m £ r ' . r t'\t T F - Finite production rate: the production rate 7T; is finite for each node in T V . A feasible policy P is a policy which satisfies all the requirements of the model under consideration. These requirements include satisfying external demands for specified products, without backlogging if it is prohibited. F F - Fast finite production rate (a special case of F): 7r8- > E A , J 7 T J , for all i £ T V . Chapter 2. Optimal Inventory Policies 68 fr = ii is the first node of r. G - General acyclic network: there is no directed cycle in network G(N,A). G B - General Backlogging: Backlogging may be allowed for some or all external de-mands, but is not allowed for any internal (induced) demand. G ( N , A ) is an acyclic direct graph, where N = {1,2, • • • , n} is the node set, and A is the arc set. The nodes are indexed such that i > j if (i,j) G A. h\ = h'l — E ^ijhj is the echelon holding cost rate of node i at instant t: it is the "added" holding cost rate for product i. h'i is the holding cost rate of product i at instant t: it is the cost of holding one unit of product i for one unit of time at instant t. h\ = the actual inventory holding cost rate at node i. A n t Hf = E(^'^/ + 1S the total holding and backlogging cost rate at instant t. which i=l is the total holding and backlogging cost in one unit of time at instant t. Holding and Backlogging Costs are inventory related cost, charged in terms of the units of products stored and backlogged and the length of time it is stored and backlogged, respectively. Let I - Isolated nodes (a special case of G): A = 0. i £ r means that node i G {z'i, i2, • • •, im}-{ i i , i2, • • •, i m } is the node set of path r. IF - Infinite production rate: the production rate 7r,- of each node is infinite. Chapter 2. Optimal Inventory Policies 69 I\ is the actual (node) inventory level of product i at instant t. I\~ = lirn Ij is the inventory level just before instant t, l\+ — lim l\ is the inventory level just after instant t. /• = max(—lj,0) is the backlogged inventory level of product i at instant t. T* = max(7',0) is the physical inventory level of product i at instant t. I\ is the actual route inventory at node / r for route r at instant t. By definition, / ' = J' for all t. Similarly, = lim/;'. r t'/t T Pr+ = lim If. t'\t T lM.(network, setup cost, holding/backloging cost, production rate, backlogging) is the in-ventory model. An infinite/finite horizon policy: If the planning horizon is infinite (resp. finite), the policy P is called an infinite (resp. a finite) horizon policy. If P is an infinite horizon policy, the restriction of P to a finite horizon [0, T) is a finite horizon policy, which is also called policy P for simplicity. Kf : 2N R+ is the setup (or joint replenishment) cost function. It is assumed that 7Y ' (0) = 0, and K*(S) > 0, VS ^ 0 , S C N. Let Jfc,- be a real number associated with each node i E TV. Latest Ordering Property: A replenishment policy P = (t, Q) satisfies the Latest Ordering Property, if the following holds for every node i and every ordering instant Chapter 2. Optimal Inventory Policies 70 t = tk: the order quantity Q\ is positive iff there exists a positive order quantity > 0 of some node j € s(i) at some ordering instant u 6 [tk,tk+1). The long-run average cost Cp of an infinite horizon policy P is defined by (2.18) A £r = im is the /as£ node of r. M D - Modularity or First Order Interaction (a special case of SM): K{$) = 0, K(S) = KQ + E VS 0) £ — where K0 > 0 is a fixed constant. M T - Monotonicity: K(S) < K(T), V 5 C T C J V . N B - No backlogging (a special case of GB): There is no backlogging at any place. N E - Nonnegative Echelon holding cost rates (a special case of CT): hi > 0 and con-stant. N N - Nonnegative Holding and backlogging cost rates: h'l > 0 and b\ > 0 for each i £ N. Thus holding and backlogging costs are increasing functions of the number of units stored and backlogged in the holding and backlogging duration. Node—instant point (i,t) is a pair of node i and ordering instant t. Over any finite horizon [0, T), if i < j or, if i = j and t < u, we say that node-instant point (i,t) is less than node-instant point (j,u), written as (i,t) < (j,u). (This is the usual lexicographic order on N x [0, T).) Node Nestedness Property: A replenishment policy P is said to satisfy the Node Nested Property, if every node i £ N orders only at instants which coincide with an ordering instant of one of its successors. Chapter 2. Optimal Inventory Policies 71 Nonnegative Filling Property: Given replenishment policy P for inventory model IM(G,-,-,IF,GB), if order quantity Q\ at node i G and ordering instant t re-duces the actual route inventory to a non-negative level (i.e., 7*+ > 0), then the Nonnegative Filling Property holds for node i at ordering instant t. If the Nonneg-ative Filling Property holds at every node in DN and every ordering instant, then replenishment policy P satisfies the Nonnegative Filling Property. Nonpositive Ending Inventory Assumption: for any feasible policy P over finite horizon [0,T) there-exists a Nonpositive Ending Inventory policy P', which domi-nates policy P. When backlogging is not allowed, the Nonpositive Ending Inventory Assumption reduces to the Zero Ending Inventory Assumption. Nonpositive Ending Inventory Policy: A finite horizon feasible policy P over [0,T) is a Nonpositive Ending Inventory policy if the inventory level of each product is nonpositive at instant T. When backlogging is not allowed, a Nonpositive Ending Inventory policy is a Zero Ending Inventory policy. Nonpositive Inventory Ordering Property: If a replenishment policy P orders quan-tity Q\ > 0 at node i and ordering instant t with actual inventory level l\~ < 0, it is said that policy P satisfies the Nonpositive Inventory Ordering Property for node i at instant t. O - One-warehouse Multi-retailer Systems (a special case of D): one node, termed the warehouse, has successors but no predecessor in network G(N,A), and all other nodes, the retailers, have no successor and exactly one predecessor, the warehouse. The optimal average cost C~* over all feasible policies is defined by V = inf CP. (2.19) all feasible P Chapter 2. Optimal Inventory Policies 72 Path r = i2, i3, • • • , « m _ i , i r a ) is a sequence of nodes i\,i2, • • •, im £ N such that all arcs (ii, » 2), (»2,13) , • •', ( ' m - i , im) € A. •Ki is the production rate at node i, i.e., the number of units that can be produced at node i per time unit. p(i) = the set of immediate predecessors of node i. P(i) = the set of all predecessors of node i. R = [j R{ is the set of all routes r in G(N, A). \r\ = m is the length of path r. A replenishment policy P = (tp,Qp) is a specification of ordering instants tp and order quantities Qp for all products over a planning horizon. That is, at instant t, and if t — tkiP the quantity Q\P may be replaced by QkP, whenever it is convenient. Note that for the finite product rate case the ordering instant t is the production starting time. When replenishment policy P is not emphasized, subscript P in t and Q may be dropped without risk of confusion. Route r = {i\,i2,iz, • • •, i m _ i , i m ) is a path terminating at a node im £ Djq. tP — (t1P,t2P,- • • ,tnP), Qp = (QiP, Q2P1 • • •, Qnp), 0 < t)P < t2iP < •• • < tkiP < ••• > * = 1,2,- • • ,n = ( Q J P ,<5?P , - - - , Q ? P,---) >O, , where n is the number of products, quantity QkP is the amount of product i ordered at instant t\P. Sometimes we use Q\P to represent the amount ordered for product i Chapter 2. Optimal Inventory Policies 73 A Route Order Quantity Qtr is that part of order quantity Q • at node i and ordering instant t which is used to satisfy the (induced) demand from node lr along route r. By definition, Q\ = £ Q\. reRi R' = " ' J ?m) with j G {1, • • •, m} is a sub-route of r, denoted by r' C r. r \ / r = ( ? 2 , • • •, im) is £/ie immediate sub-route of r. i?,- is the set of all routes r starting at node i G N, i.e., such that fr = i. S - Series Systems (the intersection of A and D): each node has exactly one successor and one predecessor in the network G(N,A), except for two nodes, one with only a successor and the other one with only a predecessor. SA - Monotonicity and Subadditivity: K(S{jT) < K(S) + K(T), \/S,T C N. s(i) = the set of immediate successors of node i. S(i) = the set of all successors of node i. SM - Monotonicity and Submodularity: K(S\JT) + K(S D T) < K(S) + K(T), VS, TCN. SP - Separability (a special case of MD): K(S) = ^ kt, VS C N. sr = ii is the second node of r. The total cost Cp(T) of policy P over finite horizon [0,T) is the sum of total setup or ordering cost Csp(T) and total holding and backlogging cost CHP{T) over horizon [0,T), that is, CP(T) = CSP(T) + CHP(T). Zero Initial Inventory Assumption: The initial inventory of each product is zero and all the products are replenished at the initial instant 0. Chapter 2. Optimal Inventory Policies 74 Zero Inventory Ordering Property: P o l i c y P orders pos i t i ve quan t i t i e s at node i o n l y at ins tan ts t where l\~ — 0. Xij is the n u m b e r of un i t s of p r o d u c t i r equ i r ed to p r o d u c e 1 u n i t of p r o d u c t j, for (ij) <E A. \ A ) 1 i f |r| = l , is the n u m b e r of un i t s of p r o d u c t fr re-A t l j 2 A , - 2 i 3 • • • A t m _ l l m , i f \r\ > 2 q u i r e d to p r o d u c e 1 u n i t of p r o d u c t £ r t h r o u g h p a t h r . m * I i f H = ^ Tr\t) = \ for any t > 0, TAfr($r(t)), i f |r| > 2 is the last node earliest ordering instant for ins tan t t, w h i c h is the earl iest o rde r ing ins tan t of the last node £ r of route r after ins tan t t. Qr = 1^ \k = 1, 2, • • • | is the latest ordering instant set of node fr for rou te r. Because some of the ins tan ts BkT m a y co inc ide , we let Qr = \&i\£ = 1,2, • • • , j where 9\ < Or < • • • < &r < • • • are a l l the distinct values of the elements i n 0 r . 0r(t)= m i n {0*10* > t, k — 1,2,- • • } , for any t > 0, is the first node earliest ordering instant after ins tan t t, i .e. , the earliest o rde r ing ins tan t of first node fr of rou te r after ins tan t t. 0 f c = t if M = 1 > k = 1,2, max{tefr\tjr<0kAU, £=1,2,---}, i f | r | > 2 is t he latest ordering instant at node fT, w h i c h can be used to satisfy the d e m a n d f r o m node £ r at ins tan t tkr t h r o u g h route r . Chapter 3 Lot Sizing Policies for Finite Production Rate Assembly Systems 3.1 Introduction This chapter considers lot sizing policies in the inventory model IM(A,SP,NE,FF,NB) , i.e., a production/inventory assembly system with finite production rates and satisfying the following assumptions: 1. External demand for the single final product is known and occurs at a constant rate in continuous time. 2. Production rates at each facility are finite, non-increasing along any path in the assembly system and greater than the external demand. The importance of the latter assumption is that, in an optimal policy, there is no need for a facility to build extra inventory to meet future withdrawals from its successor. 3. Proportional echelon holding costs are incurred at each facility, and no back-orders are permitted. A fixed set-up cost is charged at each facility when production starts. There are no cost savings on joint production at different facilities. 4. Lot transfer times are zero throughout the system, that is, the finished product of any facility is immediately available to its successor. (Szendrovits [36] (1975) considers a finite production rate series system with non-zero lot transfer times, but with identical lot sizes throughout the system). 5. We are considering policies which minimize long-run average costs. 75 Chapter 3. Finite Production Rate 76 We elaborate on these assumptions by comparing them to previous work. Most work to date has concentrated on the case when production is instantaneous, i.e., infinite pro-duction rates. Roundy [27] (1983), [30] (1986) demonstrates that with infinite production rate, a relatively simple heuristic delivers a high quality (effective) solution to the multi-stage production/inventory lot sizing problem. The heuristic restricts replenishment time intervals for all components to a power-of-two multiple of a base interval. Roundy proves that there exists a power-of-two policy which is guaranteed to be 94%-effective. Put another way, the cost of power-of-two policies is within about 6% of the unknown opti-mum. By optimizing the base interval, this can be improved to within about 2%. Several generalizations, such as to more general cost structures and acyclic networks (e.g., [24] (1985), [30] (1986), [39] (1987) ), extend the class of problems for which such guaranteed effectiveness results hold. The literature on finite production rates is less comprehensive. The main differences between finite production rate systems and infinite production rate systems arise in the following ways. First, in infinite production rate systems, an optimal policy requires that facilities start producing at zero actual and echelon inventories. Echelon inventories, therefore, follow saw-tooth patterns, i.e., all the troughs touch the zero inventory line. However, in finite production rate systems, optimal policies do not require echelon inventories to be zero when production starts. Neither actual nor echelon inventories follow simple saw-tooth patterns, see Figure 3.17 on page 116. Second, optimal policies for infinite production rate systems are nested. Nested means that each production starting time of a facility has to coincide with a production starting time of its successor. If production rates are finite, optimal policies may be non-nested. Crowston, Wagner, and Henshaw [6] (1972), Schwarz and Schrage [34] (1975) (see also Szendrovits [37] (1981)), studied integer-multiple lot size policies, wherein the lot size at Chapter 3. Finite Production Rate 77 each facility is an integer-multiple of its successor's lot size. Such policies are actually nested. Moily [20] (1986) investigated integer-split lot size policies, wherein the lot size at each facility is an integer-split of its successor's lot size. This is, in a sense, the "reverse" of being nested. We will see that neither integer-multiple lot size policies nor integer-split lot size policies dominate each other. As shown in Section 3.9.1, both integer-multiple and integer-split lot size policies may be arbitrarily bad, i.e., their effectiveness is (asymptotically) zero. In fact, no heuristics for finite production rate assembly systems have, to our knowledge, been shown to have a nonzero effectiveness. Third, it is not necessarily effective in finite production rate systems to use constant reorder time intervals, as it is done for the infinite production rate case. Actually, reorder intervals at a facility need not be the same, even for a same lot size. This is illustrated in Section 3.9.2. In addition, a formulation of the problem is simplified when couched in terms of lot sizes rather than reorder intervals. Although the production schedule will not be as simple as with constant reorder intervals, it can be readily identified using the scheduling algorithm described in Section 3.9.2. If we let all the production rates go to infinity, we obtain infinite production rate assembly systems as special cases. Therefore the Lower Bound Theorem of this chapter holds for infinite production rate assembly systems. Yet, our proof is distinctly different from Roundy's [27] (1983). The three major contributions in this chapter are as follows. First, for assembly sys-tems with non-increasing finite production rates, a formulation of the lot-sizing problem is developed in terms of integer-ratio lot size policies, expressed in terms of lot sizes rather than reorder time intervals. This formulation unifies the integer-split policies for-mulation of Schwarz and Schrage [34] (1975) and the integer-multiple policies formulation of Moily [20] (1986). Chapter 3. Finite Production Rate 78 Second, the solution to the continuous relaxation of this unified formulation provides a lower bound to the cost of any feasible policy. The derivation of this Lower Bound Theorem, a key result in this chapter, is novel and relies on the notion of path hold-ing costs, a generalization of echelon holding costs. This proof is significantly different from earlier proofs of similar results, which rely on convex duality. The proposed proof technique may perhaps itself lead to further generalizations. Third, an optimal power-of-two lot size policy is found by a 0(n5) algorithm and its cost is within 6% or 2% of the optimal in the worst case, depending on whether the base lot-size is given or not. These results are the first such results, we believe, for the finite production rate case. The structure of the chapter is as follows. Section 3.2 contains all the requisite notation for reference. Section 3.3 lists some properties of optimal policies. A basic formulation for integer-ratio lot size policies is introduced in Section 3.4. The Lower Bound Theorem is given in Section 3.5. Section 3.6 demonstrates the effectiveness of integer-ratio and power-of-two lot size policies. Section 3.7 presents an algorithm for obtaining 94% and 98% effective power-of-two lot size policies. Section 3.8 summarizes the main contribution of this chapter, discusses some of their implications, and suggests directions for further research. Section 3.9.1 illustrates that both integer-multiple and integer-split lot size policies can simultaneously be arbitrarily worse than integer-ratio lot size policies. Section 3.9.2 contains a scheduling algorithm for converting a policy described by lot sizes into a workable schedule. 3.2 Notation The following definitions (some of which are repeated from Chapter 2) are collected here for convenience. Chapter 3. Finite Production Rate 79 F i g u r e 3.1: Example of an assembly system. G(N, A) is a network with node set N = {1, • • •, n}, the facilities, and arc set A. Prod-uct i is the output of facility i. Arc (i,j) G A means that facility j uses the output of facility i directly. The network is an A s s e m b l y S y s t e m , if for each node i ^ 1, there is exactly one arc G A. The corresponding graph is a directed tree, where each node (facility), except the final facility, is the tail of exactly one arc. s(i) is the unique i m m e d i a t e successor of facility i. We assume that i > s(i) for each i, and s(l) = 0 and 1 is the final facility. S(i) is the set of all the successors of facility i. Product i will be used by all facilities j G S(i). Let S(i) = S(i) U{&'}-p(i) is the set of all i m m e d i a t e predecessors of facility i. P(i) is the set of all the predecessors of facility i. Let P{i) = P(i)\J{i}. is the unique (directed) p a t h from i to j G S(i) in G(N, A). R is the set of all the paths in the assembly system. Clearly, \R\ < (")• F ° r convenience, let k G {i,j) mean that node k is on the path (allowing k = i and k = j). A path finishing at faci l i ty! will be termed a route . The length of path (i,j) is the number of nodes in path {i,j), including i and j. We have S(i) = (s(i), 1) and S(i) = (i, 1) for all i. Chapter 3. Finite Production Rate 80 •Ki is the production rate of facility i, in the units of output of facility i per time unit. We are assuming that TT{ > irs^y The demand rate at facility 1 is denoted 7r 0. Without loss of generality, we can assume that one unit of product i, the output of facility i, is needed to produce one unit of product s(i). Ki is the set-up cost of facility i. It is incurred whenever facility i starts producing. h'i is the actual holding cost rate of product i. The echelon holding cost rate h{ of product i reflects the "added" value at facility i: hi = h'i — Z)jep(») ^ j - ^ 1S assumed that hi > 0, for all i. h{u,v) = [hi\i £ (u,v)) is the holding cost rate vector on path (u,v). The holding cost rate vector on set N is hN = (h{\i E TV). The pseudo-holding cost rate of product i at facility j is Hij = w0hi/2 (l/7rs(j) — I/KJ). Ij is the actual inventory level of product i at facility i at instant t. It is the cumulative output of facility i that has not yet been used by facility s(i). (u,v) is the path echelon inventory of any product k e P{u) on path (u, v) at in-stant t. Indeed, E^uv^ = J2ie(u,v) independent of product k. For an integer-ratio lot size policy, the average path echelon inventory (of product k G P(u)) on H{u,v)(h(u,v)) = hiE^^ is the total holding cost on path (u,v) at instant t, i£(u,v) using echelon holding cost rate h(u<vy The total holding cost on graph G(N,A) at ins tan t t u s ing echelon h o l d i n g cost ra te h^ is H^h^) = ] P hjE^y N* is the set of pos i t i ve integers: N* = {1,2, • • •}. Z is the set of integers: Z = {0, ± 1 , ± 2 , • • •}. Chapter 3. Finite Production Rate 81 3.3 Properties of Finite Horizon Optimal Policies First, observe that optimal policies exist for any finite horizon: there exists a policy with bounded total cost; any policy with cost not exceeding that one must contain a bounded number of setups; such policies form a compact set; and therefore an optimal policy exists. As we mentioned before, we will focus on assembly systems with non-increasing pro-duction rates. Some elementary properties of optimal policies over a finite horizon are listed below. Lemma 3.3.1 (Production Starting Time) For an optimal policy, a facility i will not start producing at instant t unless facility s(i) is (or starts) producing at instant t, and the actual inventory I\ of facility i is zero. Proof. By contradiction, if facility i starts producing with a non-zero inventory If, or during the idle time of facility s(i), then facility i can delay its starting time while still meeting the demand from facility s(i). Because 7r,- > irs(i), no extra inventory has to build before facility s(i) starts producing. The effect on the holding cost of this new policy is that the inventory at facility i is reduced by some amount AIj during a time interval [^1,^2)5 a n d the inventory at each facility j £ p{i) is increased by the same amount Alj. The total change in holding cost is This contradicts the optimality of the policy. • Lemma 3.3.2 (Zero Final Inventory Property) Any optimal finite horizon policy over the interval [0,T) has zero final inventories: if = 0, for all i. Chapter 3. Finite Production Rate 82 Proof. S i m i l a r to tha t of L e m m a 3.3.1 w i t h t2 =T. • If the h o r i z o n T > 0 is large enough , costs associa ted w i t h non-zero i n i t i a l inventor ies have a v a n i s h i n g effect o n long - run average costs a n d the zero f ina l i nven to ry p rope r ty holds for any i n i t i a l inventor ies . Therefore , zero i n i t i a l inventor ies are assumed w i t h o u t loss of general i ty . Corollary 3.3.3 (Proportion of Working Time) Let Wi be the total working time of facility i over the interval [0,T). For any optimal finite horizon policy over the interval [0, T) with zero initial inventories, the proportions of working time satisfy - f = A for all ieN. (3.1) 1 7T; Proof. F o r o p t i m a l f in i te h o r i z o n po l ic ies , o n l y the amoun t 7TjW,- is needed to satisfy the t o t a l d e m a n d ir0T over the in t e rva l [0,T). • 3.4 Integer-Ratio Lot Size Policies In th i s sec t ion , we define in t ege r - r a t io lot size a n d p o w e r - o f - t w o lo t size po l i c ies . L e m m a 3.4.1 l i s ts some bas ic p roper t ies of i n t ege r - r a t io lo t size po l i c ies . T h e n we derive a f o r m u l a t i o n of average route echelon inventor ies for i n t ege r - r a t i o lo t size po l i c ies . T h i s is achieved first for a spec ia l s i t u a t i o n i n L e m m a 3.4.2, a n d t h e n ex t ended to the general case i n T h e o r e m 3.4.3. F i n a l l y , L e m m a 3.4.4 gives a non- l inear m i x e d integer p r o g r a m -m i n g f o r m u l a t i o n for m i n i m i z i n g the average cost of in t ege r - r a t io lot size po l i c ies . R e c a l l the a s s u m p t i o n tha t a l l i n i t i a l inventor ies are zero. A n Integer-Ratio Lot Size Policy ( IRLSP) is a p o l i c y w h i c h satisfies: Chapter 3. Finite Production Rate 83 Figure 3.2: Path (u,v). (u,v) 1. for each facility u £ N, the lot size Qu is stationary; 2. for each pair of facilities u £ N and v £ S(u), either Qu/Qv or Qv/Qu £ -/V*; 3. each facility u £ TV starts producing at instant £ iff its actual inventory Pu is zero and its immediate successor s(u) already produces or starts producing at instant t; 4. all the facilities start producing at instant t = 0. A Power-of-Two Lot Size Policy (PoTLSP) is an integer-ratio lot size policy with each lot size Qi (i £ N) of the form Qi = Qo2m' for some positive base lot size Q0, where m,- £ Z = {0, ± 1 , ± 2 , • • •}, the set of integers. We list the following facts about integer-ratio lot size policies without proof. Lemma 3.4.1 (Production Runs on a Path) For any integer-ratio lot size policy, suppose Qi = max Qj is the maximum lot size on path (u, v), then 1. Each time facility i starts producing, so does each facility j £ (u,v). 2. Each facility j £ (u,i) produces only when facility i does. We first give a formula for average route echelon inventory in a special situation. Chapter 3. Finite Production Rate 84 Figure 3.3: Cumulated Path Echelon Inventory on path (u,v). p t 7T« — Ks(v) S { V ) (1 -1 time Lemma 3.4.2 (Average Route Echelon Inventory - A Special Case) For any integer-ratio lot size policy, if Qu > Qj-i for all j E (u,v), and then 1 1 1 77710 I J Qu, 1 fT (3-2) (3.3) (3.4) where E(UjV) = l iminf — J E^u^ dt is the average path echelon inventory on path (u,v) for an integer-ratio lot size policy, and Qo = Q A n max — max j . Note that if v = u, then (3.2) always holds. And if v — 1, then (3.3) always holds. Proof. For any integer-ratio lot size policy, (3.3) means Qs(v)/Qu = m E TV*, that is, facility u makes ra lots over the time interval that facility s(v) is making one lot Qs(v). Combining with condition (3.2), this means that the path echelon inventory E^uv^ has a saw-tooth shape when each lot Qu is producing, as shown in Figure 3.3. From this figure, it is not difficult to compute the cumulated path echelon inventory Chapter 3. Finite Production Rate 85 of (u,v) for each lot Qu: S(Qu,iru,^a(v)) = 77 ( ) Ql-Because an integer-ratio lot size policy is a periodic policy, there is a finite regeneration instant T of the system such that all the inventories in the system will be zero at instant T. By Corollary 3.3.3, W3(v)/T = 7r0/7r,,(„). Observe that the average path echelon inventory over the working time Ws(v) of facility s(v) is S(Qu,Tru,ns^)/(Qu/TTs^). Therefore, the average path echelon inventory of (u, v) on the entire horizon [0, T) is g _ S(QU,1Tu,Trs(v)) Ws(v) _ S(QU,TU,TTS(V)) 7 T 0 _ 1 / 1 1_ ^ Qu/^s(v) T Qul^s(v) ^s(v) 2 ° \ 7 T S ( „ ) 7 T „ This completes the proof. • More intuitively, to be optimal on a finite horizon, each lot Qu has to be used up over a time interval of length Qu/ivo in order to meet the constant demand rate TT0. Therefore the average path echelon inventory of (u^) is S(Qu,iru,Trs(v)) 1 / 1 1 \ &(u,v) = = XTTO The following theorem extends the formula of average route echelon inventory to a general situation. Theorem 3.4.3 (Average Route Echelon Inventory - the General Case) For an integer-ratio lot size policy, the average route echelon inventory on (u, 1) is E{u,i) = HQ;u,l), for all u <= N, (3.5) where $(Q;u,v) = \-K0 V J — — J max Qt. 2 ke{u,v) VM*) /e<u-*> Chapter 3. Finite Production Rate 86 Proof. We prove it by induction on |(u, 1)|, the length of (u, 1). 1. For |(u, = we have u = 1. By Lemma 3.4.2 (with u = v — 1), (3.5) holds. 2. Suppose (3.5) holds for 1)| < £. We show that (3.5) holds for 1)| = £ + 1. There are two cases: 2.1 Qu < Qs(u) By Lemma 3.4.2 (with u = v), the average inventory of product u is T? 1 ( 1 1 \ ^ E(u,u) = - 7 T 0 — Qu-2 \Trs(u) -Kn) Therefore, the average echelon inventory i?(u,i) o n route (u,l) is, by induction, E(u,i) = -£(«,«) + E(s(u)ti) = ^ * o [ — - — )Qu + $(Q-,s{u),i) 2 \^s(u) TTu/ = 7^0 ( — " J Qu + j^O J2 \— J . ™,a* Ql-Using Q u < Q s(„) and noting $(Q;u,v) = ^ 7 T 0 V) (— — ) max C^, £<u,l> = ^ o f - ^ ^-}Qu + \*Q £ f - ^ 2 V^(«) * V 2 fc€<a(u)il) \^s(k) ^ max Qn 2.2. Qu > Qs(u) Let i £ (^(w), 1) be the facility such that Q u > Qj for all j £ (,s(u),z), and (5« < Qs(i')) (where Qs(i) = maxQj)- If i ^ 1, then ,s(i) is the first facility on route (s(u), 1) such that Qu < Q5(i). See Figure 3.4. It is easy to check that the conditions in Lemma 3.4.2 hold on path (u,i). They also hold trivially if i = 1. Therefore, the average path echelon inventory on (u,i) is Chapter 3. Finite Production Rate 87 Figure 3.4: Route (u, 1) is divided into path (u,i) and route (s(i),l) <«»*) M O * 1 ) = -7r0 ^ ( ] max By induction on path (s(i), 1), we have = I W o ( ' J - - J - , ) Q u + *(g; a(,-),i) = TWO ( — — ) max Qe z ke(s(i),i) VM*) 1 1 • n max = - 7 T o V] ( ] max Qi 2 *eK.-)W*) 1 / 1 1 \ + 777ro V max 2 *€(.(0,i> W*) 1 V- ( 1 M n = -7r0 > max Qi = *(<?;«, l). In summary, (3.5) holds for |(u, 1)| = I + 1. This completes the proof. Q The following lemma on minimum average cost follows immediately. L e m m a 3.4.4 ( M i n i m u m Average Cost) The minimum average cost C of integer-ratio lot size policies results from the following Chapter 3. Finite Production Rate 88 mixed nonlinear integer programming problem (P), mm "A"Y2 \ 7T7 1" hXna V ( — — ) max Qt \ , (3.6a) s.t. Qi > 0, /or a// i G TV, (3.6b) or ^ G TV*, for all ti G TV, and i> G S(u). (3.6c) A continuous relaxation (RP) to (P) yields the lower bound C* on the average cost of an integer-ratio lot size policy: C* — min i ——y h hi—irn ( ) max Qp \ , (3.7) s.t. (3.66). 3.5 Lower Bound Theorem In this section, the Lower Bound Theorem (Theorem 3.5.6) shows that C* is not only a lower bound on the average cost for integer-ratio lot size policies but also a lower bound on the average cost for all feasible policies. This main result of the chapter is built upon a series of lemmas as follows. A lower bound on average path echelon inventory, which is based on average lot sizes, is given below. Lemma 3.5.1 (Lower Bound on Average Path Echelon Inventory) For any feasible policy over the interval [0,T) and any path (u,v), the average path echelon inventory satisfies ?/o^>^H4-y^ (3-8) where Qu = 7 r 0 r / n „ is the average lot size of product u over the interval [0,T), and nu is the number of lots over the interval [0,T). Chapter 3. Finite Production Rate Table 3.1: Slopes of the path echelon inventory level 89 case # status of s(v) status of u slope of E\uv) 1 Working Working 7T« — Ts(ti) 2 Working Idle — *s(v) 3 Idle Working 4 Idle Idle 0 Proof. For any feasible policy and any instant t, there are four possible cases for the slope of E\uv): Figure 3.5 on page 91 shows an example of inventory level E^uv^ on path (u,v). It shows that the cumulated path echelon inventory on (u,v) over the interval [0,T). Its total area is no less the area of cases 1 and 2, i.e., during the working time Ws^ of facility s{y). The area of cases 1 and 2 is shown under the thick lines in Figure 3.5 (A) and (B). During the idle times (cases 3 and 4) of facility s(v), there is no demand on path (u, v), i.e., the slope of E^uv^ is non-negative. Therefore the inventory level of E^uv^ before any idle time will be no less than that after the idle time. The total inventory on path (u, v) will be no less than the total inventory of nu saw-tooth areas over time interval Ws<v) with up-slope TTU — TS(V) and down-slope — ws(v), a s shown in Figure 3.5 (C). By convexity, this area is no less than that of nu equally spaced triangles, each with the base line length Ws'v)/nu. Hence we have * r l ( — - L ) — (By Corollary 3.3.3) • Chapter 3. Finite Production Rate 90 Figure 3.5: Illustrating the proof of Lemma 3.5.1 -— facility u produces four lots over the time interval [0,T). E^uv) (B) The cumulated echelon inventory is no less than the total area of cases 1 and 2: ^u—^s(v) j \ Case# : 1 ;2; 1 1 2 [2:1 2 1 2 time W. s(v) E{u v) ^ n e c u m u i a t e ( i echelon inventory is no less than four saw-tooth areas over time interval W3(vy. Case# : 1 |2; 1 ;1 2 |2;1 2 1 2 time w, (v) Chapter 3. Finite Production Rate 91 The next Lemma shows that path holding costs can be rewritten in a recursive form which is needed later. L e m m a 3.5.2 ( D e c o m p o s i t i o n of P a t h H o l d i n g Costs ) Let H^uv^{h^v)) = ^2 hjE(j,v) be the total holding cost on path (u,v) at instant t with echelon holding cost rate h(UtVy Let path (u,v) be decomposed as (u,v) = ((u,i), (s(i),v)), then H(u v)(h(UtV)) can be decomposed as h»E(u,i) + Hl(u),i)(.h(s(u),i)) + H{s(i),v)(ti{s(i)!V)), if if^v (u,v) where H{u,v)(h{u,v)) = < (3-9) huE\UiV) + Hls(u)tV)(h(s(u),v)), if i = v, K(i) = hs(i) + J2 hi-> je(«,«> h'(s{i),v) = (K(i),h{s{s{i))tV)). Proof Note that H(u,v)(h(u,v)) = Yl hiEU,v) = J2 hiIi, j€(u,v) j€(u,v) ke{j,v) i.e., H^u „ ) ( ^ ( u , v ) ) is the sum of the values of all the blocks in Figure 3.6 on page 93. The value of each block is the product of the vertical label and the horizontal label. Thus (3.9) is just another way to calculate the total value of R~\uv){h(u,v)). • The following main lemma estimates the average path holding cost based on average lot sizes by using two lemmas above. L e m m a 3.5.3 (Lower B o u n d on A v e r a g e P a t h H o l d i n g Cost s ) 1 rT •I H\u>v)(h{u,v))dt > J2 h3$(Q;j,v) = E h3K0 J2 [zr—-z~)j^t.Qt- (3-10) Chapter 3. Finite Production Rate 92 Figure 3.6: Illustrating the proof of Lemma 3.5.2 — decomposition of the path echelon holding cost on (u,v). p u P p p n hs(u) / / \ H ( s ( U ) 4 ) ( h < B ( u ) , i > h{ hs(i) / H ( s ( i ) , v ) ( h ( ' s ( i ) . v > ) K Proof. We prove it by induction on |(u,t»)|, the length of path (u,v). 1. For |(u,t>)| = 1, we have u = v. By definition, Hl(hu) = huE\. By Lemma 3.5.1, LfTHl(hu)dt > h ^ 0 ( — - — ) ^ u = hi^(Q-,u,u), that is, (3.10) holds. 2. Suppose (3.10) holds for \(u,v)\ < £. We show that (3.10) also holds for |(w,t;)| = £+1. There are two cases to be considered, 2.1. If there exists i G (u,v) such that Qs^ > Qu and Qu > Qj for all j G (s(u),i), then path (u, v) can be divided into two subpaths (u, v) = ((u, z), (s(i), v)), see Figure 3.7. By Lemma 3.5.2, we have 1 fT t1 j, Jo H(u,v){h(u,v)) dt F t 1 fT t 1 fT t J h u E\u,i) d t + f Jo H(s(u),i)(h(s(u),i)) dt + — H{s(i)tv){h{s(i),v))dt-f Chapter 3. Finite Production Rate 93 Figure 3.7: Path (u,v) is divided into path (u,i) and path (s(i),v) By Lemma 3.5.1, we have where Because \(s(u),i)\ < £, and \(s(i),v)\ < £, we have, by induction, the following two inequalities, 1 I-T T T Jo HUu)Mh<s(u)^ d t -and 1 rT where ^2 = E ^ J ' O ^ O E I " ~ —) max Q E , i€(.(u),.-> 2 f c € ( j , « > V ^ * ) ""*/ <€<j,fc> ^ 3 = E hi\*° E (V j€(s(i),v) 2 ke(j,v) \ n s ( k ) ( ^ > k ) A 4 = I h3) E (— -) m a x \j€(u,i) J 2 ke(s(t),v)\n^) te{s(i),k) Chapter 3. Finite Production Rate 94 That is, the LHS of (3.10) > A 1 + A 2 + A 3 + A 4 . However, the RHS of (3.10) can be rewritten as, E h i \ ^ E \ — - — ) ? l ^ Q t = B1 + B2 + B3 + B4 + B5, where Bi = hJ-Ko (— ~ " L m a ? v & ' -02 = u^^TTO E ( "~~ ~ I m a X Qli ^3 = E ^-.^o E (— ~).m/^ <^' i6<.(«),.-> 2 *€<*> VM*) **/ <6<*fc> B* = E E (:r ~) B^^> JBS = hj—TTo I I max Q,. It is easy to check that A x = v42 = B3, and A 3 = B5. As for i? 2 a n d B4, because k E (s(i),v), we have s(i) E (u,k) and > Q,-, for all j E Thus, we get max Q, = max Q, = max Q,. Hence, ie{u,k)^' ee{j,k) te(s(i),k) ' B2 + B4 = hj-Tv0 y^ ( j max Q, = A 4 . That is, A i + A 2 + A 3 + A 4 = Bx + 5 2 + B3 + J34 + Bs, i.e., (3.10) holds in this case. 2.2. If there is no such i E (u,v), that is, Q„ > Qj for all j E (s(u),v), then f Jo H\u,v){h{u,v))dt - — huE\u<v)dt +— J H\s(u)tV)(h(s{u),v)) dt. Because 1 f T l / l 1 \ — — / huE\v)dt > hu-ir0[ Qu (by Lemma 3.5.1) 1 Jo I \Ks(v) TT«/ Chapter 3. Finite Production Rate 95 2 k^u,v) \*>W 1 1 1 "7=r and by induction, 1 /-X y ^ H(s(u),V){h(s(u),v)) dt — X] hj -Ko Y2 \ ) m a X Qli je{s(u),v) 2 fe€(j» VM*) 'e<j,fc> (3.10) also holds in this case. In summary, (3.10) holds for = £ + 1. This completes the proof. • A l l results so far have concerned paths. They are now generalized to assembly systems. The following Lemma describes an allocation of the given echelon holding costs to so-called leaf-routes, that is, routes from the leaf-nodes to the root of the assembly system. Lemma 3.5.4 (Holding Costs Allocation in Assembly Systems) Let Z = • • •, iq} be the set of all leaves (facilities with no predecessors) in the assembly system. Call (ie,l), for all £ = l,---,q, the leaf-routes of the assembly system. Let HQ^N) = E hjE^j xj be the total holding cost on graph G(N, A) at instant t with echelon jeN holding cost rate hj^. Define hj, if j e for £ e-i h3, if je(ie,l)\ U ( * * , l ) , for 1 = 2, k=i 0, otherwise. as the leaf-route-allocated holding cost rate on (i(,l). And let hl = {h]\j e (itil)) Chapter 3. Finite Production Rate 96 Figure 3.8: Illustrating the proof of Lemma 3.5.4 — assembly system G(N, A) is partitioned into leaf-routes. be the leaf-route-allocated holding cost rate vector on (ii, 1). Then the total holding cost at instant t on the assembly system is the sum of holding costs at instant t on all leaf-routes with leaf-route-allocated holding cost rate vector he, i.e., Proof. By the definition of H Q ^ N ) , and noting that hj = ^2 ^ j ' w e have: Hh{hN) = £ h ] E \ h l ) = E E = E E = E *U(* ' ) . This completes the proof. • The lower bound lemma on average holding costs can now be extended from paths (Lemma 3.5.3) to assembly systems: Chapter 3. Finite Production Rate 97 Lemma 3.5.5 (Lower Bound on Average Holding Cost for Assembly Systems) ± [ T B & h r f d t > Y h i * ( Q ; J , i ) = E ^ 0 E r T S ^ ^ ( 3 - 1 2 ) Proof. We prove it by induction on the number of leaves. 1. For \L\ = 1, (3.12) holds by Lemma 3.5.3 with G = (n, 1). 2. Suppose (3.12) holds for \L\ = q, we show that (3.12) also holds for \L\ = q + 1. By Lemma 3.5.4 and the notation defined there, -JQ H ^ d t = -JQ HtG,{hN,)dt+-JQ Hliq+Ul)(h^)dt. By induction, ^ / H^ihN^dt > Yl hj\*° E (—— — i F i ^ Q f By Lemma 3.5.3, r = E h - 7 T 0 E (~~ ~~) max Q^. i e W 2 fceOM) ' € < i , f c > Combining these two inequalities, we conclude that (3.12) also holds for \L\ = q +1. This completes the proof. • The Lower Bound Theorem below, one of the key results in this chapter, now follows directly from Lemma 3.5.5: Theorem 3.5.6 (Lower Bound Theorem) For any feasible policy, the long run average cost Chapter 3. Finite Production Rate 98 7^+ * f &Q(*N) (3.13) That is, the optimal value of continuous relaxation for integer-ratio lot size policies is also the lower bound on the average cost of all feasible policies. Proof. For any feasible policy over the interval [0,T), the average total set-up cost is ZweAr KiTii/T = YlieN Ki/iQi/xo)- By Lemma 3.5.5, the average cost over the interval [0,T) is £ KiKQjiro) + UT HUhN) dt>Yl I<i/(Qi/*o) + £ h^(Q; i, 1). ieN 1 J 0 ieN ieN Therefore, by the definition of C*, the long run average total cost = liminf < £ H ™ / HQUIN) dt\ > C*. T^°° Kf&iQil'Ko T Jo J This completes the proof. • 3.6 Effectiveness of Integer-Ratio and Power-of-Two Lot Size Policies Given an optimal solution Q* = (Q\, - • • ,Q*n) to the continuous relaxation (RP), an Order-Preserving Solution Q = (Q\, • • •, Qn) is an integer-ratio lot size policy to problem (P) such that Qi = Qj (resp., Qi < QJ; resp., Qi > Qj), whenever Q* = Q* (resp., Q* < Q*; resp., Q* > Q*), for all i, j G N. The following Lemma repeats the result in Roundy [27] (1983), and we state it without proof. Lemma 3.6.1 (Effectiveness of an Order—Preserving Policy) If Q is an order-preserving integer-ratio lot size solution to (P), then cm . . (Qi\ > min e —— , C(Q) ~ ieN \Q*)> Chapter 3. Finite Production Rate 99 where e(q) = —2 , . V^Y Q + L/Q The next Rounding Lemma repeats the result in Roundy [27] (1983), and we state it again without proof. Lemma 3.6.2 (Rounding Lemma) If Q* is an optimal solution to the continuous relaxation (RP) and Q is defined by Qi = Q02mi, • for all i 6 N, m, = [log2(Q*/Q0)+ l/2\, then Q is an optimal power-of-two lot size solution to (P) for a given positive lot size Q0. Using these two Lemmas, we can get the following two effectiveness theorems, which are proved in Roundy [27] (1983). The effectiveness of a policy, also defined in [27] (1983), is the ratio of the infimum of the average cost over all policies to the average cost of the policy in question. Theorem 3.6.3 (94%-Effectiveness Theorem) For every fixed Q0 > 0 there exists an optimal power-of-two lot size policy with base lot size Q0, whose effectiveness is at least 9 4%. Theorem 3.6.4 (98%-Effectiveness Theorem) There exists an optimal power-of-two lot size policy with base lot size-Q^ in the interval [v^5, \/2], whose effectiveness is at least 98%. 3.7 Finding Optimal Power—of—Two Lot Size Policies We sincerely thank Roundy for suggesting the following method, which cuts down the 0(n5) running time of our original algorithm to 0(n 3 logn) for the new algorithm ob-tained below. Chapter 3. Finite Production Rate 100 First, we rewrite the original relaxation problem (RP) to a new equivalent prob-lem (RPi). Then, we present a mapping from this model to the model presented in Roundy [31] (1987). Finally, we show an algorithm solving the original problem in 0 ( n 3 logrc). L e m m a 3.7.1 (Equivalent Formulat ion) Problem (RP): C* = max f(Q) £ £ Q ieN s.t. Qi > 0 Qi/vo + £ HiJ m a X ee(i,j) VieN is equivalent to problem (RPi): C; = max fi(q) = J2 ieN s.t. qij>0 V{i,j)eR, (3.14a) 9ij<%sU) V (i,s(j)) G R, (3.14b) qn > Qs(i),j V (s(i)J) G R, (3.14c) where R is the set of all paths in G(N, A). Proof. Suppose that Q — (Qi, • • •, Qn) is a feasible solution to (RP). Let qij = maxQ/ , V (i,j) G R. (3.15) Then inequalities (3.14a),' (3.14b) and (3.14c) hold, that is., q = (qij\(i,j) G R) is also a feasible solution to (RP\). Note also that qn = Qi, V i G iV. Therefore, /i(#) = f(Q), and C* < C*. Now suppose that q is a feasible solution to (RPi). Let = 9«}V i £ N. If ^ G (i,j) G i?, then by (3.14c) ^ > qs(i)J >•••> qej, and by (3.14b) qu < qeAe) <•• < qtj. — + £ W T O I 6 < I I L ) Chapter 3. Finite Production Rate 101 Therefore, Qe = qu < ?,-j,V £ £ (i, j), and max Qe < q{j. Hence, f(Q) < fx(q), and te(t,j) c* < ci This implies C* = Cx, i.e., problem (RP) is equivalent to problem (RPX). • Let G(N\,Ai) be a network corresponding to problem (RPX): M = {«i,3(i)>,<i,j»l<f,«Ci)> e -«}U{««,j>,<*(0,i»IW0,i> e }^ Let D = max |(^, 1)| be the length of a longest leaf-route in G(N, A), where L is the set of all leaves. Let G(N', A') be the series system with node set N' = {0,1,2, • • •, D — 1} and arc set A' = {(i,i - l)\i = 1, 2, • • •, D - 1}. Let G(A^2, ^2) be a graph defined by 7Y2 = {(i,k)\ieN, k = 0,1,2, A 2 i {((», k)) \s(i) G TV, fc = 0,1, 2, • • •, D - 1} U{((i,fc),'(*,fc-l»|ie/Y,A: = l , 2 , . . - , D - l } The problem of minimizing the relaxed average cost of a nested policy on this network can be solved in 0(\R\D log \R\) time, by the algorithm in Roundy [31] (1987). Note that \R\ < n(n - l ) /2 and D < n, so 0(\R\Dlog \R\) < O(n3logn). The way to embed G(Ni,Ax) into G(N2, A2) is as follows: node (i,j) £ Nx —* node (i,k) G N2, with k = D-Note that if k < D — 1 — | ( i , l ) | then node (i, k) G N2 has no corresponding node (i,j) £ Nx. In that case, we set K(itk) — 0 and h(i<k) = 0 so that it does not effect the final solution. After embedding G(NX, Ax) into G(N2, A2), the problem can be solved on (2(^2, A 2 ) and the solution to our problem can be extracted. The number of nodes and arcs in G(N2,A2) is at most twice the number of nodes and arcs, respectively, in either G(NX,AX) or G(N',A'). Chapter 3. Finite Production Rate 102 The algorithm for finding an optimal power-of-two lot size policy consists of two stages: Stage 1 Solve relaxation (RP) in 0(|jRjZ?log 1^1) < 0 (n 3 logn) , by using the algorithm above suggested by Roundy. Stage 2 Using the "Rounding Lemma" with the complexity of 0(n log n), generate an opti-mal power-of-two solution to (P), with at least 94% effectiveness, from a solution to (RP) for a fixed base lot size Q0. Using Roundy's method in [27] (1983), de-rive an optimal base lot size Q0 and a corresponding optimal power-of-two lot size policy, which has at least 98% effectiveness. E x a m p l e . The following example of an assembly system G(N, A) in Figure 3.9 with 7 facilities illustrates the embedding procedure. The length of the longest leaf-route, which corresponds to a series network G(N', A') in Figure 3.10, is four. Graph G(Ni, A\) in Figure 3.11 is a network corresponding to problem (RPi), and is embedded in graph G(N2, A2) in Figure 3.12, which is the Cartesian product of graph G(N,A) and graph G(N',A'). Chapter 3. Finite Production Rate 103 Figure 3.9: Graph G(N, A) Figure 3.10: Graph G(N', A') 0 <D ® 0 Chapter 3. Finite Production Rate 104 Chapter 3. Finite Production Rate 105 Figure 3.12: Graph G(N2,A2) = G(N, A) x G(N',A') Chapter 3. Finite Production Rate 106 3.8 Conclusions This chapter has considered a lot-sizing problem in an assembly system with finite pro-duction rates. A key assumption is that the production rates are non-increasing along any path in the system. We show that the best integer-split policy defined by Schwarz and Schrage [34] (1975) and the best integer-multiple policy defined by Moily [20] (1986) can be arbitrarily bad in Section 3.9.1. To overcome this difficulty, we introduced a class of integer-ratio lot size policies. The non-increasing production rates assumption allows us to formulate the problem of finding a minimum cost integer-ratio lot size policy as a mixed nonlinear integer programming problem. A continuous relaxation of this for-mulation yields a lower bound on the cost of any feasible policy. The derivation of this Lower Bound Theorem is novel, and relies on the concept of path holding costs, which is a generalization of echelon holding costs. Using the methods introduced by Roundy ([27] (1983) and [30] (1986)), we then construct an optimal power-of-two integer-ratio lot size policy with cost within 2% of the lower bound. Following a suggestion from Roundy, this policy is found by a 0(n 3 logn) algorithm. The results in this chapter have several possible implications. First, it demonstrates that when studying production systems, one should not restrict attention to overly sim-plified classes of policies (here, integer-split and integer-multiple lot size policies) unless they can be proven optimal or near-optimal. Second, we have shown that the class of power-of-two policies introduced by Roundy extends to finite production rate systems, provided we consider lot sizes, instead of reorder intervals as in Roundy's original work. Third, this class of power-of-two lot size policies is a class of well-structured, provably very near-optimal and implementable policies which can be determined in polynomial time. Further directions for research may include relaxing the non-increasing production Chapter 3. Finite Production Rate 107 Figure 3.13: Three facilities in series rate assumption, and studying other production networks such as distribution systems, and general acyclic networks. Research along these lines is being undertaken. 3.9 Appendix to Chapter 3 3.9.1 Effectiveness of Integer-Multiple and Integer-Split Lot Size Policies From the analysis of integer-multiple lot size policies in Crowston, Wagner, and Hen-shaw [6] (1972) and integer-split lot size policies in Moily [19] (1982) and [20] (1986), it can be shown that either class of policies may be arbitrarily worse than the other, depending on the ratio of setup costs to holding cost rates. The example below shows that both classes of policies can simultaneously be arbitrarily worse than integer-ratio lot size policies. The system has 3 facilities in a series, see Figure 3.13. The parameters are K\ = 16m 2, K2 — 4, Kz = 8m 2 , h\ = 2 , h2 = 8m 2 , h3 = 2, 7 T 0 = 1, TTI = (16m2 + 8)/(16m 2 + 7), TT2 = (16m2 + 8)/(12m 2 + 5), TT3 = (16m2 + 8)/(8m 2 + 3), where m is a positive integer, large enough for our purpose — see below. Consider the following three classes of policies (policies in 1 are integer-multiple lot size policies, in 2 are integer-split lot size policies, and in 3 are integer-ratio lot size policies): 1. Integer-multiple lot size policies, see Crowston, Wagner, and Henshaw [6] (1972). Using actual inventory, and noting that 1/TT0 — = l / (16m 2 + 8), l/iri — lfn2 = Chapter 3. Finite Production Rate 108 Figure 3.14: Network corresponding to the constraints of the 3-facility problem 1/4, l / 7 r 2 — I / V 3 = 1/4, the cost of an integer-ratio lot size policy Q is: CIMLSP(Q) Kx K2 K3 1., , . / 1 1 \ 16m 2 4 8m 2 1 / 2 1\ ^ 1 Q i Q2 Q3 4 V 4/ 4 The Minimum Violators Algorithm of Roundy [27] (1983) will solve the following con-tinuous relaxation mm CIMLSP{Q) s.t. Q3<Q.2< Qi, and produce a lower bound of for this class of policies. The algorithm uses a graph in Figure 3.14, which is the reverse of the production graph. At the beginning of the algorithm, each group has one element, and ^ > _ 1 6 m ^ _ 2 I<W _ 4 ^ ! l _ ^ ! _ o 9 2 hW ~ 1/4 ' hW ~ m 2 + l / 4 ' fcW - 1/4 - 3 2 m • For m > 1, K&t/hW is the smallest ratio and 5(2) = 3. Therefore we collapse set {2} into set {3} and have I<W _ 8m 2 + 4 /if 2- 3) ~ m2 + 1/4 + 1/4 ~ ' Because K ^ / h ^ < K^/h^, the partition {{1}, {2,3}} is optimal. Therefore, Chapter 3. Finite Production Rate 109 and a lower bound on the average cost of integer-multiple lot size policies is, CJMLSP = CIMLSP(Q*) = 2 (7l6m2 x 1/4 + ^/(Sm 2 + 4)(m 2 + 1/4 + 1/4)) = 2 2m + \/2(2m 2 + 1)1 = 0(m 2 ) . 2. Integer-split lot size policies, see Moily [19] (1982) and [20] (1986). Using echelon inventories, the cost of an integer-split lot size policy Q is: min CISLSp(Q) Kl I<2 I<3 Qi 0.2 Q3 4 ^ ( l - l ) g 1 + k ( l _ l ) g a + h 8 ( l - l ) ( ? , 2 \ 7 T 0 7T! / 2 \ 7 r 0 7 T 2 / 2 V 7 r 0 7 T 3 / 16m 2 _4_ 8m^ 1 m 2 (4m 2 + 3) 8m 2 + 5 " Q i + ^ + " g 3 " + 1 6 m 2 + 8 g i + 4m 2 + 2 g 2 + 1 6 m 2 + 8 g 3 ' The same Minimum Violators Algorithm will solve the following continuous relaxation mm CISLSP{Q) s.t. Q 3 > Q 2 > Q U and produce a lower bound for this class of policies. The algorithm uses a graph which is the same as the production graph. At the beginning of the algorithm, each group has one element, and KM 16m 2 , , W = l / 8 ( 2 m 2 - M ) = 1 0 8 ( m K&_ _ 8(2m 2 4- 1) hW ~ m 2 (4m 2 + 3)/2(2m 2 + 1) ~ m 2 (4m 2 + 3)' _ 8m* 64m 2(2m 2 + 1) ~ (8m 2 + 5)/8(2m 2 + 1) ~ 8m 2 + 5 For m > 1, K^2}/h^ is the smallest ratio and s{2) = 1. Therefore we collapse set {2} into set {1} and have K^V _ 16m 2 + 4 hi1*) ~ l /8(2m 2 + 1)+ m 2 ( 4 m 2 + 3)/2(2m 2 + 1) Chapter 3. Finite Production Rate 110 ' 4(4m 2 + l) 1 + 12m2 + 16m 4/8(2m 2 + 1) 32(4m2 + 1) 16m 4 + 12m 2 + l' If m is large enough, then K ^ / h ^ < K^/h^\ and the partition {{1,2}, {3}} is optimal. Therefore, n* - n* - lK{h2} - A I 2 ( 4 ^ 2 + 1) n* _ P { 3 } _ « /2m 2 + 1 V i - w 2 - y fc{li2} - 4y 1 6 m 4 + 1 2 m 2 + r g 3 - y fc{3} - s m y - ^ - ^ , and a lower bound on the average cost of integer-split lot size policies is, = 2 = 2 A(A 2 , ..,16m 4 + 12m 2 + 1 «m 2 + 5 \| ^ + 1 } 8(2m2 + l) + \| 8 m 872^TT) = 0(m 2 ) . V2 Mm^ + l , „ A n „ x / 8 m2 + 5 3. Integer-ratio lot size policies. Using the results in this chapter, the cost of an integer-ratio lot size policy Q is: CIRLSP(Q) Ki K2 Ks Qi Q2 Qs + 2 ^ {T0 -7dQl + ¥ 1, +-2h3 16m2 1_ 7!"2 7T3 4 8m 2 (---) Q2 +(-"-) 1/ * L \ 7 T I 7T 2 / \ 7 r 0 7Ti / j - ) + (- - - ) (Q3 V Q 2 ) + f - - - ) (Qs V Q2 V Qr) 7T 3 / \7Ti 7 T 2 / \ 7 r 0 7 T i / Q^2 1 r 1 T ( ^ V Q a ) + & + ~Ch + 16m2 + 8 Qi + m2 Q2 + Am2 + 2 + \Q* +1 (Qs v g 2 ) + 16J 8 (Q 3 v g 2 v go where a V 5 = max{a, 6}. Applying the algorithm in Section 3.7 yields Q2 < g 3 < g i an " ° ' " ° " 1 . „ 16m2 4 8m 2 1 - mm CIRLSP(Q) = -^- + -^- + ^ - + TQi + m2Q2-r-Q3. V 2 V3 4 ^ Q>o Chapter 3. Finite Production Rate 111 We can verify that ' ' 8m 2 16m 2 A 2 8m, g 2 = w — = — , g 3 = 4m ^ 1 / 4 y m 2 - m , v 3 - ^ 1 / 2 defines a feasible integer-ratio lot size policy and its average cost is: CIRLSP(Q*) = 2 ^ 1 6 m 2 x 1/4 + V ^ 2 + ^ 8 m 2 x 1/2^ = 12m. Therefore, CIRLSP{Q*) 12m 0, (m —> 00) m i n{ C'7MLSP.C'7SL5p} ° ( m * ) That is, the effectiveness of optimal integer-multiple and integer-split lot size policies is zero in the worst case, i.e., these two policies can be arbitrarily worse than integer-ratio lot size policies. 3.9.2 Cons t ruc t ing a P roduc t ion Schedule from Integer-Ratio Lo t Size P o l i -cies Given integer-ratio lot sizes Qi, - • • ,Qm we illustrate how to obtain a corresponding production schedule. As indicated in Section 3.3, we assume that the initial inventories at all facilities are zero. As the actual working time T( = Qi/i^i for each facility i to produce one lot is constant, specifying the starting time tu(j) of each production run j at each facility u is enough to define the production schedule. Let L == • • •, ig} be the set of all leaves (facilities without predecessors) in assembly system G(N,A), where q is the number of leaves in the system. Let Qlmax = max Qj be the maximum lot size on route je(»'*,i> (ii, 1) for all it £ L. Let re = Qemax/Qi be the maximum ratio on route (it, 1) at facility 1, and r ( l ) = lcm{r!, • • •, rq}, where lcm{r l 5 • • •, rq} denotes the least common multiple of integers r 1 ; • • •, rq. Let T = r ( l )Qi/7To be the cycle period, and r(u) = r(l)(Q1/Qu) be the number of production lots at facility u over the interval [0,T). Note that r(u) is Chapter 3. Finite Production Rate 112 an integer: suppose u G (^,1), then Q^JQu is a n integer, and therefore r(«) = 5 i r(l) = 9 l r / M = QiQL*rJ}) = Qlmaxr{l) Qu Qu re Qu Qi rt Qu re is an integer. Scheduling Algorithm in Figure 3.15 will generate a periodic production schedule. Procedure Schedule(t,v) called by Scheduling Algorithm is defined in Figure 3.16. Given schedule tv(j) over interval [0,T) at node v, Schedule(t,v) will generate a schedule for each node u in p(v), and the recursive calls Schedule(t,u) generate a schedule for each node u in P(v). Recall that [a\ denotes the largest integer less than or equal to a. Chapter 3. Finite Production Rate F i g u r e 3.15: Scheduling Algorithm I n p u t : Assembly system G(N, A) and integer-ratio lot sizesQi, • • •, Qn for all facility in TV. O u t p u t : Production run starting time tu(l),tu{2), • • • for all facilities u over the time interval [0,T). Step 1. F o r £ = 0,1, • • • , q do beg in Q m a x <- max Q3; re <- Qemax/Qi end; r ( l ) <— lcm{r!, • • •, r g } , using the Euclidean Algorithm. (If Qi, • • •, Qn is a power-of-two lot size policy solution, t h e n simply r( l ) < — maxjrx, • • • ,rq}.) Step 2. F o r u = 0,1, • • • , n do r(u) <- r(l)Qi/Qu. Step 3. F o r j = 0,1, • • • , r ( l ) - 1 do ^( j ) <- jQi/fto; Step 4. Schedule(t,l); Step 5. Stop, J'6(»/,1> F i g u r e 3.16: Procedure Schedule(t,v) beg in If p(v) = 0 then r e t u r n else for each u G p(v) do b e g i n i f > 1 then for j 0,1, • • •, r(u) - 1 do tu(j) <- t v — • ,r(w) - 1 do tu(j) <r-tv[ - + (j mod end. Chapter 3. Finite Production Rate 114 The following is a numerical example for an integer-ratio lot size policy with 6 facilities in series (See Figure 3.17). Figure 3.17: Six facilities in series Production rates 7rt- and lot sizesQ; are given in Table 3.2. Recall that T{ — Qifiti is the actual production time of facility i, r(i) = r(l)(Q1/Qi) is the number of production lots at facility i over the interval [0,T), where T = r(l)(Qi/iro) ^s the production cycle period. We have ir0 = 1, Qmax — 12, r\ — r ( l ) = 4 and T — 12. Using the "Scheduling Algorithm", we get the results in Table 3.2. Note that Q2 — max 0,, 04 = max 0,, J6(4,l) J6(4,3> and Qc, — max Qj. Three graphs of path echelon inventories are shown in Figure 3.18 je(6,i) on page 115. Table 3.2: Production starting instants and lot sizes i Qi Tl r(i) j = 0 1 2 3 4 5 6 7 8 9 10 11 1 1| 3 2| 4 0 3 6 9 2 1| 6 4| 2 0 6 3 1| 1 2 3 12 0 3 4 1| 3 4 i *2 6 ' 2 9 10| 4 2 3 1| 4 0 2i 6 5 3 12 4 1 0 6 4 6 1| 2 0 2 Chapter 3. Finite Production Rate 115 Chapter 4 Series Systems With Backlogging 4.1 Introduction In this chapter we consider the inventory model IM(S,SP,NE,IF,B), i-e., the series inven-tory model with backlogging, or more specifically: 1. The production network G(N, A) is a series system, i.e., each node has exactly one successor and one predecessor in the network G(N, A). One node without successor is the only node with external demand. One node without predecessor is the only node with external supply. Let TV = {1,2, • • • ,n} be the node set and such that the node without successor is node 1, p(i) = i + 1 if p{i) ^ 0. 2. The setup cost function is separable: K(S) = £ i v * t , V S C N. ies 3. The echelon holding cost rate hi = h'i — h'i+1 > 0 for each i 6 iV is constant and non-negative. The backlogging cost rate bi > 0 is also constant. 4. The production rate at any node is infinite. 5. The external demand is allowed to be backlogged. For the inventory model IM(S,SP,NE,IF,NB), i.e., without backlogging for the exter-nal demand, Roundy [28] (1985) has shown in more general cases that a simple heuristic delivers a high quality solution, one that is guaranteed to be within 6% of the optimal. Further than this, without backlogging we would know that this worst case performance 116 Chapter 4. Series Systems With Backlogging 117 result permitted many generalizations to more complex product networks (Roundy [30] (1986), Jackson, Maxwell, Muckstadt [13] (1985), Federgruen, Queyranne, Zheng [7] (1989) and Zheng [39] (1987) ) or to finite production rate assembly systems in Chap-ter 3. However, apart from one paper by Mitchell [18] (1987) for the one-warehouse n-retailer backlogged problem no generalizations to include backlogging appear to have been made. The reasons to undertake such a generalization are twofold. Firstly, there is the obvious reason to continue to explore the extent to which these rather remarkable worst-case performance results remain valid. In addition to the generalizations listed above for which the results remain valid, the results fail to be true for many obvious generalizations such as to subadditive joint costs. Thus to more carefully delineate the boundaries of where the result is true or not is worthwhile in itself. The second, and perhaps more important, reason to consider the backlog case is rather different. The real target in much inventory/production research is ultimately to learn useful properties about the case of stochastic demand. To consider the case of series systems under stochastic demand it is important that we are confident about our understanding of the deterministic case. As the stochastic case must include the risk of shortages, so ought the deterministic comparisons to include the shortage case as well. The results of the paper are as follows. Section 4.2 derives the total holding and backlogging cost over a finite horizon for feasible policies and the best Integer Frequency Policies, which are essentially identical to the average integer ratio policies explored by Mitchell [18] (1987). Section 4.3 proves that the continuous relaxation of this problem is a lower bound on any feasible policy and the worst-case result follows directly from this. Section 4.4 illustrates that the backlog problem may be reduced to an equivalent no-backlog problem and presents an algorithm to solve this problem. Chapter 4. Series Systems With Backlogging 118 4.2 Best Integer Frequency Policies As a route (and path) in a series system is uniquely defined by its two ending nodes i and j, we may use to represent this path. For the inventory model IM(S,SP,NE,IF,B), we know from Chapter 2 that given any replenishment policy P = (tp, Qp) over any finite horizon [0, T), there exists an optimal replenishment policy P' = (tP, Qp>) such that P' dominates P and satisfies the Nonposi-tive Inventory Ordering Property, the Latest Ordering Property, the Nonnegative Filling Property and the Route Nestedness Property. Therefore, without loss of generality, we consider only policies satisfying these properties. Because of the nestedness property, we know that if node i > 2 orders at instant t then node j E {1, • • • — also orders at instant t. Because of the Nonpositive Inventory Ordering Property, the inventory level of node i before instant t is zero. Considering the Nonnegative Filling Property and the nestedness property, no node orders when node 1 is backlogged. Therefore, in this time interval before instant t, the inventory of node i > 2 is zero and their inventories equal the inventory of node 1. For simplicity of description, we say that node i is backlogged, if the echelon inventory of a node i is negative. Then the property described above may be rephrased as there is an time interval before the ordering instant t of node i in which node i and all its successors are backlogged. This property allows us to conveniently label the time epochs in [0,T) by two indices. See Figure 4.1 on page 120 in this chapter. The first index refers to the node i and labelling is started with i = n and proceeds to i = 1. As upstream (larger i) nodes order less frequently than downstream (smaller i) nodes there are fewer backlogging periods to label for upstream node. The second index labels all backlogging periods of node i. Thus in Figure 4.1, node n = 3 has two backlogging periods labelled (3,1) and (3,2). A l l the nodes i with i < 2 share these periods, which are labelled as (^,1) and (i,2) for all Chapter 4. Series Systems With Backlogging 119 Figure 4.1: The Actual Inventory and Echelon Inventory Level for Series Sys-tem with backlogging 0—.0—.Q—* T Chapter 4. Series Systems With Backlogging 120 i < 2. Now label the rest of the backlogging periods of node 2 from (2, 3) to (2, 6). This continues until all periods of all nodes are labelled. Let Aij (resp. Bij) be the areas shown in Figure 4.1 and n'- (resp. r)"j) the base length (time interval) of triangle (resp. Bij). For i £ {1, • • • ,n — 1} and j = 1, • • • ,m,- + 1 . we have Bi+ij = Bij or = rj"j. Refer to Figure 4.1. Without loss of generality, we may assume that A r = 1 for all r £ R and di = 2, then A^ = TJ'-2 and Bij = rj'/j2. Let m,- be the number of replenishment of node i £ N over finite horizon [0,T). Because of nestedness, m\ > m 2 > • • • > m n > m n + 1 = 0. Lemma 4.2.1 For the inventory model IM(S,SP,NE,IF,B), the total holding and backlogging cost for any feasible policy P over the finite horizon [0, T) is . rT n l mi mi 1 J 0 «=1 l j = l j = m i + 1 + l J (4.1) where h'i+1 = 0 by convention. The total setup cost over the finite horizon [0, J1) is CSP{T) = f>,-J-\ , i=i where Ki is the setup cost of product i. The total cost over the finite horizon [0,T) is CP(T) = CSP(T) + C„P(T). Proof. By Corollary 2.4.9, rT CHP(T) = i Hl Jo = 5> j f [ 2 ( r < u > ( i ) - i ) + A T < " 1 > ( < ) dt rT = Yhi ieN = x> dt+(!>!+hD r px Jo dt E ( A i - ^ ) £(^2 - O mi + (61+ /.;)'E i^i mi + (*i + *i )IX- a Chapter 4. Series Systems With Backlogging 121 n mi mi n mi = E^E rt + (*i + K - h) E rt - E E rt-i-i j = i j=i i=2 i=i Note that for i = 1, 2, • • •, n — 1, we have r j " + 1 j = 77"-, therefore, = ft+ *'_+_) E rt + (b1 + h'l+2) E rtj-j = m 1 + i + l j = l By convention = 0 and m n+i = 0, we have mi n mi n mi (61 + /I'1-/LA)E^ 2-E^ E<-2 = 5> + A . + i ) E ^ j = l i=2 j = l i = l j=m; + 1+l and n mi n mi CHP(T) = E^E^Z + ^ + ^ E E t = l j = l t = l j = 77li + 1 + l It is obvious for the total setup cost. This completes the proof. • Now let's consider following special replenishment policies: A n Integer Frequency Policy is a nested replenishment policy where the number of replenishments of node i G {1, • • • , n — 1} in each cycle of node i -j- 1 (which is the time interval between two consecutive replenishments of node 1; + 1), is a fixed integer £i, which is called the replenishment ratio. Note that the total number of replenishments of node i G N over the finite horizon [0, T) is ra;. Therefore, m ; / r a t + i = £i and JJ £j — —- for i £ { l , 2 , - - - , n — 1}. Denote the set j=i mn of all Integer Frequency Policy over the finite horizon [0, T) with replenishment numbers mi , • • •, mn as A(m\, • • •, mn). A Best Integer Frequency Policy is an Integer Frequency Policy, which minimizes the holding and backlogging cost CHP{T) among all the policies P £ «4(mi, • • •, mn) Chapter 4. Series Systems With Backlogging 122 over the finite horizon [0,T). Denote this minimum holding and backlogging cost n as CHA(mi,-,mN)(T) or CJJA{T), and minimum total cost as CU(T) = Em«'-K» + CHA(T). t=i Similarly, we may define A Power—of—two frequency policy is an Integer Frequency Policy where all the re-plenishment ratios £\, - • • ,£n-i are power-of-two integers. A Best power—of—two frequency policy is a power-of-two frequency policy which minimizes the holding and backlogging cost CHP(T) among all the power-of-two frequency policies. Given a replenishment policy P £ A(m\, • • •, mn) over the finite horizon [0, T) , there are rat- replenishments of node i over [0,T). As in each cycle of node i + 1 there are £{ replenishments of node i, we may partition the set of indices {1, • • •, m,} into m t + 1 equal size sets Ln, • • •, Limi+1, such that \Lij\ — £i, ' j 6 Lij, E rlik+ E Vik = Vi+ij, i — 1, • • •, n — 1, j = l,---,mi+1. Recall that Vi+hj = Vij, for i = 1, • • •, n - 1, j = 1, • • •, mi+1. Now we can express CHA{T) as follows: CHA(T) = m\nCHP(T) = min]T h^V* + ( * i + h'i+i) E % . (4-2a) i'=l \ j=l j=m; + i+l J Chapter 4. Series Systems With Backlogging 123 s-t. E V'ik + E ^ m„ E Wnk + Vnk) k=l - ^t+l,i> z = 1, • • •, n — 1, j = l , - - - , m , - + i , (4.2b) (4.2c) (4.2d) The following lemma is useful in solving the quadratic programming problems below. L e m m a 4.2.2 The optimal value of the problem m — l f = m i n \ E a » x i 2 + E bixf *i--.*m><» U = l rr" ••• >0 t'=l m — l t = i t = i zs / = X /2 where D m -i m — l -j 1=1 u « i=l u« and the optimal solution to the problem is given by: 1 • x i = — „ , i = l , 2 , - - - , m , 1 X' . x i = ^ - p , * = l , 2 , - - - , m - 1. Proof. A n easy computation. • In the following we will use recursive equations to derive an explicit expression for CHA(T) for fixed t u 4 _ a . Chapter 4. Series Systems With Backlogging 124 First we introduce the.recursive relations for variable Di, which depends on and Di = oo, ( Di = + \ixh + ^ b i + h> ti-i -1 bi + h'i 11 (4.3a) for i = 2 ,3 , - - - ,n . (4.3b) We define C,-+I(T/',^I, • • • , £ { ) in terms of D T: CM = £ = o, (4.4a) • for i = 1, • • •, n — 1. (4.4b) Ci+i{r]',£i, ••-,£{) — m i n { ( i : + g ^ + ( i l + ^ £ ' r/">0, j = l , - - - , ^ - l . In fact, Ci+i(r}',£x, • • • ,£,) may be explained as the minimum total holding and back-logging cost of node 1 to i inclusive over time interval rj', in which the echelon inventory level of "node i + 1" (not node i\) is positive. By Lemma 4.2.2, the following lemma solves the quadratic programming problem of dW, £i,---, £t-i): L e m m a 4.2.3 The optimal value of problem (4-4^) Ci+i(n',£i,- • • ,£i) = -^—•q'2, Di for i = \,2 • • • ,n — 1, (4.5a) +i Chapter 4. Series Systems With Backlogging 125 and the optimal solution to problem (4-4) is: 1 rf Vi = 1 TTi + h{Di 1 for j = 1,2, •••,£{, for j = 1,2, •••,4 - 1 , J W + h'i+1 A+i where Di is defined in equation (4-3). Proof. By Lemma 4.2.2, it is obvious. (4.5b) (4.5c) • Lemma 4.2.4 For s = 1, • • • ,n, CHA{T) may also be expressed as: n I m; CHA(T) = m i n ^ ^ Z + ^ ^ ^ ^ + ^ + ^ J £ ^ . H , (4.6a) j = l s i=3 ( j=l j=mi+1+l J •t- S) >& + Z) ^ = Vi+ij, keLij keLi:i\{j} •n'f z = 5, • • •, n — 1, j = l , - - - , m i + 1 , mn Vij, Vij>0, i = s, • • • , n, j = 1, • • • , m,-. (4.6b) an<i £/ie optimal solution to problem (4-%) is: I 1 Vs+l,j r 1 s- T \ - + h. Ds+1' 1 V's+lJ TK for e i S J \ { i } , /or 6 = 1, 1, (4.7) &i + h's+l Ds+1' where Ds is defined in equation (4-3). Proof. For 5 = 1, two expressions (4.2) and (4.6) of CHA{T) a r e exactly the same. Chapter 4. Series Systems With Backlogging 126 N o w suppose (4.6) holds for s(< n — 1). B y de f in i t ion of Lsk, we have J=l * j = l j = m 3 + i + l Therefore , OM(T) = minEyj^ + E E ^/+ ft + E V* j=l s i=s \ j=l j = m , + i + l s.t. (4.66) m m k=l [ V X y * 7 i6L. t i€L.*\{*} J + ^ n E ^-vWu + E E + ft + ) E rt , s.t. (4.66) F o r k = 1, • • • , m s + 1 , each t e r m i n the s u m m a t i o n of the first par t of the above f o r m u l a t i o n p lus the relevant cons t ra in t s i n (4.66) m a y be fo rmu la t ed as i n p r o b l e m (4.4): CsM+hkA,---x) = m i n + +ft+ E rt II 2 r jeLsk\{k} I-T- E Vsj + E n"j = v',+i,k> i e L s k j£Lsk\{k} n" — n" 'ls+l,k — 'Isk-B y L e m m a 4.2.3, for k = .1, • • • , m s + 1 , the o p t i m a l value of the p r o b l e m is 1 I 2 C s+l ( l s+l , i t ) ^ ) " " ) ^ ) = Tj Vs+l,k and the o p t i m a l s o l u t i o n to the p r o b l e m is: , 1 n's+l,k r • T h + h's+1 Ds+1 ' l"i = , },, n + 1 ' * » forJ€L.k\{k}. Chapter 4. Series Systems With Backlogging 127 Therefore, the problem becomes 1 CHA(T) = min J2 rJ^-^+hi + E \h<T,Vij + + h'i+i) E V*\> i=s+l ( 3=1 s.t. (4.66) (change s to s + 1) J=m ; + 1 + 1 That is, the lemma holds for 5 + 1. By induction, the expression (4.6) holds for s = 1, • • • , n , and the optimal solution (4.7) holds for s = 1, • • • ,n — 1. D The following Corollary is an immediate result of Lemma 4.2.4 Corollary 4.2.5 The total holding and backlogging cost for the best Integer Frequency Policy over time interval [0,T) is T2 CHA(T) where [ D„ 1 + 1 \ and the optimal solution is given by 1 T Vn3 1 T nj for j = 1,2, • • • , m n . hi r v Proof. Let 5 = n in Lemma 4.2.4, we have CHA(T) = min (4.8) (4.9) (4.10) Chapter 4. Series Systems With Backlogging 128 By Lemma 4.2.2, the result is immediate. • To derive an explicit expression for Di is not easy; therefore we introduce a new variable Fi which is a function of Di+1 and easier to manipulate. F0 t 0 Fi = — if i — 1,2, • • • , n — 1. °1 + Let OLi A K + K +i W + K for i = 1,2, • • •, n, where h'n+1 = 0. It is obvious that a,- £ (0,1]. Lemma 4.2.6 (1) The following recursive relations holds for Fi: a ~ Fi = (hi + onFi-^j-, for i = 1,2, • • • ,n - 1. (2) In addition, for i = 1, 2, • • •, n — 1: Proof. (1) First note that hj JjJ (bl + h'jXW + h'i+1) 1 r , 1 F-! h + K and 1 1 1 i>. + K+i (4.11a) (4.11b) 1 av (4.12) (4.13) + ^ Fi.i W-rh'i hi Fi_! (bx + h'i)hi Fi^ hi Chapter 4. Series Systems With Backlogging 129 Therefore, we have 1 1 + A ( 6 i + K+1) + 1 + hiDi + K) + 1 ^ + A,- 6i + h'i+1 (1 + M*)(&i + h'i+i) (Di + 7T J -T7)(^ + h'i) 6i + AS-CI + + 1 1 6 + and 1 l i i + 1_ + />. 6a + 1 4 (by definition of F{ in (4.11b) ) (by definition of Dt in (4.3b) ) (hi + ctiFi-^oti That is, equation (4.12) holds. (2) For i — 1, by equation (4.12), we have Fx 1 &! + h' O i 4 " ^ i f t i + A i hi^ = h^ ^ - J L = (b1-rh'2y ti (bi + K)(bl + h'2y i.e., equation (4.13) holds. Suppose equation (4.13) holds for i. For i + 1, we have Fi+1 = (hi+i + cti+iFi) 4 (by equation (4.12) ) = /t8-+i h + h'i+2 1 &i + h'i+1 £i+i + 1 (by induction) n i h litk (W + h'3)(bl + h'^) (bi + K+2)2 hi £l+1 (br + h'+1)(bl + h'l+2) Chapter 4. Series Systems With Backlogging 130 + (&i + M + 2 ) 2 £ 5 M (fti+w+^+i) i.e., equation (4.13) holds for i + 1. • Corollary 4.2.7 ] " 1 / i -1 » 2 , r - ^ (4.i4) (recall that h'n+l = 0). Proof. Note that / i n = h'n and „ 1 1 1 1 1 6X Dn + — = , , , + — = -— + h + K hn F n _ ! (6a + hn)hn We have, by equation (4.9), DH _ 1 , 1 + i t + *. _ ^ + KTK + 1 6i + K 7 ^ 7 _ fei + hn 1 6 i h 1 FEL F Ol + hn Note that for i = n — 1 equation (4.13) becomes Chapter 4. Series Systems With Backlogging 131 D H "•n + 1 —[—rn-\ bi + hn 1 bihn 71—1 1 hj mn W + hn fr{ rrij (bt + h'^h + h'j+1) n 1 h (bi + h'j)^ + h'j+1y • Based on Corollary 4.2.5 and Corollary 4.2.7, the following corollary is immediate. Coro l l a ry 4.2.8 T Let the average replenishment interval length for node i be Tj = —. Then the average m3 holding and backlogging cost is l-CHA(T) = « E [ j ^ L j the average setup cost is 1 n K — CSA{T) = YI yf> j=l j and the average cost is (4.15) T ^ ' tr\Ti (&i + W i + *:-+i)J ' Therefore, we have the following integer programming problem to get the optimal value of best Integer Frequency Policies: L e m m a 4.2.9 The minimum average cost of the series system for best Integer Frequency Policies is Zs = m i n g ( ^ + ( 6 l + W l + , : . + 1 )}' ( 4- 1 6 a) s.t. Tn > T n _ i > • • • > Tr > 0, (4.16b) Ti/Ti-i = an integer. Chapter 4. Series Systems With Backlogging 132 Its continuous relaxation is ZB = min J2 I TrT + b*hiTi s.t. Tn > T n _! > • • • > Ti > 0. This can be compared to the single facility case where ZB K bhT min <, — + T " ( 6 + ' note that h'n+1 = 0 and h'n = hn. (4.17a) (4.17b) 4.3 Lower Bound Theorem In this section, we show that the optimal solution Zg to the continuous relaxation prob-lem (4.17) is a lower bound on the average cost of all feasible policies over any finite horizon [0, T). First we derive a lower bound on the holding and backlogging cost of any feasible policy P. Then we prove that this lower bound in fact has the same form as the holding and backlogging cost of best Integer Frequency Policies. Finally, the lower bound theorem follows immediately. Lemma 4.3.1 We recursively define B{ and Bi(xi) as follows: A Bo = 0, BiiXi) ± x2 ( + — ] + y m,y m, — m , + 1 Bi min BAx;), ^€[0,1] V ' > for i = 1,2 • ,ra. (4.18a) (4.18b) Chapter 4. Series Systems With Backlogging 133 Then for the inventory model IM(S,SP,NE,IF,B), the holding cost of any feasible policy P over the finite horizon [0, T) satisfies the following inequality: CHp(T) > T2Bn. Proof. By equation (4.1) in Lemma 4.2.1: CHP(T) = E k E ^ + ft + ^+i) E rt . «'=1 l. j=l j=mi+1+l ) where h'n+1 = 0 and m n + 1 = 0. Let = E^'j' for i — 1,2, • • •, TZ , i.e., T?,' is the total time during which the echelon inventory of node i is not in backlogging. Then E Vij = Vi+i ~ Vi> for i = 1,2, i = m ; + i + l where 0 < fj[ < rj'2 <•••<< < V ' n + 1 = T. Then it is obvious that ,/2 E^i > -m,-\ p , 2 ~ r/Q2 i = m , + 1 + l Therefore, CWJ»(T) > E t'=l m, — m,-+i ,/2 m,- — m,-+i where = 0 and m n + 1 - 0. Let recursively define function Bi(xi, • • •, Xi) as follows: (4.19) Chapter 4. Series Systems With Backlogging 134 and for i = 1, • • •, n, Bi(xu---,Xi) + A± ^ ± L. ( 1_ X.)2. m,' - m i + 1 Then by induction it is easy to verify that k I k Bk(xu---,xk) = Y2\ Ii x i i=i K x 2 + 61 + h>+1 _ 3 m-i ui i — m , + i where JJ = 1. Let Xi = —j1— £ [0,1]. Then = ; J = and inequality (4.19) becomes Vi+i £ Hv dt > T2J2 m n / n ' r 2 E n i=i \j=;+i , + A + ^±i.(i_Xi)2 — T2Bn{x\, x2, • • •, £n)-By induction we prove #i < # t ( z i , • • •, for all Xj € [0,1]. (4.20) For i = 0, B0 = BQ(-). Suppose inequality (4.20) holds for i, then by induction B l + i < Bi(xi+1) H+l + - ( l - ^ + i ) 2 m i + i ) m i + 1 - m i + 2 < xi,(B^,•••,xi)+ *±L) + BL + K + 2 (1 - X t + 1 y V m,-+i / m i + 1 - m i + 2 This completes the proof. • Chapter 4. Series Systems With Backlogging 135 In order to estimate Cfjp(T), we only need to derive a direct expression for B{. Lemma 4.3.2 below gives us a recursive formulation of Bi based only on the previous value i ? t _ i . L e m m a 4.3.2 For i = 1,2, • • •, n, Bi satisfies the following recursive relationship: B~ ~ \miBi-i + hi + h + h'i+l) m* " h + h'i+1' ( ' ' Proof. By differentiation, we have = f B , _ 1 + M 2 x , . _ A ± ^ ± ! _ 2 ( 1 _ I i ) = o. a Xi \ rrii) m8-— m , + 1 The solution Xi to this equation satisfies U^^)* = W + K + 1 (1 - fr), (4.22) \ m-i ) rrii — m,i+1 and U1 + hL + ±±J^.)I{ = iL±»k.. (4.23) \ m, m,- — m t + 1 J rrii — From equation (4.23), it is obvious that xt- £ [0,1], i.e., fr is the optimal solution to B(xi). Therefore, Bi = B(xi) = ^(Bi.1 + ^ ) + ^ ± ^ . ( l - x i y \ rrii) rrii - mi+1 = x2 \Bi_i + — J + + — J fr(l - (by equation (4.22) ) ^ mi) V M « / / h{\ = Xi Bi_-i + — V rrii I Bi-! + h{ \ ( h + h'i+1 rrii J \rrii — rrii+1 j (by equation (4.22) ) Chapter 4. Series Systems With Backlogging 136 Finally, we have 1 _ _ % ~ ~ 1 Bi-i + mi + 1 ruj - m , + 1 h + h'i+1 1 + \ m , - A-i + hi bi + h'i+l This completes the proof. rrii — mi+1 W + h'i+1 • Lemma 4.3.3 1 ,=i m 3 ft + M)( f ti + h'i+i) (recall that h'n+1 = 0). (4.24) Proof. Let D> A -1 i D' = rriiBi-i £'. = m ' m /or ?' = 2, • • • ,n , /or z = 1, • • • ,n , 79 , A 1 H Bn Note that l\ is not necessarily an integer. By Lemma 4.3.2, we have D\ = oo, 1 i • i N + . * + ^ * - t - i 1 bi + K for i = 2, 3, • • •, n, / 1 1 KD>n+hn \ I Chapter 4. Series Systems With Backlogging 137 Comparing D[, D'H with the definition of D, , Du, it is obvious that D'H = DJJ. Note that the integrality of t{ is not required in the proof of Corollary 4.2.7. Therefore, D'H has the same expression as DH even for noninteger • Based on the previous lemma, the following lower bound theorem follows directly. Theorem 4.3.4 (Lower Bound Theorem) For the inventory model IM(S,SP,NE,IF,B), the long-run average cost Cp of any feasible •policy P satisfies Cp > ZB-That is, ZB is a lower bound on all feasible policies. Proof. By Lemma 4.3.1 and Lemma 4.3.3, the total cost Cp(T) of any feasible policy P over the finite horizon [0, T) is bounded below by n n 1 h tim*(bi + K)(bi + K+1y Recall that Ts- = T / m , is the average replenishment interval length for ieN and we have 1 n [Ki b2h{Ti Because mi > m 2 > • • • > m n , we have Tn > T n _ i > • • • > T\ > 0. By the definition of Zg, we get —Cp(T) > ZB, and this completes the proof. • Chapter 4. Series Systems With Backlogging 138 4.4 Reduction to an Equivalent No-Backlog Problem and Scheduling Algo-rithm For an instance of the inventory model IM(S,SP,NE,IF,B), we can easily define a cor-responding instance of the inventory model IM(S,SP,NE,IF,NB) as follows. A l l the pa-rameters of two instances are exactly the same except the holding and backlogging cost rate. Suppose the holding cost rate of node ieN for the instance of the inventory model IM(S,SP,NE,IF,B) is h\ and the backlogging cost rate of node 1 is V The actual holding cost of node i G N for the instance of the inventory model IM(S,SP,NE,IF,NB) is defined a s M = 1—1 a n d there is no backlogging at node 1. Then it is easy to verify that the »i + hi echelon holding cost rate hi satisfies We can formulate this problem by power-of-two policies as in Roundy [27] (1983) who solved this no-backlog problem by the minimum violating algorithm in 0(n log n) time. The formulation of this problem for power-of-two policies is min { —r + /i.-Ti f^\Ti s.t. Tn > T n _! > • • • > Ti > 0, Ti/Ti-i = power-of-two integer, which is the same as the equivalent backlogging problem. Therefore they have the same average cost and the same lower bound ZB- Thus, the results of the no-backlogging problem can be easily applied to the corresponding backlogging problem. We state only two consequences of Roundy's results here. Theorem 4.4.1 (94% Effectiveness of Power-of-Two Frequency Policies) For each fixed base period TB, there is an optimal best power-of-two frequency policy P Chapter 4. Series Systems With Backlogging 139 with the cycle time Tn = 2 ?"Tg of product n for some integer qn and the average cost Cp of policy P satisfies Cp > 94%ZB for the inventory model IM(S,SP,NE,IF,B). Moreover, the optimal best power-of-two frequency policy P can be found in O(nlogn) time. If allowing the base period TB varies, we have a better estimate. Theorem 4.4.2 (98% Effectiveness of Power-of-two Frequency Policies) There is an optimal best power-of-two frequency policy P whose average cost Cp satisfies Cp > 98%ZB for the inventory model IM(S,SP,NE,IF,B). Moreover, the optimal best power-of-two frequency policy P can be found in O(nlogn) time. In the following, we illustrate how can we get an optimal best power-of-two frequency policy P, if the optimal average replenishment intervals are 7\*,T2, • • • ,T* and ZB — CA(T*) are the solution to the continuous relaxation (4.17): Consider a power-of-two policy P with a base period TB and the optimal average T* 1 power-of-two interval of node i £ TV is Ti — 2q,TB, where qi — l o g 2 7jT •LB 771' m . = 2?n-9< for i = 1, • • •, n and £4 = = 2 9 i + 1 - ( ' i for i = 1, • • •, n - 1. m,-+i Let T = Tn be the cycle time of product n and Iii = d f o r 3 = 1, Vij = Z", f o r J = mi+u •••,rnl. where d and are recursively (from n to 1) given by following equations: 1 T Let -rj- + hnDH 1 T £" = — — Chapter 4. Series Systems With Backlogging 140 where D{ (for i = 1, • • - , « ) is defined in equations (4.3) and DH is defined in equa-tions (4.9). Let & = + then the schedule for product i £ N is to order products at instants A f " _ 1 ] £,(&;,- • •, fcn_i, kn) = < T x fcn + £ x kj > such that the echelon inventory level of product i reaches 2^,', where kj = 0,1, • • •, £j — 1 for j = 1, • • •, n — 1 and kn is any non-negative integer. Alternatively, the order quantities of node i at instant £;(&;, • • • , kn_i, kn) is 2£ + 2£j ' + 1 , if ki = --- = kj = 0, > 0, for i < n - l , IT, for i = n. Qi(ki, • - • , kn) — < See the example in Figure 4.2. 4.5 Conclusions In this chapter, we derive a best power-of-two frequency policy for the series systems with backlogging. This policy is guaranteed to be within 6% of the optimal, and can be found in O(nlogn) time. We also present an algorithm to show how to get the replenishment schedule for the best power-of-two frequency policy in linear time to calculate all the parameters. Chapter 4. Series Systems With Backlogging Figure 4.2: The Power-of-Two Frequency Policy (T) • © * <*i 4 = 4, £ 2 = 2 141 Chapter 5 The Performance Ratio of Grouping Policies for the Joint Replenishment Problem 5.1 Introduction We consider the inventory model IM(I ,SM,CT,IF,NB), i.e., a multi-product extension of the traditional Economic Order Quantity (EOQ) model where there is a cost in-centive for simultaneous replenishment of several products. There are n products, and N = {1, •••,n} denotes the set of products. Except for the setup costs (see below), the products are independent: there are no joint or dependent demands, no substitution opportunities, and products in N are not being used in making other products in N. As in the EOQ model, we make the following assumptions: 1. We consider a continuous time, infinite horizon model, with stationary data (de-mand and cost rates) and no discounting. As a result, we focus on minimizing the long run average cost per time unit, while satisfying demands for all products. 2. The demand for each product is deterministic and occurs at a constant rate. By rescaling the units for each product, we are assuming that the demand rate is of two units per time unit, for each product. 3. The demand for each product is satisfied by continuously withdrawing from the inventory of that product. No shortages or backlogs are allowed. The inventories are replenished at times and in quantities to be determined. Replenishment of each product is instantaneous and lead times can be assumed to be zero, w.l.o.g. (without loss of 142 Chapter 5. Grouping Policies 143 generality). 4. The total cost is the sum of all holding costs and setup costs. 5. The holding cost for product i accumulates at a constant rate hi dollars per unit of product and per unit time. For each product i (i = 1, • • •, n), rate hi is a positive real number. 6. At each replenishment, a positive setup cost K(S) is incurred, depending only on the set 5" C N of products being replenished. In the traditional EOQ model, we have K(S) = Hies where the fc,-'s are given separate setup costs. In this case, there is no incentive for joint replenishment, and an optimal policy has each product being independently replenished according to the familiar EOQ (or square root, or Wilson's) formula. We depart from the traditional EOQ model by allowing the joint setup cost K(S) to be less than the sum of the separate setup costs of the products in S, therefore making joint replenishment costwise attractive. The model for joint setup costs we use here is that of a submodular setup cost introduced by Queyranne [24] (1985). We assume the set function K : 2N r-y R+ satisfies the following conditions: 1. K(Q) = 0; 2. K(S) > 0, for all S C N, S ^ 0; 3. K(S) < K(T), whenever S CT; 4. K(S\JT) < K(S) + K{T) - K(S n T), for all S,T. Conditions 1 and 2 are necessary for the model to be meaningful (otherwise optimal total costs for any finite period may go to ±oo) . The nondecreasing property of condi-tion 3 may be assumed w.l.o.g. (otherwise, set S is never used in an optimal solution, and function K can then be redefined so as to satisfy condition 3). The submodularity property of condition 4 is fairly general, and allows the derivation of very tight bounds on the optimal cost. For example, the most popular joint setup cost function, defined by Chapter 5. Grouping Policies 144 K(S) = k0 + J2ies h a n d sometimes called the major/minor, or quasi-linear, or modular, setup cost function, is submodular. We refer to Goyal and §atir [10] (1989) for a survey on models using this function. The "family model" of Roundy [30] (1986) and the exam-ple in Rosenblatt and Kaspi [26] (1985) are also submodular. We refer to Queyranne [24] (1985) and Zheng [39] (1987) for further discussion of submodular setup costs. Section 2 below recalls how very tight bounds on the optimal cost may be obtained for submodular setup costs. A replenishment policy is a specification of all replenishment epochs and quantities, for all products, over an infinite horizon. A feasible policy is a replenishment policy whereby all demands are satisfied, that is, inventory levels are never negative. The joint replenishment problem is to find a feasible policy with lowest possible long run average total cost per time unit. The only known fact about optimal policies is that it must satisfy the following zero inventory property: the inventory of every product drops to zero just before any replenishment of that product. This property implies that replenishment quantities are directly implied by replenishment times (and conversely). Much attention has focused on stationary policies, that is, policies where each product is replenished at constant time intervals (and therefore, by the zero-inventory property, in constant quantities). Nonstationary policies may have lower cost than any stationary policy (Andres and Emmons, [1] (1976) ). For submodular setup costs, however, it is known that the cost of a particular stationary policy (a "power-of-two" policy) cannot be more than 2% above the cost of any feasible policy (see Section 5.2). One class of stationary policies that has been considered in the literature, is that of grouping policies (or fixed partition policies), whereby the set of products is par-titioned into groups of products, and all items in the same group are always jointly Chapter 5. Grouping Policies 145 replenished. Each group is then considered as a single "aggregate product" being replen-ished independently of the other groups, and therefore according to the EOQ formula. As a result, possible savings when several groups are simultaneously replenished are sim-ply ignored. Grouping policies are considered by Chakravarty et al. [4] (1982), [5] (1985), by Rosenblatt and Kaspi [26] (1985) and by Queyranne [25] (1987). A n apparent advantage of grouping policies is that an optimal grouping may be rel-atively straightforward to compute. Chakravarty et al. show that, for special types of setup costs, the products can be indexed such that an optimal grouping is consecutive, that is, each group contains only products with consecutive indices. They also provide an 0(n 2 ) shortest path algorithm for finding a corresponding optimal grouping policy. Rosenblatt and Kaspi propose to find an optimal grouping by Dynamic Programming, for an arbitrary (not necessarily submodular) setup cost function. A correct Dynamic Programming algorithm runs in (9(3n), Queyranne [25] (1987). This might be acceptable when n is fairly small and the setup cost function is complicated, rendering other ap-proaches (see Section 5.2) more cumbersome. Another apparent advantage of grouping policies is that they may be very easy to implement in practice, by permanently "tying together" products in a same group. In terms of cost, unfortunately, a best grouping policy can be somewhat worse than some other good feasible policy. A n example in Zheng [39] (1987) shows that the cost of a best grouping policy can be worse than 20% above the cost of another feasible policy. The objective of this chapter is to study, for submodular setup costs, how bad can best grouping policies be in the worst case. We use submodular costs here because, as mentioned above, they provide a fairly general model and a very tight estimate on the optimal cost of any feasible policy is available for such setup cost functions. The organization of the chapter is as follows. In Section 5.2, we recall the properties of another class of stationary policies, namely, the integer ratio policies, which allow the Chapter 5. Grouping Policies 146 derivation of a very tight lower bound on the optimal cost of a feasible policy. This lower bound will be used in the definition of the performance ratio for grouping policies. A special class of stationary policies, the power-of-/? policies, is also discussed, and will be used later for deriving an upper bound on that performance ratio. Section 5.3 defines grouping policies and their performance ratio. Three lemmas in this section reduce the space of problem instances that has to be searched for determining the worst case performance ratio of grouping policies. It is interesting to note that the resulting instances are such that the consecutiveness property holds for an optimal grouping (Lemma 5.3.3), which can therefore be found by an 0(n 2 ) shortest path algorithm. The last lemma in this section presents a useful transformation of variables for estimating the performance ratio. Section 5.4 gives an upper bound on the worst case performance ratio of grouping policies, which is the main results of the chapter. Bad examples in Section 5.5 give us a lower bound on the worst case performance ratio of grouping policies. Section 5.7.1 collects the proofs of lemmas in the text. Section 5.7.2 includes all the main notation in the chapter for reference. Section 5.7.3 is the table of performance ratios of power-of-/? policies. 5.2 Lower Bound on the Average Cost of All Feasible Policies Besides grouping policies, another class of stationary policies has been widely studied, that is, base period policies, whereby all products are replenished at constant intervals ("cycles") which are integral multiples of a common base period. Base period policies are surveyed by Goyal and §atir [10] (1989) for the case of major/minor setup costs. Integer ratio policies are base period policies where, for any two products, the cycle of one product is an integer multiple of the cycle of the other one. A special class of Chapter 5. Grouping Policies 147 integer ratio policies is that of power-of-two policies, where each interval is a power-of-two times the base period. A n extension to power-of-f3 policies, where is an arbitrary integer greater than one, is discussed below. Power-of-two policies were introduced for joint replenishment problems by Jackson et al. [13] (1985) and Roundy [28] (1985). One of Roundy's major contributions was to show that finding a best integer ratio policies also yields, as a by-product, a lower bound on the cost of any feasible policy. Power-of-two policies, and the corresponding lower bound result, have also been ex-tended by Roundy [30] (1986) to his "family model" of setup costs, and by Queyranne [24] (1985) and Zheng [39] (1987) to general submodular setup cost functions. For all these cases, the lower bound is also a very tight estimate (within about 2%) of the cost of a feasible (power-of-two) policy. As mentioned in the Section 5.1, this very tight bound is the main tool used here for assessing the performance ratio of grouping heuristics. We now introduce the requisite notations and definitions. Let R+ ^ (0, oo) be the set of positive real numbers; A 71 i?" = x R+ be the set of n-dimensional positive real numbers; power-of-/3 po l icy t be a sequence t = ( T J 1 ? t2, • • •, tn) £ R1^ with the following three properties, see Roundy [28] (1985): 1. Orders for product i are placed once every ti > 0 units of time, beginning at time zero; Z = {0, ± 1 , ±2 , • • •} is the set of integers, and N = {1,2, • • • , « } is the set of products; 3. The zero-inventory property holds, i.e., an order is placed for a product only when the inventory of that product is zero. 2. ti = f3mi (30, m-i £ Z, Ve £ N and for some /30 £ Chapter 5. Grouping Policies 148 For a joint replenishment inventory model, we can easily derive a formulation of the average cost for a given power-of-/? policy, see Queyranne [24] (1985) and Zheng [39] (1987) for details. Power-of-/? policy t induces a permutation a = (ai , a 2 , • • •, ctn) of the indices in N such that — ^<*2 — ' ' ' — tan- (5.1a) Let {ai,a 2,- • • ,a;} , Vi 6 N (5.1b) be the sets associated with permutation a. (Ties are broken arbitrarily). Observe that under a power-of-/? policy £, whenever product a; is replenished, all the products in set Ui-i are also replenished. The average set-up cost for power-of-/3 policy t is 1 K[t] = E ^ i ) t t I ^ t where tan+1 = oo, rj 0 = 0 and if(0) = 0. The optimal average cost for power-of-/3 policies (for fixed /? and {30) is given by a non-linear integer programming problem: 'K(Ui)-K(U^) {JR)t Cp(n,K,h,Po)= min. £ »=i -f-s.t. U = (3mi /30, mi G Z, Vi G TV, where a satisfies (5.1a) and the U-s are defined by (5.1b). The following non-linear programming problem (RJR), independent of /? and /?0, is a continuous relaxation of (JR)p. ~K{Ui) - K(U^) (RJR) : LB(n, K, h) = min £ i = l where a satisfies (5.1a) and the £/,'s are defined by (5.1b). -f- hai tai Chapter 5. Grouping Policies 149 Sequence (Si,S2, • • •, Sq) of subsets of N is a nested path in N, if 0 = S0 C Si C S2 C • • • C Sq = N. Note that the inclusions are proper in this definition. Note also that (Ui, U2, • • •, Un) defined above forms a nested path in N. Let K(<f>) = 0; K(S) > 0, and K(N) > 0 (non-negativity); R+ K(S) < K(T), if S C T (non-decreasing); K(SHT) + K(SIJT) < K(S) + K(T), V5, T C N (submodularity) submodular set functions on N. K : 2 N denotes the set of The following characterization theorem in Zheng [39, Theorem 4.5] (1987) solves (RJR). Theorem 5.2.1 (Op t ima l Solut ion to ( R J R ) ) Assume that K £ Sn and the components of t = (rj1? t2, • • •, tn) take on q distinct val-ues t(l) < t(2) < ••• < t(q), q < n, and (Sx, S2, • • •, Sq) is a nested path in N with St\St-i = {ieN :ti= t(£)}. Then t is optimal for (RJR) iff the following two condi-tions hold for each £ = 1,2, • • •, q: 1. t(£) = ^[K(Se)-K(S(-i)}/h(Se\Se-i), where h(S) = ^ hi, for any set S e N. 2. y/[K(S) - K(St-i)]/h(S\St-i) > t(£), V5, such that C S C Se Besides, the optimal value of (RJR) is LB(n, K, h) = 2J2yJ[K(St)-K(St-i)]h(St\St-i). Chapter 5. Grouping Policies 150 Proof. See Zheng [39, Theorem 4.5] (1987). • We introduce two sets' of problem instances related to (K,h). They will be used in the sequel: Mn = { K : 2N h-> R •+ 0 < K\ < K2 < • •" < Kn, (non-decreasing) K(S) = max 7^, VS C /V, (maximum) • denotes the set of 'maximum' submodular set functions on N. Note that Ki = K({i}) V i 6 7Y. 0" =A(K,h) G (Mn,Rl) -r^- < \ — < • • • < \ —^—;—1 denotes the set «i V h2 \ kn \ of 'monotone path' instances. Note the strict inequalities in the definition. The following corollary is an immediate result of Theorem 5.2.1. Coro l l a ry 5.2.2 (Op t ima l Solut ion to ( R J R ) for monotone paths) If (K, h) e ttn, then LB(n, K, h) = 2 £ yf(Kt - Ki-i)hi is the optimal value to problem (RJR). i = l The Lower Bound Theorem, Roundy [28] (1985), is a fundamental result for the analysis of heuristics for the joint replenishment problem: Theo rem 5.2.3 (Lower B o u n d Theorem) LB(n, K, h) is a lower bound on the average cost of any feasible policy over any finite horizon. A worst case performance ratio for a class of solutions to a problem is defined as the supremum, over all instances, of the ratio of the cost of the best policy in that class, to the optimum cost. Chapter 5. Grouping Policies 151 The following lemma is a direct extension of a rounding lemma in Roundy [28] (1985). There, for x G R+, e(x) = - (x + —), and log^ x denotes the logarithm of x with base j3. Lemma 5.2.4 (Performance Ratio Rp(f30) of Power-of-/? Policies) For any fixed base period f30, let where t = (ti,t2, • • • ,tn) is the optimal solution to (RJR). Then t* = (ij,t2, • • •,tn) is an optimal power-of-fi policy for (JR) with f30 fixed. The worst case performance ratio Rp(fio) of power-of-(3 policies satisfies A C/3(n,K,h,p0) LB(n, K, h) Proof. see Section 5.7.1. • The next result, also a direct extension of Roundy, allows base period f30 to vary. Lemma 5.2.5 (Performance Ratio Rp of Power-of-/? Policies) Let Cp(n, K, h) = inf C/j(n, K, h, 0o) be the optimal average cost of power-of-(3 policies 0o>O for instance (K, h) of n-product. The worst case performance ratio Rp of power-of-/3 policies satisfies A • t & ,n\ Cp(n,K,h) R?= ^ o R ^ = LB(n,K,h) * where pp = -—-^—=- is the upper bound of worst case performance ratio of power-of-f3 lnp V P policies. Proof. see Section 5.7.1. • Chapter 5. Grouping Policies 152 5.3 Grouping Policies and Performance Ratio Say G = {Gi, G2, • • •, Gp} is a grouping of N, if {G\, G2, • • • , Gp} forms a partition of N, i.e., (jGi = N; Gi n Gj = 0, iff i^j, V i , i = l , 2 , . - . , p . »=i Set Gi is called a group (of products). The corresponding grouping policy G will replenish all the products in each group Gi at the same time T,-, the replenishment period of group Gi. As we mentioned in the introduction, we ignore the possible cost saving due to replenishing different groups at the same time. Therefore, the optimal average cost g(Gi) of group Gi is g(Gi) = 2yjK(Gi)h(Gi), the corresponding optimal replenishment time T* of group Gi is T* = yjK(Gi)lh(Gi), and the optimal average cost CGP(W, K, h, G) of grouping policy G is the sum of optimal average costs of all groups in G: CGP{n,K,h,G) = JZoiGi), t=i where \G\ = p, and the corresponding optimal replenishment period vector is T* = (T*,T;,---,T;). If we use the (not necessarily optimal) replenishment period vector T = [T\, T 2 , • • •, TV) for grouping policy G, the corresponding average cost is CGP(n,K,h,G,T) ± t{^- + HGi)Tty Therefore, the optimal average cost of grouping policy G can also be expressed as CGP{n,K,h,G) = inf CGp(n,K,h,G,T). Chapter 5. Grouping Policies 153 Let T>n be the set of all partitions on N, and CGP(n,K,h,Vn) £ mmCGP(n,K,h,G), be the average cost of optimal grouping policies for n-product instance (K, h). Because we are mainly concerned with finding an upper bound on the performance ra-tio of grouping policies, we replace the optimal average cost by its lower bound LB(n, K, h) in our definition of performance ratio of grouping policies. This substitution cannot de-crease the performance ratio. Therefore, the upper bound obtained here will also be an upper bound on the 'real' performance ratio. However, because LB(n, K, h) is a very tight lower bound—within 2% of the optimum cost, see Roundy [28] (1985) (by letting f3 — 2 in Lemma 5.2.5), we do not really lose much by this substitution. Now we are ready to define various performance ratios of grouping policies. Let , , A CGP(n,K,h,G,T) r(n, K,h,G,T) = L B { n J ^ h ) be the performance ratio of grouping policy G with replenishment period vector T for n-product instance (K,h). Let , u n\ A CGP{n,K,h,G) r ( n ' 7 ^ ' G ) = LB(n,K,h) be the performance ratio of grouping policy G for n-product instance (K, h). Let be the performance ratio of an optimal grouping policy for n-product instance (K,h). Let r*(n) = sup r(n,K,h,Vn) be the worst case performance ratio of grouping heuristics for n-product, and let r* = sup r*(n) Chapter 5. Grouping Policies 154 be the worst case performance ratio of grouping heuristics (over all problem instances). Note that iV = {1,2,3, •••} is the set of natural numbers. Estimating an upper bound on ratio r* is the main objective of this chapter. A partition G € T>n is a consecutive partition iff the indices of the products in each group Gi are consecutive integers. Let Cn be the set of all consecutive partitions on N. Lemmas 5.3.1 to 5.3.5 imply that, to find the worst case performance ratio r*, we may limit the problem instances to (K,h) 6 Cln ('monotone path' instances), and grouping policies to G e Cn. First, we may limit problem instances from submodular set functions (Sn) to 'maxi-mum' submodular set functions (A4n): Lemma 5.3.1 (First Reduction) r*(n) = sup r(n,K,h,Vn). (K,h)e(M",R1) Proof. See Section 5.7.1. • Because of Lemma 5.3.1, we will assume K G j\4n hereafter. The following lemma shows that we may restrict attention to grouping policies using only consecutive partitions of N, which we call the consecutive grouping heuristic. Let CGP(n, K, h, Cn) = min CGP(n, K, h, G) be the average cost of consecutive grouping heuristics, for rt-product instance (K, h). Let *•.*.*•«•> -be the corresponding performance ratio. The following inequality is useful in proving Lemma 5.3.3 - consecutive grouping heuristics are optimal. Chapter 5. Grouping Policies 155 Lemma 5.3.2 (Consecutive Grouping of Three Products) If& > 6 > 0; »h,»72,»?3 > 0, then > m i n | ^ 2 ( 7 / i + ^ 2 ) + v ^ 3 > V 7 ^ 3 ^ 1 + ^ 2 + ^3)} • Proof. See Section 5.7.1. • Lemma 5.3.3 (Consecutive Grouping Heuristics are Optimal) IfK E Mn, then CGp(n,-K,h,Cn) = CGP(n,K,h,Vn). Proof. See Section 5.7.1. • Therefore, using the method proposed in Chakravarty, Orlin, and Rothblum [4] (1982), the optimal grouping policy can be found by an 0{n2) shortest path algorithm. The second reduction follows directly from Lemmas 5.3.1 and 5.3.3: Corollary 5.3.4 (Second Reduction) The worst case performance ratio of consecutive grouping heuristics for all problem in-stances K E M.n is r*(n), i.e., r*(n) = sup r(n,K,h,Cn). {K,h)e(M",R1) The next lemma shows that we may further restrict our attention to problem in-stances (K, h) E 0". Recall that O n is the set of 'monotone path' instances. Lemma 5.3.5 (Third Reduction) Chapter 5. Grouping Policies 156 The worst case performance ratio of consecutive grouping heuristics for all problem in-stances (K,h) £ 0,n is r*(n), i.e., P j r*(n) = sup r(n,K,h,Cn) = sup fc=1 i=l where Gk = { 4 - i + !,-••,4} ieGk forp= 1,2, Proof. See Section 5.7.1. • Now we only need to consider problem instances (K, h) G fl™. We find it convenient to replace variables (K,h) by as follows: 1 VieN. (5.2) Let i2£ = { i G i2£ | t i < t2 < • • • < tn} be the 'monotone cone' in R7}. It is easy to verify that (K, h) G £ln is equivalent to (x,t) G (R+, R<)- For simplicity, we do not change function names when variables (K, h) are replaced by (x,t). The following lemma establishes the correspondence between variables (K, h) and (x,t). L e m m a 5.3.6 (Transformation of Variables) Let G = {Gl,G2,--- ,GP} G Cn, (x,t) be defined by (5.2), and f3k(t,T) =\ + VjeGk,k = l,2,-..,p, Vifc' 1 i=k+l *i Chapter 5. Grouping Policies then for any (K,h) 6 On, i.e., (x,t) G (i?+,i?<), we have, CGP(n,K,h,G,T) = 2 £ £ / j f c(*,r)x,, a n d k=ljeGk n LB(n,K,h) = 2£x,-. 1=1 Proof. Clearly, hi — Xi/ti, Ki - Ki-i - XiU, for i = 1,2, • • • , n. Therefore, = Ki - K0 = £(#; - Kj-i) = £ xjtj, for i = 1,2, j=i j=i As G = {Gi, G 2 , • • • ,GP} 6 Cn, suppose G< = {4_i + 1,...,4}, for* = l,2,---,p. Then K(Gt) = Ke„ h(Gi)=J2hi> for * = 1,2, • • • ,p. Therefore, CGp(n,A-,/»,G,r) = £ { ^ | i ) + fc(G,)r,} ,=i (/« j=i jeGi l J . p ti , p ii rp. = E E k + E £ ^ i=i j=i i=i j=^_i+i Li = E E £ ^ + £ E f*i k=l .7=4-1+1 «'=* * fc=l .7=4-1+1 l3 E E \^ + r-+ E j J k , rjr + — "'" ^ T- ( fc=l j=4-l+l I fc J' i=k+lXl I 2E E fik(t,T)Xi. k=i jeGk Chapter 5. Grouping Policies 158 This completes the proof. D 5.4 Upper Bound on the Worst Case Performance Ratio of Grouping Policies Based on the transformation provided in the previous section, we may rewrite the worst case performance ratio of grouping heuristics r*(n) in the following form: min 2 G6C" £-< fc=i r*(n) = sup — (*,«)€(K£,rt») 2j2%i i=l V infG 2 E E fAt,T)xj, sup . (*,t)6(flJ,H5) j ^ . This problem is much simpler than the original problem defined on submodular joint setup cost functions. It has only 0{n) variables. The minimization problem on a set of consecutive grouping policies can be solved by an 0{n2) shortest path algorithm. However, as a max-min problem, it is still too difficult to find the value of r* = sup r*(n) n for the following reasons: (1) The objective function of this problem is neither quasi-concave nor quasi-convex in variables x and t. It has many local minima and maxima. Therefore, the classic convex analysis methods does not apply. (2) This problem is first to minimize on a set of consecutive grouping policies, then to maximize with respect to variables x and t. The problem cannot be solved by exchanging the max and min operators. (3) This problem also has many constraints, which further complicate the situation. Therefore, in this section, we will use a different approach to estimate an upper bound Chapter 5. Grouping Policies 159 on r*. First, we reduce the search space from set Cln to a subset of it — Bp, the set of 'root-of-/? path' instances defined next. Although the worst case performance ratio rp of grouping heuristics over problem instances in Bp used not equal to r*, they yield an upper bound on r*: r* < ppr*p. As we know the value of pp, the next step is to estimate an upper bound on r*p. To do this, we construct a grouping heuristic Hb, which uses at most two products in each group. An upper bound Wp on the performance ratio for the heuristic Hf, is also an upper bound on rp: r*p < Wp for f3 = 2,3,- • •. Finally, we use nonlinear programming technique to get the upper bounds on Wp and therefore on r*. First, let us define the following concepts, Bnp= { {K, h) £ Q,n mi(/30) < m2(/90) < • • • < m n(/3 0), for some /?0 6 [ l / / # , V ? ) • be the set of 'root-of-/3 paths'. Note that rat(/?0) = Hp t £ RnK mi(/30) = ' hi fa J miiPo) < m 2 (^ 0 ) < • < mn(/30), for some /30 € [l , y/0) \/i. • be the 'root-of-/? cone'. Note that log A) , V i . It is clear that (K,h) £ Bp is equivalent to (x,t) £ Note that the strict inequalities in the definition imply that all the replenishment times ti = \J(Ki — Ki-\)/hi are in distinct 'root-of-/?' intervals [ l / / # , V ? ) A) P™' • Therefore, we have U/tj > 01 3 1, for all i , j, j > i Theorem 5.4.1 (Upper Bound on Performance Ratio of Grouping Policies) Let r*p = sup sup r(n,K,h,Cn) be the worst case performance ratio of consecutive Chapter 5. Grouping Policies 160 grouping heuristics over problem instances (K,h) £ Bp — 'root-of-(3 paths', then the worst case performance ratio of grouping heuristics r* satisfies: r* < inf pg rZ. Proof. See Section 5.7.1. • We now use variables (x,t) to replace (K,h) defined in (5.2). The following Lemma gives us an upper bound on the performance ratio of any grouping G. Lemma 5.4.2 (Upper Bound on Performance Ratio of Grouping G) Suppose (K,h) £ f i n , or equivalently (x,t) £ (i?+,i?<) defined by (5.2). For any group-ing G, let W(n,t,G) = inf max f]k{t,T) 1 fc/t+ *=1,2,--,|G| where fjk(t,T) is defined in Lemma 5.3.6. Then we have . CGP{n,K,h,G,T) sup inf ^——— < W(n,t,G). x6R + red? LB(n,K,h) K ' Proof. By definition, we have: W(n,t,G) = inf max fjk(t,T) Ten |G| ieak + fc=l,2,-,|G| |G| > i n f Efc=iEj 6G f c fjk(t,T)xj ~ TTR™ EUxi J n f CGP{n,K,h,G,T) TfR\o\ LB(n, K, h) This completes the proof. • We can now define a grouping heuristic Hi, in Figure 5.1, where b £ R+ is a parameter which satisfies 1 < b < fl and whose precise value will be determined later. Chapter 5. Grouping Policies 161 Figure 5.1: Grouping Heuristic Hb Input: instance (K, h) 6 fi", real numbers fl > 1 and b € ( l , y/p^ • Output: number p of groups, and grouping G(b) = (G\, G 2 , • • •, Gp). Step 1: for i := 1 to n do := \J{Ki — <o := 0; r j n + 1 := +oo; Step 2: j := 1; k := 0; repeat ifc := k + 1; if ti+i > then begin Gk := {i}; i := ii + 1 end else begin G*. := + 1}; i := i -f 2 end until z > n; p := As each group Gk (k = 1,2, • • • ,p) contains at most two products, let 4 = max{i : i e Gk), so that Gk = {4} or Gk = {4 - 1,4}-Lemma 5.4.3 Suppose t is generated by heuristic Hb- Then we have £4+1 > 6£4 Vfc. Proof. If Gk = {i}, then t(k+1 = / J , + 1 > bti = bt^k. Otherwise, Gk = {i,i + 1}, and using ii+2 > fiti and b < y/fi, we have t(k+1 = ti+2 > PU> f3 (ti+1/b) > bti+1 =bttk. • The following technical Lemma is used in the proof of Lemma 5.4.5: Lemma 5.4.4 If 1 5; V < 0 and 0 < °2 5; V ^ ; we Aa^e Chapter 5. Grouping Policies 162 Proof. See Section 5.7.1. D To get an upper bound on fjk(t,T), we introduce two additional parameters a x and a 2 , which will be optimized later, satisfying 0 < ai}a2 < \fb. For any grouping policy G = { G i , G 2 , • • •, G p } , let Tk = t,Ja\Gk\, for k = 1,2, •• • ,p, (5.3) L e m m a 5.4.5 (Upper B o u n d on f!jk(t,T)) For any /? > 1 anc? fe satisfying 0 < fe < c = m a xU'^J' #i(ai,a2,fe) = - oi + I - T + 2 \ ai 6 / 3 - i y ' , , •. A 1 // 1 a 2 c \ 52(«l ,«2, fe) = « a l + • " " f l * 2 ^ 0 1 / 3 / 3 - 1 ^ n A 1 / 1 fee/? g3(a1,a2,b) = - a 2 + r - a i ^ + 2 v « 2 1 LP / 5 - i y / , \ A 1 / 1 a 2 c 5f4(ai,a2,fe) = -\a2-\ H + a 2 P 0-1J ' , .. A 1 (a2 b , a, c \ 5s(ai,«2,fe) = o - r + — + ^ + 2 \ r a, J ^ - 1 / ' , A 1 ^ 2 . fe , C t 2 , C ge{a1,a2,b) = 7; [ ~T + ~ + ~^ + 2\b a2 P* W - l ) / ' T/ien, /or t £ Rp and any ax,a2 satisfying 0 < a i , a 2 < y/b, we have, for j = 1,2, • • • , n : /,-*(*, < max Oi(ai,a 2 ,fe), J t=l,---,6 where T and fjk(t,T) are defined by equation (5.3) and (5.4) respectively. Chapter 5. Grouping Policies Proof. Observe that E |G>|, for i = k + 1, =fc+i •ti-j-i for j > £i, we have *; E =Y+2 *4 < y- a|G.I i=k+2 P Because t £ R^, we have > /?' ^ x , for all z, j , j > i. Therefore, P I p\Gk+a\ + p\Gk+2\+\Gk+3\ a\Gk+3\ < < 1 + ^ | G f c + 1 | - l I 1 ^|G f c + 2| C 1 + ••• + + . . . + 1 a\GP p\Gk+2\+-+\Gp\ /3|Gfc+2l+-+|Gp_i| p\Gk+1\-l I -\/p fi p\Gk+1\-l There are two cases to consider: Case 1: Gk = {£k},j = tk. Using Lemma 5.4.3, we have a \ G k + 1 \ f 4 + i ( Oi b: I fi" if\Gk+1\ = 1, if | G f c + 1 | = 2, Therefore, flk(t,T) = e(«l) + | ± 1 i=k+i t(i Chapter 5. Grouping Policies 164 < I 2 f l l + ^ + I + M ' if 1 a 2 c \ 2 V ai p P ~ 1J if = 1; if |G*+i| = 2. Case 2: G f c = { 4 - 1 ,4}-Observe that 1 < tfk/tek-i < o, and tek+\/tik > p/b > b. We have two subcases: Case 2.1: j = 4 -flk(t,T) if i=k+l If 1 b C0 ' 2 l a 2 + ^ + a ^ + ^ T . 1 / 1 a 2 c \ 2 l a 2 + ^ + J + J^l if |G*+i| = l , if \Gk+1\ = 2, Case 2,2: j = 4 - 1. Because 1 < tek/tek-i < b and 0 < a 2 < by the inequality in Lemma 5.4.4, we have e (*'* a,*"1) - e (^)- B e c a u s e * G we have 0 ^ E T * E i=fc+2 i=k+2 a\G.\ < C_ pti-tk ~ p\Gk+i\ p _ 1' Therefore = e a 2- 1 £ t ' = J b+l a |gj| 1^ 4 . ^ 4 . ^ 1 4 . C \ 2\a2 + b + P + P-l) \ 1 f b a 2 a 2 c 2 U + T + jP + /5(/?-l), if | G f c + 1 | = l , if |Gj t + i | = 2. This completes our proof. • Chapter 5. Grouping Policies 165 Corollary 5.4.6 (Upper Bound on W(n,t,G(b))) Suppose G[b) is the grouping generated by heuristic Hb, and let Wp = min \ max gi(a1,a2,b) 0 < a x,a 2 < y/b, 1 < b < \ff3 \ . then W(n,t,G(b))<Wp. Theorem 5.4.7 (Upper Bound on Performance Ratio) The following is an upper bound on the average cost of worst case performance ratio of grouping policies: r* < inf PBW0 < 1.4480 - peN\{i} r p p -Proof. For any f3 £ N\ {1}, by definition of r* in Theorem 5.4.1, we have r*p = sup sup r(n, K,h,Cn) n€N (K,h)eB% min inf CGP{n, K, h, G, T) sup sup sup G^cn refill neN <6Hj LB{n,K,h) • f Cgp(n,jr,/\,G( 0),r) < sup sup sup mi ————— neN t€Rnp xeR^TeR^ LB\n,K,h) < sup sup W(n, t, G(b)) (by Lemma 5.4.2) neN teRp < Wp. (by Corollary 5.4.6) Therefore, by Theorem 5.4.1, we have r* < inf pp Wg ~ peN\{i} r p p Chapter 5. Grouping Policies 166 Table 5.1: Values of pp, Wp and r fi 1 0-1 r* < ppWp 2 < 1.6453 < 1.6785 3 T s t i "1-05105 < 1.4413 < 1.5149 4 4 1 ^ , - 1.08202 < 1.3540 < 1.4651 5 ^ m s - 1 - 1 H 4 8 < 1.3028 < 1.4480 6 T ^ i - 1-13924 < 1.2730 < 1.4503 7 - 116541 < 1.2625 < 1.4714 8 \7fci - 1 1 9 0 1 6 < 1.2529 < 1.4912 9 3, 4„ a -1-21365 < 1.2571 < 1.5257 In Table 5.1, we list the values of pp and the upper bounds on Wp and r* for fi = 2, ••• ,9 . From this table we get the best estimate from 0 = 5. More specif-ically, let 0 = 5, pp = 1.111478, ax = 0.7675, a2 = 1.2243, b = 2.2361. We have gx(ax,a2,b) = 1.3028, $r 2(ai,a 2,6) = 1.1768, g3(aua2,b) = 1.2881, gA{ax,a2,b) = 1.1622, ^ 5 ( a i,«2 , 6 ) = 1.2829, ^ 6 (ai ,a 2 ,6) = 1.2153. Therefore, Wp < 1.3028, and pp Wp < 1.4480. • 5.5 Lower B o u n d on the worst Case Performance R a t i o and B a d Examples In the previous section, we have established an upper bound 1.4480 on the worst case performance ratio r* of grouping heuristics. In this section, we give bad examples fol-lower bounds on r* and r*(n). We also get the exact value of r*(2). To begin with, we introduce a sufficient condition to check that the singleton grouping heuristic, where each group contains exactly one product, is a best grouping: Chapter 5. Grouping Policies 167 L e m m a 5.5.1 (Sufficient C o n d i t i o n s for O p t i m a l S ing le ton G r o u p i n g ) Suppose that (K,h) 6 (Mn, R+), and Ki+i - Kj hi+i . 2V*.- +i*.- " V^T' / ° ^ = l , 2 , . . . , n - l . ( 5- 5) Ze£ G s = {{1} , {2} , • • • , {«}} oe £/&e singleton grouping. Then Gs is an optimal grouping, i.e., CGP(n,K,h,Cn) = CGP(n,K,h,Gs), and (K,h) e £ln. Proof. We leave it as an exercise for the readers. O It is not difficult to show that the following Lemma holds: L e m m a 5.5.2 ( M o n o t o n i c i t y of r*(n)) r*(n) < r*(n + l ) < r * , Vn G 7V\{1}, and r* = l im r*(n). n — K X > Proof. Another exercise for the readers. • For n = 2, we have a closed form for r*(2). L e m m a 5.5.3 (Va lue of r*(2)) r*(2) = 1 ± M = 1.108741. Proof. By using differentiation and a few inequalities, we can show the Lemma holds. We omit the details and give an example which achieves the worst case performance ratio: (K,h) e (Mn,Rn+), tfo = 0, Chapter 5. Grouping Policies 168 Kx = 1, K2 = 2 / V / 3 + l , fca = 1, fc2 = 2 / v / 3 - l , then CGP{2,K,h,C2) = 2(l + l/V3), LB(n,K,h) = 2 ( l + 1 / \A /3 - 2/A/3~) , r*(2) = (7 + 3>/3) /ll. This completes the proof. Q For n > 2, we do not have a closed form expression for r*(n), but we have upper and bower bounds on r*(n). It is obvious that the upper bound 1.4480 on r* is also an upper bound on r*(n). The following example, which is a modification of an example appearing in Zheng [39] (1987), and independently found by the author, produces a lower bound on r*(n). E xa m ple . Let (K,h) £ (Mn,Rl), K0 = 0, Ki = 3\ hi = 3~\ for i = 1 , 2 , - - - , n - 1 , K = 2 -3"" 1 , h'n = 1/(8 -3"- 1 ) . Then iTi+i - 3 i + 1 - y 1 2y/Ki+1Ki 2V3 7 T T 3 r \/3 V K Kn — Kn-\ 1 / hn 1 for i = 1,2, • • •, n — 2, 2V'A rn#n-l 2V2 V By Lemma 5.5.1, C G P ( n , />, C") = CGP(n, K, h, Ga) = 2 £ = 2 [(n - 1) + 1/2], t=i Chapter 5. Grouping Policies 169 and (K,h) € fin. By Corollary 5.2.2, we have LB(n, K, h) = 2J2 y/(K< ~ Ki-i) k = 2 [l + (n - 2)^/2/3 + ^ /l/S j=i • L Let n-1/2 ri(n) n^/2/3 + ( l + y/2/4 - 2^/2/3)' then r*(n) > ri(n), Vn G JV\{1}. That is, r^n) is a lower Bound on r*(n). Let n —> 00, we get r* > is a lower bound on the performance ratio of grouping policies. 1.2247, which • Note that the lower bound given in this example is not tight, for n = 2: ri(2) 6 / ( 4 + y/2) = 1.10819 < 1.108741 = r*(2). Note that Zheng's example [39] (1987) with K0 = 0, K{ = 3*', h{ = 3 -*, for i 1, 2, • • •, n, produces a lower bound r2(n) = n l + (n- I)y/2JS' For all n > 2, we have rx{n) > r2(n) , i.e., the lower bound on r*(n) given by the example above is always strictly better than that given by Zheng's example for any finite n. However, r a (n) and r 2(n) have the same limit \j2/3, when n goes to infinity. In summary, the bounds on r* we have established herein are: \J2ji = 1.2247 < r* < 1.4480. 5.6 Conclusions Grouping policies have been widely used in real world for the simplicity of their im-plementation. If the setup cost function is separable, i.e., there is no saving on joint Chapter 5. Grouping Policies 170 replenishment, the grouping policy consisting of the EOQ solution for each product is the optimal and outperforms power-of-two policies. But when setup costs are not sep-arable, power-of-two policies can have the average cost lower than grouping policies by 20%, as shown in the example above. For the inventory model with network structure, some heuristics, such as integer-multiple lot size policies and integer-split lot size policies in Chapter 3, can be arbitrarily bad. Therefore, it is of interest to determine whether grouping policies can be arbitrarily bad or not. As the submodular setup joint cost is fairly general, and allows' the derivation of very tight bounds on the optimal cost, we limit ourselves to this case. In order to find the worst case performance ratio of grouping policies, we first intro-duce three reduction lemmas which reduce the space of problem instances from the sub-modular setup joint cost function to the 'maximum' submodular set function, which has only 0(n) variables. The minimization problem is then on a set of consecutive grouping policies, and can be solved by an 0{fi2) shortest path algorithm. This problem is much simpler than the original one defined on submodular joint setup cost functions. However, as a max-min problem, it is still too difficult to find the exact value of r* = sup r*(n) n because: (1) The objective function of this problem is neither quasi-concave nor quasi-convex in variables x and t. It has many local minima and maxima. Therefore, the classic convex analysis methods does not apply. (2) This problem is first to minimize on a set of consecutive grouping policies, then to maximize with respect to variables x and t. The problem cannot be solved by exchanging the max and min operators. (3) This problem also has many constraints, which further complicate the situation. Therefore, we use a different approach to estimate an upper bound on r*. we further reduce the search space from set Q.n to a subset of it — Bp, the set of 'root-of-/? path' Chapter 5. Grouping Policies 171 instances. Although the worst case performance ratio rp. of grouping heuristics over problem instances in Bp need not equal r*, it yields an upper bound on r*: r* < pprp. We construct a grouping heuristic Hb. An upper bound Wp on the performance ratio for the heuristic Hb is also an upper bound on r*p\ r*p < Wp for /? = 2,3, • • •. Finally, we use nonlinear programming to get upper bounds on Wp and therefore on r*: r* < 1.448. This means that the average cost given by the best grouping policy is within 44.8% of the optimal. This result can be easy to extend to the case with backlogging by establishing an equivalence between the backlogging and non-backlogging cases. 5.7 Appendix to Chapter 5 5.7.1 The Proofs of Lemmas in the Text Lemma 5.2.4 (Performance Ratio Rp(/30) for Power-of-/? Policies). For any fixed base period j30, let where t = ( i 1 ? t2, • • • , tn) is the optimal solution to (RJR). Then t* = (*i, ''' > *5 an optimal power-of-0 policy for (JR) with /30 fixed. The worst case performance ratio Rp(fio) of power-of-0 policies satisfies A Cp(n,K,h,f30) LB(n,K,h) Proof. The proof of the optimality of power-of-/? policies is the same as the proof for power-of-two policies, please refer to Queyranne [24] (1985) and Zheng [39] (1987). We do not repeat it here. Though the proof of the worst case performance ratio is also the same, we need the estimate value in the next lemma and therefore give a brief description in the following. Chapter 5. Grouping Policies 172 From the definition of £*, we have l o 4 = log; LWF I A) , 1 < Wl tJl Po ~ Po A> ' TP s I * & i.e., ^ £ Let = fr^W**^)!, for £ = l,2,---,o, then for all i G St\St-u because = *(£), we have t* = t*(£) and t(£)/t*(£) G [l///? , v7?) • Therefore, Cp{n,K,h,(lQ) = 2 E ^ / T O ) - ^ ( 5 M P W M ) e(J^j < LB(n,K,h) e(Jp) . This completes the proof. • Lemma 5.2.5 (Performance Ratio Rp of Power-of-/9 Policies). Let C/j(n, K,h) == inf C^(n, i f , / i , /30) oe £/ie optimal average cost of power-of-f3 policies for instance (K, h) of n-product. The worst case performance ratio Rp of power-of-(3 policies satisfies Rp= ^QMPo)= L B M h ) * Chapter 5. Grouping Policies 173 where pp = j——^ --y=~ is the upper bound on worst case performance ratio of grouping policies. Proof. Though the proof is exactly as in Roundy [28] (1985), we need the value of pp and thus repeat it below. Let rne = [log^^J , for £ = 1,2, then t(£) G [/3mt, /3mt+1). Let ^ = ^ ^ 7 2 » f a r / = l , 2 , - . . , g . then Qt e[l/s/P Let MA>) = — ^ = s , for £ = 1,2, • • • ,5, A) we have 1. if A> G [l/v^ , Qt], then [lo g / J = mt + 1. 2. if (30 G (Q/, V ? ) , then [\ogp ge(f30)\ = m<. Therefore, t*(£) = or r(£) A)/r< + 1 , i f ^ e A,/T<, i f / ? 0 G feuy/H), 1 v f e ' ^ O G ( Q „ ^ ) , d/30 Because / / ——-—- = 1, and i / V ^ Poln/3 > ft*(£)\ d/30 Chapter 5. Grouping Policies 174 h/yfi C\ Qt ) 0ohi0+Jq V* ( Po \ dpo e Qt \VPQiJ PolnP < v d y _ L f1/Ql i \ dy t o \ dPo ~ kj^ e W P W 1 ryfi ( 1 \npk/^\pl 1 0 - 1 Inp V ? ' we have Cp(n,K,h) min Cp(n,K,h,0o) Po€[l/y/i3,y/i3) < LB(n,K,k)±££. This completes the proof. • Lemma 5.3.1 (First Reduction). r*(n) = sup r(n,K,h,Vn). Proof. By theorem 5.2.1, for any K £ 5 n , there exist g distinct values t(l) < t(2) < • • • < t(q), and a nested path (S1,S2-) • • •, 5 g) in N with Sg\Se-i = {i £ TV | = i (•£)}, Chapter 5. Grouping Policies 175 = v ^ l ^ l S F ' i o T i = * ' 2 ' • • • ^ such that LB(n,K, h) •= 2 £ ^ ( ^ ) - ^(^-i)] where = 0. Now define a new set function K' : 2N i—• i ? + such that for all 5" C N, K'(S) = min { | 5 C Se, for * = 1,2, • • •, q] It is obvious that K'(S) is nondecreasing, that is, if S C T, then K'(S) < K'(T). Because /{'(.S) is nondecreasing, K'(S) > K(S), for all S C. N. Therefore, we have CGP(n,K',h,Vn) > CGP(n,K,h,Vn). It is easy to verify that all the conditions of theorem 5.2.1 hold for problem instance (K', h). Therefore, by K\St) = K(St), for £ = 1,2, • • •, q, we have LB(n, K', h) = 2j2 \/[K'(St) - tf'(S/_i)] h(SASe-i) = LB(n, K, h). Observe that 0 = S0 C Si C S2 C • • • C Sq = N and 0 = K(S0) < K(Si) < K(S2) < • • • < K(Sq) = K(N). If i G Sj\Sj-i, then, since K is non-decreasing, K\{i}) = min {K(Se) \ {i} C 5,, for £ = 1,2, • • •, q} = min K(Se) = K(S]). (5.6) ^€0,J+l,-,9} For any S Q N, let j = min{^ | 5" C 5^}, then there exists i G 5" fl (Sj\£'j_i). Therefore, by definition and equation (5.6), K'(S) = K(Sj) = K'({i}). However, {i} G 5" implies that K'({i}) < maxK'({k}) < K'(S). Therefore, we have K'(S) = maxK'({k}), for all SCN. Now let Iff = K'({i}), and we reorder the index set such that 0 < K[ < K2 < ••• < K'n, we have K'£ Mn. Therefore, for each K G Sn, there exists a K' G Mn such that r(n,K',h,Vn) = LB(n,K',h) Chapter 5. Grouping Policies 176 CGP(n,K',h,Vn) LB(n, K, h) = r(n,K,h,Vn), and we get sup r(n,K,h,Vn) > sup r(n,K,h,Vn). However, M.n C Sn implies the reverse inequality. Hence, we have sup r(n,K,h,Vn) = sup r(n,K,h,Vn). This completes the proof. • Lemma 5.3.2 (Consecutive Grouping of Three Products). If £3 > 6 > 0, 77!, 7/2,7/3 > 0, then \/i^2 + yf&iVi + y3) > min {1/6(771 + V2) + y/bva, s/izijli + V2 + Vs)} • Proof. By contradiction, if < min {\j£2(Vi + V2) + \ft3V~3, yf&ivi + V2 + ^3)} , then we have \/frl2 + yj&ivi +Vs) < y/tiim + 7/2) + yf&fr, (5.7) and \/£2V2~+ \f^3(vi + T/S) < \ /6 (77i + 7/2 + r/3). (5.8) From (5.7), we have 6772 + 6(7/1 + 7/3) + 2>/66772(7/i + 7/3) < 6(77i + 7/2) + 6773 + 2^66773(7/1 + 7/2), Chapter 5. Grouping Policies 177 and therefore, ( 6 - 6)>7i < (y/m{vi + V2) - \Jv2{m + 1/3)) • From (5.8), we have 6>72 + 6 ( » / l + ^3) + 2y/£}&»?2 (>/l +T / 3 ) < 6 ( 7 / ! + 7?2 + V73), and therefore, 2 ^ 6 6 0 / 1 + %) < ( 6 - 6 ) v ^ Combining these two inequalities and noticing the conditions of the Lemma, we have 2»/iv /66('7i + < 2 ^ ^ (y/v3(Vi + V2) ~ \Jm(vi + V^2 T?I\A7I + 773 < \Jr)3r)2(rix + n2) - rjiVVi + "3 (m + mWm + V3 < \/v3V2(m + m) m(m + V2 + vs) < o This contradiction completes our proof. • Lemma 5.3.3 (Consecutive Grouping Heuristics are Optimal). If(K,h) G {Mn,Rl), then CGP{n,K,h,Cn) = CGP(n,K,h,Vn). Proof. Because of Cn C T>n, we have CGP(n,K,h,Cn) > CGP(n,K,h,Vn). For the converse inequality, we show that, if (K,h) G (Mn, -R"), and partition G = (G i , G2, • • •, Gp) G £> n \C n , then CGP{n,K,h,G) > CGP{n,K,h,Vn) (5.9) Chapter 5. Grouping Policies 178 We prove (5.9) above by induction on n: Let £ 3 = K3, £2 = K2, « i = hi, n 2 = h2, r/3 = h3. Then inequality (5.9) follows from lemma 5.3.2 for the case of n = 3. Next, suppose inequality (5.9) holds for n in general. For any instance (K,h) G [Mn+1, i?+ + 1), let G = (G x , G2, • • •, Gp) be a partition of Ni = {1,2, • • •, n, n + 1} such that G ^ C n + 1 . To show that inequality (5.9) also holds, we consider two cases: Case 1: If there is at least one group in G containing two consecutive indices j, j' + 1, then we define (K1, h') G (Ain, i?") by combining j and j + 1 together, i.e., let if- = JC', M = A t , for j = 1, 2, • • •, j - 1; •^j = ^ J ' + i ' ^ = h3 + M+i'> /f- = Ki+i, h'i = hi+i, for i = j + 1, j + 2, • • •, n. We also define partition G ' = (G[, G'2, • • •, G^) of N by letting, for i = 1,2, • • • ,p, G'i = {m : m G G;,ra < j}\J{m : m + 1 G G t-,m > j + 1} . Every grouping of n-product for (K1, h') induces a grouping of n + 1-product for (K, h) with the same cost. Therefore, CGp{n + l,K,h,Vn+1) < CGP{n,K',h',Vn). It is obvious that CGP{n + l,K,h,G) = CGp{n,K',h',G'). Note that G g Cn+1 implies G' (£Cn, and (if ' , /i') G ( . M n , by the induction we have: CGP(n,K',h',G') > CGP(n,K',h',Vn). The last three inequalities imply inequality (5.9) for n + 1. Chapter 5. Grouping Policies 179 Case 2: If there is no group in G which contains consecutive indices, let group Gp contain product n + 1. There are two subcases to consider: Case 2.1: Group Gv contains only one product, i.e., Gv = {n + 1}. Since partition G £ Cn+1, partition G' = ( G 1 ( • • •, Gp_i) Cn. Let (K',ti) denote the restriction of (K, ti) to production set N = {1,2, • • •, n). By induction, we have CGp(n, K', ti, G') > CGP(n,K',ti,Vn). Note that CGp(n + 1, K, h, G) = 2^Kn+1hn+1 + CGP(n, K', ti, G% and CGP(n, K', ti, Vn) + 2 y ^ +i^n+i > CGp{n + l,K,h,Vn+1). We get that inequality (5.9) holds for n + 1. Case 2.2: Group Gp contains more than one product, but does not contain product W.l.o.g, suppose n 6 G p _ i . To apply Lemma 5.3.2, let £ 3 = Kn+x = K{GP), £2 = Kn = K{Gp-x) = K(GP-X U G ; ) , J/X = /*(Gp) > 0, r;2 = h{Gp-x) > 0, r/3 = h(Gp) > 0. It is easy n. (Otherwise, Case 1 applies.) Let G'p = Gp\ {n + 1}: we have G'p ^ <p, and n ^ G p . to verify that the conditions of Lemma 5.3.2 hold. Therefore, min < > . k yjKn+xKGp[jGp-x) Let G' (Gx, G 2 , • • •, G p _ 2 , Gp-x U Cpi {n + I}), G in (Gx,G2 Then we have CGp(n + l,K,h,G) > minlc G P (n + l,K,h,G'), CGP(n + \,K,h,G") As G' fits Case 2.1, we have CGP{n + l,K,h,G') > CGP{n + l,K,h,Vn). As G" fits Case 1, we have CGp(n + l,K,h,G") > CGP(n + l,K,h,Vn). Chapter 5. Grouping Policies 180 The last three inequalities imply inequality (5.9) for n + 1, and this completes the proof. • L e m m a 5.3.5 ( T h i r d Reduct ion) . The worst case performance ratio of consecutive grouping heuristics for all problem in-stances (K,h) G H n is r*(n), i.e., r*{n) = sup r{n,K,h,Cn) (K,/i)enn v sup fc=l t=l wh ere Gk = {4-i + !,-••, 4} hGk = for p = 1,2,- •• ,p. Proo/. The inequality sup r(n,K,h,Cn) < r*(n) follows from C ( . M n , i ^ ) . For the converse inequality, suppose (K,h) £ (A4™, i2+). By Theorem 5.2.1, there exists a nested path (Si, S2, • • •, Sq) such that LB(n,K,h) = 2 £ v t o 5 * ) - ^ (&-i ) l HSt\Se-i) and t(£) = ^ ( ^ ) - i T ( 5 , _ i ) ] / M 5 A ^ - i ) , with *(1) < t(2) < Define a g-product problem instance (q,K', h') by • < t(q). max i i ^ h'e = h(St\St-i) for £ = 1, 2, • • •, q, and V 5 C { l , 2 , - , g } . Chapter 5. Grouping Policies 181 It is obvious that (K',ti) G By lemma 5.3.2, we have LB(q, K', ti) = 2j^ y/[K'e - KU\ h'e = LB(n, K, h). Because each grouping policy in Cq with problem instance (K', h') corresponds a grouping in Cn with problem instance (K, h) having the same average cost, we have CGP(q,K',h',C«) > CGP(n,K,h,Cn). Therefore, r(q, K',ti ,Cq) > r(n,K,h,Cn), that is, for any (K,h) G (Mn,R%), we have sup sup r{q,K",h",Cq) > r(n,K,h,Cn), q<n (K",h")eQn which implies the requisite inverse inequality, and completes the proof. Q Theorem 5.4.1 (Upper Bound on Performance Ratio of Grouping Policies). Let r*g = sup sup r(n,K,h,Cn) be the performance ratio of consecutive grouping pol-icy for the 'root-of-fl paths' instances, then the worst case performance ratio of grouping policies r* satisfies: "* < inf pa r*0. Proof. By Lemma 5.2.5, for any (K,h) G {Mn,Rn+), there exist p0 G [ l / / / ? , yfp) and a power-of-/? policy associated with a nested path (5i , S2, • • •, 5",) with base period Po, such that Cf}(n,K,h,p0) < ppLB(n,K,h), where C3(n,K,h,P0) = ± { K ( S i ) - * { S ' - X ) + fc(SA&-i) **(*)} , LB[n,K, h) = 2 £ y/[K(St) - K(S^)} h(Se\S^), e=i Chapter 5. Grouping Policies 182 for £= 1,2, •••,q: t(t) = \ t*(£) = PoPnt, ni G Z, with m < n2 < • • • < nq, t* = t*(£), iiieSe\Se-u Note that the consecutive inequalities between {n x ,n 2 , • • •,nq} are not strict. In the following we define a problem instance (K', h') G B30 by putting all products with the same replenishment time t* into a same group. Suppose n 2, • • •, nq} take j different values, i.e., let ( r i , r 2 , • • •, rj) satisfy nr f c_!+i = 1 •" = " i - * , for fc = 1,2,-• •, j , n r f c < n r f c + 1 , for fc = 1,2, • • • J - 1, where r0 = 0, rj = q. We recursively define S'k by letting S 0 = 0, S'k\S'k-i = Srk\Srk_1+ifork = l,2,---,j. Partition {S[, S'2,---, Sj j has the following properties: 1. [S[, S2, • • •, Sj} forms a nested path. 2. t7 = t*(rfc) = / 3 o ^ * , i f i e 5 i \ 5 i _ 1 . 3. Note also that KiS'J-KiSU) U (St\St-x), f = r * _ i + l f ; M $ \ S / - I ) Chapter 5. Grouping Policies 183 4. t*(k) = K(S'k) - KiSU) e l/\/PjP )t*(rk),iork = l,2,---,j. This follows from property 3 and £ [l jyjfi , \fP^t*(rk), f ° r ^ = + 1, * • •, r^, we have this property. 5. C0(n, K, h, ft) > 2 £ y/mS'J-KiSUyhiSASU). k=i Indeed, by properties 2 and 4, we have: Ce{n,K,h,pQ) = £ { K{S'k\:^S'k-l) + HS'AS'^) r ( r f c ) | > 2 E y/[K(S'k) - K(SU)] KS'^SU)-Now we define a j»'-product instance (K', h') of the joint replenishment problem by letting K'k = K(S'k), K'(S) = maxkGSK'k, for all 5 C N, and ^ = M ^ N ^ - i ) . f o r * = 1,2, • • • , j . Instance (K', h') has following properties. 1. (K',h') e [M\R\). 2. (IC, h') £ H£. By property 4 of partition ^S[, S'2, • • •, Sj}, we have, for k = 1, 2, • • •, j: t'(k) = = t * ( k ) e [ i / > , ^ ) / ? 0 r s where K'0 = 0, all n r ( [ £ Z and n n < n r 2 < • • • < nrj. 3. LB(j,K',h') < p0LB(n,K,h). Indeed, by Corollary 5.2.2, property 5 for partition {S[, S'2, • • • , S'j} and Lemma 5.2.5: LB(j,K',h') = 2 E yJ{K'h - KU) K k=i Chapter 5. Grouping Policies 184 = 2E/TO-m-1p(m-1) fc=i < Cp(n,K,hJ0) < p0LB(n,K,h). 4. CGp(n,K,h,Cn) < CGP(j,K',h',Cn). Because to each grouping for j-product instance (K', ti) corresponds a grouping for n-product instance {K, ti) with the same average cost. Based on these properties, for any (K, ti) G (Mn, there exist j < n and (K', ti) € B such that 3 CGP(j,K>,ti,Cn) r(j,K',ti,Cn) = > LB(j,K>,h>) CGP(n,K,h,Cn) ppLB(n, K, ti) — r(n,K,h,Cn) Therefore, for any (K,h) <E (Mn,R\), maxr(j,Bn0,Cn) > —r(n,K,h,Cn) 3<n pa m a x r ( j , £ " C " ) > — sup r(n,K,h,Cn) J-n Pp {K,h)e(Mn,R1) PpRB > R • This completes the proof. • Lemma 5.4.4 If 1 < U < b and 0 < a2 < Vb, then we have 6 ( a 2 ) ~ e ( a 2 / ' Chapter 5. Grouping Policies 185 Proof. Considering e(^") a s a function of y, we know that e(^") achieves its minimum at y = a2. If y > 02, e(^") increases as y increases. If y < 02, e ( ^ ) increases as y decreases. We have the following two cases: Case 1: 0 < a 2 < 1. As y > 1 > a2, e{jt~) achieves its maximum at y = b. Therefore e(y/a2) < e(b/a2). Case 2: a2 > 1. There are two subcases: Case 2.1: a2 < y < b. e ( a 2 " ) a c n i e v e s ^s maximum at y = b. Therefore e(y/a2) < e(b/a2). Case 2.2: 1 < y < a2. achieves its maximum at y = 1. Therefore e(y/a2) < e(l/a2) = e(a2) < e(b/a2). The last inequality holds because 1 < a2 < 6/a2-That is, e(y/a2) < e(b/a2) holds for all cases. • 5.7.2 Notation The followings are the collection of notation arranged in lexicographic order. k ak = 0 , for any a, by convention. i=M-l mi(/30) < m 2(/? 0) < • • • < mn(P0), for some /?„ G [ l / / ? , y^) , is the set of 'root-of-/? paths'. Note that m,(/?0) He iKi - Ki-x A,- A) , Vi. CQP{TI, K, h, Cn) = min CGP(W , i f , h, G) is the optimal average cost of consecutive group-ing heuristics. Chapter 5. Grouping Policies 186 CGp(n, K, h, T>n) = Ccp{n, K, h, G) is the optimal average cost of grouping policies for n-product instance (K,h). CGp(ni K-i h, G) = inf C(jp(n, K, h, G, T) is the optimal average cost of grouping pol-l<3 icy G. I K{Gi) CGP(n,K,h,G,T) = E J H ^ + h(G,)TJ. Cn = the set of all consecutive partitions on N ~K(Ui) - AT(A-i) Cg(n,K,h,/30) = min E i=l L -\- hai tai s.t. u = pmi ft, m,- e Z , Vi e /Y and the £/'s are defined by (5.1b). where a satisfies (5.1a) Cp{n, K, h) — min Cp(n, K, /i, ft) is the optimal average cost of power-of-/? policies for A)>o n-product instance (K,h). T>n = the set of all partitions on N. e(x) = - (x H — ^ , for x £ is the "effectiveness function". 2 V xj / i*(* .r)= e ( - f ) - f i E ^ , Vj = 1,2, . - . .IGI, G = {Gi, G2, • • •, Gp} is a grouping of N. \G\ = p is the cardinality of set G. g(G{) == 2 \JK(Gi) h(Gi) is the optimal average cost of group G,-. M^) = E *^ *s ^ n e holding cost rate for any set S C. N. Chapter 5. Grouping Policies 187 LB(n, K,h) = minE t>o . 1 »=i K(Ut) - K(U^) is the lower bound on all feasible ten policies. Note that a satisfies (5.1a) and the U-s are defined by (5.1b). 0 < Ki < K2 < • • • < Kn, (non-decreasing) K : 2N ^ R + denotes the set of K(S) = maxKi, WS C N, (maximum) 'maximum' submodular set functions on N. Note that Ki = K({i}) Vi 6 N. N = {1,2, • • •, n} is the set of products. N = {1,2, 3, • • •} is the set of natural numbers. r(n, K,h,Cn) = ^°rn/—Is i^ x ^ * s ^ n e optimal performance ratio of optimal consecu-t i o n , K, h) tive grouping policies for n-product instance (K, h). r(n, K, h, Vn) = ^ '—' ' —- is the optimal performance ratio of optimal grouping LB{n, K, h) policies for n-product instance (K, h). r(n,K,h,G) = — ' — ' ' ^ is the performance ratio of grouping policy G f o r n-LB(n, K, h) product instance (K,h). r(n, K, h, G, T) = —G P^ \—' ' '—- is the performance ratio ratio of grouping policy LB{n, K, h) G with replenishment period vector T for n-product instance (K, h). r* = sup r*(n) is the worst case performance ratio of grouping heuristics. n€N r*(n) = sup r(n, K,h,T>n) is the worst case performance ratio of the grouping (K,h)e(S",Rl) heuristics for n-product. r*n = sup sup r(n, K, h, Cn) is the worst case performance ratio of consecutive g r O U p -n e N (K,h)eB% ing heuristics over problem instances (K, h) 6 Bp — 'root-of-/? paths'. Chapter 5. Grouping Policies 188 Rp is the worst case performance ratio of power-of-/3 policies with base period PQ fixed. Rp is the worst case performance ratio of power-of-/? policies with variable base period (30. R+ (0, oo) is the set of positive real numbers. A 71 R+ = x R+ is the set of n-dimensional positive real numbers. i=i i2< = {t E R+ \ tx < t2 < • • • < tn} is the 'monotone cone' in R\. "h(/?0) < m2(P0) <•••< mn(p0), for some f30 G [l/VP VP Rnp= { t G R% • is the 'root-of-/? cone'. Note that , Vi. denotes the set of K(<j>) = 0; K(S) > 0, and K(N) > 0 (non-negativity); A" : 2 " ^ R+ K(S) < K(T), \iSQT (non-decreasing); K(S n T) + J f (5 (J T) < K(S) + K{T), VS, T C jV (submodularity) submodular set functions on N. (Si, S2, • • •, Sq) is the Nested path of N satisfying 0 C Si C S2 C • • • C Sq = N. t = (ti, t2, • • •, tn) is the replenishment time vector of a power-of-/? policy. t* H pop[l°S0(^)\, Vi G N, is an optimal power-of-^ policy to (JR) with p0 fixed. Note that t = (ti,t2, •••,£„) is the optimal solution to (RJR). T = (Ti, T2, • • •, Tp) is the replenishment period vector of grouping G. Chapter 5. Grouping Policies 189 T* = yjK{Gi)lh(Gi) is the optimal replenishment period of group Gi. A T* = (T-j*, T 2 , • • •, T*) is the optimal replenishment period vector of grouping G. W(n,t,G)= inf max fjk(t,T). TeR] |G| ieak + fc=l,2,.-.,|G| Wp = min < max gi(ai, a 2 , 6) 0 < ax,a 2 < Vb, I < b < Jf3 \ ai,a2,b (.«=!,—.6 , v J Z = {0, ± 1 , ± 2 , • • •} is the set of integers. pp = - — „ is the upper bound on worst case performance ratio of power-of-/? poli-cies. nn = \(K,h) € (-M n,i^) -7-^ - < \ — < • • • < \ — ^ — : — — - 1 denotes the set «i V ^2 V "n I of 'monotone path' instances. Note the strict inequalities in the definition. 5.7.3 Performance Ratios of Power—of— /3 Policies Table 5.2: Performance Ratios of Power-of-/? Policies Fixed. Base Period Variable Base Period 0 1 1.06066 \/2"ln2 = 1.02014 1.15470 %/31n3 = 1.05105 1.25000 4 In 2 1.08202 1.34164 4 \/51n5 5 = 1.11148 1.42887 = 1.13924 1.51186 ~ J 3 = 1.16541 1.59099 \/81n8 1.19016 1.66667 3 In 3 1.21365 10 1.73925 1.23602 Bibliography [1] F . Andres and H . Emmons. "On the Optimal Packaging Frequency of Products Jointly Replenished". Management Science, 22, No. 10:1165-1166, June 1976. [2] S. Anily. "Integrating Inventory Control and Transportation Planning". PhD thesis, Columbia University, 1986. [3] D. R. Atkins and P. Iyogun. "A Lower Bound on a Class of Coordinated Inven-tory/Production Problems". Operations Research Letters, 6, No. 2:63-67, May 1987. [4] A . K . Chakravarty, J . B. Orlin, and U . G. Rothblum. "A Partitioning Problem with Additive Objective with an Application to Optimal Inventory Groupings for Joint Replenishment". Operations Research, 30, No. 5:1018-1022, September-October 1982. [5] A . K . Chakravarty, J . B . Orlin, and U . G. Rothblum. "Consecutive Optimizers for a Partitioning Problem with Applications to Optimal Inventory Groupings for Joint Replenishment". Operations Research, 33, No. 4:820-834, July-August 1985. [6] W. B . Crowston, M . H . Wagner, and A. Henshaw. "A Comparison of Exact and Heuristic Routines for Lot Size Determination in Multi-Stage Assembly Systems,". A HE Trans., 4:313-317, December 1972. [7] A . Federgruen, M . Queyranne, and Y.-S. Zheng. "Simple Power of Two Policies are Close to Optimal in a General Class of Production/Distribution Networks with Gere-nal Joint Setup Costs". Working Paper 89-MSC-012, Columbia University Graduate School of Business, University of British Columnbia, and Warton School University of Pennsylvania, August 1989. [8] A . Federgruen and Y.-S. Zheng. "Minimizing Submodular Set Functions: Efficient Algorithms for Special Structures with Applications to Joint Replenishment Prob-lems". Research Working Paper No. 87-6, Columbia University Graduate School of Business, and Warton School University of Pennsylvania, June 1988. [9] S. K . Goyal. "Comment on ' A Dynamic Programming Algorithm for Joint Re-plenishment Under General Order Cost Functions'". Management Science, 33, No. 1:151-153, January 1987. [10] S. K . Goyal and A . T. §atir. "Joint Replenishment Inventory Control: Deterministic and Stochastic Models". European Journal of Operations Research, 38:2-13, 1989. 190 Chapter 2. Optimal Inventory Policies 191 [11] D. Gusfield, C. Martel, and D. Fernandez-Baca. "Fast Algorithms for Bipartite Network Flows,". SI AM Journal of Computing, 16, No. 2:237-251, Apri l 1987. [12] R. Hassin and N . Megiddo. "Exact Computation of Optimal Inventory Policies over an Unbounded Horizon". Working paper, Tel Aviv University, Israel, School of Mathematical Sciences, Aviv University, Tel Aviv 69978, Israel, October 1989. [13] P. Jackson, W. Maxwell, and J . Muckstadt. "The Joint Replenishment Problem with a Power-of-Two Restriction". HE Transactions, 17, No. 1:25-32, March 1985. [14] P. Jackson and R. 0 . Roundy. "Constructive Algorithms for Planning Production in Multi-Stage Systems with Constant Demand". Technical Report 632, School of Operations Research and Industrial Engineering College of Engineering Cornell University, Ithaca, New York 14850, August 1985. [15] P. Jackson and R. 0 . Roundy. "Minimizing Separable Convex Objectives on Ar-bitrarily Directed Trees of Variable Upper Bound Constraints". Technical Report 767, School of Operations Research and Industrial Engineering College of Engineer-ing Cornell University, Ithaca, New York 14853-7501, January 1988. [16] W. L. Maxwell and J . A . Muckstadt. "Establishing Consistent and Realistic Re-order Intervals in Production-Distribution Systems". Operations Research, 33, No. 6:1316-1341, November-December 1985. [17] W. L. Maxwell, J . A . Muckstadt, P. L. Jackson, and R. O. Roundy. "Production-Distribution Systems Inventory Planning (SIP): Rationale, Economics and Reali-ties". Technical Report 659, School of Operations Research and Industrial Engi-neering College of Engineering Cornell University, Ithaca, New York 14850, M A Y 1985. [18] J . S. B . Mitchell. "98%-Effective Lot-Sizing for One-Warehouse Multi-Retailer Inventory System with Backlogging". Operations Research, 35, No. 3:399-404, May-June 1987. [19] P. J . Moily. "Optimal and Heuristic Lot-Sizing Procedures for Multi-Stage Manu-facturing Systems". PhD thesis, University of Wisconsin, 1982. [20] P. J . Moily. "Optimal and Heuristic Procedures for Component Lot-Splitting in Multi-Stage Manufacturing Systems". Management Science, 32, No. 1:113-125, January 1986. [21] J . A . Muckstadt. "A Model for a Multi-Item, Multi-Echelon, Multi-Indenture Inventory System". Management Science, 20, No. 4, Part 1:472-481, December 1973. Chapter 2. Optimal Inventory Policies 192 [22] J . A . Muckstadt and R. O. Roundy. "Multi-item, One-warehouse, Multi-retailer Distribution Systems". Management Science, 33, No. 12:1613-1621, December 1987. [23] J . A . Muckstadt and R. 0. Roundy. "Analysis of Multistage Production Systems". Technical Report No. 806, School of Operations Research and Industrial Engineering College of Engineering Cornell University, Ithaca, New York 14850, July 1988. [24] M . Queyranne. " A Polynomial-Time, Submodular Extension to Roundy's 98%-Effective Heuristic for Production/Inventory Systems,". Working Paper No. 1136, University of British Columbia, Faculty of Commerce, August 22 1985. [25] M . Queyranne. "Comment on ' A Dynamic Programming Algorithm for Joint Re-plenishment Under General Order Cost Functions'". Management Science, 33, No. 1:149-151, January 1987. [26] M . J . Rosenblatt and M . Kaspi. " A Dynamic Programming Algorithm for Joint Replenishment under General Order Cost Functions". Management Science, 31, No. 3:369-373, March 1985. [27] R. 0. Roundy. "94%-Effective Lot-Sizing in Multi-Stage Assembly Systems". Tech-nical Report No. 674, School of Operations Research and Industrial Engineering Col-lege of Engineering Cornell University, Ithaca, New York 14850, September 1983. [28] R. O. Roundy. "98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse M u l t i -Retailer Systems". Management Science, 31. No. 11:1416-1430, November 1985. [29] R. 0. Roundy. "Rounding off to Powers of Two in the Economic Lot Scheduling Problem". Technical Report No. 663, School of Operations Research and Industrial Engineering College of Engineering Cornell University, Ithaca, New York 14850, July 1985. [30] R. 0. Roundy. "A 98%-Effective Lot-Sizing Rule for a Multi-Product, M u l t i -Stage Production/Inventory System". Mathematics of Operations Research, 11, No. 4:699-727, November 1986. [31] R. O. Roundy. "Computing Nested Reorder Intervals for Multi-Item Distribution Systems". Technical Report No. 751, School of Operations Research and Industrial Engineering College of Engineering Cornell University, Ithaca, New York 14850, August 1987. [32] R. 0. Roundy. "Rounding off to Power of Two in continuous Relaxations of Capaci-tated Lot Sizing Problems". Management Science, 35. No. 12:1433-1442, December 1989. Chapter 2. Optimal Inventory Policies 193 [33] L . B . Schwarz. "A Simple Continuous Review Deterministic One-Warehouse N -Retailer Inventory Problem". Management Science, 19, No. 5:555-566, January 1973. [34] L. B . Schwarz and L. Schrage. "Optimal and System-Myopic Policies for M u l t i -Echelon Production/Inventory Assembly Systems". Management Science, 21, No. 11:1285-1294, July 1975. [35] E. A . Silver and R. Peterson. "Decision Systems for Inventory Management and Production Planning". John Wiley and Sons, Inc., New York, 1985. [36] A . Z. Szendrovits. "Manufacturing Cycle Time Determination for a Multi-Stage Economic Production Quantity Model". Management Science, 22, No. 3:298-308, November 1975. [37] A . Z. Szendrovits. "Comments on the Optimality in 'Optimal and System Myopic Policies for Multi-Echelon Production/Inventory Assembly Systems'". Management Science, 27, No. 9:1081-1087, September 1981. [38] H . M . Wagner and T. M . Whitin. "Dynamic Version of the Economic Lot Size Model". Management Science, 5:89-96, 1958. [39] Y. -S . Zheng. "Replenishment Strategies for Production/Distribution Networks with General Joint Set-Up Costs". PhD thesis, Columbia University, 1987.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Structured policies for complex production and inventory...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Structured policies for complex production and inventory models Sun, Daning 1990
pdf
Page Metadata
Item Metadata
Title | Structured policies for complex production and inventory models |
Creator |
Sun, Daning |
Publisher | University of British Columbia |
Date Issued | 1990 |
Description | For inventory models minimizing the long-run average cost over an infinite horizon, the existence of optimal policies was an open question for a long time. Consider a deterministic, continuous time inventory system satisfies the following conditions: the production network is acyclic, the joint setup cost function is monotone, the holding cost and the backlogging cost rates are nonnegative, the demand rates are constant over time, the production rates are infinite or finite non-increasing, and backlogging may be allowed or not. For this very general extension of the Wilson-Harris EOQ model, we prove the existence of optimal policies. Very few properties of optimal policies have been discovered since the 1950's. Restricting the above inventory model to infinite production rates, we present some new properties of optimal policies, such as the Latest Ordering Property, and explicit expressions for echelon inventories and order quantities in terms of ordering instants. An assembly production system with n facilities has a constant external demand occurring at the end facility. Production rates at each facility are finite and non-increasing along any path in the assembly network. Associated with each facility are a set-up cost and positive echelon holding cost rate. The formulation of the lot-sizing problem is developed in terms of integer-ratio lot size policies. This formulation provides a unification of the integer-split policies formulation of Schwarz and Schrage [34] (1975) and the integer-multiple policies formulation of Moily [20] (1986), allowing either assumption to be operative at any point in the system. A relaxed solution to this unified formulation provides a lower bound to the cost of any feasible policy. The derivation of this Lower Bound Theorem is novel and relies on the notion of path holding costs, a generalization of echelon holding costs. An optimal power-of-two lot size policy is found by an 0(n³ log n) algorithm and its cost is within 2% of the optimum in the worst case. Mitchell [18] (1987) extended Roundy's 98%-effectiveness results for one-warehouse multi-retailer inventory systems with backlogging. We extend this 98%-effectiveness result for series inventory systems with backlogging. The nearly-integer-ratio policies still work. The continuous relaxation provides a lower bound on the long-run average cost of any feasible policy. The backlogging model is also reduced in 0{n) time to an equivalent model without backlogging. Roundy's results [27] (1983) are then applied for finding a 98%-effective backlogging policy in O(nlogn) time. In an EOQ model with n products, joint setup costs provide incentives for joint replenishment. These joint setup costs may be modelled as a positive, nondecreasing, submodular set function. A grouping heuristic partitions the n products into groups, and all products in the same group are always jointly replenished. Each group is then considered as a single "aggregate product" being replenished independently of the other groups, and therefore according to the EOQ formula. As a result, possible savings when several groups are simultaneously replenished are simply ignored. Our main result is that the cost of the best such grouping solution cannot be worse than 44.8% above the optimum cost. Known examples show that it can be as bad as 22.4% above the optimum cost. These results contrast with earlier results for power-of-two policies, the best of which never being worse than about 2% above the optimum cost. |
Subject |
Inventory control -- Mathematical models |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-01-31 |
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.0100417 |
URI | http://hdl.handle.net/2429/31002 |
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_1990_A1 S86.pdf [ 9.23MB ]
- Metadata
- JSON: 831-1.0100417.json
- JSON-LD: 831-1.0100417-ld.json
- RDF/XML (Pretty): 831-1.0100417-rdf.xml
- RDF/JSON: 831-1.0100417-rdf.json
- Turtle: 831-1.0100417-turtle.txt
- N-Triples: 831-1.0100417-rdf-ntriples.txt
- Original Record: 831-1.0100417-source.json
- Full Text
- 831-1.0100417-fulltext.txt
- Citation
- 831-1.0100417.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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0100417/manifest