ESSAYS IN INVENTORY CONTROL By Kaan K . Katircioglu Sc. (Industrial Engineering) Bogazici (Bosphorus) University, 1986 M . Sc. (Statistics) Simon Fraser University, 1989 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E DEGREE OF D O C T O R OF PHILOSOPHY in T H E FACULTY OF GRADUATE STUDIES FACULTY OF COMMERCE AND BUSINESS ADMINISTRATION (MANAGEMENT SCIENCE / TRANSPORTATION AND LOGISTICS) We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA May 17, 1996 © Kaan K . Katircioglu, 1996 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. CO < N \ V s / v ^ ^ C L ^ Department of ^ ^ i M ^ r V O A A , W \ S ^ A T v O * M The University of British Columbia Vancouver, Canada Date t W * W , M9t DE-6 (2/88) Abstract This thesis studies four important problems faced in the theory of inventory control. The first chapter addresses the issue of calculating optimal inventory policies in stochastic inventory problems, when unknown demand parameters are estimated from a sample of demand observations. A general framework for combining estimation and optimization problems is developed for a class of inventory problems when the demand distribution belongs to the scale-location family. The results show that biasing the scale parameter estimates gives better inventory policies for both cost minimization and service achievement objectives. The second chapter studies a periodic review, single-product, single facility inventory problem with multiple customer classes, each requiring a different service level. Customer demands are random and independent with a stationary probability distribution. The objective is to find a stock allocation policy among the customers and an inventory re-plenishment policy so as to achieve target customer service levels with minimum possible inventory holding cost. An easy-to-calculate myopic heuristic allocation-order policy is developed and its performance is tested through simulation. The third chapter finds an optimal inventory policy for a classical single-stage, single-product, unit demand, continuous review inventory problem where the interdemand times are independent identically distributed random variables with increasing failure rate. Unmet demand is fully backlogged and orders arrive after a lead time. The costs of backlogging and inventory carrying are linear. The objective is to minimize the long run average cost. If there is no fixed cost for placing an order, it is proven that a Delay ed-(s-l,s) policy is optimal. In case of a fixed order cost, a Delayed-(s,S) policy is proven to ii be optimal. In chapter four, the same problem as in chapter three is studied for a Poisson demand in the case of lost sales. No fixed cost for placing an order is assumed. For this problem, an optimal policy is unknown and it is commonly believed that an (s-l,s) policy is sufficiently good. A new heuristic policy is suggested as an alternative, which uses more information, but is myopic in nature and its performance is compared with that of (s-l,s). 111 Table of Contents Abstract ii List of Tables vii List of Figures viii Acknowledgement ix Dedication x Introduction 1 1 Improving Traditional Inventory Policies Through Biased Estimation 6 1.1 Introduction 7 1.2 Inventory Models 11 1.2.1 Newsboy Problem 12 1.2.2 A Base-Stock Model 12 1.2.3 {Q,r) Model With Fixed Q 13 1.3 A n Alternative to the Traditional Approach 14 1.3.1 Unconstrained Case 14 1.3.2 Constrained Case 17 1.4 Scale-Location Family 18 1.4.1 Normal Demand Case 22 1.4.2 Gamma Demand Case 26 iv 1.5 (Q,r) Model with Normal Daily Demand 30 1.6 Conclusions and Remarks 33 2 Managing Inventory for Mult iple Customers 36 2.1 Introduction 37 2.2 A Newsboy Example 40 2.3 A Finite Horizon Periodic Review Problem 43 2.3.1 Cost Minimization with Quadratic Backlog Costs 46 2.3.2 Holding Cost Minimization with Service Constraints 51 2.4 Infinite Horizon Problem with Service Constraints 56 2.4.1 A Heuristic for the Infinite Horizon Service Problem 59 2.4.2 A Simulation Study . . ' 60 2.5 Conclusions and Remarks 66 3 New Optimal Policies for A Unit Demand Inventory Problem 70 3.1 Introduction : 71 3.2 A New Optimal Policy 76 3.2.1 Single Demand Case 77 3.2.2 Case of N Demands 81 3.2.3 Infinite Horizon Case 86 3.3 An Example with Normal Interdemand Times 87 3.4 The Inventory Problem With Fixed Order Cost 91 3.5 An Example with Normal Interdemand Times 100 3.6 Conclusions and Remarks 102 4 A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 106 4.1 Introduction 107 v 4.2 A Heuristic 110 4.3 Simulation Results 122 4.4 Conclusions and Remarks 126 A Appendix for Chapter 1 130 A. l Proofs for Chapter 1 130 B Appendix for Chapter 2 134 B. l Solution of the Relaxed Problem 134 B.2 Calculation of the Optimal Order Policy for the Relaxed Cost Problem . 135 Bibliography 137 v i List of Tables 1.1 The value of optimal bias for normal distribution 25 1.2 The value of optimal bias for gamma distribution 28 1.3 The effect of biasing on the cost for (Q,r) model. i?i(2): % reduction in controllable (total) cost 31 1.4 The effect of biasing on the service for (Q,r) model 32 2.1 Heuristic performance for moderate service industry (L = 6) 64 3.1 An example: Interdemand times are Normal(10,1), and K = 10 101 4.1 Results of simulation (LOW lost sales cost per unit) 124 4.2 Results of simulation (HIGH lost sales cost per unit) 125 vn List of Figures 2.1 Attainable service levels by linear costs in a 2-customer newsboy problem. 42 2.2 The performance of the heuristic (2-customer problem) 67 2.3 The performance of the heuristic (5-customer problem) 68 2.4 The performance of the heuristic (10-customer problem) 69 3.1 A comparison of Delayed-(s-l,s) and (s-l,s) for normal interdemand times. 89 3.2 Delayed-(s,S) versus (s,S) for normal interdemand times (K = 3) 103 3.3 Delayed-(s,S) versus (s,S) for normal interdemand times (K = 10) 104 4.1 An illustration of the effect of pipeline inventory arrival schedule I l l 4.2 A n illustration of the myopic heuristic. 116 4.3 A comparison of the heuristic and the one-for-one policy 127 vm Acknowledgement My deep appreciation and thanks to my supervisor Professor Derek Atkins for his con-tinuous support, especially at times I desperately needed it. I enjoyed being his student and received invaluable benefits from his experience and insight. My special thanks to Professor Martin Puterman for his help in my thesis and for the consulting research op-portunity he gave me during my study. I would like to thank Professor Garland Chow for the ideas he raised during the development of this thesis and for his effective lectures which had an influential role in my career objectives. Finally, I would also like to thank Professor Hong Chen for his help and Professor Maurice Queyranne for his remarks and for bringing some important references to my attention during the developmenet of this thesis. I must thank my friends, Michael Armstrong, L i Liu, Mohammad Darvish, Aqi l Jamal and Ayhan Akinturk for various help I received. I can not thank my wife, Miyase, enough for the extraordinary patience she showed during this marathon and for her genuine continuous prayers for my success. A l l praise be to God, The Most Merciful, The Most Compassionate. I pray to Him that the knowledge He has given me in this thesis will serve for the good of mankind. ix Dedication This thesis is dedicated to my father, Hasan Katircioglu. x Introduction Mathematical intractability in attempting to solve many practical inventory problems has been a serious barrier for advancement in inventory control. This difficulty has left many important problems still unsolved today. This thesis studies and attempts to bring solutions for the following four important issues faced in the the theory of stochastic inventory models, which are not addressed in the literature satisfactorily, mainly because of their mathematical complexity: • Optimization of stochastic inventory models by taking estimation errors into ac-count when demand parameters are estimated. • Development of inventory policies when the objective is to deliver different service levels to different class of customers with minimum possible cost. • Calculation of optimal policies for low demand inventory problems with backlog-ging. • Alternative policies for a Poisson-demand inventory problem with lost sales. These topics are studied for some specific inventory models in four chapters. Chapter 1 addresses the combined estimation and optimization problem. In stochas-tic inventory problems, when the form of the demand distribution is known, a common traditional approach in practice has been to estimate the unknown parameters of demand first, and then by using these estimates to carry out an optimization separately in order to determine an optimal inventory policy. This practical method treats the estimation and optimization problems separately. The problem with this method is that a purely 1 statistical criterion used to do the estimation (such as unbiasedness of the estimates) may not give good policies when fed into the optimization. Here, the key issue is how the cost function behaves with respect to the errors in estimation. Typically, since shortage costs are much higher than holding inventory, underestimation of demand results in a much higher penalty cost than overestimation. Because of this, the cost function is not sym-metric with respect to the errors in estimation. This property puts the performance of unbiased estimators in question. This chapter attempts to develop a general framework for the use of unbiased estimators. First, three inventory models (a newsboy problem, a base-stock model and a (Q,r) model with fixed Q) are presented and it is shown that they have similar forms. Then, a general theory of introducing a bias to the commonly used estimators is developed in order to take estimation errors into account during opti-mization in these models. To be implementable, a biasing factor needs to be independent of any unknown parameters. This is proven to be true for the optimal bias when the demand is in the scale-location family, in both problems with cost minimization and service achievement objectives. While biasing can give lower costs in cost minimization problems, it is guaranteed to deliver service levels exactly at targets for service achieve-ment problems. The effects of biasing for different values of cost and demand parameters are examined for Normal and Gamma demands in detail. For the (Q,r) model which is studied at the end, it is shown through some numerical examples that biasing can give significant improvement in costs. Chapter 2 studies an inventory problem with multiple service level requirements. Introducing service constraints instead of. shortage costs in inventory models has been popular mainly because of their practical use and the difficulty involved in measuring shortage costs. However, exact analysis of inventory models with service constraints is much more difficult compared to those with no constraints. Thus, although there are 2 extensive studies in the literature with single service constraints, even for simple inven-tory problems it is hard to find any which addresses multiple-customer classes requiring different levels of service. In this chapter, a periodic review single-product, single facility inventory problem with multiple customer classes, each requiring a different service level is studied. The service is defined as the backorder rate and the objective is to find a combi-nation of an allocation policy (which will allocate available inventory on hand among the customer classes) and an order policy for inventory replenishment so as to achieve target customer service levels with minimum possible inventory costs. Demands from customer classes are assumed to be independent continuous random variables and replenishment orders arrive after a fixed lead time. A correspondence is observed between the cost min-imization objective with quadratic backlogging costs and service achievement objective with no backlogging costs, when a relaxation is introduced to both models. Then by using this correspondence, an easy-to-calculate myopic heuristic allocation-order policy is developed for both finite and infinite horizon cases. The performance of this heuristic is tested over a range of problem parameters with normally distributed demand, using simulation in the infinite horizon case. The results show that the service levels delivered by the heuristic are very close to the targets. It is also proven that the cost of this heuristic is a lower bound for any feasible' policy. In Chapter 3, a classical single-echelon, single-product problem is studied. Demands arrive in single units and times between successive demands (interdemand times) are assumed to be independent identically distributed random variables. The inventory is reviewed continuously and unfilled demand is fully backlogged. Orders placed arrive after some fixed lead time. The backlogging and inventory holding costs are linear in time. The objective is to find an optimal inventory policy so as to minimize the long run average cost. 3 For this problem, it is well known that an (s-l,s) policy (i.e. a "sell-one-buy-one" or a "one-for-one" policy) is optimal when demands are Poisson; or in other words, the interdemand times are exponential. However, there is no proof of its optimality for other demand processes. Since it is believed that (s-l,s) policies would have satisfactory perfor-mance in other cases, rather than seeking an optimal policy, almost all the research in the literature focused on studying various characteristics of these policies in problems with more general set of assumptions. In this chapter, an optimal policy is determined for this problem when the demand distribution has increasing failure rate. First, it is observed from the literature that an optimal inventory depletion policy will be a first-in-flrst-out type policy. This optimality property results in a one-to-one correspondence between demands and units ordered, which makes it possible to find an optimal replenishment policy. A Delayed-(s-l,s) is proven to be optimal under the assumption that the interde-mand times have any general distribution with increasing failure rate. This policy is an (s-l,s) policy in which when a demand arrives, an order is not placed immediately but delayed for some time. A numerical study is presented for normally distributed interde-mand times, which shows that an (s-l,s) policy may have significantly poor performance compared to the optimal policy. Finally, the results are extended to a case in which there is a fixed order cost and it is proven that a Delayed-(s,S) policy is optimal under the increasing failure rate assumption. An algorithm to calculate optimal values for the reorder point s, the lot size Q = S — s and the delay is provided. In chapter 4 , a similar unit-demand problem as in Chapter 3 is addressed with the assumptions that the demand is Poisson and unfilled demand is completely lost. There is no cost for ordering and the objective is to minimize long run average holding and lost sales costs. For Poisson demand, although the optimality of one-for-one policies is known when unmet demand is fully backlogged, in case of lost sales, an optimal inventory policy is unknown and believed to be complicated. Therefore, one-for-one policies have been the 4 main focus of research for lost sales just as for backlogging, because of their simplicity and the their optimality for the latter case. Although simplicity of policies may still be an appealing factor, the application of more sophisticated policies is feasible and easier with today's computer technology. For this particular problem, it is possible to use more information than a simple one-for-one policy does in order to find a policy which can give lower costs, but with more computational work. The difficulty with the lost sales case is due to the fact that the state space has to include inventory both on hand and in the pipeline. For continuous review models, the problem becomes even more difficult as the state is a vector of continuous variables and has to include the remaining lead times. An (s-l,s) policy does not make use of this information. In this chapter, the effect of the arrival schedule of the orders in the pipeline is explained by an example. Then, a myopic heuristic which takes the vector of remaining lead times as a state variable and utilizes all the information is developed. Finally, a test set of problems is generated and a simulation study is conducted in order to examine the performance of the heuristic as compared to an (s-l,s) policy. The results show that the heuristic can give up-to 15% cost reduction over an optimal one-for-one policy for long lead times and low lost sale costs although the one-for-one policy performs better in problems with short lead times and higher lost sale costs. 5 Chapter 1 Improving Traditional Inventory Policies Through Biased Estimation Abstract When implementing optimal policies for stochastic inventory problems with unknown demand parameters, the traditional method is to replace the unknown parameters with their estimates and then carry out optimization. It is hoped that the policy determined this way is satisfactory. This work presents some analytical results which take account of estimation errors, and can be used to improve this procedure. The method is devel-oped generally for a class of inventory problems with and without service constraints, which have a random demand whose probability distribution belongs to the scale-location family. Applications to Normal and Gamma demand cases are presented. 6 Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 7 1.1 Introduction Statistical estimation of unknown problem parameters in inventory control models has been studied since early times in the literature. Some of the early work includes [3, 12, 25, 47, 48, 84, 113]. Although the estimation of cost parameters has received some interest (see [19, 24, 64]), the major focus has been on demand forecast. For sporadic demand, an exten-sive study was conducted at Yale University during 1970's by a number of researchers. MacCormick [65] investigated the behavior of multi-item inventory systems with highly variable demand whose distribution is estimated from a sample of limited size. He had substantial computations to examine the performance of simple replenishment policies in practical use. Later, Estey and Kaufman [30], Kaufman and Klincewicz [55], and Klincewicz [57] carried on this research for different problems. Updating the demand distribution using Bayesian theory is one of the popular meth-ods used [5, 6, 17, 25, 51, 54, 84, 114]. However, exact solutions are difficult to calculate in Bayesian approach especially for problems which have fixed order costs (see [51, 52]). The lead time demand is an important variable of interest in most inventory problems. Hence, some reaserchers studied techniques to estimate the lead time demand [8, 11, 29, 58, 59, 61, 63, 72, 73, 108, 109]. Eppen and Martin [29] developed a procedure using exponential smoothing in order to estimate the reorder point of a (Q,r) model when both demand and lead time are random and their distributions are unknown. Bookbinder and Lordahl [11] note that the reorder levels are generally sensitive to the upper tail of underlying lead time demand distribution. They present a distribution free bootstrapping technique for fractile estimation, in order to identify re-order levels. They, then, compare bootstraping approach to the use of normal distribution. Their numerical tests show that their approach is less sensitive to the shape of the lead time demand distribution Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 8 than the normal approach. Lordahl and Bookbinder [63] also study order-statistics as a means of estimating fractiles with a similar objective. Their numerical results indicate that for symmetric and positively skewed distributions, using order-statistics gives more robust estimates of fractiles than assuming normal distribution. In cases where the form of the demand distribution is known, a more practical ap-proach is to estimate the unknown demand parameters first, and then determine the optimal policy by using the estimates of those unknown parameters. This approach splits the problem into two parts; finding the best estimators (in statistical sense) and then determining the optimal policy under the assumption that these estimators are very close to the true values of the parameters. The concern about such an approach has been that a statistically good job of estimation does not necessarily result in a good optimal policy so as to deliver minimum expected cost. There have been some results in the literature which show that using biased estimators may lead to a smaller expected cost. The key issue is how the objective function would behave with respect to the errors in estimation or in the assumptions about the demand distribution. There has been little work that addresses and clarifies this matter. The most relevant papers in the literature are Hayes [47], Weerahandi [115], Silver and Rahmana [101, 102], and Ritchken and Sankar [80]. Hayes [47] essentially studies a newsboy problem. He derives the expected total op-erating cost (ETOC) for exponential demand and then calculates an optimal bias (a multiplier) for the sample mean of demand observations and uses this as a biased esti-mator for the mean demand so as to minimize the E T O C . He also works with Normal demand with unknown mean, known variance and, both unknown mean and variance. In both cases, he approximates the E T O C by Taylor's expansion. Then, using this approx-imate cost, he calculates an optimal bias. Unlike the traditional method, this approach combines both estimation and optimization. He explores the impact of a non-stationary Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 9 demand distribution, and calculates the optimal bias when the mean demand is esti-mated by using a moving average technique. He finally notes that although his approach seems not to assume any prior distribution for the unknown parameters, an implicit as-sumption for a prior is unavoidably made [47]. This paper is particularly thorough, but unhappily seems to have been ignored or overlooked by the papers that followed, which studied many of the same topics but added little. His thesis has applications to other distributions and more details [48]. Weerahandi [115] also considers the newsboy problem. He, too (but without any approximation), determines an optimal biasing factor for the standard deviation of de-mand, when demand is normally distributed. Although Hayes uses an approximate cost, his bias is the same. Weerahandi also provides an optimal bias for the sample mean if demand is gamma. Silver and Rahmana [101] examined the cost penalties caused by estimating the de-mand distribution parameters in the case of a normal distribution. They use a variant of a (Q,r) model with Q being a predetermined constant. Later, they presented a nu-merical algorithm to calculate the optimal bias that should be used to overestimate the reorder point so as to minimize the cost penalty. Since the cost function is nonsymmetric, underestimating the reorder point r has a higher cost penalty than its overestimation. Thus, the optimal bias turns out to be positive [102]. Ritchken and Sankar [80] consider a newsboy problem with two types of constraints. In case of a probability of stock-out constraint, they give a correction factor for the sample standard deviation to achieve the targeted service level for a normally distributed demand. They develop a regression approach for the second type of constraint which ensures that a desired percentage of demand (fill rate) is satisfied with a certain level of significance. There are other papers somewhat relevant to the context of this work. Among those Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 10 are [28, 52, 53, 10]. In order to handle uncertainties in the demand distribution, Ehrhardt [28] suggested a power approximation to forecast the demand in the (S,s) model. The approximation yields near optimal policies for a variety of demand distributions and a wide range of demand and cost parameter values. When using time series estimation methods, Jacobs and Wagner [52] showed that using exponentionally smoothed estimators of the mean and variance gives a smaller total system cost for the (S,s) model as compared to using classical unbiased estimators, sample mean and variance, when the demand variability is large. In another paper [53], they presented some simulation results which show that if there is a significant functional relationship between the mean and variance of the demand, a regression-based estimator of the variance may perform even better than the sample variance in the power approximation suggested by Ehrhardt. Biggs and Campion [10] showed by simulating an MRP-based production system with capacity constraints that utilizing a biased (a positive forecast error) demand forecast yields better performance measures (these are the quantities that constitute the system cost) than using an unbiased forecast.. In this work, we attempt to place all of the work in as general a framework as possible, where necessary reproving existing results and then generalizing and extending them. We consider both the constrained and unconstrained cases with a demand that has a scale-location family type of distribution. By constrained, we mean a service level constraint such as the probability of a stockout during the lead time being less than a certain critical level. First, a summary of three inventory problems is presented and it is shown that these three problems have similar forms for our purpose. Then, Hayes' alternative approach to the traditional method of determining the optimal policy is developed in a more general context. Finally, the general theory is applied to a demand whose distribution is in the Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 11 scale-location family and some analytical results are derived for Normal and Gamma demand. For the unconstrained case, the optimal bias given by Hayes and Weerahandi is appli-cable. In addition, we give an expression for the percent cost improvement due to using the optimal bias and explain some properties of it. To be useful, a biasing factor needs to be independent of any unknown parameters. We prove this to be true for the optimal bias when using the scale-location family. This independence had already been obtained for the Normal and Gamma cases. When we consider the objective of minimizing the cost subject to a probability of stockout constraint, we add to the results of Ritchken and Sankar, by showing that for a demand in the scale-location family one can calculate a biased estimate with which a targeted service level can be achieved without having to know the true demand param-eters. We, then, examine the effect of biasing for different values of cost and demand parameters for a Normal and Gamma demand. Finally, in section 1.5, we give exact expressions for the optimal bias and cost in a (Q,r) model with normal demand eliminating the need for Silver and Rahmana's numerical algorithm. 1.2 Inventory Models We now provide a framework for investigating the effect of biasing in estimation. We describe three inventory models below and show that they are equivalent in terms of our biasing approach we develop later in Section 1.3. Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 12 1.2.1 Newsboy Problem In this well known single-period inventory problem, one has to decide how much initial inventory, y, to have so as to maximize the expected profit. The demand, X, during the period is random with a known distribution function with mean fi. An item is purchased at a price c, and sold at a price p. Unsold units are salvaged at a value s per unit (p > c > s). The expected profit at the end of the period is given by P{y) = VEX[X - (X - y)+] - cy + sEx[y - X]+ where Ex[-] denotes the expectation with respect to X, and [y — X]+ = max{0, y — X}. The objective is to maximize P(y) over y, which is equivalent to minimizing F(y) = (p- s)Ex[y - X}+ + (c - p)y. 1.2.2 A Base-Stock Mode l Consider a continuous review inventory model in which demands arrive in a continuous stream and unmet demands are fully backlogged. The replenishment orders are placed continuously to bring the inventory position (stock on hand + on order - backorders) up-to a critical level (base-stock). Note that this policy always maintains the inventory position at this base-stock level. There is a positive replenishment lead time. Inventory holding and backlogging costs are linear and no cost is incurred for ordering. The objective is to determine an optimal base-stock level so as to minimize the long run average holding and backlogging costs. Let us denote the critical base-stock level by y and let X be a continuous ran-dom demand during the lead time, with mean fi. Let the inventory holding cost be Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 13 h ($/unit/time), and the backlogging cost be p ($/unit/time). Note that at any ran-dom point in time, all outstanding orders a lead time ago will have arrived. There-fore, the inventory on hand at a random point in time will have the same distribu-tion as (y — X)+, and the backorders will have the same distribution as (X — y)+. Then, the long run average cost per time for a base-stock level of y can be written as F(y) = hEx[y ~ X}+ + pEx[X - y} + . Equivalent^, F(y) = (h+ p)Ex[y - X]+ + p(u - y). 1.2.3 (Q,r) Mode l W i t h Fixed Q We consider a two critical number, (Q, r), policy in a continuous review inventory prob-lem. When the inventory position is at or below r (reorder level) we make an order of size Q which is a fixed quantity. The demand during lead time is random with mean u-. However, the annual demand A is assumed to be fixed and known. Each order costs K dollars. Unfilled demand is backlogged and each unit backordered costs TT ($/unit). The annual inventory holding cost is h ($/unit). We use Hadley and Whitin's [45] approximation (which is also used by Silver and Rahmana [101, 102]) for the average cost function. F(y) = I-^ + h(® + y-») + 7 ^ E x i x - y } + 7rA „ r .7rA , . , . A'A hQ where the reorder level is denoted by y. Note that the cost functions in all three models are of the form F(y; 6) = AEx[y - X]+ + B(u - y) + Cy + D . (1.1) Although discrete demand distributions can also be handled in a similar way, we assume continuous demand distributions throughout this work as presentation becomes easier. Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 14 Thus, we have F{y-0) = A ( V $ ( X | 0 ) dx + B{u - y) + Cy + D Jo where <f>{.) and $(.) are pdf and cdf of X, and constants A , B, C, D satisfy A > B — C > 0. 1.3 An Alternative to the Traditional Approach The objective for the control of inventory is to minimize the cost function F(y; 9), given the demand parameter 9. min F(y;9), (1.2) y The first and second derivatives of F(y; 0) are dF(y;6) dy d 2 F ( y , e ) = A$(y\6) - B + C , (1.3) dy2 As F(y; 9) is convex in y for all 6, letting M = (B — C)/A, the solution to (1.2) is y*(6) =$-\M\6). (1.5) 1.3.1 Unconstrained Case If 6 is unknown, the standard practical approach is to replace 9 by an estimator 9. Let y*{6) solve (1.2) with 9 replaced by 9. Now, we want to know what the actual cost F(y; 9) would be at y = y*(9). Clearly, F(y\9) need not attain its minimum at y = y*(9), because y*(9) can be different from y*(6) at which it is minimized. The question is whether it is possible to improve this solution by trying different estimators for 0. Since F(y*(0); 9) is a random variable, the expected value of F(y*(9); 9) can be taken as a good measure of performance for y*{9). The closer to F(y*(9); 9), the Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 15 better. Namely, we want to solve m i n { ^ F{y*{9)-0) - F(y*(9);9)} , $e@ L J where 0 is a class of estimators in which we are interested. Since F(y*(9); 9) is a constant with respect to the above problem reduces to mm Eg F{y*{9)-9) Note here that using y*(.) in F(.) imposes a restriction which was not necessary. A more general problem would be to solve min Eg F(y(9);9) where y is some class of functions Since we do not want 0 and y to be too general to work with, we restrict them as follows 0 = {0 : 9 = u§,u 6 R] , y = {y*(-)}, where 9 is a given estimator of 9 and y*(.) is of the form given by (1.5). The reason for our choice of these particular sets is that when we try to find the best value for u>, the mathematics is tractable. Moreover, for demand distributions in the scale-location family, we can prove that the optimal value of w is independent of the unknown demand parameter 9, and thus becomes implementable. Therefore, we choose to focus on the following problem. min £ 2 (1.6) [F(y*(u9);9)\. Problem 1.6 can be interpreted as follows: Find the optimal biasing factor for 9 (that is u) so as to obtain a better solution y*(uj9) at which the expectation of F(y*(iu9); 9) is as close as possible to the unknown minimum F(y*(9); 9). Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 16 Let G(9) be the distribution function of 9. That is, G(9) gives the sampling distribu-tion of 9. Then, the expectation is F(y*(io9);9)\ = I F(y*(u9);9) dG{9). J Je L e m m a 1.1 Let y*(u9) be linear in ui. Then, if the expectation Eg F(y*(u>0)\Q) it is convex in ui for all 8. exists, Proof: Now, from (1.4), we know that F(y; 6) is convex in y for all 6. Since y*(u9) is linear in u>, F(y*(u>9); 9) is convex in u for all 9 as convexity of a function is preserved by a linear transformation of its argument. Then, the expectation over 9 is an integral which is just a weighted sum (or a linear combination) of convex functions, which is convex. • Using Lemma 1.1, the proposition we give below characterizes the optimal bias co*. Proposition 1.1 Let F(y;9) be given by (1.1) with A > B - C > 0, and let y*(u9) be linear in u. If Ez satisfies F(y*(u9);9) exists, then, the optimal solution to (1.6), say u*, j^{y*(u9)\9)9 dG{9) - M E^[8] = 0, where M = (B-C)/A. A A A Proof: Since y*(u9) is linear in UJ, let -^y*(uo9) = a9, where a is a real number. From Lemma 1.1, the optimal solution satisfies F(y*(u9);9)} = £ [F(y*(u9);9)dG(9) J Je = j (A$(y*(u9)\9)a9 + (C - B)a9) dG{9) = aA j(${y*{wb)\9)9 - M9}dG{9). Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 17 Since F(y*(u9); 9) exists and is differentiable for all co, interchanging the integral and the differentiation above is allowed. Setting it equal to zero, we have f §(y*{u9)\9)0dG{9) - M f 9dG(9) = 0. Je Je The second derivative of the expected cost is we have = / £ (A$(y'(u>0)\e)a0 + (C- B)a§) dG(9) = A fj)(y*(uj§)\0)a2e2dG(e) Je > 0 for all 9 and to. Thus, the solution is a minimum. • 1.3.2 Constrained Case The constrained case refers to the situation where stockouts are controlled by a service level constraint rather than a stockout cost. There are a number of different service level definitions— here we use the probability that the demand is satisfied in a certain period of time (usually lead time) is at least a. We assume that the cdf of demand, is both continuous and strictly increasing in y. Then, the minimum inventory, y, that achieves a service level a will be unique and given by = a. The solution is y*(6) = ^~1(a\6). Now, if 8 is known, $(y*(6)\6) = a is the actual service level that would be realized when y*(9) is the inventory policy. However, if 9 is unknown, the traditional approach has been to replace 9 by 9 and use y*(9) = <&-1(a|(9). Thus, the actual but unknown service level in this case would be a a, :E, F(y*(u6);e) Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 18 which does not necessarily equal a. As before, we can modify this traditional method by introducing a bias UJ to 9 so as to achieve the targeted service level a. That is, E§[*(y:(u,e)\6)] = a, (1.7) Thus, denoting the solution of (1.7) by u>*, if it exists, using LO*9 instead of just 6 would result in a long run average service level of a, as required. 1.4 Scale-Location Family Now, we make some assumptions for the demand distribution to get more specific results. Definition 1.1 Let $(x|/?,0) be the cdf of a random demand X with parameters ft and 9. Then, we say that X belongs to the scale-location family with scale parameter 9 and location parameter ft if its cdf can be written as <D(x|/?,0) = <D(^ |O, l ) , (1.8) where <&(.|0,1) is called the standardized cdf, which does not depend on (8,9). It is easy to see from Definition 1.1 that. <f>(x\B,6) = ±<f>'z*\0,l). (1.9) The scale-location family includes the Normal, Gamma and Weibull with fixed shape parameters, Cauchy, Uniform, Logistic, Student's t and Laplace distributions. Now, Problem (1.2) becomes min F(y;ft,9). (1.10) y ' . . Noting in (1.8) that §(M\B,6) = $ ( ^ | 0 , 1 ) , the solution in (1.5) becomes y*(ft,9) = k9 + ft, where k = $ _ 1 ( M | 0 , 1 ) is a known constant. Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 19 If 9 and 0 are replaced by their estimates 9 and 0, then the solution will be y*(0,9) = k9 + 0. ( L U ) We restrict our class of estimators to 0 = {(0,co9) :u> G R, 0,9 are given}, although other choices are possible. This choice satisfies the linearity assumption of y*(.) in u>. Therefore, Lemma 1.1 holds provided that the expectation given there exists. From Proposition 1.1, the optimality condition for u will be JJ§§ (V^ + / ~ V 1) - M) dG§J(9,0) = 0, (1.12) where G§ p(9, 0) is the joint distribution function of 9 and j3, and thus implementable. The following proposition shows that the optimal bias is independent of 9 and 0. Proposition 1.2 Let the cdf of X, <&(x\0,9), belong to the scale-location family with location parameter 0 and scale parameter 9 > 0. Note that E(X) = a9 + 0, and Var(X) = b92, where a and b > 0 are constants. Suppose we estimate E(X) by the sample mean x and Var(X) by the sample variance s2 (if one of 9 and /3 is known, we estimate only E(X)). Then, ifu satisfies (1.12), it is independent of (9,0). Proof: We have 9 = s/y/b and 0 = x — a§. Let Z{ = (xi — 0)19 and z = ^ 2^"=i z%-Note that both Zj and z are independent of (9,0). Now, Prob{^- < t} = Prob{^- (^-f^) ^ = Prob{z < t}. i=i ^ ' Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 20 8 1 Prob{-<t} = Prob{-, 8 9 = Prob{, = Prob{ Y, & ~ ~zf ^ WK* ~ !)}• \ 1 = 1 Thus, (a; — and 5/0 are independent of (0,8). The optimality condition in (1.12) is jj_9 ($((kco - a)9- + 0,1) - JUJ dG9^(8,$) = 0. Let u = 8/8, v = (x — 8)/9 and let HUiV(u,v) be the joint distribution of (u,v). Then, dividing both sides by 9, the optimality condition becomes i j u ($((ku> - a)u + v\0,1) - M) dHUiV(u, v) = 0 J V J u which is independent of (9,8). • An important implication of Proposition 1.2 is stated in the following corollary. Corollary 1.1 Let S be the set of all possible values of (9,8) for which F(. ;9,8) is defined. Then, if to* satisfies (1.12), it solves Proof: From (1.11), £y*(u>9) = k9. Then, from Proposition 1.1, we have d_ r? 3w 0,4 F(y*(8,u§); 8, 8)] = kA J p (<D(y*(/?, cod); 9, 8) - M) dG§J(9, $). Note that the integral is equivalent to the one in (1.12). Then, using the last equation in the proof of Proposition 1.2, we can write J L Tp F(y*(8,u9);9,8)\ = kA9 f f u ($((Jfew - a)u + u| 0,1) - M) dHUiV(u, v). J v J u Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 21 Let the term in brackets be g(uj). Proposition 1.2 implies that g(uj) is independent of (0,0). Let G(UJ) be such that dG(uo) = g(uj)duj. Then, we can write the expected cost as E U [F(y*(uO);0)] = kA0G(uj) + 1(0,0), where 1(0,0) is a function independent of UJ. Let (0* (UJ) , 0* (UJ)) maximize this expecta-tion. Substituting 0*(UJ) and 0*(UJ), and differentiating with respect to UJ, we have ^ I M X ^ ^ M ) ; ^ ) ] = kAfj*(u)G(uj)-^kA0*(uj)g(uj) Now, if 0*(UJ) is an interior solution, then J^I(0*(UJ),0*(UJ)) = 0. If it is a boundary solution, this will imply -J^0*(UJ) = 0. In both cases, the last term vanishes in the equation. Similarly, if 0*(UJ) is an interior solution, then kAG(uo) + ^1(0*(UJ),Q*(UJ)) = 0. If it is a boundary solution, this implies -£0*(UJ) = 0. In both cases, the equation will be £m^sE§^[F(y*(0,uOy,O,0)] = kA0*(uj)g(uj). The second derivative is ^ v ^ E ^ F i y ^ u e y ^ B ) ] = kA8*(uj)£g(uj) — kA0*(uj) I I uk(j)((ku - o)u + v\0, l)dHUiV(u,v). JV Ju Note that for UJ satisfying the first order condition, g(uj) = 0, the second derivative is positive. Hence the optimality occurs when g(uj) = 0, which is equivalent to (1.12). • Corollary 1.1 implies that UJ* is also a minimax policy among the policies of the form y*(0,uj0) = kuoO + 0. Thus, UJ* not only minimizes the average cost but also the worst possible average cost. This could be useful for problems with budget limitations. Turning now to the constrained ease, if we let I = $ - 1 ( O J | 0 , 1), UJ* will satisfy j ^*'™±JLzlL\ 0,1) dG^(0,0) = a, (1.13) It follows from the proof of Proposition 1.2 that UJ* is also independent of (0, 0). Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 22 1.4.1 Normal Demand Case Let (f>(.\p,cr) and be the pdf and cdf of the Normal distribution with mean fi and standard deviation <r. We denote their standard versions by <j>(.) and $(.). Suppose p and cr are unknown and we have a sample of demand observations for n periods. We use sample mean x and variance s2 to estimate fi and a2, respectively. Namely, i=i From (1.11), the inventory policy is y*(X,s) = ks + X. (1.14) Before we start applying the idea we state two lemmas which will be useful. L e m m a 1.2 (Grundy et al. [43]) Let Z have a standard Normal distribution. Then, for any real numbers a and b, Ez{^aZ + b)] = ^-=L=). V I + a2 L e m m a 1.3 Let Y have a Chi square distribution with v degrees of freedom and m be a real number such that r = 2m + v > 0 is an integer. Then, for any real number b we have Ey Ym<S>(bVY)] = 2 m ^ ^ T r ( b ^ ) where TT is the cdf of Student's t distribution with r degrees of freedom. Proof: See Appendix A . l . • Now, we want to bias s by to and use uis as an estimator of cr, whereas x estimates p. From (1.12), the optimal ui satisfies j r^kus + x - ^ s ) = M j j d Q _ ^ a ) i ( L 1 5 ) Js Jx ® JS JX Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 23 where Gx,a(x, s) is the joint cdf of x and s. Make the following change of variables: {n-l)s2 z ji We know that z has a standard Normal distribution and that u has a Chi square distri-bution with n — 1 degrees of freedom, and they are independent. Then, substituting z and u in (1.15), the optimality condition for to becomes / / r^—-r$(4=+ Vu <t>{z) x(u) dz du = Ju Jz Vn-l V n V n - 1 M °" y/u <j>{z) x(u) dz du Ju Jz Vn - I or equivalently y/ux{u)du = M / \ A * x ( ' u ) ^ u -J u y/n ' y^n - 1 where x(-) 1S the pc?/ of Chi-square with n — 1 degrees of freedom. From Lemma 1.2 the expectation on the left is v / l+1/™ V ^ 2 - 1 The integral on the right is simply the expectation of the square root of a Chi square random variable with ra — 1 degrees of freedom, which is V2T(n/2) r ( ( r a - l ) / 2 ) ' Then, the optimality condition is simplified to From Lemma 1.3 the integral on the left is ' " 1 / 2 $ ( A / ^ T ^ 1 / 2 ) y nz — 1 T(n/2) m j n r((ra-i)/2)r"(V^ T ^ Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 24 where Tn(.) is the cdf of Student's t distribution with n degrees of freedom. Thus, the optimality condition reduces to UJ* = T ~ \ M ) ^ ^ . n { ' nk Note that replacing k by we can also write UJ* as , T-\M) I 1 u = i ^ ( M ) V 1 " ^ ( 1 J 6 ) It is easy to see that as n becomes large, UJ* tends to 1, as one would expect. This expression was obtained by Weerahandi [115] for the newsboy problem and is identical to that found by Hayes [47], although there, an approximation to the expectation of F{y*{X,UJS); p,o~) was made with a Taylor's expansion about y*(u-,o~). It is also impor-tant to note that UJ* is independent of a and p and hence implementable as predicted in Theorem 1.2 above. The sensitivity of UJ* to values of M and n is shown in Table 1.1. Note that for small sample sizes, a significant amount of bias is required to minimize the expected costs especially when M is high. In all models we consider, high value of M corresponds to a high value of unit shortage cost compared to unit inventory holding cost (for instance, in the base-stock model, M = p/(p + h) is high when backlogging cost p is high). Therefore, when sample sizes are small and shortages cost significanly more than holding inventory, the amount of bias is high. For example, over 40% increase in the sample standard deviation is required for M = 0.99 when the sample size is 5. From (1.14), the optimal inventory policy adjusted for estimation errors is thus y*{X,uj*s)=X-rsT-1{M)^l-^2. Now, we state the following lemma for the expectation of the cost function. L e m m a 1.4 For any bias UJ, Ex<s[F(y*(X,ujs)-u-,o-)} = an{uj)Aa + Cu. + D, Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 25 Optimal Bias UJ* for Normal M n=5 n=10 n=15 n=20 0.10 1.128 1.065 1.044 1.033 0.30 1.045 1.027 1.019 1.015 0.50 0.980 0.995 0.998 0.999 0.90 1.128 1.065 1.044 1.033 0.95 1.200 1.096 1.063 1.047 0.99 1.417 1.182 1.116 1.085 Table 1.1: The value of optimal bias for normal distribution. where n + 1 1 + nk2uj2^ ~2 + «-iiW) ^ . nkuj . T „ ( - = = ) - M v n — 1 2irn V n 2 — 1 Proof: See Appendix A . l . • Note that an(uj) depends only on M and n and that the expectation of the cost function is linear in a and u. When UJ — UJ*, an(uj) reduces to a - ( u ; ) = V ^ r l 1 + — n — n-1 2 \ - — The percent reduction in cost is given by [a n(l) - an(uj*)]Aa (100). a n ( l ) A a + C7/i + D Note that for the base-stock model, since C = D — 0, the percent reduction in the total cost is independent of ft and a. Since D is a constant, the percent reduction in the controllable portion of the cost (i.e. F(y;9) — D in (1.1)) can be calculated by letting D = 0, which depends only on the ratio cr/fi. That is an(l)- an(w*)\A6 an(l)AS + C (100). Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 26 where 6 = a/p is the coefficient of variation. In the (Q,r) model we have C = 0. Thus, the percent reduction in the controllable cost does not depend on the unknown parameters. For the constrained case, the following lemma gives the optimal bias UJ*. L e m m a 1.5 If the demand is normally distributed with mean \i and variance a2, then Equation 1.13 is satisfied by c V n Proof: See Appendix A . l . • This is previously obtained by Ritchken and Sankar [80]. The expected cost of y*(u*s) can be calculated by using Lemma 1.4 with UJ = UJ*. As can be seen in the proof of Lemma 1.5, letting / = $ _ 1 ( a ) , the expected service level is EsAS(x,uJs)}=Tn-l(^), (1.17) which equals a for UJ = UJ*. The usefulness of Lemma 1.5 is that the bias UJ* can be applied without any knowledge of the parameters [i and <r, and the long run average service level is guaranteed to be a. 1.4.2 G a m m a Demand Case Let <t>r{-\l) and $ r ( - | 7 ) denote the pdf and cdf, respectively, for the Gamma distribution with shape parameter r, scale parameter 7 and location parameter 0. We use the notation X ~ Gamma(r,^) to mean that r(r) Now, we state a lemma that will be useful in our further calculations. Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 27 L e m m a 1.6 If X ~ C7amma(r 1,71) and Y ~ Gamma(r2,72) then for b > 0 Ex[<$>r2{bX\l2)\=Br2,Tl{ hi ) Wi + 72 where BT2,Tl is the cdf of a Beta distribution with parameters r^ and r\. Proof: See Appendix A . L • Note that E(X) = n, and that 7 = £ V™=i is an unbiased estimator for 7. Further, X^=i ^ ~ Gamma{nr^). Thus, 7 ~ Gamma{nr^/nr). If we use a biased estimator of the form coj for 7, from (1.12), the optimal value of ui will satisfy where k — $r ( M | l ) . Using the relationship 7 ^ n r ( 7 l 7 / ^ ^ ) = lKr+i{l\llnr), the optimality condition will be 7 Note that the integral above is Ex M kuX 1) 7 where X ~ Gamma(nr + 1, ^ ) . Then, from Lemma 1.6 we have Therefore, u is optimal if ku ) = M. r,nr+l kco + nr Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 28 Optimal Bias OJ* for Gamma r-=1 r-=3 r-=8 M n=5 n=20 n=5 n=20 n=5 n=20 0.10 0.841 0.955 0.913 0.977 0.950 0.987 0.50 0.883 0.968 0.958 0.989 0.984 0.996 0.90 1.016 1.007 1.039 1.012 1.033 1.009 0.95 1.081 1.024 1.072 1.019 1.048 1.013 0.99 1.254 1.065 1.147 1.037 1.086 1.022 Table 1.2: The value of optimal bias for gamma distribution. That is, Weerahandi [115] has the same bias except that in his, nr + 1 appears to be incorrectly stated as nr. Again note that OJ* is independent of 7 and is thus implementable. From (1.11), the optimal inventory policy adjusted for estimation errors would be y*(oj*j) = ku*j -nx. (1.19) 1 - B r ^ r + 1 ( M ) The optimal bias is shown in Table 1.2 for various values of n, r and M. We see similar results as in the case of normal distribution. For small sample sizes and high M values (indicating high shortage costs relative to inventory holding costs), the bias is significantly bigger that 1, which means that an increased value of the sample mean should be used. However, for problems with relatively high inventory costs (i.e. small M value), the bias is smaller than 1, in which case a decreased sample mean should be used. Now, the following lemma states the expected cost. Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 29 Lemma 1.7 For any bias LO, E*/[F(y*iul)i 7)] = an{u)jr + D, where , . Akto / ( kto \ , \ A„ ( kto , a n (c j ) = Br,nr+i i ; J - M - A B r + i , n r - • 1 + £ . r \ \kio + nr J J \ku> + nr • Proof: See Appendix A . L • For LO = LO*, an(co) simplifies to kto* an(tO*) = B - ABr+it„ kto* + nr The percent reduction is, then, given by [an(u*) - an(l)]ir a n ( l ) 7 r + Z> U U U J -Note that when D = 0 (as in newsboy and base-stock models) this is independent of 7, which means the reduction in the controllable cost is not affected by the unknown parameter 7, as in the case of Normal distribution. For the constrained case, using Equation 1.13 we have 1 M — \l)dG^) = a. 7 Using Lemma 1.6 the integral is simply 7 r'nr{lLo + nr}-Then, the bias that will yield an average service level of a will be = / ( 1 - 6 - W ) " ( 1 ' 2 0 ) where / = ^ ( a l l ) . Note that the long run average service level for any bias LO is ILO Br,nr(~, j )• ILO + nr Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 30 1.5 (Q,r) Mode l with Normal Daily Demand In this section we will give exact closed form expressions for the optimal bias and the expected cost if one has a (Q,r) model with a given fixed Q. We assume daily demand data are used for estimation as in Silver and Rahmana [101]. The derivations of these expressions follow from Lemmas (1.2), (1.3), and are done very similarly to the previous calculations. The optimal reorder level, from (1.11), will be y*d(d,ujsd) = Ld+ ku\fLsd , where d, Sd are the sample mean and standard deviation of daily demand data, and L is a fixed lead time in days. Assuming that the demand during a day has normal distribution with mean p and variance <r2, the optimal bias and the expected cost can be shown to be . _ T~\M) . / ( n - l ) ( n + £ ) UJi — where k V n 2 Ed,Sd[F(y*(d,usdy,U;a)} = ad,n(uj)Aay/L + C pL + D n + L ( nk2u n - l 2, ,2 \ " — 2irn V (n-l)(n + L), ( nku n y/(n-l)(n + L) - M These closed form expressions eliminate the need for Silver and Rahmana's algorithm. A n Example We conclude with an example in which we will examine a (Q, r) model with fixed Q, no order cost (K = 0) and Normal demand as in Silver and Rahmana [102]. a) Unconstrained case: We let the annual demand A = 1000, and the annual holding cost h = $1 per unit. It is assumed that the estimation of lead time demand Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 31 n L 7T Optimal Bias and % Reduction Q=15 Q=30 io*d R\ R2 n=5 L = l 7T = 1 7T = 5 7T = 15 1.36 11.4 3.4 1.63 34.7 15.7 1.87 54.2 32.6 1.26 5.6 0.8 1.50 23.2 5.4 1.71 41.9 14.2 L=5 7T = 1 TT = 5 7T = 15 1.75 31.2 19.0 2.10 59.0 46.7 2.41 74.7 66.3 1.63 20.3 7.3 1.94 47.2 26.4 2.21 65.3 46.5 n=10 L = l 7T = 1 TT = 5 TT = 15 1.16 3.9 0.9 1.26 14.2 4.5 1.33 26.4 10.2 1.12 1.8 0.2 1.21 8.7 1.4 1.28 18.2 3.7 L=5 7T = 1 7T = 5 TT = 15 1.35 15.1 7.3 1.47 34.8 21.4 1.56 51.2 36.5 1.31 9.3 2.6 1.42 25.4 9.7 1.50 40.8 19.6 n=20 L = l 7T = 1 TT = 5 7T = 15 1.08 1.1 0.2 1.12 4.1 1.1 1.15 8.2 2.4 1.06 0.5 0.1 1.10 2.5 0.3 1.13 5.4 0.9 L=5 7T = 1 7T = 5 TT = 15 1.17 5.3 2.2 1.22 13.2 6.5 1.25 21.6 11.9 1.16 3.2 0.8 1.20 9.2 2.7 1.23 16.0 5.5 Table 1.3: The effect of biasing on the cost for (Q,r) model. Rip)'- % reduction in controllable (total) cost. parameters is done using a daily demand data for a fixed lead time L, and that the actual daily demand parameters are p = 3, o = 3/4, when calculating the percent reduction in total cost. Table 1.3 shows the effect of biasing the standard deviation. We have previously seen that the percent reduction in controllable cost does not depend on the unknown demand parameters (if the demand is normal). Note that as the cost of a backorder, IT, increases the effect of using a bias factor is more significant. The percentage gain in cost is more significant for larger lead times, and intuitively enough, this gain decreases with Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 32 (Q,r) model with M=0.80, p=4,o=2 Traditional Method Biasing Alternative n OL Service Cost * Cost 5 0.80 0.757 1.601 1.225 1.608 0.90 0.847 1.671 1.311 1.865 0.95 0.896 1.844 1.420 2.329 0.99 0.950 2.322 1.764 3.883 20 0.80 0.789 1.448 1.048 1.448 0.90 0.887 1.552 1.062 1.591 0.95 0.938 1.766 1.077 1.860 0.99 0.982 2.330 1.119 2.587 Table 1.4: The effect of biasing on the service for (Q,r) model. sample size. In short, biasing is the most effective when we have small sample size, high backorder cost and long lead time. In such cases, the amount of biasing one must use is the greatest. Our further calculations revealed that there is no clear effect of Q, although larger Q may seem to decrease the effect of biasing from the table. b) Constrained case: We let Q = 20, ir = 1, p, = 4, a = 2, and the other parameters remain as in part (a). The objective is to achieve a long run average service level a during the lead time. Table 1.4 shows the expected total costs and service levels for both the traditional method and the biasing approach. The costs for the traditional method and the biasing approach were calculated by the formula given in Lemma 1.4 by letting LO equal 1 and LO*, respectively. The long run average service level of the traditional method was calculated using (1.17) for LO = 1. Note that in the traditional method, the actual average service levels in the long run are consistently lower than expected. In other words, an inventory manager using the tradi-tional method will deliver a service level below, and for small sample size, significantly below the level being targeted. For example, with a sample size of n = 5, a manager Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 33 planning a service level of 90% will find that the long run service actually achieved is more than 5% lower than this. 1.6 Conclusions and Remarks When the demand parameters are estimated in inventory control problems, there is an increase in the expected operating cost or a degradation in expected service level of the system due to estimation errors. It is possible, however, to adjust the traditional estimators of sample mean and standard deviation by introducing biases which result in a lower operating cost. This work has generalized the idea of biasing for the scale-location family of distribu-tions and has shown that the newsboy problem, base-stock model and (Q, r) model with fixed Q are identical in terms of applying the biasing approach. We have attempted to bring together and extend a variety of papers dealing with the introduction of bias to compensate for estimation errors in inventory control. There seems to have been some 'reinventing the wheel' happening on this topic, with the early paper of Hayes being missed by later authors who have ended up in some cases delivering less than he had already done. Because of the common practice of setting customer service levels for in-ventory, the paper of Ritchken and Sankar [80] with the extension given here is practically noteworthy, because for small samples major errors in the actual service levels delivered from those targeted can occur. Some other interesting observations we made are: In all three models with either normal or gamma demand, the amount of savings due to biasing is a multiple of the standard deviation of demand and thus increases as the standard deviation increases. That is, biasing gives more savings for problems with large variations in demand. In par-ticular, for base-stock model if the effectiveness of biasing is based on percent reduction Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 34 in cost rather than the amount of savings, one can calculate the exact effect of biasing. This implies that if biasing is effective for a problem of certain cost parameters, it will remain equally effective regardless of how demand parameters change. Since our analysis assumes stationary demand, the results here should be used with caution in problems where the demand shows seasonal patterns or a steady change. However, such problems are generally difficult to handle by other methods, too. A practical approach can be to apply the results developed here myopically, especially when simple estimates such as sample mean and variance from a sample of the most recent observations are used to forecast demand and the past observations are not effective forecasters. That is, biases can be calculated based on a recent sample and inventory policies can be modified accordingly by assuming stationary demand. Since sudden dramatic changes in demand parameters is not very typical even in problems with non-stationary demand, if the bias calculation is updated frequently, this method can provide a good approximate solution to such problems, as an alternative. The extention of this study to other inventory models is possible provided that the quantities involved in calculating the measures of performance (such as expected cost and expected service level) allow mathematical tractability for this kind of analysis. Since many inventory models have similar quantities as building blocks (such as ex-pected amount of inventory, expected amount of backorders, probability of stockout, etc.), this method may have considerable chance to be applied to a wider class of prob-lems. However, the results are not guaranteed to be implementable. The fact that the optimal bias was independent of the unknown parameters is what makes the results here implementable for the scale-location family. This might not be the case in general. An alternative method could be to apply a Bayesian approach, assuming a prior distribution for the unknown parameters. As for discrete-demand models, the analysis here should be extendible. This will Chapter 1. Improving Traditional Inventory Policies Through Biased Estimation 35 need the replacement of some integrals by sums. However, in calculating an optimal bias, differentiation should not be a problem. There may be some technical difficulties with the discrete nature of the problem in places where we needed continuity assumptions. Chapter 2 Managing Inventory for Mult iple Customers Abstract In this research, we study a periodic review single-product, single facility inventory prob-lem with multiple customer classes. The customer classes differ in that each class requires a different service level, which is defined as the backorder rate. The objective is to find an allocation policy which will allocate available inventory on hand among the customers and an order policy for inventory replenishment so as to achieve prespecified customer service levels with minimum possible inventory holding cost. Customer demands are random and independent with a stationary probability distribution. We develop an easy-to-calculate myopic heuristic allocation-order policy for both finite and infinite horizon cases. For the latter case, we test the performance of the heuristic, using simulation over a range of problem parameters. The results show that this heuristic delivers service levels very close to the targets and its cost is always at the lower bound. 36 Chapter 2. Managing Inventory for Multiple Customers 37 2.1 Introduction The study of inventory systems with service requirements has been popular because of its practicality and the difficulty in quantifying or measuring shortage costs. Although exact analysis becomes more difficult with the introduction of service level constraints, the practical use of service levels in industry has been stimulating researchers for quite a long time to study especially multi-echelon models with the objective of achieving desired customer service levels. This generated a substantial amount of work in the literature. Among some early papers are [3, 40, 69, 90, 96, 98, 100, 104]. Two of the most popular in the literature are Sherbrooke [98], and Muckstadt [69] ( M E T R I C and M O D -M E T R I C ) which study multi-item, multi-echelon, inventory systems for recoverable items (i.e. stocks, typically spare parts, which can be repaired and reused) with the objective of minimizing backorder levels at the lowest echelon subject to a budget constraint. A survey of early work can also be found in Clark [14]. Relatively more recently, Schwartz [94] compiled a diverse set of problems for multi-echelon systems with the contribution of a number of researchers. Later research includes [4, 7, 13, 26, 33, 70, 71, 82, 94, 95]. An up-to-date book by Graves, Kan and Zipkin [41] has some recent advancements in the area. In a more relevant paper to this study, Cohen et al [16] study a single-product, single-facility problem with periodic review. They have two types of (stochastic) demand that are classified as regular and eniergency. Their objective is to calculate an inventory policy so as to minimize long run average cost subject to a fill rate constraint. They approximate the cost and the fill rate to develop a greedy algorithm which gives a near-optimal inventory policy whose performance is reasonably good for short lead times. Srinivasan and Swaminathan [107] study a newsboy type of problem where there is a single period with random demands from different customers. They introduce different Chapter 2. Managing Inventory for Multiple Customers 38 service levels for different customers and analyze the structure of the optimal allocation and provide an algorithm to calculate the optimal order quantity. Most of the above papers are all motivated by practical problems that come from industry. Even for single-product, single-facility problems, however, there are not many studies in the literature that address multiple-customer classes requiring different levels of service. Topkis [111] studies a periodic review inventory problem with multiple customers having stochastic demands. The objective is to find an optimal ordering and allocation policy so as to minimize the total cost in a finite number of periods. He proves that a rationing policy is optimal, which means a customer's demand is satisfied if all other customers with higher backlogging costs are fully satisfied and as long as stock on hand is above some level. However, his model is basically a newsboy type of problem in which there is only one opportunity for order placement and that is at the beginning. He also studies a repeated newsboy problem in which there is a chance of ordering at the beginning of each period, assuming that backlogs are cleared by an immediate order arrival at the end of each period. In his problem, a myopic allocation policy in the form of the rationing policy described above is optimal when unmet demand is fully backlogged. In the lost sales case, the optimal policy is of this rationing form, but it is not myopic. Recently, Ha [44] studied an infinite horizon, discounted cost single-facility inventory problem with multiple-customer classes having Poisson demands with lost sales. The facility manufactures a single product and has limited capacity. He shows that a rationing policy is optimal in which a customer's demand is rejected if stock on hand is lower than some level. Then, he compares the performance of an optimal rationing policy with an optimal policy on a first-come-first-served basis and finds that the rationing policy is significantly better when the capacity of the facility is moderate, the demands are heterogeneous, and the difference .between the lost sales costs are large. Our problem is different from Topkis' and Ha's in that we make the usual assumptions Chapter 2. Managing Inventory for Multiple Customers 39 that unmet demand is backlogged and these backlogs are carried to a next period. We also impose service constraints and are interested in a good allocation policy in combination with an order replenishment policy. Another related work is Federgruen and Zipkin [33]. They study an allocation policy of the stock on hand in a depot to N retailers in a 2-echelon system. No stock is held at the depot and arriving orders are immediately allocated and delivered to the retailers. This delivery cost is linear and the order cost at the depot consists of a fixed cost and a linear variable cost. At the retailers, both unit holding and backlogging costs are linear with a constant ratio for all retailers. The demands at the retailers are stationary normal with different parameters. The objective is to minimize long run average cost. They calculate a lower bound on cost and develop a near-optimal allocation policy which performs well. In a similar study, Federgruen [32] suggests three different myopic allocation policies combined with an (s,S) order policy all of which result in costs that are within a few percentage points of the optimal cost. When the coefficients of variation of demand are equal for all retailers, all three of these allocation policies are equivalent. We use a method similar to his and that of Federgruen and Zipkin to calculate a lower bound for the cost of our model. A typical work in the literature which studies service constrained problems treats customers as identical and aims to deliver a uniform service for all of them unless the customers are a part of a multi-echelon system. Some examples of these multi-echelon papers are studies of one-warehouse N-retailer systems with service contraints. Among them are Muckstadt and Thomas [70], Schwartz et al [95], Badinelli and Schwartz [7], Deuermeyer and Schwartz [23]. Studies of single echelon systems include [16, 87, 88, 89, 97, 110, 120]. Here we study both penalty (or backorder) cost and service constrained models for Chapter 2. Managing Inventory for Multiple Customers 40 multiple customer classes. We start with a motivating example in the next section. In Section 2.3, we introduce a periodic review multi-customer inventory problem. Then, in Section 2.3.1, we address a cost oriented approach where we assume a nontraditional cost structure with quadratic backorder costs and no service constraints. In Section 2.3.2, we present a service oriented approach to the control of inventory where we have different service targets for different customer classes and no backlogging costs. Finally, in Section 2.4.1, we contrast these two problems and observe a correspondence between their relaxed versions. By using this correspondence we develop a heuristic allocation policy for the service problem and we present some computational results to test the performance of this heuristic. We give some conclusions and remarks in the last section. 2.2 A Newsboy Example The study of inventory systems with customer service requirements can be modeled in two apparently distinct ways. The most popular approach in the literature has been to levy a cost, typically called a penalty cost, against unfilled demand. Although this method leads to more tractible models, the difficulty of specifying penalty costs has led practical applications to turn more often to constraints on service levels. Little concern has been generated by this dichotomy of approaches between theory and practice because it has always been assumed that moving between these two models is fairly straightforward. A penalty cost will actually give some service level, however defined (we will explain our choice of the service definition later in Section 2.3.2). The reverse is also true, and hence given a one-to-one correspondence, the choice of model seems more one of convenience rather than correct modeling. The most common assumption used is to make backlog costs proportional to the Chapter 2. Managing Inventory for Multiple Customers 41 amount backlogged, i.e. linear costs. When we consider multiple-customer classes re-quiring different levels of service, however, linear costs have a serious drawback in that the above correspondence between the service levels and backlog costs breaks down. To illustrate this, let us consider a single period (newsboy) problem with two customer classes with random demands X\ and X2 whose means are pi and p2. Linear shortage costs are V\ > p2. A holding cost rate h applies to the inventory left unused. Let y be the choice of opening inventory. Since class 1 has higher backlogging cost the problem can be abbreviated to min p^ElX, - y]+ + p2E[X2 - [y - X,}+}+ +.hE[y - Xx - X2}+. y>0 This is because class 1 would be satisfied before any product is used to satisfy class 2 customers. The first and second expectations are expected backorders for classes 1 and 2, respectively, which would typically be used to define service levels for the classes. That is, let us assume h = 1 without loss of generality, as it is just a scale difference to use other values for h and let y*(pi,Pi) be the optimal starting inventory (i.e. solution to the above problem) for a given pair of (pi,p2). Then, the services (defined as the ratio of expected backorders to the mean demand) delivered to classes 1 and 2 are E[Xi - 2/*( Pi,p 2)] +/Vi and E[X2 - {y*(Pl,p2) - X,]+] + /p2, respectively. Figure 2.1 illustrates the attainable service levels for all possible values of pr > p2. Note that as y* varies only a trajectory of service levels is attained. If the second class is considered to have more priority (i.e. p\ < p2), then the attainable service levels will be given by a symmetric curve to the one in Figure 2.1. Thus, given any pair of service levels, there is no reason that a value of y* exists that gives them (except when px = p2j in which case we no longer have two classes). We see from Figure 2.1, for instance, that 0.30 and 0.90 are achievable service levels (expected backorders) for classes 1 and 2, respectively. However, 0.10 and 0.90 can never Chapter 2. Managing Inventory For Multiple Customers 42 Figure 2.1: Attainable service levels by linear costs in a 2-customer newsboy problem. Chapter 2. Managing Inventory for Multiple Customers 43 be achieved. In the case of a single class of customers it is easy to show that there is a one-to-one mapping between a linear holding cost and a service level. For this two-customer case, however, we see that this one-to-one mapping is lost. In fact, the mapping left is really unsatisfactory in that if the backlogging cost of one class is only infinitesimally higher than the other, this class will receive all the inventory it needs before the other can get anything. In other words, linear costs imply that we would always want to satisfy a higher class at the expense of a lower, and hence only a subset of service levels would be attainable. However, if there is some level of backorders for the higher class that is less important to reduce when substantial backorders exist for the lower class, then management will want alternative service levels. This indicates that to model this more general situation as a cost minimization problem we require nonlinear shortage costs. If they were not linear we must ask ourselves what is the appropriate model of shortage costs to capture these contingent marginal costs. It turns out that quadratic costs, which are about the simplest non-linearity to consider, achieve most of what we need in order to model the situation in which management has the freedom to dictate service levels instead of having to accept those limited to a small subset. Besides, they provided easy tractability and some useful properties in calculations. We introduce the inventory model we would like to study in the next section. 2.3 A Finite Horizon Periodic Review Problem A facility carries a single product and serves N distinct customer classes. Here, a cus-tomer class means a group of customers with identical service requirements and identical backlogging cost rates. We do not model individual customers but treat the entire such class as a single entity. Inventory is reviewed periodically. In each period, each customer Chapter 2. Managing Inventory for Multiple Customers 44 class demands product from the facility. These random demands are independent from each other and drawn from a stationary distribution (this assumption can be relaxed for the finite horizon case). The facility allocates available product to classes and after the allocation, unmet demand is backlogged. Observe that it is possible for product to re-main unallocated in inventory despite there being backlogs. This can happen when there is a shortage expected in the near future. The management may keep some inventory for higher priority customers and not fill all demands of lower priority classes. The facility then places an order from the supplier incurring only proportional, not fixed, costs. A n order arrives at the facility after a lead time of L periods, from the supplier whom we assume has an unlimited supply. The sequence of events in each period is assumed to be the following. • Orders placed L periods earlier is received. • Customers place their demand. • The facility allocates some or all of the existing on hand inventory among classes to fill demands. • The facility places a new order. • Accounting for penalty costs (backlogging and holding) and order cost (purchasing) takes place. We formulate the problem as a Markov decision process using the following notation: • N: the number of customer classes. • L: lead time for an order to arrive at the facility. • ct: purchasing cost of a unit in period t. Chapter 2. Managing Inventory for Multiple Customers 45 • ht: holding cost rate in period t. o yt: size of order placed at the end of period t. o y t = (yt-L, Vt-L+i, Ut-i)'- vector of outstanding orders in period t, just before customer demands are observed. • Ujt: demand by customer class j in period t. • Xjt: new demand plus the backorders for customer class j in period t. • Zjt: amount allocated to customer class j in period t. • vt: stock on hand available for allocation after order arrival in period t. • Xt, lit, Zt: summations of Xjt, U j j , Zjt over j = 1,2, . . . , iV , respectively. • X t , u t , z t : vectors of Xjt, Ujt, Zjt for j = 1,2, . . . , /V , respectively. Here, the decision epochs are just after observing customer demands in each period. The state of the process at decision epoch t is (u t, x t , y t ) - The action in period t is ( z t , yt)-The transition from period t to period t + 1 is described by the following relationships: vt+1 = vt - Zt + yt_L, y t + i = (yt-L+i,yt-L+2, —,yt), x t + i = x t - z t + u t + i . In the last expression, and henceforth, the vector arithmetic simply means Xjt+i = Xjt — zjt + Ujt+i for all j = 1 , 2 , N . The constraints on the process, in period t, are: Cl. Zjt > 0, Vj C2. Zjt <Xjt, V j C3. = zt Chapter 2. Managing Inventory for Multiple Customers 46 C4. 0 < Zt < min{vt,Xt] C5. yt > 0 We will consider two different objectives. The first one aims to minimize the ex-pected cost in a finite number of periods with no service constraints, but with some penalty charges for backlogging. We call this a cost problem and present it in the next section. The second one is what we call a service problem in which the objective is to achieve prespecified customer service levels with minimum possible inventory holding and ordering costs. We will formulate this problem in Section 2.3.2. 2.3.1 Cost Minimization with Quadratic Backlog Costs Our objective is to find an allocation and an order policy so as to minimize the expected total cost (backlogging + holding + order) in T periods. We call this the cost problem. Our choice is to use quadratic backorder costs for which we have provided our moti-vation in Section 2.2. The penalty cost incurred at the end of period t is given by A f N ? t ( u t , x t , z t ) = ^Pjtixjt - z3tf + ht(vt - ^Zjt). j=i i=i where pjt is the backlogging cost constant specific to customer class j in period t. Define / t ( u t , x t , y t ) to be the minimum total expected cost of periods t through T, given that the state is ( u t , x t , y t ) at the beginning of period t. Then, for t = 1 , 2 , T , we have ft(vt, x t , y t ) = min { ctyt + qt(vt, x t , z t) +Eft+1(vt -Zt + y * - L , x t - z t + u t + i , (yt-L+i,yt-L+2, —,yt)) : s.t. C I , C2, C3, C4, C5} (2.1) with / T + l ( u T + l , X T + l , y T + l ) = 0 f ° r a ^ ( u T + l , X T + l , y T + l ) -Chapter 2. Managing Inventory for Multiple Customers 47 To be practical for computational purposes, we would like to avoid an optimal solution to this problem that depended on the full rank of the state vector. Hence, we will seek an easy-to-calculate near optimal policy by relaxation. The Relaxed Cost Problem: We use the methodology in ([32],pp.148) and relax C I (i.e. we allow negative allocations). We want to prove the following proposition for this relaxed problem. Proposition 2.1 A . The value functions / t ( u 4 , x t , y t ) in Problem (2.1) depend on the vectors X t only via their sums Xt. B . In each period it is optimal to choose Zt = Xt — (Xt — vt)+ (i.e. satisfy the total demand and backorder as much as the stock on hand allows) and an allocation Z t which achieves m i n g t ( u t , x t , z t ) : s.t. C2, C3. C . A critical number policy is optimal for order replenishment. Before proving it, the interpretation of Proposition 2.1 is that when we are allowed to use negative allocations, a myopic allocation policy which minimizes the total cost for the current period and ignores the future periods is an optimal allocation policy. Moreover, our multi-customer problem given in (2.1) reduces to a single-customer problem for which a single critical number order policy is known to be optimal. Now, we will give a proof for the proposition. Proof (A): We use induction. Clearly A is satisfied for t — T + 1 since / T + I ( ^ T + 1 J X T + I , Y T + I ) = 0 by definition. Assume for £ + l ,2- | -2, . . . ,T that / t + i ( u t + i , x t + i , y t + i ) = / s + i ( u t + i , X t + i , y t + i ) . Chapter 2. Managing Inventory for Multiple Customers 48 That is, Xt+\ = Xt — Zt + Ut+i , where Ut+i = 2~ j^=i (total demand in period 2 + 1). Then, / t ( w t , x t , y t ) = min{ ctyt + gt(i>t, x t , z t ) +Eft+i(vt - Zt+ yt-L,Xt - Zt + t/i+i, (yt-L+i,yt-L+2, •••,yt)) : s.2. C2, C3, C4, C5}. Note that the allocation vector zt appears in / t + i only through its sum Zt. Thus, for any given value of the sum Zt we can compute the minimum value of ft by minimizing only qt(vt: xt, zt). Then, we can rewrite the recursion as /i(u<,xt,yt) = min{ ctyt + min Z t {^( t ; t ,x t ,z t ) : 5.2. C2, C3} + - Zt + yt-L,Xt - Zt + Ut+i, (yt-L+i,yt-L+2, •••,yt)) : s.2. C4, C5}. Consider the inner minimization problem N min^(ui ,x t ,z t ) = y^Pj i (z j i - zjt)2 + /*t(ut - Zt) : 5.2. C2, C3. (2.2) zt +-f After some algebra (see appendix B.l), the solution will be zjt* = xjt - _ j V ^ i , (-^"t - ^ t ) - (2.3) 2Zk=lllPkt Note that Z j t * may be negative and thus infeasible for the original cost problem. To complete the proof, define pt = l/2~^ jfcLi a n < ^ substitute (2.3) in (2.2). The minimum one-period cost becomes qt*{vt,Xt,Zt) = pt{Xt - Zt)2 + ht(vt - Zt) Chapter 2. Managing Inventory for Multiple Customers 49 which depends on x]t and zJt only through their sums Xt and Zt. Thus, our recursive equations become Hence ft depends on xJt and zjt only through their sums Xt and Zt and the induction (B): From the recursive equations in (2.4) we see that this is a dynamic program-ming formulation of a single-customer, single-facility, T-period inventory control problem with order lead time L, order cost per unit ct, linear holding cost rate ht, and (convex) quadratic backlogging cost with parameter pt. What is different here from the classical formulation of the problem is that this formulation allows for satisfying a portion of the demand of our single customer in any period even though we may have enough stock on hand to satisfy it fully. That is, we have the option of carrying backlog and inventory simultaneously. However, in a single-customer problem, it is well known that it is never optimal to carry both, in case of full backlogging (see Scarf [85]). This is simply because any inventory carried forward simultaneously with some backlog will have to clear this backlog in the future and thus will bring no cost advantage but only an extra carrying cost. Therefore, an optimal policy would satisfy the demand as much as possible. Thus, the optimal total allocation after having observed the demand will be Zt,yt +E ft+i(vt - Zt + yt-uXt - Zt + Ut+1,(yt-L+i,yt-L+2, •••,2/t)) : s.t. C4, C5}. holds. Therefore the result follows for all t. Zt* = min{Xi •t,vt} = Xt-(Xt^vt) Substituting Z* for Zt in (2.3), we get the optimal allocation: (Xt-vt)+. (2.5) Chapter 2. Managing Inventory for Multiple Customers 50 (C): Using the results in the proofs of A and B , we have vt+1 = vt-Xt + (Xt - vt)+ + yt-L = (vt - Xt)+ + yt-L, Xt+1 = (Xt - vt)++ ut+1: zjt = xjt - N ^,—[xt - vty, Y.k=illvkt anc qt*(vt, xu zt*) = Pt((xt - Vtyy + ht(Vt - xt)+. Note that q* and the recursion depends on Xt, and vt through their differences. Define It as the inventory position (inventory on hand + on order - backorders) just before order placement in period t. That is, It = vt + F< — Xt, where Yt = Y^f=o Vt-L+i-The practice is to charge the expected cost of period t + L + 1 in period t (see [32]). Noting that all of Yt and yt arrive at t + L + 1, our one-step cost according to this accounting scheme can be written as q;(It + yt) = Pt+L+iE[(Ut -It- yt)+}2 + ht+L+1E[(It + yt - Ut)+}. where Ut = Y^=\ ^t+i? ^ n a ^ ^s ^ n e total demand during periods t + 1 through t + L + 1. Then, the value functions in terms of It are given by /,(/,) = mm{ctyt + q*(It + yt) + E fw(It + yt - Ut+1)} (2.6) Ut>° This is the well known formulation of a single customer problem with convex backlog costs. Consequently, we know that a critical number policy is optimal (see [85]). • Although Proposition 2.1 reduces the relaxed multi-customer problem to a single-customer problem, its results are not implement able since negative allocations are not Chapter 2. Managing Inventory for Multiple Customers 51 realistic. We are yet to deal with the actual cost problem with the assumption of nonneg-ative allocations. We give a myopic allocation below, which respects the nonnegativity constraint. A Feasible Myopic Allocation for The Cost Problem: Let us impose the nonnegativity of allocations (CI), and use the optimal total allocation, Zt, in Proposition 2.1(B). Then, the proof in Appendix B . l can be used with C l imposed to show that the allocation which solves Problem (2.2) will be Z j t = (xjt - —)+ (2.7) Pjt N ^ = min{Xt, vt} (2.8) i = i where 9 > 0. It is easy to calculate Zjts from these equations. Note that at 9 = 0 we have Zjt = Xjt, and the cost is at minimum. However, this may violate C3. Since the cost increases in 9, we can increase 9 until C3 is satisfied at which we will have optimal values for ZjtS. Since this allocation depends on the Xj^s in a complicated way (no closed form expression is available) so does the minimum value of q(.). This invalidates the proof of Proposition 2.1. Thus, although feasible, we have no proof for the overall optimality of this myopic allocation. However, we will utilize this allocation in developing a heuristic for the infinite horizon problem with service constraints in Section 2.4.1. Now, our focus will be on a service oriented problem for which we will follow a similar approach. 2.3.2 Holding Cost Minimization with Service Constraints It is well known that the shortage costs are very difficult to estimate. Hence, using backlogging costs has limited application in practice. A widely used alternative approach to overcome this problem is to minimize inventory holding and order costs subject to Chapter 2. Managing Inventory for Multiple Customers 52 service constraints. Now we will study a problem of this kind and call it a service problem. The objective is to minimize the expected total inventory holding plus order costs subject to a prespecified service level for each customer. Backlogging is allowed with no charge (pjt = 0, V(j, t)), but there is a service constraint which is different for each customer class. Since the backorders depend on random demands which can be extremely large, it is not sensible to impose a tight restriction on the backorders. Thus, we will try to control expected backorders for some future period. In order to keep the notation simple we assume a stationary demand distribution and a stationary service target for each customer in all periods, which can easily be,generalized to a nonstationary case. We impose service constraints C6. E(xjt+L+1 - Zjt+L+i) < am,, j = l,2,...,N, t = l , 2 , . . , T - J L - l . for periods X + 2, L + 3 , T . Since we have no control over the quantity of stock available for allocation in periods 1 , 2 , L + 1, we impose no service constraints for those periods. C6 means we must follow an allocation and an order policy from period t on, so that when viewed from period t, the expected backorders for period t + L + 1 is at most ctjU-j for customer j. This form we have chosen for the service constraint will allow us to interpret it as a backorder rate constraint in the infinite horizon problem in Section 2.4. Since there is no cost for backlogging, the penalty cost incurred at the end of period t is N qtjvt, x t , z t ) = ht(vt - ^ zjt) i=i Define ft(vt, xt, yt) to be the minimum total expected cost for periods t through T, given that the state is (u t ,xt ,yt) at the beginning of period t. Chapter 2. Managing Inventory for Multiple Customers 53 Then, for t = 1,2, . . . ,T we have ft{vt, x t , y t ) = min { ctyt + qt(vt,xt, z t ) z t ) i/ t +Eft+1(vt - Zt + y t_L,x t - zt + ut+i , ( j / t_L+i ,J /*-L+2,— : s.*. C1-C6} (2.9) with / T + i ( u r + i , X T + i , y T + i ) = 0 for all (vT+i,XT+I,yT+i)-This problem is difficult to solve due to the complexity of C6. The optimal solution would probably have a very complicated form. This is because an optimal allocation policy would have to anticipate how much stock would be available for allocation in future periods and thus would probably want to retain some stock to the next period even at the cost of backlogging the demands of some low priority customers (those who want a relatively lower service level). We will consider an easier problem below. Then, using the results we obtain, we will develop a heuristic allocation policy for the service problem. The Relaxed Service Problem: We now relax the nonnegativity of allocations (CI) and state the following result for this relaxed service problem. Proposition 2.2 For Problem (2.9) with Cl relaxed, *ft = ~ -P" (*« - vt)+ (2.10) is an optimal allocation policy in period t. Proof: Let us replace C6 by C 6 ' . E(Xt+L+1 - Zt+L+1) <Zk=ia^k t = l , 2 , . . . , T - Z - l . This constraint simply requires satisfying an aggregate backorder level for all customer classes, rather than a seperate one for each class which is required by C6. Note that Mi Chapter 2. Managing Inventory for Multiple Customers 54 this is a further relaxation because C6 implies C&. Since C& and qt(.) depend on Zj^s and Xjt's only through their sums, Proposition 2.1 holds for the relaxed service problem. Thus, the optimal total allocation in period t is Zt* = min{Xt,vt} = Xt- (Xt - vt)+. Given the above Zt*, by Proposition 2.1(B), an allocation which solves minc/t(ut,xt,zt) = ht(vt - Zt) : s.t. (72, C3. z t is optimal for the relaxed service problem. Since qt(.) depends only on the sum, Zt, but not the individual allocations, any feasible allocation (which satisfies C2 — C5 and C6') will be optimal. Consider the allocation in (2.10). The expected backorders it delivers for customer class j will be E(xjt+L+1 - Zjt+L+l) = ^N1^ E(Xt+L+l - Vt+L+l) + = ^NJ^J—~E(Xt+L+i — Z*+L+1) 2^k=iakPk - v ^ i v 2^k=iaktlk l^k=\ak^k Thus, the allocation in (2.10) satisfies the service constraint C6 and the other constraints (except C l which is relaxed). Therefore, it is optimal. • Now, let us calculate an optimal order policy for the relaxed problem. Define It as the inventory position (inventory on hand + on order - backorders) just before order placement in period t. That is, It = vt-\-Yt — Xt, where Yt = Vt-L+i-Noting that all of Yt and yt arrive at t + L + 1, we have Xt+L+1 - Z;+L+1 = (Xt+L+1 - vt+L+i)+ = (Ut - I t - yt)+ (2.11) Chapter 2. Managing Inventory for Multiple Customers 55 where Ut = Y^if=i Ut+i, that is the total demand during periods t + 1 through t + L + 1. Then, C6' can be rewritten as C6'. £ ( / 7 T - J, - yt)+ < ELiW* t = l,2,...,T-L-l. Note that since the left hand side in CQ' is decreasing in It•+ yt, C6' is equivalent to + < = i , 2 , . . . , r - z - i . where St satisfies (assuming continuous demand) E(Ut - St)+ = TZ=i<*kl*k. (2.12) We will charge the expected cost of period t + L + l in period t. Using this accounting scheme, our one-step cost is q*(It + yt) = ht+L+iE[(It + yt - Ut)+). Then, the recursion will be ft{It)= min {ctyt + ht+L+1E(It + yt - Ut)+ + Eft+1(It + yt - Ut+1)} (2.13) yt>max{0,St — It) for t = 1, 2 , T — L — 1. It is easy to see that the quantity in brackets to be minimized increases in yt. This is because in the last period n = T — L — 1, for fn{In) = min {cnyn + hTE(In + yn - Un)+ + 0} the quantity in brackets increases in yn and thus (by induction) assuming the correspond-ing quantity in brackets for ft+\ increases in yt+i, so does the quantity in brackets for ft in yt. Therefore, the optimal policy in period t is y* = max{0, St — It}. Therefore, the critical number policy, St, defined through (2.12) is an optimal order policy for the relaxed service problem. Note that this order policy gives a lower bound for the cost of any feasible policy for the service problem since it is optimal for the relaxed service problem. We will use this policy in our heuristic in Section 2.4.1, which will insure that the heuristic gives a cost at the lower bound. Next, we study the infinite horizon case with service constraints. Chapter 2. Managing Inventory for Multiple Customers 56 2.4 Infinite Horizon Problem with Service Constraints In this section we will study the infinite horizon problem. Our main interest is the problem with service constraints and no backlogging costs (the service problem). First, we will clarify the definition of customer service for the infinite horizon. The most common definitions used in the literature are the probability of stock-out and the fill rate (the expected demand met divided by mean demand in a period). We define the backorder rate in a period as E(Demand + Backorder - Allocation) E(Demand) This is in contrast to the definitions in the literature where both numerator and denom-inator have consistently been either only demand or demand + backorder. Ours has a clear interpretation especially when backorders are higher than the mean demand. For instance, suppose that the mean demand of a customer class is 100 units per period and that the facility has poor response to demand so that an average of 200 units are back-logged for this customer every period. Thus, the average total demand of this customer class waiting to be satisfied is 300 units of which only an average of 100 units are satisfied. The backorder rate according to our definition will be 200/100 = 2 and this will mean an average of twice as many backorders as the mean demand are maintained. In other words, the customers will wait an average of 2 periods to be completely satisfied. Thus, the backorder rate can theoretically be any nonnegative real number. Rewriting C6, we have C76. - *JF+L+i) J = h2,...,N. to for t = 1,2,... The ratio on the left is identical to the backorder rate explained above. Thus, C6 means a long run average backorder rate of no more than QJJ is required for customer class j. Chapter 2. Managing Inventory for Multiple Customers 57 Our objective is to minimize the long run average holding and order costs subject to the constraints C1-C5 defined previously, and the service constraints C6, above. Igle-hart [50]) shows that with the long run average cost criterion, an (s, S) policy is optimal in a similar problem with an additional fixed cost for placing an order and without any constraints. The proof involves extensive technical issues such as the boundedness of the objective function and the existence of an optimal policy. A detailed analysis of this issue in a general context for Markov decision processes can be found in Puterman [78]. The fixed order cost makes the analysis more complicated. Since, we do not have any fixed costs, our model is a relatively easier special case of his model with the exception that we have a constraint. Thus, at this point we conjecture that a critical number policy is optimal for our problem and avoid the technicality of a proof. Then, the optimal value for this critical number can be calculated using (2.12) and dropping the subscript t. That is, the optimal critical number S satisfies E(UL+1 - S)+ = Ek=^kuk, (2.14) with UL+I being the total demand in L + 1 periods. The optimal order quantity is y* = max{0, S — I}. Hence, for the infinite horizon relaxed service problem an optimal inventory policy is a critical number order policy, S, given by (2.14) and an optimal allocation policy is the one given by (2.10). The following corollary will be useful in Section 2.4.1. Corollary 2.1 For t sufficiently large, the optimal order quantity in the finite horizon relaxed service problem in period t is y* = S — It, where S satisfies (2.14)-Proof: The inventory position in (2.13) is It+i = It + yt — Ut+\. This means if the optimal order is y*t = 0 for some t, then It+i = It — Ut+X- Thus, the inventory position Chapter 2. Managing Inventory for Multiple Customers 58 decreases as long as we do not order. Therefore, there exists a period t + n for which It+n = It — 2^fc=i Ut+k < S with probability one. Then, in such a period, the optimal order quantity is y*+n = S — h+n- But, this means Then, it follows that y*+n+k — S — It+n+k for all k = 1,2, . . . with probability one. • Corollary 2.1 means after a sufficiently long time, the inventory position will always be at or below a critical number S1, and the optimal order policy will be an order up-to-S" policy. Now, we state a corollary which will be useful in measuring the performance of the heuristic to be developed in Section 2.4.1. We assume that the single critical number policy in Corollary 2.1 is used in the infinite horizon case. Then, at steady state, the inventory position will always be at or below S. Corollary 2.2 In the infinite horizon relaxed service problem, the backorder rate deliv-ered by the allocation in (2.10) and the order policy in (2.14) for customer class j is exactly aj. Proof: From Corollary 2.1, y* — S — It, for t sufficiently large. From (2.11), we have It t+n+l It+n + Vt+n — Ut+n+l = S-Ui t+n+l _i < s. E(Xt+L+l — Vt+L+l) + (Ut - It (Ut - S)+ 2^k=ia^k-Then, from (2.10) E(xjt+L+1 - Zjt+L+l) ajlJ-j E{Xt+L+1 - v t + L + 1 ) + = aju-j.n E 1M k=iakH Chapter 2. Managing Inventory for Multiple Customers 59 This corollary will provide a useful benchmark in calculating simulation errors in Section 2.4.2, and help measure the performance of the heuristic we develop in the next section. For a reader interested in the cost problem with quadratic backlogging costs and no service constraints, Appendix B.2 shows how to calculate the optimal critical number S for the infinite horizon case with stationary demand and stationary cost parameters when negative allocations are allowed. Then, this S combined with the allocation policy in (2.5) will be the optimal inventory policy for the relaxed cost problem. Since this allocation is infesible for the cost problem, an alternative is to use the allocation in (2.7) combined with the order policy in Appendix B.2. Our numerical tests showed that this combined order-allocation policy gives a long run average cost per period very close to the lower bound obtained by solving the relaxed cost problem. We now propose a heuristic for the service problem, below. 2.4.1 A Heuristic for the Infinite Horizon Service Problem Consider relaxed versions of the cost and service problems with stationary parameters. From (2.5) and (2.10) we observe that they both have the same form of optimal allocation. That is, if Xjt is the demand plus accumulated backorders for customer j and vt is the available stock for allocation in any period i , we have where Wj = {1/Pj)/J2k=i^ f ° r the relaxed cost problem and Wj = ctj^j/Ylk=iaklJ'k for the relaxed service problem. Thus, if we let zjt* = Xjt - Wj(Xt - vt)+ 1 , j = 1 , 2 , N PJ = Chapter 2. Managing Inventory for Multiple Customers 60 both problems will have the same allocation policy. In other words, for any given order policy S, these two problems correspond through (2.15). Using this correspondence, we suggest a heuristic for the service problem as follows: Use the order policy S given by (2.14) which is optimal for the relaxed service problem. As for the allocation, convert the service problem with parameters ctj to a cost problem with parameters p3 using (2.15). Then, use the myopically optimal allocation of the cost problem as an allocation policy for the service problem. That is, our heuristic order-allocation policy for any period t, (S,Zjt,j — 1, 2 , N ) , is given by E{UL+1 - S)+ = Y!k=iakPk zjt = (xjt- 0 a ^ j ) + where 0 satisfies ^ j = i ( x . 7 * ~ = imin{Xt,vt}. Note that this heuristic may not give feasible service levels, but we know form Corollary 2.2 that its cost is a lower bound for the cost of all feasible policies. This is because S is optimal for the relaxed service problem. Thus, we will measure its performance by how close the service levels it delivers are to the targets. 2.4.2 A Simulation Study Now, we examine the performance of the heuristic described above for the infinite horizon service problem. In the infinite horizon case, the expected backorders can be interpreted as the long run average backorders per period. Thus, ctj is the long run average backorder rate per period for customer j. It is hard to calculate analytically the service levels our heuristic delivers. Thus, we will use simulation over a test bed of problems and compare the services delivered with the targets. In the simulation, we considered three ranges for the service level which may be typical Chapter 2. Managing Inventory for Multiple Customers 61 of different industry groups. Group 1 operates with the highest customer service standard and aims to deliver a backorder rate between 0.01 and 0.20. Group 2 is a moderate group with a backorder rate between 0.20 and 1. Group 3 is the slowest response group and it operates to deliver a backorder rate between 1 and 2. In each of these groups we varied the number of customer classes (N = 2,5,10). As for setting the service targets, we consistently covered the service ranges specified above for each group. • Group 1 (High Service Industry) - N = 2 : ( a i , a 2 ) = (0.01,0.20) - N = 5: ( a i , a 2 , a 3 , a 4 , a 5 ) = (0.01,0.05,0.10,0.15,0.20) - N = 10 : (ai , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9 , aw) = (0.01,0.02,0.04,0.06,0.08,0.10,0.12,0.14,0.16,0.18) • Group 2 (Moderate Service Industry) - N = 2 : ( a i , a 2 ) = (0.20,1.00) - N = 5 : (a i , a 2 , « 3 , « 4 , as) = (0-20,0.40,0.60,0.80,1.00) - N = 10 : (ai , a 2 ,0 :3 , « 4 , o>5, a6, a7, a 8 , a 9 , a 1 0 ) = (0.20,0.30,0.40,0.50,0.60,0.70,0.80,0.90,0.95,1.00) • Group 3 (Low Service Industry) - N = 2 : ( a i , a 2 ) = (1.00,2.00) - N = 5 : (a i , a 2 , a 3 , a 4 , a s ) = (1-00,1.25,1.50,1.75, 2.00) - N = 10 : (tti, a 2 , a 3 , a 4 , a 5 , a 6 , « 7 , as, « 9 , «io) = (1.10,1.20,1.30,1.40,1.50,1.60,1.70,1.80,1.90,2.00) Chapter 2. Managing Inventory for Multiple Customers 62 We assume the demand of customer j is normal with mean Uj and standard deviation Oj = fij/3. We used the following values for the demand means: o A. N = 2 - {puu2) = (5000,1000) a B . N = 5 - ( / * ! ,^2 ,^3 ,^4 , ^5 ) = (5000,2000,1000,500,100) • C. N = 10 ~ (pl, f-2, H3,p4, /^5, fJ-6, fJ-7, P8, p9, ^ l f j ) = (5000,4000,3000,2000,1000,800,600,400,200,100) As for the cost parameters, we used a holding cost rate of $1 per unit per period. However, we will not report cost results since we know that the heuristic has a cost always at the lower bound as explained earlier. For each of the above 3 groups we have 3 cases (N = 2,5,10), and for each of these cases we have 6 different values for the lead time (L = 0,2,4,6,8,10). Thus, we have 3x3x6=54 simulations in total. Each simulation was done for 10,000 periods, which was satisfactory enough to reach steady state. We define the following measures of performance. • cti: Target backorder rate for customer class i. • OL\: Backorder rate for customer class i delivered by the heuristic in the simulation. • a\: Backorder rate for customer i delivered by the optimal inventory policy of the relaxed problem in the simulation. This would equal ai, if error due to simulation were zero. Chapter 2. Managing Inventory for Multiple Customers 63 To define the error in services, we take only those classes of customers for which the service delivered is below the target. Let / be the set of such customer classes. We define an average percent error es as a weighted average, weights being the ratio of individual demand means to the total mean demand. That is, Note that the weights do not add up to 1, in general, since / may not include all classes. This error is the average rate of demand which is not satisfied on time although promised by the target service level (all customers combined). We also define a maximum percent error as em = max{(ojf — a;)}xl00. Since there is an error in service levels due to simulation, in calculating es and em, instead of .a^s we used aj's, in order to isolate the error for the heuristic. If there were no simulation error, we would have ai = a\ for all i, since the relaxed service problem gives service levels exactly at targets. ' As an example, we give some detailed results for the moderate service industry at a lead time of 6 in Table 2.1. The table shows the order policy, S, and the service levels achieved by the heuristic allocation for three different problems (2, 5 and 10 customers). Among the three service columns, the ones in the middle are the services delivered by the optimal allocation-order policy when negative allocations are allowed (a\). Since we know that theoretically they must be equal to the targets, the apparent differences between them and the target levels are due to simulation error. If we compare, then, the first two columns, we see that the service levels achieved by the heuristic are very close to the targets. The fact that these services are delivered by a policy whose inventory cost is known to be at the lower bound is quite pleasing. Chapter 2. Managing Inventory for Multiple Customers 64 Number of Demand Demand Order SERVICE L E V E L S Customers Mean St.dev. Policy S Heuristic ( a,-) Relaxed (a\) Target (a) 2 5000 1500 41,282 0.2180 0.2046 0.2000 1000 300 0.9563 1.0230 1.0000 5 5000 1500 58,232 0.2121 0.2101 0.2000 2000 600 0.4231 0.4202 0.4000 1000 300 0.6285 0.6304 0.6000 500 150 0.8238 0.8405 0.8000 100 30 1.0102 1.0506 1.0000 10 5000 1500 113,463 0.2133 0.2133 0.2000 4000 1200 0.3199 0.3199 0.3000 3000 900 0.4266 0.4266 0.4000 2000 600 0.5329 0.5332 0.5000 1000 300 0.6391 0.6399 0.6000 800 240 0.7451 0.7465 0.7000 600 180 0:8511 0.8531 0.8000 400 120 0.9551 0.9598 0.9000 200 60 1.0067 1.0131 0.9500 100 30 1.0581 1.0664 1.0000 Table 2.1: Heuristic performance for moderate service industry (L = 6). Chapter 2. Managing Inventory for Multiple Customers 65 We give a summary of the performance of our heuristic for all the test problems in Figures 2.2, 2.3, 2.4. From Figures 2.2(a), 2.3(a), 2.4(a), the average error is no more than 3% in all cases. With 5 or 10 customer classes these errors are within 0.5%. Figures 2.2(b), 2.3(b), 2.4(b) show that even the maximum errors are within 4%, except for group 2 with 2 customers and short lead time in which case it gets close to 9%. In general, as the number of customer classes increases, we tend to have better per-formance. The reason for this is simple portfolio effect or a kind of risk pooling that occurs among the customer classes. The more customer classes, the more likely to ob-serve a balancing effect among the demands of classes so that a dramatic deviation of the total demand received from the expected amount is less likely to occur. Due to the same reason, a longer lead time results in an increase in the performance. We did not report the costs because we know that theoretically the average cost of the heuristic is always at the lower bound as we mentioned earlier. Chapter 2. Managing Inventory for Multiple Customers 66 2.5 Conclusions and Remarks In this research, we developed a heuristic allocation-order policy for a periodic review inventory problem with multiple customer classes each of which demands a different ser-vice level. Our heuristic has a myopic nature and does not require extensive calculations and thus is easy to apply in practice. It links the cost and service problems by utilizing a correspondence that exists between their relaxed versions. First, it converts the service problem which is difficult to solve to a an easier cost problem. Then, it solves this cost problem myopically. It uses this myopically optimal allocation policy of the cost problem for the service problem. As for the inventory replenishment policy, it uses the optimal order policy of the relaxed service problem. Therefore, it delivers an inventory cost at the lower bound. Although, it may fail to satisfy the service constraints, our numerical tests showed good performance. We tested the heuristic in a fairly wide range of problems using simulation. The results showed that the heuristic delivers services which are satisfactorily close to the target levels for practical purposes. Our results are valid for both finite and infinite horizon problems and can easily be extended to nonstationary demand and service targets in the case of finite horizon. Extensions to problems with stochastic lead times, multi-echelon problems (especially one-warehouse, multi-retailer systems) and continuous review inventory problems would be exciting research topics. We also illustrated the inconsistency between the holding plus backorder cost min-imization with linear backorder costs and holding cost minimization with service con-straints in case of multiple customer classes. We showed that quadratic backlogging costs have enough flexibility to establish a one-to-one mapping between these two problems. Chapter 2. Managing Inventory for Multiple Customers 67 2-Cuotomor Problem Lead lime Industry Group 1 KS>^SI Industry Group 2 X////A Industry Group 3 (a) Average Error 2-Cueiomer Problem S Lead time Industry Group 1 K ^ s S l Industry Group 2 V///A Industry Group 3 (b) Maximum Error Figure 2.2: The performance of the heuristic (2-customer problem). Chapter 2. Managing Inventory for Multiple Customers 68 5-Customer Problem 10 9 8 7 6 5 4 3 2 1 O O 2 Lead time Industry Group 1 ^^ y^S^ Industry Group 2 V///A Industry Group 3 (a) Average Error 5-Customer Problem 4 Lead time Industry Group 1 Industry Group 2 V///A Industry Group 3 (b) Maximum Error Figure 2.3: The performance of the heuristic (5-customer problem). Chapter 2. Managing Inventory for Multiple Customers 69 1.5 1.4 1.3 1.2 1.1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 O 10-Ouetomer Problem lO Lead time Industry Group 1 £sSSSl Industry Group 2 W//A Industry Group 3 (a) Average Error lO-Customer Problem Industry Group 1 Lead time R^^Sl Industry Group 2 V///A Industry Group 3 (b) Maximum Error Figure 2.4: The performance of the heuristic (10-customer problem). Chapter 3 New Optimal Policies for A Unit Demand Inventory Problem Abstract In this research we analyze the classical single-echelon, single-product, unit demand, continuous review inventory problem with full backlogging where the interdemand times have a general stationary distribution with increasing failure rate, and are independent. Orders arrive after a fixed and known lead time. The costs of backlogging and inventory carrying are both linear in time. The objective is to minimize long run average cost. If there is no fixed cost for placing an order, we prove that a Delay ed-(s-l,s) policy is optimal in general. We observe, through some numerical examples, that the classical (s-l,s) may perform significantly poorer than the optimal policy for demand processes other than Poisson. In case of a fixed order cost, we show that a Delayed-(s,S) policy is optimal and we give an algorithm to calculate optimal values for the reorder level s, the lot size Q=S-s, and the delay. 70 Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 71 3.1 Introduction We study a classical inventory problem where we have a single-echelon and a single-product for which the demand arrives in single units. Interdemand times are assumed to have a general stationary distribution with increasing failure rate and are independent. The review is continuous and unmet demand is fully backlogged. There is no cost for placing an order which arrives after some fixed lead time. The backlogging and inventory holding costs are linear in time. Our objective is to find an optimal inventory policy so as to minimize the long run average cost. For this and more complicated problems it has been common to assume that the demand is generated by a Poisson process, perhaps due to the optimality of (s-l,s) policy. This is a simple "sell one buy one" policy which is also called one-for-one order policy in the inventory control literature. It may also be because the Poisson distribution fits demand data well in some practical cases. As mentioned, it is well known that an (s-l,s) policy is optimal for this problem when demands are generated by a Poisson process (i.e. interdemand times are exponential). Although there is no proof of its optimality for other demand processes, this policy has been analyzed in general settings by several authors with the belief that its performance would be satisfactory. Another factor has been that (s-l,s) policies are easy to apply in practice. The common opinion that the actual optimal policies may take a very complicated form and would probably not provide much improvement over (s-l,s) policies has discouraged researchers to look for one, further. Thus, two approaches are typically taken: Either a Poisson demand is assumed or order decisions were restricted to occur only at demand arrival times. Both assumptions lead to the optimality of (s-l,s) policies. Most of the research prefered focusing on how to calculate the optimal value for s and various quantities, efficiently. Especially when there is fixed order cost, in which case an (s,S) policy is used, efficient calculation of optimal Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 72 values for s and S has received significant attention (see [27, 28, 34, 35, 38, 112, 121, 122]). Croston [18] gives conditions under which a slow moving item should not be stocked due to unprofitibility or an order-to-demand policy should be adopted when the arrival times of customers, and their demands are random. He also provides optimal replenish-ment levels when the item has enough demand so that holding some amount of inventory is more profitable than order-to-demand. Gross and Harris [42] study an (s-l,s) policy where the lead times depend on the amount of outstanding orders, and the demand is Poisson. Sivazlian [105] studies an (s,S) inventory policy under the assumptions that the de-mands arrive in single units and the interdemand times are random with a general dis-tribution, when full backlogging of unsatisfied demand is allowed. He shows that the limiting distribution of the inventory position (on hand + on order - backlog) is discrete uniform over {5 + 1,5 + 2 , S } , regardless of interdemand time distribution. This result allows one to calculate some common steady state measures such as the average cost, and the probability of stockout, etc. Then, he calculates the optimal reorder level and the optimal lot size Q — S — s, when the delivery of orders is instantaneous. For the same problem with positive delivery lag, Sahin [83] provides necessary and sufficient conditions for s and S to be optimal. He gives an approximation for the optimal policy which is easy to compute. More recently, Zheng and Federgruen [122] provided an easy way to calculate the optimal s and S values using the uniformity of the inventory position at steady state. Feeney and Sherbrooke [36, 37] studied an (s-l,s) inventory policy under compound Poisson demand and random lead times with an arbitrary distribution. They showed how to calculate the steady state probabilities for the number of units on order in both full backlogging and lost sales cases. For the same problem with full backlogging, and exponential lead times, Higa et al [49] calculated the steady state distributions of waiting Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 73 times of backorders. Later, Sherbrooke [100] derived these distributions under the as-sumption of constant lead times and compared the average stocks held and probabilities of stock-out for both cases of constant and exponential lead times. As shown in earlier works by Feeney and Sherbrooke [37] and Hadley and Whitin [45], the steady state dis-tribution of stock on hand at a random time depends only on the mean lead time but not its distribution, in the case of an ordinary Poisson process. Kruse [60] provides a more accurate way of calculating these distributions for Poisson demands and random lead times with a general distribution using results known from the infinite-server queuing problem. Having these distributions enables one to calculate an optimal value for s, long run average cost and various service measures such as the probability of stock-out, or the probability that a randomly arriving customer waits no longer than a given time, etc. Schultz [91] considers a continuous review, constant lead time problem with general interdemand distributions and full backlogging. He finds the conditions under which no batching of orders (i.e. an (s-l,s) policy) is optimal as opposed to a batch order policy. He gives examples with the compound Poisson demand. There is also some work in the literature which combines inventory control of slow moving spare parts with optimal maintenance. Among these are [1, 31, 56, 77, 79]. In the case of a general demand process for slow moving items, the first work which proposed an alternative inventory policy to an (s-l,s) policy, to our knowledge, was pub-lished fairly recently by Schultz [92]. He assumed a general interdemand time distribution with increasing failure rate, and introduced the concept of delaying the placement of an order. He considered a problem in which demands arrive in single units, and in case of shortages, emergency shipments can be made at a premium cost, or the closest unit in the pipeline can be expedited at a cost either fixed or proportional to the remaining lead time of the unit. Both ways make it possible for the unit to arrive instantly so that there are no lost sales incurred. He studies a (0,1) policy with a delay in order shipment. That Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 74 is, a single unit is held in the inventory and whenever this unit is sold, a shipment of a replenishment order is scheduled at a future time. If there is a demand before the arrival of the unit in the pipeline, an instant delivery at a premium charge is made to satisfy demand. The question is to calculate an optimal delay for scheduling the shipment so as to minimize long run average cost which consists of a linear holding cost of a unit in stock and a penalty cost due to emergency shipment or expediting of a unit. This model is applicable when instant delivery or expediting is feasible. Furthermore, it would give a superior policy when the holding cost rate is relatively close to the shortage cost rate, which makes holding no more than one unit in stock reasonable. However, more often than not, holding more than a single unit in stock may be needed for slow mov-ing items especially when lead times are long relative to average time between demands and/or when shortage costs are significantly higher than holding costs. Moreover, there are cases in which instant delivery may not be feasible and backlogging may be the only feasible alternative. Thus, Schultz's model does not address a large set of problems which are common in practice. Our model differs from Schultz's in the following ways: 1. We assume full backlogging of unsatisfied demands. 2. We allow any amount to be held in stock. 3. We calculate shipment delays dynamically by continuously updating the distribu-tion of time until next demand. 4. We prove that a Delayed-(s-l,s) policy is optimal. 5. We extend our results to the problem with fixed order costs and prove that a Delayed-(s,S) policy is optimal. In order to take a different view, one would have to have a good reason to give attention to a wider class of policies. After observing a characteristic of the class of (s-l,s) policies mentioned by Axsater [4], we came to understand that perhaps there is Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 75 an optimal policy that is not so difficult to calculate and applicable under a more general set of assumptions. Axsater observes that if the holding and backlogging cost rates are linear then there is a one-to-one correspondence between orders and demands under an (s-l,s) policy. This is an observation that was also made by some earlier researchers. Derman and Klein [21, 22] mention that if the expected utility function of a unit of inventory drawn out of a stockpile of inventories is a nonnegative concave decreasing function of age of the unit, then a first-in-first-out order of inventory depletion is optimal. Hanssmann [46] shows that for any concave expected utility function a FIFO inventory depletion is optimal. In other words, if the expected cost of a unit in stock is a convex increasing function of age of the unit, then a FIFO depletion policy is optimal. This observation results in an important optimality property of one-to-one correspondence between demands and units ordered in a problem where we have full backlogging. That is, anytime we place an order, we know that this unit will be consumed after all older units have been consumed. This means we know, at the time we place an order for an item, which demand in the future will take it. It is this optimality property that allows us to find an optimal replenishment policy for a more general set of interdemand time distributions than just the Poisson process. In the next section we will present our approach in three stages and prove that what we call a Delayed-(s-l,s) is an optimal policy under the assumption that the interdemand times have any general distribution with increasing failure rate. We first calculate an optimal policy for the first demand to come and ignore others. Then, we extend the result to the case of N demands. Finally we generalize this result to the infinite horizon case. In Section 3.3, we give numerical examples for normal interdemand times in order to show that this new optimal policy can outperform the usual (s-l,s) significantly in a wide range of problem parameters. Finally, in Section 3.4, we extend our results to a problem with fixed order cost and prove that a Delayed-(s,S) policy is optimal under the Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 76 IFR assumption. We also show how to calculate the optimal delay and give an algorithm to calculate the optimal lot size Q = S — s. 3.2 A New Optimal Policy Suppose demands come in single units and the times between successive demands are independent and identically distributed random variables with a continuous probability distribution. Unmet demand is fully backlogged and replenishment orders arrive after a fixed time L. Each demand unit backlogged costs p ($/time) and each unit held in stock costs h ($/time). The objective is to minimize long run average cost per time. First, let us explain why one-for-one policies can not be optimal for this problem in general. Consider a product which is demanded fairly infrequently by a single customer. Suppose a product arrives in stock after a short lead time when a replenishment order is placed. Then, having just sold one such product, the chance of receiving another demand within a replenishment lead time may be very small. In this case, if we follow a one-for-one policy and place an order immediately after a sale, this order may have to wait long until a demand arrives, incurring a significant holding cost. A better alternative may be to wait for some time and place an order when a demand looks relatively more likely to arrive. This could be a good alternative especially when waiting gives us more information about the arrival time of a demand. This may typically be the case in many practical problems. Clearly, however, when demand is Poisson, the interdemand times (i.e. time between two successive demands) are exponential and no information is gained by waiting as the distribution of the remaining time until arrival will not change by waiting. This is basically the reason that a one-for-one policy is optimal for Poisson demand. For more general interarrival distributions this need not be the case and thus waiting until some critical time when demand becomes more likely to arrive may be wiser. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 77 Therefore, in order to find a better policy one has to allow order placement at any point in time rather than at epochs of demand arrival only. As we will show, it turns out that a one-for-one policy with some delay in placing a replenishment order is optimal for a more general class of interdemand time distributions. Now, we develop a new technique to search for an optimal order policy in continuous time. In our approach we break down the problem into stages in each of which we focus on individual demands. In the first stage, we examine a very simple problem where there is only a single demand to arrive at a random time in the future, identify the optimal policy and show how to calculate it. In the second stage, we assume only demands are to arrive in the future in single units and solve the problem. In the final stage, having observed a pattern in the previous stages, we extend our approach to the infinite horizon problem. 3.2.1 Single Demand Case Suppose we start at time zero with no stock on hand and on order and there will be a single demand for one unit in the future. Let X be the arrival time of this demand, which is a positive random variable with cdf pdf <f>(x) and mean pi. Since there is only one demand there will be only.one order. Our objective is to minimize the total expected cost for this demand. Clearly, the universal set of all policies is characterized by a single number t, the time that single order is placed. If we can determine the best time to place the order, we have an optimal inventory policy. Now, we start at time zero. Suppose we choose to order immediately. That is, our policy is t = 0. The expected cost of this policy as a function of lead time L is given by g{L) = hE(X - L)+ + PE(L - X)+ = (h + p)E(L - X)+ + h(p - L) Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 78 = (h + p) f dx + h(p - L) (3.1) Jo where h and p are the holding and backlogging cost rates, respectively. Note that ordering at time zero can not be optimal if delaying the order until some time t > 0 gives a lower expected cost (i.e. g(L + t) < g(L) for some t > 0). If we decide to wait until some time t, two events may happen: The demand may arrive before time t in which case it will obviously be optimal to immediately order. Alternatively, the demand may not arrive until after time t in which case the distribution of time until a demand arrives will have to be revised. Given that there is no arrival by time t, we denote the remaining time until demand arrival by Yt, its distribution function by $ i ( y ) , and its mean by pt- That is, we have $ t(y) = P{X — t < y \ X > i} , or »(y+_.) - *( t ) where $(.) = 1 — <&(•)• This is called the failure rate in reliability theory and r Mv) y gives the hazard rate or instantaneous failure rate (see Barlow and Proschan [9], pp.23). Note that since $(.) is assumed to be continuous, so is $*(•)• The expected cost, C(t), of waiting to place an order until time t or the demand arrival X whichever is earlier, can be written by conditioning on the two possible events {X < t} and {X > t} as follows: C(t) = <S>(t)Lp + $(t)[hE(Yt-L)++PE(L-Yt)+] = <S>(t)LP+$(t)l(h + p) f My)dy + h(ut-L)} Jo Noting that ^ = + * ) + ] Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 79 and / $t(y)dy = f Jo Jo $ ( y + £ ) - $ ( * ) dy 1 [E(L + t-X)+ -E{t-X)+ -$(*)£] , . • m the expected cost can be written as C(t) = hE(X-L-t)++PE{L + t-X)+-PE(t-X)+ = (h + p) dx + h(p - L - t) - pj §(x)dx. (3.2) Jo Jo Differentiating with respect to t, we have C\t) = (h + pML + t)-h-p$(t) = p$(t) - (h + p)$(L + t) = -h$(t) + {h + p)$(t) - (h + p)$(L + t) = » w M + ( * + r t * w - t y + t ) i = $ ( t ) P + p)$«(I)-fc]. Setting C(£) equal to zero and solving for t, the solution satisfies <*«(/,) = -r^- (3.3) n + p Note that (3.3) may not have a solution or may have multiple solutions, in which case the expected cost will have multiple minima or maxima. Thus, we will focus on the interdemand time distributions with increasing failure rate below. Increasing failure rate: Now, suppose the interdemand time has increasing failure rate (IFR), that is $t(y) increases in t for all y > 0. The following establishes the optimal time to order. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 80 Proposition 3.1 If the time until demand arrival has a continuous cdf which is IFR, then the optimal time to order is 0 if 1fc<*(L) fopt _ ) where t* solves (3.3). mm in{t*,X} if $(/,) < ^ < l i m ^ 0 0 $ i ( X ) X if l i n w $t(L) < h h+p Proof: If $„(£) = $(L) > then due to IFR assumption $ f (L) > ^ for all t > 0. Thus, the expected cost increases in t for all t > 0. That is, the optimal policy is to order immediately at time zero. Similarly, if < < l i m * - ^ <&t(L) then, due to the continuity of in t and IFR assumption, (3.3) has a unique solution, t*. Note that the expected cost decreases for all t < t* and increases otherwise. Then, t* must be a global minimum. Therefore, it is optimal to defer placing an order until t* or X, whichever is earlier. Finally, if r\mt->oo$t(L) < then due to IFR assumption, we have <&t(L) < for all t > 0. Thus, the expected cost decreases for all t > 0. That is, delaying the order until the demand arrival is optimal. • It can easily be seen that if the interdemand times are exponential, the left hand side of (3.3) becomes $(L). Thus, for all t the expected cost is either decreasing (if < o r increasing or constant for all t. Then, the optimal time to order for Poisson demand is topt = < ^ ^ ^ ( ^ ) ^ h+p \o if In case $(L) = any time between zero and X is an optimal order time. Chapter 3. New Optimal Policies for A. Unit Demand Inventory Problem 81 3.2.2 Case of N Demands Now, we generalize our approach to solve the problem for N demands with total cost criterion. We will see that for every demand there is an optimal time to place an order for its unit, and this optimal time will have the same form which will repeat itself for subsequent demands. This will help us solve the infinite horizon problem. We assume iV-demands are to arrive and our objective is to minimize the total ex-pected cost for them. Before we try to write down the expected cost, note that a first-come-first-served policy is optimal simply because h and p do not depend on time or demand. Thus, there is no incentive to backlog a demand in order to satisfy the next one to come as both are identical in terms of unit costs (see [21, 22]). Since we know that the first order placed will be given to the first demand to arrive and the second to the second demand, and so forth, the expected total cost can be written as the sum of the costs incurred for each demand. Furthermore, choosing the best time to order for each demand separately will minimize the total expected cost. We will use the following notation: • Xj\ jth interdemand time. • Tn = Y^j=i Xj '• time of nth demand. • = Y^j=k+i Xj '• time between kih. and nth demands. • Yt: remaining time until first demand arrival given it has not arrived by time t. Prob{X - t + Tl < y | X > t}: cdf of Yt. P r o b { r n < y } : cdf of Tn. t°p : optimal time to place the jt 'th order. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 82 Note that T% is equivalent to Tn-k in distribution and independent of X\, ...,Xk and Yt. Now, let s be such that exist a finite integer s which satisfies (3.4). Now, we will find an optimal policy through the following propositions. We assume N is large enough so that s < TV. Otherwise Proposition 3.2 below will suffice to prove that it is optimal to order TV units at time zero. The propositions below assume that interdemand times, Xj,j = 1,2, ...,7V are IFR, with continuous cdf. It is well known that sum of IFR random variables is also IFR Proposition 3.2 For demands 1,2, ...,s — 2,5 — 1, it is optimal to order at time zero (i.e. t°npt = 0forn<s). Proof: We use induction. For the first demand (n = 1), we have shown in single demand case that if $l(L) > j ^ , then €£l = 0. Now, assume t°*li = 0 for some n — 1 < 5 — 1. Then, for the nth demand unit, let us find the optimal policy. Note that if we wait until X\, we will have to order immediately at X\. This is because at time X\, the problem for the nth demand is equivalent to that of the n — l'st demand at time zero and 2 ° ^ = 0 by the assumption of induction. Thus, we know that 0 < topt < Xi. More specifically, the optimal time to order is of the form min{t,Xi}. Conditioning on the two events {Xi < t} and {Xi > t}, the expected cost of this policy as a function of t can be written as (see [9], pp.36). Cn(t) *{t)[hE(Yt + TI - L)+ + PE(L -Yt- Ti)+] +m[hE(n-L)++PE(L-T^}. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 83 Note that the expression in brackets in the second term is equal to C„_i(0). Define g»(L) = hE(Yt + TI - L)+ + PE(L -Yt- Tn1)+. (3.5) This is the expected cost of ordering at time t, given that no demand has arrived until t. Then, we have Cn(t) = $(t)g?{L) + $(i)Cn_x(0). (3.6) Equivalently, Cn(t) = hE[{Xi-t)+ + T]i-L]++pE[L-(X1-t)+-T*]+ = (h + p)E[L - (X, - t)+ - T*]+ + h{E{X1 - t)+ + fi(n - 1) - L) rL rL+t pL—x+t = (h + p)[$(t) / $n-1{y)dy+ / / ^n-\y)(j)(x)dydx] Jo Jt Jo +h[np-t-L+ / $(x)dx] Jo Now, differentiating with respect to t, we have Cn'(t) = (h + P)(^(t)Jo $n-l(y)dy + / ^n-1(y)dy(j)(L + t)- J $n-l{y)dy<f>(t) rL+t \ + J ^ ( L - x + WWdxj rL+t /+t -x + t)<f>{x) dx - h$(t) rL+t ' 6(x) = (h + p)*{t)J *»-\L-x + t)^+dx-h*{t) Note that the integral in the last expression is $"(X). Then, we have Cn'(t) = ^(t)[(h + p)^{L)-h]. (3.7) Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 84 But, we know from the assumption of IFR that $"(£)• > $n(L) > ^ for all n < s and all t > 0. Then, Cn(t) is increasing in t > 0. Thus, topt = 0. This completes the induction and the proof. • Proposition 3.3 For demand s, the optimal time to order is toPt = I ™n{nM if ifc<lim^- *'t(L) I Xi otherwise where t = t* solves ^ st(L) = Proof: From Proposition 3.2 we know that for the s — 1st demand it is optimal to order at time zero. Thus, the optimal time to order for sth demand must be at or before X\. This is because, if we wait until X\ to order for the sth demand, we will have to order at Xi to be optimal as the problem of sth demand at time Xi becomes identical to the problem of s — 1st demand at time zero. Thus, the form of the optimal policy is min{t,Xi}. Then, the expected cost of this policy Cs(t) will be given by (3.6) for n = s. Thus, from (3.7) we have C;(t) = Q{t)[{h + p)*'t(L)-h]. But, l i m ^ 0 $ ? ( £ ) = ®S(L) < j ^ . If we have h lim $st(L) > t—+oo h+p then, since $*(L) in continuous in t, there exists a finite time t* which satisfies W) = iH-p ( 3- 8) Note that for all t < t*, we have Cs\t) < 0 and thus Cs(t) is decreasing. Similarly, for all t > t*, Cs(t) is increasing. Therefore, t = t* is a global minima for Cs(t). Hence, the optimal time to order for demand s is t°f = min{t*s,Xi}. (3.9) Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 85 K xfe > l i n w , there is no solution to (3.8) and Cj(i) > 0 for all t > 0, which means it is optimal to wait until the arrival of the first demand. Thus, we have t°pt = Xx. • P ropos i t ion 3.4 For demands s + j, j = 1,2,3,..., it is optimal not to order until Tj. Proof: Define Note that gn~1(y) is the cost of ordering for demand n — 1 at time t = 0 (or for demand n at time t = Xi) with a lead time of y. The derivative with respect to the lead time is dan~l(v) y d =(h + p)^n~1{y) -h<0 for all y < L, when n > s. Hence, g^iy) > g71'1^) for all y < L. Now, suppose we have waited until some time t, and no demand has arrived (t < X\). Then, from (3.5), the cost of ordering now (at time t) for the nth demand (n > s) is g?{L) = hE[(T' + Yt-L}++pE[L-n-Yt] + = hE[Tl - (L - Yt)}+ + pE[{L - Yt) - T'n] = E[gn-\L-Yt)] > 9n-\L) = C7n_!(0). The inequality follows because gn~l(L — Yt) > g71*1^) for all realizations of nonnegative random variable Yt. The above implies that having waited until any time t < X\, the cost of ordering at time t is always higher than the cost of waiting until X\. Therefore, topt > Xi for all hE[Tl - y}++ pE[y - Tl\ Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 86 n > s. Furthermore, let us use a simple induction. That is, for j = 1 we have just shown that £°^j > T i . Assume t°^- > Tj for some j > 1. Now, for j + I, we know t°^-+1 > T\. But, at t = T i , the problem of demand s + j + 1 is equivalent to the problem of demand 5 + j at t = 0. Thus, £°^- + 1 > T j + i . • Proposition 3.4 implies that for demands s + l , s + 2 , t h e optimal policy is not to order until s demand units remain to its arrival, at which time it is optimal to wait as long as t* or the next demand arrival, whichever is earlier. Therefore, propositions 3.2, 3.3, 3.4 establish that in general the optimal order policy will be given by toPt ( TJ+mm{t*s,XJ+l} if j = 0,l,...,N-a ^ ^ \ 0 if j = - s + l , - s + 2 , . . . , - l . 3.2.3 Infinite Horizon Case Now, we see that t* does not depend on n. Therefore, the optimal order policy takes the same form for sth demand and all others to come later. Therefore, the optimal expected cost for each demand to come after the s — 1st will be the same. Since, we can ignore the effect of the initial 5 — 1 demand units for the -infinite horizon, the long run average cost will be equal to the expected cost of a single such demand. Thus, the long run average cost per time can be calculated by taking the time between the two successive demands as a cycle and cost per item as cost per cycle. Then, using the basic Renewal Reward Theorem (see Wolff [119], pp.60), the long run average cost per time can be calculated by dividing the expected cost per cycle by the cycle length. Thus, the average cost per time as a function of s and t is AC(s,t) = C.(t)/p. Note that the cycle time is not .affected by the the order policy (this is mainly due to Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 87 the full backlogging assumption). Therefore, minimizing total expected cost is equivalent to minimizing the expected cost per cycle. The policy we have here is like an (s-l,s) or one-for-one order policy except with some delay of at most t for placing an order. We will call this a Delayed-(s-l,s) policy, and denote it by (s, t) for a delay of t. Since every (s-l,s) policy can be viewed as a delayed policy with a zero delay, (s-l,s) policies constitute a subset of Delayed-(s-l,s) policies. The optimal values of s and t can be calculated from (3.4) and (3.8). Also note that if s satisfies (3.4), either (s-l,s) or (s-2,s-l) is an optimal one-for-one order policy and the cost of either is no smaller than the cost of the optimal delayed policy (s,t*). 3.3 A n Example with Normal Interdemand Times The theory in the previous section gives an optimal inventory policy for a wider class of problems with unit demand than just Poisson demand. We know that this policy would do better than regular one-for-one policy unless interdemand times are exponential. However, an important question is whether the added complexity of introducing a delay and not restricting ordering at demand epochs is worth all the trouble in the case of general (non-exponential) interdemand times. In other words, can widely used (s-l,s) perform as well as the Delayed-(s-l,s) for more general interdemand times? In order to answer this question, we will present an example. We assume interdemand times are normally distributed with an appropriate standard deviation to mean ratio so that the chance of negative interdemand times is negligible. We varied this ratio as well as other critical parameters such as the lead time L, holding cost rate h and backlogging cost rate p. Since the rate of cost reduction will not be affected by nominal values of h and p, we will take the ratio p/(p + h) as a variable parameter. Since the same applies for the relative values of L and p, we let p = 10, and vary L and standard deviation a. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 88 Let 8 = oIp denote the coefficient of variation. Here are the values used: • 6 = (0.1, 0.2, 0.3) • L = (5, 25, 75) For each combination, we calculated the optimal Delay ed-(s-l,s) and (s-l,s) policies and their costs for a grid of values of the ratio p / ( p + h) in the interval (0,1). The results are summarized in Figure 3.1. The savings are defined as Cost( Del ayed-(s-l,s)) - Cost(s-l,s) %Savmg = . Cost(s-l,s) Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 89 (a) js t .dev / mean = 0 . 1 o» c •> CO # 100.00 80.00 60.00 40.00 20.00 0.00 (c) s t . d e v / mean = 0 . 3 Lead time = 5 -O- Lead time = 25 Lead time = 75 Figure 3.1: A comparison of Delayed-(s-l,s) and (s-l,s) for normal interdemand times. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 90 It is surprising to see how poorly (s-l,s) performs in the majority of cases. Interest-ingly, for relatively smaller values of the standard deviation, the performance is poorer. This may sound counterintuitive, but it is a good illustration of the non-optimality of (s-l,s). Suppose the standard deviation is near zero. That is, we know fairly well when the demand will arrive. In this case, it is trivial to know when it is optimal to place an order. Let us take a lead time of L = 5. If the last demand has just arrived and we know that the next demand will arrive more or less 10 units of time later, we will order after a delay of 5 so that both stock ordered and the demand will come at the same time enabling us to avoid incurring any holding or backlogging cost. However, an (s-l,s) policy would make us order immediately after observing a demand in which case we would incur a holding cost of 5h, or when the next demand arrives in which case we would incur a backlogging cost of 5p. When the variance is eliminated, (s-l,s) becomes completely unacceptable. But, one would think that when the uncertainty is reduced, a stochastic model should converge or link to its deterministic version. An optimal (s-l,s) policy for a stochastic model will not converge to an optimal inventory policy of its deterministic version when we eliminate the variance. It is easy to see, however, that a Delayed-(s-l,s) policy has this link and thus remains optimal when we reduce the variance of interdemand times to zero. Thus, Delay ed-(s-l,s) policy also closes the conceptual gap that exists between stochastic and deterministic problems for the classical one-for-one policy. One may think, from the above discussion, that when lead time is an integer multiple of mean interdemand time, the performance of (s-l,s) may improve, as it converges to an optimal deterministic policy when uncertainty is eliminated. However, this does not seem true, as our further numerical studies with L = 10,30,80 showed similar savings. Figure 1 also indicates that as lead time increases, cost reduction decreases. This is because as the optimal stock level increases, the problem becomes one with a relatively high demand item (i.e. more demand during lead time) in which case the interdemand Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 91 times are no more significantly long compared to the lead time. This reduces the impact of delaying the placement of orders. . As for the effect of cost parameters, although the greatest reduction seems to occur consistently when holding and backlogging cost rates are comparable, we think this was due to the consistent phase difference between the mean interdemand time of 10 and L — 5, 25, 75. When we did the same calculations for L = 10, 30,80, the biggest reduction occured consistently for the extreme values of p/(p + h). 3.4 The Inventory Problem With Fixed Order Cost We will use the same method as we did in the case of no fixed order cost. Our objective is to minimize the long run average cost, and thus we can choose to start with the demand unit s, first (here s is defined by (3.4)). We assume the demand units l,2,...,s-l are satisfied with some order policy which can be ignored as their cost will be insignificant in the long run. Since there is a cost of K everytime we order regardless of the amount we order, there will be a saving on this fixed cost if we choose to place the orders jointly. However, this will increase the expected cost of backordering and stock holding since we will not be able to order at the best time for each individual demand so as to minimize its individual expected cost as we did in the previous problem. We will rather have to choose a single order time for all of these Q demands. Due to this trade-off between the costs, we face two decisions: What size should the order be? When should the order be placed? Now, let us consider a joint replenishment for demand units s, s + 1 , s + Q — 1. If we chose to order for them separately at their optimal times given by (3.10), their total expected cost would be QK + QCs(t*). Suppose we have chosen to place an order for a lot of size C}, to be consumed by Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 92 demands s,s + 1, ...,s + Q — 1. We will seek to minimize the total expected cost of this lot. Later, we will look for an optimal lot size. Given that the order size is Q, the only problem which remains to be solved is when to place this order. If this time is t < Ti for instance, the total expected cost of the lot will be s+Q-l Note that the optimal order time cannot be earlier than t°pt or later than r^+g^. This is because all individual costs, Ci(t), will be decreasing if we wait until t°pt and increasing after t^Q_v Now, from the individual optimal order times in (3.10), we have 0 = To < < Tx < * £ \ < T 2 < . . . < T Q _ ! < i f Q _ i ^ TQ-where Tj is the time of j th demand as defined previously, with T 0 = 0. Let us consider ordering no earlier than TQ_I. Clearly, if we wait for some time r after Tg_i , two things may happen: We may receive the next demand before TQ_I + T, or we may reach TQ_I + r before the next demand. Now, if the next demand arrives early, the optimal action is to order immediately as the individual costs will all be increasing after time TQ. If we have waited for a duration of r and the next demand is yet to arrive, we place the order. Note that under this order policy, the individual expected costs of demands s, s + 1 , s + Q - 1 will be CS-Q+I(T), C S _Q + 2 (T), CS'(T), respectively. Then, denoting the expected total cost of this lot of size Q by TCo(Q, r) (the reason for using the subscript 0 will be clear later), we have s TC0{Q',T)= Y, C i ^ - t 3 - 1 1 ) i=s-Q+l Here unlike the case of no order cost, it is possible for i to be negative. This means we order a lot of size Q no earlier than the arrival time of stli demand, in which case we Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 93 start backlogging some demands even before we order for their units. For instance, if s — Q + 1 = —2, this means the lot is ordered sometime between TS +2 and T S +3, and thus demands s, s + 1 and 5 + 2 are already backlogged when the order is placed. For negative i, C;(r) will have the same interpretation, however, the expected cost of policy (i — with delay r . That is, we wait until we have \i — 1| backorders and then place an order after a delay r , or when the next demand arrives, whichever is earlier. Notice that this order will always find a backlog when it arrives and thus no holding cost will be incurred. Thus, the expected cost for i < 0 will be Ci{T) = p(L — ip) + pE[min{r, X}] = p{L - ip) + pE[r - (r - X)+] = p[L + T-iu.-E(T-X)+] = p[L + r - i p - I $(x)dx]. Jo where X is an interdemand time with cdf and mean p,. The derivative of the expected cost is C\{T) = p-p^r) • = P$(T). (3.12) As for i > 0, the expected cost is given by (3.6). That is, we define the individual costs in (3.11) as N ( , \ $(TU(L) + $(T)C^(0) if » = 1,2,... M T ) = \ ( p[L + r - i p - E(T - X)+] if z = . . . , - 2 , - 1 , 0 . In order to find the latest time until which we should keep waiting in case of not receiving the next demand, we simply minimize TCQ(Q,T) over r . Differentiating with Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 94 respect to r, from (3.7) and (3.12) we have s TC'0(Q,T) = *{T) Y [(h + PWT(L) - h]. i = s - Q + l where = 1 for i = ... - 2, -1 ,0 . Note that the sum is increasing in r due to IFR assumption. Thus, the optimal value of T for a lot size of Q is s T^KTQ^ if T Q Q , 0 ) = £ [{h + p)&(L)-h]>0 i=s-Q+l TQ-I < TQ1 < TQ otherwise . We will show this to be true in general by induction. That is, suppose for some integer m > 1, we have s+m —1 £ [(h + P)^(L)-h}>0. i—s — Q+m That is, the optimal time to order is TQ1 < TQ-M. Then, for m + 1, let us consider ordering in the interval [Tg_m_i, T<g_m]. If we choose to wait for some time r, in case of early demand arrival we know it is optimal to order immediately. Otherwise, we order when we reach r<g_m_i + r. Then, the expected total cost can be written as s + m TCM(Q,r)= £ C,-(r). i—s—Q+m+l Differentiating with respect to T , we have s+m TCm(Q,T) = <f>(T) £ [(/i + p)$;(L) - h]. i=s—Q+m+l Then, the optimal time to order will be s+m T°^<TQ_M_X if Y [(h + p)&(L)-h]>0 i=s—Q+m+l T Q _ m _ ! < Tg pt < T g _ m otherwise. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 95 This completes the induction. Thus, given a lot of size Q, let m(Q) be such that s+m(Q) s+m(Q)-l a(Q)= £ [(h+p)&(L)-h]<0< £ [(h+p)&(L)-h] = b(Q). (3.13) i-s-Q+m(Q)+l i=s-Q+m(Q) Then, the optimal time to order will be TQ-m(Q)-\ < Tg pt < r Q _ T O ( Q ) . More specifically, given (3.13), the optimal time to order a lot of size Q is T ° p t = m m { r g _ m ( Q ) _ 1 + TQ, TQ_m{Q)} (3.14) where at r = TQ we have s+m(Q) £ [ ( ^ + p ) ^ ( i ) - ^ ] = o. i=s-Q+m(Q)+l Now that we have calculated the optimal time to order given that for demands s, s + 1, ...,s + Q — 1, a joint order of size Q is to be placed, we can turn to calculating an optimal lot size. The average cost per unit, when a lot of size Q is ordered at an optimal time, is given by AC(Q) = ^ - - W Q H i + ( 3 1 5 ) The next step is to calculate an optimal lot size Q. Once we find an optimal lot size, it is easy to see that it will be optimal to place an order of the same size for subsequent demands. This will give us an optimal lot size in the infinite horizon. Then, similar to the case of (s-l,s) in Section 3.2.3 let us define an interdemand time as a cycle, and the expected cost per unit demand as cost per cycle. Then, we can use the Renewal Reward Theorem in order to calculate the long run average cost per time by AC(Q)/u.. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 96 H o w to Calculate an O p t i m a l Lot Size: When we increase the lot size to Q + 1, fortunately, we do not have to search for the optimal delay too long due to the following proposition. P ropos i t ion 3.5 If m(Q) is given by (3.13) for a lot of size Q, then for a lot of size Q + 1, m(Q + 1) is either m(Q) or m(Q) + 1. Proof: By definition m(Q + 1) satisfies s+m(Q+l) s+m(<3+l)- l a(Q+l)= [(h+p)&(L)-h]<Q< [(h+p)*i(L)-h] = b(Q+l) i=s-Q-l+m{Q+l)+l i=s-Q-l+m(Q+l) We know is nonincreasing in i. Then, the sums are also nonincreasing in m(Q). Now, let m(Q + 1) = m(Q) + 1. We have s + m ( Q ) + l a(Q + l)= J2 [(h + p)&(L)-h]<a(Q)<0. i=s-Q+m(Q)+l Then, if 6(0 + 1)= Yl [(h + p)&(L)-h}>0, i=s-Q+m{Q) (3.13) is satisfied for Q + l, and thus proposition holds. Otherwise, let m(Q + l) = m(Q). We have s+m(Q) a(Q + l)= Y [(h + p)&{L)-h}<0. i=s-Q+m{Q) Also, s + r o ( Q ) - l 0<b(Q)< Y [{h+p)&{L)-h] = b(Q + l). i=s-Q+m(Q)-l Then, the (3.13) is satisfied again, and thus the proposition holds. • From Proposition 3.5, the average cost for a lot size of Q + 1 is Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 97 Unfortunately, we have no proof for the unimodularity of AC(Q) in Q. This is because, for each lot size Q , we have a different T Q , and thus, values of C , ( T Q ) ' S will change by Q. Therefore, simple search methods for calculating an optimal lot size will not work. However, we will provide some upper and lower bounds for the optimal lot size, below. Although, we are not able to give any theoretical assessment of the performance of these bounds, they appeared to be quite tight in our numerical calculations. Now, we will present these bounds and an algorithm which utilizes them in order to calculate an optimal lot size. Clearly, the propositions 3.2, 3.3, and 3.4 imply the following order for all r > 0, T I > t*s and r 2 < t*: - > C s _ 2 ( r ) > C s_ 2(0) > GVxtr) > C s_i (0) > CS{TX) > CB{t% ... > C s + 2 ( r ) > C s + 1 ( 0 ) > C , + 1 ( r ) > C.(0) > C s ( r 2 ) > C,(t;). (3.17). Also, from (3.17), we have the following lower bounds on individual costs for all r > 0: Ci(r) > C,(0) for i = ...,s - 2,s - 1. Cs(r)> CM) C,-(r)> C,-_!(0) for i = s + l,5 + 2,... Now, let us find a lower bound for the optimal lot size. Replacing all C^TQ) by their lower bounds in (3.15), we define a lower bound for average cost AC(Q) by E £ - q + m ( q ) + i cm + + E f f f f * c,-(o) + K ; Q • (3-18) Note that ACLBi(Q) always has the Q — 1 smallest C;(0)'s and Cs(t*). Since C;(0)'s are fixed quantities, with respect to Q, it is easy to see that ACLB\(Q) is unimodal in Q. Let Q* be the optimal lot size which minimizes ACLB\(Q). ACLBAQ) Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 98 Propos i t ion 3.6 Let QLB be the biggest integer less than Q* + I, such that ACLBI(QIB - 1) > AC(QLB). Then, QLB is a lower bound for the optimal lot size. Proof: Since AC LB\{Q) is unimodal, we must have ACLB1{\) > ACLBi(2) > ... > ACLB^QLB - 1). Then, it is easy to see that AC(Q) > ACLBtiQ) > ACLBX{QLB - 1) > AC{QLB) for all Q — 1,2,..., QLB 1. This completes the proof. • Now, we will find an upper bound for the optimal lot size. Define x QAC(Q) + C*0 ACLB2(Q + 1) = - ^ 5. (3.19) where C*Q = mm{C7 s_ g + m(Q)_i(0),C7 s + m(Q) +i(0)}. Note from (3.17) that CQ is always nondecreasing in Q, since rn(Q) is nondecreasing from Proposition 3.5. From (3.16) and Proposition 3.5, rewriting the expected total cost for a lot size of Q + 1, we have A n / n l n E'=r(q|m(q)+i Ci(TQ+i) + min{Cs-Q+m(Q){rQ+1),Cs+m{Q)+1(T^+1)} + K AC(Q + l) - — Ej=^.(q|m(0)+1 C i ( T Q ) + mm{Cs-Q+m(Q)(r^+1),Cs+m{Q)+1(T^+1)} + K Q + l > Q AC(Q) + m m { C , ^ + m ( g ) - i ( Q ) , C s + m ( Q ) + 1 (0 )} Q + l Q AC(Q) + C*Q Q + l . = ACLB2(Q + 1) Then, ACLB2(Q + 1) is a lower bound for AC{Q + 1). Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 99 Propos i t ion 3.7 Let QUB be the smallest integer Q which satisfies AC{Q) < ACLB2(Q + 1). Then QUB is an upper bound for the optimal lot size. Proof: First, we can see from the definition of ACLB2(Q + 1) and the condition of the proposition that AC{Q) < ACLB2(Q + 1) < C*Q. Also note that CQ < CQ+1. Now, we will use induction. For Q + 2 we have (Q + 1)AC(Q + 1) + CQ+1 AC(Q + 2) > ACLB2(Q + 2) > Q + 2 {Q + l)ACLB2{Q + 1) + CQ+X Q + 2 > ACLB2(Q + 1) > AC(Q). Assume ACLB2(Q + n)> ACLB2(Q + 1), for any n > 2. Then, for n + 1, (Q + n)AC(Q + n) + C*Q+n AC(Q + n + 1) > ACLB2(Q + n + 1) > > > Q + n + 1 (Q + n)ACLB2(Q + n) + C*Q+n Q + n + l (Q + n)ACLB2(Q + 1) + C*Q+n Q + n + 1 {Q + n)ACLB2(Q + l) + C*Q+1 Q + n + l > ACLB2(Q + 1) > AC(Q). This completes the proof. • Now, based on these two propositions, we have the following algorithm for calculating an optimal lot size Q. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 100 Algorithm: 1. Calculate Q*. Q <— Ql, AC* <— AC{Q). 2. Q <— Q-l. If (Q = 0 or ACLBi(Q - 1) > AC*) then go to 4 3. If AC{Q) < AC* then (Q* ^ — Q, AC* <— AC(Q)). Go to 2. I Q <— Ql-5. Q < — Q + l. 6. If ACLB2{Q) > AC* then go to 8. 7. IfAC{Q) < AC* then (Q* <— Q, AC* <— AC(Q)). Go to 5. 8. Stop. Q* is the optimal lot size and AC* is the minimum cost. We could have used ACLBi(Q) to calculate an upper bound as well as a lower bound for the lot size. However, our calculations showed that the upper bound given by ACLB2(Q) is much tighter. Table 3.1 shows the performance of the algorithm in terms of the bounds for an example problem with normal interdemand times. When we changed various problem parameters, the performance of bounds were similar. 3.5 A n Example with Normal Interdemand Times In order to see how significant of a cost reduction Delayed-(s,S) policies would result in as compared to (s,S) policies, we have generated a set of test problems with normal interdemand times. We varied the coefficient of variation 8, the lead time L, and the order cost K. The values we used are: o 8 = ( 0.1, 0.2, 0.3 ), L = ( 5, 25, 75 ), K = ( 3, 10 ) Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 101 No-delay Optimal Delayed Optimal Optimal Delay Savings Lead Time p/(p+h) ..( s,Q) (s,Q) TQ QLB , QUB (%) 5 0.10 (-3, 4). (-3, 5) 5.01 3 , 6 9.34 0.30 (-1, 3) (-1 3) 3.72 2 , 3 1.66 0.50 .(-1,4) (0, 3) 5.01 2 , 3 9.34 0.70 ( °, 3 ) (1 ,3) 6.28 2 , 3 1.67 0.90 ( 0, 6) (1 ,5) 5.01 3 , 6 9.34 0.95 (1 ,6) (1 ,6) 4.48 5 , 6 6.06 0.99 ( 1,14) ( 1,14) 3.92 11 ,14 2.41 25 0.10 (-2, 5) (-1, 5) 5.00 3 , 6 8.04 0.30 (1 ,3) (1 ,3) 2.76 2 , 3 1.02 0.50 ( 1,4) (2 , 3) 5.00 •2 , 3 8.05 0.70 ( 2 , 3) (3 , 3) 7.20 2 , 3 1.02 0.90 ( 2, 6) (3 , 5) 5.00 3 , 6 8.05 0.95 ( 3, 6) (3 , 6) 4.08 5 , 6 4.73 0.99 ( 3,14) ( 3,14) 3.15 11 ,14 1.60 75 0.10 ( 3, 5) (4, 5) 5.05 3 , 6 6.22 0.30 ( 6, 3) (6, 3) 1.54 2 , 3 0.36 0.50 (6 , 4) (7, 3) 5.05 2 , 3 6.32 0.70 (7, 3) (8, 3) 8.42 2 , 3 0.27 0.90 ( 8, 5 ) (8 , 5) 5.05 3 , 6 6.27 0.95 ( 8 , 6 ) (8 , 7) 3.88 5 , 7 3.01 0.99 ( 8,14) ( 8,14) 1.98 11 ,14 0.57 Table 3.1: An example: Interdemand times are Normal(l0,1), and K = 10. Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 102 In total we have 18 combinations in each of which we calculated savings for different values of p/(p + h) ratio. The results are in figures 3.2 and 3.3. Generally, as one would expect, savings drop by increasing lead time and increasing order cost. Increasing these parameters cause reorder inventory level and batch size to go up, respectively. This, in turn, reduces the effect of delaying due to the same reason as in the case of one-for-one order policies. Again, savings are higher for lower standard deviation to mean ratios, consistently as in the previous case. Although p/(p + h) seems to have an impact on the amount of savings, it looks case dependent and no trend is observable. This is probably due to the discrete nature of the problem (i.e. unit demands, discrete reorder levels and batch sizes). 3.6 Conclusions and Remarks For single-echelon, single-item, unit-demand inventory problems, a one-for-one order pol-icy in case of no fixed order cost, and a batch ordering policy in case of positive order cost are known to be optimal when demands are generated by a Poisson process. However, for demand processes other than Poisson, optimal policies have been unknown. This study shows that their delayed versions are optimal when demand has a general distribution with IFR interdemand times. Our numerical examples reveal that at least for normally distributed interdemand times, by using the delayed versions, it is possible to obtain significant savings especially when the degree of uncertainty about the demand arrivals is relatively low. Significant cost savings are possible not only for expensive items with high holding costs, but also for inexpensive items with long lead time relative to the mean interdemand time. The most relevant factors for inventory cost reduction seem to be the coefficient of variation and the lead time to mean interdemand time ratio. Although the price of Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem (a) s t . d e v / mean = 0 . 1 p/(p + h) (b) st. dev / mean = 0.2 20.00 g 15.00 | 10.00 (c) s t . d e v / mean = 0 . 3 p/(p+h) Lead time = 5 Lead time = 25 -• Lead time = 75 Figure 3.2: Delayed-(s,S) versus (s,S) for normal interdemand times (A' = 3). Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem (a) s t . dev I mean = 0 . 1 10.00 8.00 > 6.00 CO 4.00 2.00 0.00 (b) s t . d e v / mean = 0 . 2 8.00 p/(p + h) (c) s t . d e v / mean = 0 . 3 Figure 3.3: Delay ed-(s,S) versus (s,S) for normal interdemand times (A' = 10) Chapter 3. New Optimal Policies for A Unit Demand Inventory Problem 105 the item and the backlogging cost rate do not seem to be relevant factors, they may turn out to be so when the actual amount of savings is considered rather than the relative savings. We have not extended our numerical work to other distributions. However, we are convinced that savings will remain significant especially for distributions with low coef-ficient of variation. There may be some difficulty involved in calculating optimal delay when convolutions of interdemand time distribution is not easy to take, as the optimality equation needs convolutions. For the normal distribution, we did not have this difficulty as its convolution remains to be normal. Convolutions of gamma are also easy as they will remain gamma. A gamma distribution with high shape parameter could give signifi-cant savings. This is because, a high shape parameter means low coefficient of variation. Obviously, for a shape parameter of 1 (exponential interdemand times), there are no savings. An application of gamma distribution would be for a supplier facing a major customer which orders in fixed batch sizes. If the customer receives Poisson demands, then interdemand times for the supplier will be gamma distributed. For instance, if the customer orders in lots of size 100, then the interdemand time for the supplier will have a coefficient of variation of 0.1, which is fairly low. As this is comparable to our example with Normal distribution, delaying should have a significant cost reduction. Delayed order policies may have a potential to yield considerable cost reductions in 2 or more echelon models when substituted for their no delay versions. In problems where the delivery lead times between the echelons are long and the demand frequency is low with relatively low uncertainty, the reductions should be higher. Chapter 4 A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales Abstract We develop a heuristic for a single-echelon, single-product, Poisson demand, continuous review inventory problem with lost sales. Orders arrive after a fixed and known lead time. The costs of backlogging and inventory carrying are both linear in time, and there is no fixed cost for placing an order. It is well known that if full backlogging of unsatisfied demand is allowed, a one-for-one order policy is optimal for this problem. Although the optimality of this policy is not known for the lost sales case, it has been used with the belief that its performance is satisfactory. We suggest a new policy as an alternative which, although myopic in nature, uses more information. We calculate its cost through simulation over a test set of problems and show that although one-for-one policy performs well in problems with short lead times and high lost sales costs, the heuristic performs better for problems with long lead times and low lost sales costs. 106 Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 107 4.1 Introduction We study a classical inventory problem where we have a single-echelon and a single-product for which the demands arrive according to a Poisson process in single units. The review is continuous and unmet demand is lost. There is no cost for placing an order which arrives after some fixed lead time L. The cost of a lost sale is TT per unit and the cost of carrying inventory is h per unit per time. For this problem, it has been established for some time that an (s-l,s) policy or a one-for-one order policy is optimal under the Poisson assumption if unsatisfied demand is fully backlogged [3, 45]. This is also called a "sell one buy one" policy under which, as its name indicates, a base amount of inventory, s, is maintained in stock and whenever there is a sale of an item, a replenishment order is placed immediately. However, it is also well known that when unsatisfied demand can not be backlogged and thus will have to be lost, an optimal inventory policy is unknown and believed to be complicated. Therefore, one-for-one policies have been the main focus of research for the lost sales case just as for the backlogging case. The popularity of the (s-l,s) policies can be explained by the fact that it is known to be optimal for the backlogging case and that it is simple and practical. Today's competitive business environment with its significant focus on customer ser-vice has generated a need for more efficient inventory policies. Although simplicity of policies may still be an appealing factor, today's advanced computer technology makes the application of more sophisticated policies more feasible and easier than ever. In the context of this particular problem, it is possible to use more information than a simple one-for-one policy in order to come up with a more efficient but also more complicated policy. Most of the work in the literature deals with the case of backlogging. A summary Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 108 of the literature can be found in the introduction part of Chapter 3, and will not be repeated here. Although the case of unsatisfied demand being lost is typically more common in practice, there has been considerably less research on both periodic and continuous review problems with lost sales, most likely because the theory becomes much more difficult. Since the form of an optimal policy is conjectured to be very complicated, most researchers focused on calculating an optimal policy of an (s,S) type. Feeney and Sher-brooke [36] studied (s-l,s) policies when there is no fixed order cost for both backlogging and lost sales cases. They assumed a compound Poisson demand and stochastic lead time and derived exact expressions for the steady state probability distributions of the num-ber of units in the pipeline. This allows one to calculate several performance measures including the long run average cost. Archibald [2] developed a method to calculate optimal values of s, and 5, so as to minimize long run average cost, assuming compound Poisson demand for a continuous review problem with a fixed cost for ordering. His method works only when the fixed order cost is large enough so that no more than a single order can be outstanding, (i.e. S-s>s). In two subsequent papers, Morton [67, 68] obtains bounds for the optimal policy and expected discounted cost for an infinite horizon periodic review problem. He shows for normal, exponential and a long-tailed demand distribution that a myopic policy (which aims to minimize the expected cost affected by the last order) delivers a cost within 2.5% of that of the optimal. The performance decreases with increasing lead time. Since, he does not extend his numerical study to problems with lead time longer than 2 periods, it is not known how weak his myopic policy will become for longer lead times. Smith [106] studies an (s-l,s) policy with Poisson demand under the assumptions that the lead times are random with a general distribution, and shortages are handled with Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 109 an emergency shipment at a premium charge. He derives an approximate formula for the optimal stock level s, and shows through some numerical tests that the approximation gives near optimal policies. He also gives approximate formulas for two service measures, the expected number of shortage per time unit and the probability of shortage on any given demand. As mentioned in the previous chapter, a work which seeks an alternative inventory policy to an (s-l,s) policy was published very recently by Schultz [92]. However, his model is very similar to Smith's with the exception of a constant lead time instead of random. Thus, it is not a typical lost sales problem due to the assumption that instant delivery of the items in the pipeline is possible with a premium charge in case the facility faces a shortage. Thus, in his model like Smith's, lost sales are not allowed and they never occur. This assumption is not made in an ordinary lost sales problem and therefore lost sales will have to be incurred. This is exactly what makes it difficult to solve, since the use of inventory position (stock on hand plus on order) as the state variable is no longer a valid approach that leads to an easy steady state analysis, as in the case of full backlogging. As explained much earlier in Hadley and Whitin [45] and in Arrow et al [3], the difficulty is due to the state space having to include inventory both on hand and in the pipeline, whereas in case of full backlogging, modelling is possible by taking the inventory position as the state variable. For continuous review models, it becomes even more difficult as the state has to include the remaining lead times of all pipeline inventory. This makes the state a vector of continuous variables. When using an (s-l,s) this information is not made use of The idea of using the information given by the arrival schedule of the pipeline inventory has been considered by Schmidt and Nahmias [86] in the context of perishable inventory problems. When the type of product under consideration has short shelf life, the information as to when the pipeline inventories will arrive and how long Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 110 they will have to wait in stock becomes more crucial. Schmidt and Nahmias studied an (s-l,s) policy for a perishable inventory with Poisson demand and derived joint steady state probability distribution of the ages of the pipeline inventories. Then, based on this, they provide an expression for the long run average cost of an (s-l,s) policy. Other work on perishables include [39, 74, 116], and a review can be found in Nahmias [75]. The effect of the arrival schedule of the orders in the pipeline will be explained further by an example for our lost sales problem in the next section. Then, a myopic heuristic which takes the vector of remaining lead times as a state variable and utilizes all the information will be developed. Finally, some numerical results will be reported in order to examine the performance of the heuristic as compared to an (s-l,s) policy. 4.2 A Heuristic We need to take a close look at the nature of the unit-demand inventory problem with lost sales. Our focus will be especially on its behaviour under a one-for-one order policy in order to identify what information this policy misses and understand its significance. The best way is to look at a particular example depicted in Figure 4.1. Suppose we operate under an (s-l,s) policy. Let the amount of stock on hand be n and that in the pipeline be ra, just after satisfying a demand. Thus, we have n + m = s — 1, so that placement of an order is now due. Notice that all we consider as information is the total amount of stock on hand plus on order. If this amount is below s, we place an order regardless of the possibility that we may have all of s — 1 on hand or all on order. Clearly, however, these two cases are very different. Ignoring this information is quite alright in the case of backlogging, because the order we place now will be consumed by the sth demand to come from now no matter what portion of s — 1 is on hand and what portion is on order. Therefore, the actual cost trade-off between the backlogging cost of Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 111 n = 4. m = 0 3 T r 0 1 T 4 T h 9 10 time (days) (a) Expected waiting time on shelf = m = 4, n = 0 T r I I 0 1 10 (b) Expected waiting time on shelf = • • time (days) Figure 4.1: An illustration of the effect of pipeline inventory arrival schedule. Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 112 the sth demand and the unit to be ordered will not be affected by how much of s — 1 is on hand. In the case of lost sales, however, we have quite a different situation. For instance, let us consider two extreme cases as shown in Figure 4.1. The first one is a case in which all of s — 1 is on hand as seen in Figure 4.1(a). Then, we know for certain that first 5 — 1 demands will be satisfied and the unit we are about to order will be consumed by the 5 t h demand to arrive. The second case, in Figure 4.1(b), is one in which all of s — 1 is in the pipeline and we have no stock left on hand. In this case, the unit we are about to order will be consumed by 5 t h demand to come only if there are no lost sales until this unit arrives in stock. However, there is a good chance of lost sales in this situation, especially when all the pipeline stock are scheduled to arrive quite late. This could have been triggered by a large number of demands arriving shortly before the present time. Notice that we will most probably have a number of items on hand L later, when the unit we order now arrives. In this case, the expected time this unit will have to wait in stock will be much higher than in the first case. It is clear that delaying the placement of the order may save some inventory costs without much risk of lost sales. Therefore, the use of the additional information as to when the pipeline inventories are scheduled to arrive could improve our decision. Since an (s-l,s) policy makes no use of this information, one may be losing some potential savings in inventory costs by employing (s-l,s) policies. Now, we will develop a formal approach to the above problem and come up with a policy which utilizes this additional information. A crucial step is to redefine the state of the system so as to include the arrival times (remaining lead times) of all units in the pipeline. Furthermore, we will have to calculate the probability distribution of stock on hand at some future point in time. Then, we will be able to propose and calculate a myopic cost trade-off. This will be the basic idea of our heuristic. At any point in time, Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 113 we define our state vector by where n is the number of units on hand, m is the number of units in the pipeline, and Lj is the arrival time of j th order in the pipeline. Note that Lj < L for all j = 1, 2 , m . We do not use any time subscript, as our heuristic will not depend on it. We will use the following additional notation. • ALj = Lj — Lj-\\ time between the arrivals of j th and j — 1st units in the pipeline (j = 1, 2 , m ) , with L0 — 0. • Ij\ number of units on hand just after the arrival of j t h unit in the pipeline (j = 1 , 2 , m ) , with I0 = n. • Im+i- number of units on hand at time L. • pk = P{Ij = k}: probability distribution of lj. • pk(i) = P{Ij — k | = i}: conditional probability distribution of lj. • A: demand rate. • N(t): number of demands that arrive during a time interval of length t. We have already mentioned the idea of not placing an order immediately after satis-fying a demand without considering the arrival schedule of pipeline inventory. We need to decide exactly when an order has to be placed. We know that this decision will be significantly influenced by how much stock we expect to have L units of time later. If it is too low, then we will want to order immediately. Otherwise, we may want to de-lay ordering. In order to make this decision with more precision, one has to know the (4.1) Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 114 probability distribution of stock on hand L later. Unfortunately, there is no easy way of calculating this distribution. The following recursion can be used. Note that if IQ = n now, and the oldest order arrives L\ later, the probability distri-bution of I\ will be P{N{ALx)>n\ if/c = l , p\ = I P{N(AL1) = n-k + l} if k = 2,3,...,n + 1, 0 otherwise. Then, the probability distribution of I2 can be calculated by conditioning on I\. Given that {Ii — z}, we have rf(0 = < P{N{AL2) > i} iffc = l , P{N(AL2) = i - k + l} if k = 2,3, + 1, 0 otherwise. Further, the unconditional distribution of I2 will be Y.tlv}P{N(AL2)>i) if k = 1, P l = < E3f-i p}P{N(*L2) = i - k + 1} if k = 2, 3, n 0 otherwise. In general for any / j , j = 2,3, . . . ,m, the probability distribution can be found to be n = S Z££:lpi-1P{N{ALj) = i - k + l} if A = 2 ,3 , . . , n + j , (4.2) 0 otherwise. We will also need the probability distribution of i m + i , stock on hand L later. This is slightly different from p3k in 4.2, because we do not expect to receive any stock at time L as no order has been placed yet. Thus, we have Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 115 YZ+?p?P{N{L--Ln)>i} if k = 0 Pk m+1 _ k} if k = 1, 2 , n + m 0 otherwise Next, we will propose a myopic cost trade-off for a heuristic. We would like to assign or attribute inventory and lost sales costs to individual inventory units that enter and leave the facility. The inventory cost attributable to a stock can naturally be its own inventory cost. That is, since we assume a linear inventory cost rate, each stock will have its waiting time on the shelf multiplied by h as its inventory cost. As for the lost sales cost, for each unit in inventory, we will assign the lost sales costs incurred between the time it arrives and the time the next order arrives. Based on the above assignment of costs and the state vector given in 4.1, one may want to formulate the problem as a continuous time Markov decision process. However, attempting to solve it does not seem to have much chance to be fruitful. This is due to the complexity of its state space and its transition. A possible approach is to reduce the state space and try to solve the resulting problem. Using the (s-l,s) policy as a heuristic aggregates the state vector to a scalar n + m. Clearly, information is lost by this reduction. The unknown issue here is the extent that this aggregation reduces the quality of the solution. This will become part of the analysis below. An alternative heuristic is to use some myopic optimization. Rather than minimizing the total costs until the end of the planning horizon, one may want to minimize the total costs for the next few units, only. Our myopic heuristic minimizes the total cost associated with the most recent order in the pipeline. Note that when the state is (ra, L\, L 2 l L m ) now, the ordering decision for the next unit will not affect the costs assigned to n units on hand and units 1, 2 , m — 1 in the pipeline. Only the cost of the youngest unit in the pipeline (mth unit) will be affected by the ordering decision. Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 116 time myopic planning horizon Figure 4.2: An illustration of the myopic heuristic. Now, suppose we decided to place the next order t units of time later. We will calculate the expected costs associated with the youngest order in the pipeline for ordering t later. As shown in Figure 4.2, these are HC (the expected holding cost of this unit), L C (the expected lost sales cost during the time interval (Lm,L)) and Ci(t) (the expected lost sales cost during the time interval (L,L + t)). The reason we calculate the expected lost sales costs in two intervals is that in the first interval it is a constant with respect to t, and in the second it is a function of t. This will be more useful when we calculate a myopically optimal value for t. Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 117 The expected holding cost of the youngest unit can be calculated based on the probability distribution of inventory on hand just after its arrival, 7m , by condition-ing as follows: Given that the youngest order becomes the kth on hand when it arrives (i.e. Im = k), the expected time it will wait until it is sold will be equal to k interdemand times, k/X. Then, the unconditional expected time it will spend on the shelf is n+m , k=l Therefore, its expected holding cost will be n+m . k=l = \E(Im). (4.3) Similarly, the expected lost sales in ( L m , L) will be n-\-m oo LC = 7rYPk £ P{N(L - Lm) = i}(i - k). k=l i=k+l Using the equality oo £ P{N(L - Lm) = i}i = \(L - Lm)P{N(L - Lm) > k}, i=k+l we can rewrite L C in a form easier to calculate as follows: n+m LC = Tr^p^[X(L-Lm)P{N(L-Lm)>k}-kP{N(L-Lm)>k + l}].{AA) k=i Similar to 4.4, the expected lost sales in (L, L + t) will be given by n+m oo cm = ^ £ p ™ + 1 E p{N(t) = i}(i-k) k=0 i=k+l n+m = T r Y P k + 1 [ X t P { N ( t ) > k } - k P { N ( t ) ^ k + 1}}- (4-5) Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 118 Note that in calculating the above probability distributions and expectations we used the memoryless property of exponential interdemand times and the independence of Poisson demand arrivals in disjoint time intervals. Had the demand process been other than Poisson, these calculations would have been very difficult. Now, we are able to identify a trade-off associated with the youngest order in the pipeline. We define the expected cost per time associated with it by A C ( t ) = HC + IC + C,H) ( 4 6 ) L — Lm + t Note that when we delay an order longer {i.e. as t increases), the expected lost sales Ci(t) will increase (see its derivative in 4.9). Therefore the total cost increases. However, the time interval in which this total cost is incurred expands by t at a rate of 1. Thus, the average cost per time may be decreasing for small values of 2, especially when Im is high in which case the risk of incurring any lost sales will be small. Let us denote the first and second derivatives of Ci(t) by C[{i) and C"(t), respectively. Now, differentiating the average cost, AC(t), we have C',(t)(L -Lm+t)- (LC + HC + Ci{t)) AC\t) = {L-Lm + tf C[(t) - AC{t) L — Lm + t The second derivative is given by [C['(t) - AC'(t)](L - L m + t)- \C\{t) - AC(t)} AC"(t) (L-Lm + ty [C'/jt) - AC'jt)} - [C[{t) - AC(t)]/(L -Lm+t) L Lm -\-1 C'l'(t)-2AC'(t) L — Lm "f" t Then, the first order condition is (4.7) C[{t) = AC(t). (4.8) Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales Note that - " A ^ ^ + (i-iy. x = \[P{N(t) = i-l}-P{N(t) = i}], and 2=0 k 1=0 = -XP{N(t) = k}. Then, from (4.5), the marginal cost of lost sales will be / CO C/(0= *TE?P? +1 E KP{N(t)=i-l}-P{N(t) = z})(z-k) \i=k+l / oo > = ^EtoPk+1 (Yl(P{N(t) = i-l}-P{N(t) = i})(i-k) \i=k+l oo '^TZOPT 1 E =1 - ^ - E pw*) = ^ \! = fc + l J = fc + 1 oo -k E ^ W ) = * - 1 } + * E P w * ) = ^ t=it+i. t=fe+i oo oo = *A zto PT+1 E P W) = ^ + E P w ) = Z> - E P w ) \ i=k i=k i= oo oo ^ -kYp{N(t) = i} + k E mco = o oo = ^T,toPk+1 ^P{N(t) = i} i=k = ^EtoPT+1 P{N(t)>k}. Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 120 The second derivative is n+m dt i=k n+m 0 0 cm = 7 r A £ ^ + 1 E ^ ( p w ) = *}) k-0 i=k = ^X2YpT+1P{N(t) = k-l} (4.10) > 0 for all t > 0. Below, we state a proposition which characterizes the optimal time to order. Proposition 4.1 The optimal order time which minimizes (4-6) is given by I 0 otherwise where t* solves (4-8), provided that a solution exists. Otherwise, t* = 0 0 . Proof: For any t which satisfies (4.8), from (4.7) we have (4.11) because C"(t) > 0 for all i > 0 from (4.10) and L > Lm. Therefore, t* must be a local minima if it exists and AC(t) has no local maxima. Furthermore, since AC(t) is continuous in t, if there exists more than one minima there must exist a local maxima, which is a contradiction. Therefore, if t* exists, it is a unique minimum for AC(t). Note that we have HC + LC C,(0) = 0, Cl(0) = ic\pZ+\ AC(0) L — Lr, Now, suppose C/(0) > AC(0). Then AC(t) is increasing at t = 0. Furthermore, since we know that AC it) does not have a local maxima, it must be always increasing in t. Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 121 Therefore, topt = 0. Similarly, if C/(0) < AC(0), then AC(t) is decreasing at t = 0. Then, if the first order condition in (4.8) does not have a solution, AC{t) must be always decreasing in t. Therefore, topt = oo. Finally, if C/(0) = AC(0) then t* = 0 must be a unique solution to (4.8) and thus topt = t*. • Proposition 4.1 indicates that we try to order when the marginal cost of lost sales equals the average cost. If they are never equal, then we either order immediately, or never order until the next event. We use the term "optimal" above with caution in a restricted sense. That is, if we minimize the myopic average cost defined in 4.6, then 4.11 gives the "optimal" time we should place the order. Two things are clearly ignored here. These are the accounting of future costs and the fact that the state vector will change when we start delaying the order. Note that even if we are satisfied with the myopic nature of the cost minimization, changing state vector by time calls for continuous updating of the optimal time to order. The optimal time we calculate here is static and is not updated. In order to improve this we decided to update the calculations at the following discrete points in time: 1. Demand arrival. 2. Order arrival. 3. t* amount of time has passed since the last update. In each of these events, the heuristic updates the state vector and recalculates the myopic optimal time to order according to the new state. Although this is not exactly continuous updating, it should capture a significant portion of the effect of any change in the state vector. Chapter 4.' A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 122 4.3 Simulation Results We are interested in the performance of the heuristic we described in the previous section, and we will measure it by comparing its cost to the cost of an optimal (s-l,s) policy. Unfortunately, theoretical calculation of the long run average cost of the heuristic proved to be a very difficult task. This is due to the complexity of the state vector and the fact that the decision of when to order is frequently updated. The steady state calculation of the probability distribution of the state vector looks very difficult to calculate. As the only available alternative, we coded a simulation program in C++ in order to calculate long run average cost of the heuristic. Since, the order decision is updated very frequently, and each update needs to solve the first order conditions in (4.8), the simulation had to be run in a fast computer, in order to achieve a small simulation error within a reasonable amount of computer time. Our experience was that in order to obtain reasonable accuracy in our test problems, we had to have at least 25,000 iterations in each run. Each iteration corresponds to a demand arrival. In our test problems, we assumed that the interdemand time mean is 1 week (A = 1/7 units per day) and the daily holding cost rate is $1. We generated 40 different problems by varying the lead time, L, and the lost sales cost per unit, ir. The values we used are • L = (14, 30, 60,90,120) in days. • 7r = (25, 50, 75,100,125,150,175,200) (in $/unit). For these problems if one uses an (s-l,s) policy, the optimal inventory level s will be between 3 and 5 for L — 14 and between 10 and 20 for L = 120. These values were thought to be reasonable for low demand items. For each problem, we had 3 simulation runs, each with 40,000 iterations. The simula-tion error for the average cost was less than 1% for all of the problems except those with Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 123 longest lead time (L=120) which had error within 2%. The time it takes to complete a large problem (ones with long lead time and high lost sales cost per unit) was quite long for a 486-66MHz. C P U . We used a SUN-SPARC 20 which needed about a day to complete all 40 problems. Table 4.1 shows the long run average costs for both the heuristic and the (s-l,s) policies for half of the problems for which lost sales costs per unit are lower (IT — 25, 50, 75, 100). Table 4.2 shows the same results for higher lost sales costs per unit (ir = 125, 150, 175, 200). The costs for the (s-l,s) policies are calculated by using the results of Feeney and Sherbrooke [36] and they are exact. The costs for the heuristic are calculated through simulation as described above. The last column has the simulation errors which are basically the standard deviations of costs in a sample of size 3 (sample size = number of simulation runs). The errors tend to increase by lead time i , and lost sales costs per unit p. However, in most of the cases, these errors are small enough to draw conclusions. Our experience showed us that a higher number of iterations has a much more significant effect in reducing the simulation error compared to a bigger sample size. Therefore, in order to save computation time, we kept the sample size small and the number of iterations large. Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 124 Comparison of Costs Optimal Cost(s-l,s) Cost (heuristic) Cost Ratio Simulation L 7T s (A) (B) (A /B) Error 14 25 3 2.173 2.141 1.015 0.008 50 4 2.871 2.919 0.984 0.022 75 4 3.211 3.422 0.938 0.020 100 4 3.551 3.750 0.947 0.055 30 25 4 2.366 2.253 1.051 0.008 50 5 3.279 3.156 1.039 0.009 75 6 3.786 3.764 1.006 0.032 100 7 4.162 4.206 0.990 0.035 60 25 6 2.524 2.297 1.099 0.010 50 9 3.611 3.318 1.088 0.037 75 10 4.281 4.050 1.057 0.039 100 11 4.791 4.594 1.043 0.006 90 25 8 2.594 2.294 1.131 0.017 50 11 3.780 3.381 1.118 0.017 75 13 4.541 4.096 1.109 0.044 100 14 5.114 4.736 1.080 0.029 120 25 10 2.633 2.298 1.146 0.015 ' 50 14 3.878 3.402 1.140 0.040 75 16 4.712 4.229 1.114 0.041 100 18 5.344 4.838 1.105 0.067 Table 4.1: Results of simulation (LOW lost sales cost per unit). Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 125 Comparison of Cost s Optimal Cost(s-l s) Cost(heuristic) Cost Ratio Simulation L 7T s (A) (B) ( A / B ) Error 14 125 5 3.729 4.062 0.918 0.042 150 5 3.860 4.240 0.910 0.026 175 5 3.991 4.464 0.894 0.056 200 5 4.122 4.609 ' . 0.894 0.029 30 125 7 4.441 4.571 0.972 0.006 150 7 4.719 4.895 0.964 0.027 175 8 : 4.889 5.113 0.956 0.022 200 8 5.032 5.413 0.930 0.027 60 125 11 5.160 5.061 1.020 0.037 150 12 ' 5.491 - 5.467 1.004 0.026 175 12 5.737 5.730 1.001 0.069 200 12 5.982 6.026 0.993 0.054 90 125 15 5.565 5.233 1.063 0.018 150 16 5.960 5.755 1.036 0.105 175 16 6.254 6.072 1.030 0.060 200 16 6.547 6.345 1.032 0.047 120 125 19 5.851 5.357 1.092 0.092 150 19 6.259 5.837 1.072 0.116 175 20 6.612 6.218 1.063 0.100 200 20 6.930 6.555 1.057 0.039 Table 4.2: Results of simulation (HIGH lost sales cost per unit). A graphical comparison of the heuristic and the one-for-one order policy is shown in Figure 4.3. A clearly visible pattern indicates that the heuristic is superior to one-for-one policy for long lead times and low lost sales costs per unit. This is most probably because in systems with long lead times, the probability distribution of the stock on hand ( / m + i ) a lead time later tends to be less variable (since m, the number of orders in the pipeline, is likely to be larger). Therefore, delaying order placement will have a smaller risk of causing lost sales. Another reason is perhaps the variation between the amount in the pipeline and the actual on hand inventory. For long lead times, since an (s-l,s) policy Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 126 will tend to hold more inventory, when the inventory position comes down to s — 1, the benefit of knowing how much of it is in the pipeline can be potentially more. For instance, a system with a lead time of 120 days may be maintaining an inventory position of 20 units. When the inventory position is 19 just after a sale, the pipeline inventory can be any value between 0 and 19. There seems to be more information hidden in this case than in the case of a system which maintains only 2 units. In the latter, when the inventory position is 1, we know it is either on hand or on order. This indicates that knowing the arrival schedule of the pipeline inventory is of less value. The lost sales cost per unit seems to have the opposite effect compared to the lead time effect. The heuristic performs poorer for high it values. The reason for this can be explained: A close examination of the cost trade-off we used in the heuristic will show that the heuristic attempts to save some inventory costs by risking some lost sales. Thus, when the lost sales cost per unit is higher, the risk becomes higher. This makes the heuristic incur more lost sales costs, since it will have to take a considerable risk of lost sales, in order to save from inventory costs. The detailed results of simulations showed that the average holding cost given by the heuristic in problems with high 7r values constituted a smaller portion of the total cost compared to the problems with low 7T values. Thus, we see that the heuristic becomes more agressive in its attempt to save holding costs. As a result of this, it has a poor performance for high lost sales costs per unit. 4.4 Conclusions and Remarks This research has focused on the continuous review, Poisson-demand inventory model with lost sales. One-for-one policies appear to make no use of the information given by the arrival schedule of the orders in the pipeline. Therefore, an alternative policy Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales .127 Figure 4.3: A comparison of the heuristic and the one-for-one policy. Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 128 which utilizes this information could do better. Here we developed a heuristic policy as an alternative. Although it is myopic in nature, it uses more information than a one-for-one policy. We tested the performance of this heuristic policy against the best one-for-one policy in a range of problems, by comparing their long run average costs through simulation. Our results showed that the heuristic is superior to one-for-one policies when the order lead times are long and/or the lost sales costs per unit are low. Otherwise, one-for-one policies are better. A n important application of this heuristic as an alternative to the popular one-for-one policies would be in a competitive industry where profit margins are low (therefore lost sale cost rate is low) and the suppliers work with high backlogs causing long lead times. Long lead times may be common also for some expensive special products which are manufactured on make-to-order basis by the manufacturers. Another application area can be in retail industries which sell expensive items with low demand, whose main supplier is not local and delivers with a long lead time. In this case, when stockouts occur, in order to avoid causing customer dissatisfaction, many retailers may want to use an alternative local supplier which can deliver almost instantly at a higher price. Retailers facing this kind of a supply market may want to make their regular replenishments from the price-competitive supplier with a long lead time and use the local supplier in case of shortages only. Then, shortages will effectively cost only as much as the price difference between the two suppliers and this would be typically low. A caution must be stated clearly that the heuristic developed here is not appropriate for problems where there is subtantial cost for lost sales. If the loss of good will is a major concern, for example, lost sales costs will have to reflect this and will typically be very high. Although we have not extended the scope of our simulation to such problems, from the trend our simulation results show it can be predicted that the heuristic will perform poorly for higher values of lost sale costs per unit. The scope we have chosen addresses Chapter 4. A Heuristic for a Poisson-Demand Inventory Problem with Lost Sales 129 more the problems where a lost sales cost means a lost profit or a small premium paid to use an alternative supplier in order to avoid customer dissatisfaction as explained above. The situations above are possible to find in the industry and the heuristic developed here may be a better alternative than a one-for-one policy in such cases. Of course, we must emphasize again that the complexity involved in calculating the order times in the heuristic is a drawback as compared to the simplicity of one-for-one policies. However, wide spread use of computerized inventory control even in medium firms makes the application feasible today. Finally note that there is a similarity between the concept we have developed here and the concept of delay mentioned in Chapter 3. In both problems, the order placement is delayed to a better time in the future, although both problems have significantly different dynamics. This suggests that the concept of delay has a potential to be applied to a more general set of problems with continuous review. Appendix A Appendix for Chapter 1 A.l Proofs for Chapter 1 Here, we present the proofs for the lemmas. Proof 1.3: (This lemma is given without any proof in Weerahandi [115] and m is unnecessarily restricted to be an integer) foo rb^/y ymct>{z)x{y)dz •oo dy where x{v) 1S the pdf of Y. Note that t = zxjvjy is a Student's t random variable with v degrees of freedom. Then, /•oo rb-^fv EY[Y m$(bVY)] = / / ym^{t^/yJ^)yM^x{y)dtdy. Interchanging the integrals, and rearranging we have /i fb^/U poo - J Jq ym+1/2cj>(ty/y~^)x(y)dydt. N ow, <f>{ty/y~JZ)X(y)dtdy = ^ e " ^ r T ^ 2 ) ( 1 / 2 r / 2 2 / f " l e " / 2 = 1 ( 21/ V / 2 /*'+ i / V / a ( 1 / 2 ) ^ feQ, yfa \t2 + uj \ 2v ) T(p/2) V 1 / „ \ "/2 2^\t2 + v & 7 2 ( y ) , 130 Appendix A. Appendix for Chapter 1 131 where <f>l//2(y) is the pdf of a Gamma random variable with shape parameter u/2 and scale parameter 2vj{t2 + v). Then, u/2 ^ r~r / \ m + 1 / 2 r(^f±i) / 1/ y / 2 V ^ V ^ T ^ J i>/2) \¥+~v) d L Letting u = tyju+2m and noting that v + 2m = r, we get 1 { n I>/2) T(r/2)Vr^W + rJ r ( r/2), r(i//2) Proof 1.4: We first find 2mTT{byft). ExtS[Ex[y*(X,us)-X}+}. . The inner expectation is actually conditional on (X, s), with X being independent of both X and s. Replacing y*(X,us) by X + kuis, we have + E^a[Ex[X. + kus -X]+ \X,s] = E x , s A x + k " s - X ) Let u — (n — l)s2/a2 and v — x — x. Note that u and v are independent, u having a Chi-square distribution with n — 1 degrees of freedom and v having a Normal distribution with mean 0 and variance (1 + l/n)a2. Then, the expectation is Eu[Ev[v + -==^/u\+ | u . V n — 1 The partial expectation inside is messy but straight forward to calculate and equals the following. ^ r kuja /—,, \Jn + la »2*2'" uka r-^ ( I n , r-, \ V n — 1 V27rn \Jn — 1 \ y n^ — 1 / Appendix A. Appendix for Chapter 1 132 Now, the outer expectation with respect to u can be calculated by noting that Eu[eau] = (1 - 2 a ) - ^ , a < 1/2, Using the above equations and Lemma 4 for m = 1/2, the outer expectation is nk2u2 n + 1 2irn n - 1 ,2, ,2 \ - — 1 + ra2 - 1 ra (T. Given the above, the expectation of F(y*(X,us); p, o) can easily be found. Proof 1.5: (This proof is taken from Ritchken and Sankar [80]) Equation 1.13 is simply , lus + X — fi, -) \X,8] P r o h [ Z < lus + X-fy o = Prob{aZ + » - X <lu} where Z is a standard Normal variable. It can easily be verified that t Student's t random variable with ra — 1 degrees of freedom. Thus, lu , _ / t r Z + ^ x — X sy/l+l/n is a a = Prob{t < --} = r n _ ! ra V 1 + i A Noting that / is <&-1(a) the result follows. Proof 1.6: Here we generalize the proof in [115] for any two scale parameters 71 and 72-Ex[$r2(bX\l2)} = EX[$r2( — \l)} 72 = Ex[Prob{Z < —} \X] 72 Appendix A. Appendix for Chapter 1 133 where Z ~ Gamma(r2, 1). Let M = X/j±. Then, M ~ Gamma(ri, 1). Thus, Ex[$r2{bX\72)} = EM[Prob{Z<b-^M}\M] 72 = P r o b { z < lM 72 J The last equality follows from the relationship between the Gamma and the Beta distri-butions, which is a known result from distribution theory. Proof 1.7: Note the following expectation: EA,[Ex[kui - X]+] = {kui - x) 4>r{x\~j) (t>nr(i\— )dxd^ = kid 1 <l>r(x\l) 0nr(l\—) dx d*f ~ j j X (j>r{x\l) <t>nr{l\ —) dx dj. Using the fact u<j>i{u\j) = ij(f>i+i(u\j) in both terms (for 7 in the first term and for x in the second) and simplifying, this expectation is equal to = k u j -A Ix<k^ 7 Mxh) <t>nr+i{l\%) dx d 7 - / . r 7 cVufcb) M 7 l ; £ ) d x d ^ kuriE^ [$r(A;w7i|7)] - n E4$r+1(kujj\-{)} where 71 ~ Gamma{nr + 1, ^ ) and 7 ~ Gamma(nr, ^ ) . Then, from Lemma 1.6 we have , / kto \ ( kto E^Exiku-y - Xy\ = kLu<yBTtnr+i • - rjBr+ltnr kto + nr J ' \kto + nr Given the above, the expectation of F(y*(uj); 7) can easily be found. Appendix B Appendix for Chapter 2 B . l Solution of the Relaxed Problem Here is the solution of Problem (2.2): Let us drop the subscript t in all variables for ease of reading. Define a Langrangian function L{y, x, z, A) = q(v, x, z) + X(Z - Y!k=izk) which we want to minimize subject to C2 and C3. The first order conditions are —2pj(xj — Zj) + h — A = 0, Z ~ Y!k=lzk = o-At optimality, we have 9 = Pj(Xj"- z*) = Pi(Xi - z*) V(t, j ) (B. l ) Q Zj* — Xi (B.2) Pj YlLi** = z (B-3) where 6 is a common factor. Then, from (B.2) and (B.3) we have Thus, o = & - zvxLii; 134 Appendix B. Appendix for Chapter 2 135 and Note that Zj* may be negative. Thus, this allocation policy is not feasible and is used to calculate a lower bound in cost. B.2 Calculation of the Optimal Order Policy for the Relaxed Cost Problem We use Zheng and Federgruen's approach [122] to calculate the average cost (although they formulate the problem for discrete demand, it can also be used for continuous de-mand for a critical number policy). Let h and p be the stationary holding and backlogging costs per unit per period, respectively and let c be the order cost per unit. Then, the long run average cost of a critical number, 5", policy is given by G(S) = pE[(U - S)+}2 + hE(S - U)+ + cp/{L + 1), where U is the total demand in L + 1 periods with mean \i and variance er2. Let </>(.) and $(.) be the pdf and the cdf of [/, respectively. The first term in the above equation is E[(U- S)+}2 = E[(S - U)+ - (S - U))2 = E(U - S)2 + 2E[(U - S)(S - U)+] + E[{S - U)+}2 = E(U - S)2 - E[{S - U)+f = a2 + u2-2pS + S2 - ( (S - x)2<f>{x)dx Jo The previous to the last equality follows from E[(U - S)(S - U)+] = -E[(S - U)+]2. Then, the cost is G(S) = p[a2 + u2 - 2pS + S2 - / (S - x)2cf>(x)dx} + h f (S- x)<f>{x)dx + cp/(L + 1). Jo Jo Appendix B. Appendix for Chapter 2 136 The first and the second derivatives are: G'(S) = 2p[S - u - I <$>{x)dx) + h$(S), Jo G"{S) = 2p[l - $ ( 5 ) ] + h<f>{S). since the second derivative is nonnegative for all S, G(S) is convex, and thus the opti-mality occurs at G'(S) = 0. Noting that E{U-S) +=I <$>{x)dx - S + p, Jo the optimality condition is E(U - S)+= ±*(S). Bibliography [1] Armstrong M . J . , D.R. Atkins. "Joint Optimization of Maintenance and Inventory Policies for a Simple System.", Working Paper # 94-MSC-012, (1994), Faculty of Commerce, University of British Columbia. [2] Archibald, B .C . "Continuous Review (s,S) Policies with Lost Sales.", Management Science, 27, 10, (1981), 1171-1177. [3] Arrow, K . J . , S. Karlin and Ff. Scarf. Studies in the Mathematical Theory of Inven-tory and Production., Stanford University Press, Stanford, California, (1958). [4] Axsater, Sven. "Simple Solution Procedures for a Class of Two-Echelon Inventory Problems.", Operations Research, 38, 1, (1990), 64-69. [5] Azoury, Katy S. "Bayes Solution to Dynamic Inventory Models Under Unknown Demand Distribution.", Management Science, 31, 9, (1985), 1150-1160. [6] Azoury, K . and B . Miller. "A Comparison of The Optimal Ordering Levels of Bayesian and Non-Bayesian Inventory Models.", Management Science, 30, (1984), 993-1003. [7] Badinelli, R.D. , L . B . Schwartz. "Backorders Optimization in a One-Warehouse N -Identical Retailer Distribution System.", Naval Research Logistics, 35, 5, (1988), 427-440. [8] Bagchi, Uttarayan, J.C. Hayya and J .K. Ord. "Modelling Demand During Lead Time.", Decision Sciences, (1984), 157-175. [9] Barlow, R .E . and F. Proschan. Mathematical Theory of Reliability. John Wiley & Sons, New York, (1965). [10] Biggs R.J . , W . M . Campion. "The Effect and Cost of Forecast Error Bias for Multiple-Stage Production-Inventory Systems.", Decision Sciences, 13, (1982), 570-584. [11] Bookbinder J .H. , A . E . Lordahl. "Estimation of Inventory Re-ordel Levels Using The Bootstrap Statistical Procedure."", HE Transactions, 21, 4, (1988). [12] Brown, R .G . Statistical Forecasting for Inventory Control. McGraw Hi l l , New York, (1959). 137 Bibliography 138 [13] Burns, L .D. , R.W. Hall and D.E. Blumenfeld, C.F. Daganzo. "Distribution Strate-gies that Minimize Transportation and Inventory Costs.", Operations Research, 33, 3, (1985), 469-490. [14] Clark, A . J . "An Informal Survey of Multi-Echelon Inventory Theory.", Naval Re-search Logistics Quarterly, 19, 4, (1974), 621-650. [15] Cohen M . A . , P.R. Kleindorfer and H.L. Lee. "Optimal Stocking Policies for Low Usage Items in Multi-Echelon Inventory Systems.", Naval Research Logistics Quar-terly, 33, (1986), 17-38. [16] Cohen M . A . and P.R. Kleindorfer, H.L. Lee., "Service Constrained (s,S) Inventory Systems With Priority Demand Classes and Lost Sales.", Management Science, 34, 4, (1988),482-499. [17] Cohen, C D . "Bayesian Adjustment of Sales Forecasts in Multi-Item Inventory Control Systems.", Journal of Industrial Engineering, 17, (1966), 474-479. [18] Croston, J.D. "Stock Control for Slow Moving Items.", Operations Research Quar-terly, 25, (1974), 123-130. [19] Das, C. "Sensitivity of the (Q,R) Inventory Model to Penalty Cost Parameter.", Naval Research Logistics Quarterly, 22, 1, (1975), 175-179. [20] Das, C. "The (s-1, s) Inventory Model Under Time Limit on Backorders.", Opera-tions Research, 25, (1977), 835-850. [21] Derman, C , M . Klein. "A Note on the Optimal Depletion of Inventory.", Manage-ment Science, 5, 2, (1959), 210-213. [22] Derman, C , M . Klein. "Inventory Depletion Management.", Management Science, 4, 4, (1958), 450-456. [23] Deuermeyer B .L . and L.B.Schwarz. "A Model for the Analysis of System Service Level in Warehouse/Retailer Distribution Systems: The Identical Retailer Case.", Chp.8, in Multi-Level Production/Inventory Control Systems: Theory and Practice, North-Holland, Amsterdam, (1981)/ [24] Dobson, Gregory. "Sensitivity of the EOQ Model to Parameter Estimates.", JORSA, 4, (1988), 570-574. [25] Dvoretzky, A . , J. Kiefer and J. Wolfowitz. "The Inventory Problem: I. Case of Known Distribution of Demand.", Econometrica, 20, (1952), 187-222. Bibliography 139 [26] Eppen, G. and L. Schrage. "Centralized Ordering Policies in Multi-Warehouse Sys-tem with Lead Times and Random Demand.", TIMS Studies in the Management Sciences, 16, (1981), 51-67. [27] Ehrhardt, R. "Analytical Approximations for (s,S) Inventory Policy Operating Characteristics.", Naval Research Logistics Quarterly 28, 2, (1981), 255-266. [28] Ehrhardt, R. "The Power Approximation for Computing (S,s) Inventory Policies", Management Science, 25, (1979), 777-786. [29] Eppen, Gary D. and R.Kipp Martin. "Determining Safety Stock in The Presence of Stochastic Lead Time and Demand.", Management Science, 34, 7, (1988), 1380-1390. [30] Estey, Arthur S. and R.L. Kaufman. "Multi-Item Inventory System Policies Using Statistical Estimates: Negative Binomial Demands (Variance/Mean=9).", Techni-cal Report #3, Sept. (1975), School of Organization and Management, Yale Uni-versity. [31] Falkner, Charles H. "Jointly Optimal Inventory and Maintenance Policies for Stochastically Failing Equipment., Operations Research, 16, (1968) 587-601. [32] Federgruen, A. , "Centralized Planning Models for Multi-Echelon Inventory Systems under Uncertainty.", chp.3 in Logistics of Production and Inventory., Grave S.C. et al, (Ed.), North-Holland, (1993). [33] Federgruen, A . , P. Zipkin. "Allocation Policies and Cost Approximations for Mul-tilocation Inventory Systems.", Naval Research Logistics Quarterly, 31, (1984), 97-129. [34] Federgruen, A . and P. Zipkin. "An Efficient Algorithm for Computing Optimal (s,S) Policies.", Operations Research32, 6, (1984), 1268-1285. [35] Federgruen, A. , Yu-Sheng Zheng. "A Simple and Efficient Algorithm for Comput-ing Optimal (r,Q) Policies in Continuous-Review Stochastic Inventory Systems.", Operations Research, 40, (1992), 808-812. [36] Feeney, G.J. and C.C. Sherbrooke. "The (s-l,s) Policy Under Compound Poisson Demand.", Management Science, 12, 5, (1966), 391-411. [37] Feeney, G.J . and C.C. Sherbrooke. "Generalization of a Queueing Theorem of Palm to Finite Populations.", Communications to the Editor, Management Science, 12, 11, (1966), 907-908. Bibliography 140 [38] Freeland, J.R. and E.L. Porteus. "Evaluating the Effectiveness of a New Method for Computing Approximately Optimal (s,S) Inventory Policies.", Operations Research, 28, 2, (1980), 353-366. [39] Graves, S.C. "The Application of Queuing Theory to Continuous Perishable Inven-tory Systems.", Management Science, 28, (1982), 400-406. [40] Graves, S.C. and L . B . Schwartz. "Single Cycle Continuous Review Policies for Arborescent Production / Inventory Systems.", Management Science, 23, 5, (1977), 529-540. [41] Graves, S . C , H .G. Rinnooy Kan and P.H. Zipkin (Ed.) Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, Vol. 4, North-Holland, Amsterdam, (1993). [42] Gross, D. and C M . Harris. "On One For One Ordering Inventory Policies with State Dependent Lead Times.", Operations Research, 19, (1971), 735-760. [43] Grundy P . M . , Healy M.J .R. and Rees, D.H. "Economic Choice of the Amount of Experimentation.", J.R. Statistics Soc, B. 18, 32-55., (1956). [44] Ha, Albert Y . "Inventory Rationing in a Make-to-Stock Production System with Several Demand Classes and Lost Sales.", Working Paper, Apri l (1994). Yale School of Management, New Haven, Connecticut. [45] Hadley., G. and Whitin T . M . Analysis of Inventory Systems, Prentice-Hall, Eagle-wood Cliffs, N . J . (1963). [46] Hanssmann, Fred. Operations Research in Production and Inventory Control, J .W. k Sons, Inc. New York (196?). [47] Hayes, R . H . "Statistical Estimation Problems in Inventory Control.", Management Science, 15, 11, (1969), 686-701. [48] Hayes, R .H . "Statistical Estimation Models for Optimal Inventory Control.", Ph.D. thesis, February (1966), Operations Research Program, Stanford University. [49] Higa, Isamu, Arlin M . Feyerherm and A . L . Machado. "Waiting Time in an (s-l,s) Inventory System.", Operations Research, 23, 4, (1975), 674-680. [50] Iglehart, D.L. "Dynamic Programming and Stationary Analysis of Inventory Problems.", in Multistage Inventory Models and Techniques, (ed.) Scarf H.E. , D.M.Gilford, M.W.Shelly., Stanford University Press, California, (1963). Bibliography 141 [51] Iglehart, D.L. "The Dynamic Inventory Problem with Unknown Distributions of Demand.", Management Science, 10, (1964), 429-440. [52] Jacobs A.R . and H . M . , Wagner. "Reducing Inventory System Costs by Using Ro-bust Demand Estimators.", Management Science, 35, (1989), 771-787. [53] Jacobs A .R . and H . M . Wagner. "Reducing Inventory System Costs by Using Regression-Derived Estimators of Demand Variability.", Decision Sciences, 20, (1989), 559-574. [54] Johnson, G. and H. Thomson. "Optimality of Myopic Inventory Policies for certain Dependent Demand Processes.", Management Science, 21 (1975), 1303-1307. [55] Kaufman R.L . and J .G. Klincewicz. "Multi-Item Inventory System Policies Using Statistical Estimates: Sporadic Demands (Variance/Mean=9).", Technical Report #6, Apri l (1976), School of Organization and Management, Yale University. [56] Klein, M . , Rosenberg, L. "Deterioration of Inventory and Equipment.", Naval Re-search Logistics Quarterly, 7, 1, (1960), 49-62. [57] Klincewicz, J .G. , "Inventory Control Using Statistical Estimates: The Power Ap-proximation and Sporadic Demands (Variance/Mean = 9).", Technical Report #9, Nov.(1976), School of Organization and Management, Yale University. [58] Kottas, J . and H.S. Lau. "A Realistic Approach for Modelling Stochastic Lead Time Distributions.", A HE Transactions, 11, (1979), 54-60. [59] Kottas, J. and H.S. Lau. "The Use of Versatile Distribution Families in Some Stochastic Inventory Calculations.", JORS, 31, (1980), 393-403. [60] Kruse, W. Karl . "Waiting Time in an (s-l,s) Inventory System with Arbitrarily Distributed Lead Times.", Operations Research, 28, 2, (1980), 348-352. [61] Lau H.S. and Zaki. "The Sensitivity of Inventory Decisions to the Shape of Lead Time Demand Distribution.", HE Transactions, 14, 4, (1982), 265-271. [62] Lee, H.L. , and S. Nahmias. "Single-Product, Single-Location Models.", in Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, S.C. Graves, H .G. Rinnooy Kan, and P.H. Zipkin (Eds.), Vol. 4, North-Holland, Amsterdam, (1993). [63] Lordahl A . E . , J .H. Bookbinder. "Order Statistics Calculation, Costs and Service in an (s,Q) Inventory System.", Naval Research Logistics, 41, (1994), 81-97. Bibliography 142 [64] Lowe, Timothy J., L . B . Schwarz, E .J . McGavin. "The Determination of Optimal Base-stock inventory Policy When the Costs of Under and Over Supply is Uncer-tain.", Naval Research Logistics, 36, 4, (1989), 463-477. [65] MacCormick, Alastair. "Statistical Problems in Inventory Control.", Technical Re-port #2, Dec.(1974), School of Organization and Management, Yale University. [66] Mine, H . , H.Kawai. "Optimal Ordering and Replacement for a 1-Unit System.", IEEE Transactions on Reliability, 35, (1986), 82-84. [67] Morton, Thomas E. "The Near-Myopic Nature of the Lagged-Proportional-Cost Inventory Problem With Lost Sales.", Operations Research, 19, (1971), 1708-1716. [68] Morton, T .E . "Bounds on the Solution of the Lagged Optimal Inventory Equation with No Demand Backlogging and Proportional Costs.", SIAM Review, 11, (1969), 572-596. [69] Muckstadt J .A. "A Model for a Multi-Item, Multi-Echelon, Multi-Indenture Inven-tory System.", Management Science, 20, 4, (1973), 472-481. [70] Muckstadt, John A. and L . J . Thomas. "Are Multi-Echelon Inventory Methods Worth Implementing in Systems with Low-Demand-Rate Items ?", Management Science, 26, 5, (1980), 483-494. [71] Muckstadt, J .A. and R.O. Roundy. "Multi-Item, One-Warehouse, Multi-Retailer Distribution Systems.", Management Science, 33, 12, (1987), 1613-1621. [72] Mykytka, E.F. and J.S.Ramberg. "On the Sensitivity of the EOQ to Errors in the Forecast Demand.", HE Transactions, 16, 2, (1984), 144-151. [73] Naddor, E. "Sensitivity to Distributions in Inventory Systems.", Management Sci-ence, 24, (1978), 1769-1772. [74] Nahmias, S. "Queuing Models for Controlling Perishable Inventories.", in Eco-nomics and Management of Inventories: Proceedings of the First International Conference on Inventories, A . Chikan (Ed.), Elsevier Scientific Publishing Com-pany, New York, (1982), 449-457. [75] Nahmias, S. "Perishable Inventory Theory: A Review.", Operations Research, 30, (1982), 680-708. [76] Nahmias, S. and S.S. Wang. "A Heuristic Lot Size Reorder Point Model for Decay-ing Inventories.", Management Science, 25, (1979), 90-97. Bibliography 143 [77] Park, K.S. , Y.T.Park. "Ordering Policies under Minimal Repair.", IEEE Transac-tions on Reliability, 35, (1986), 82-84. [78] Puterman, Martin L. Markov Decision Processes: Discrete Stochastic Dynamic Programming., John Wiley & Sons, Inc., New York (1994). [79] Pyke, D.F. "Priority Repair and Dispatch Policies for Repairable-Item Logistics Systems.", Naval Research Logistics, 37, 1, (1990), 1-30. [80] Ritchken H.P. and Sankar R. "The Effect of Estimation Risk in Establishing Safety Stock Levels in an Inventory Model.", JORS, 35, 12, (1984), 1091-1099. [81] Rose, M . "The (s-1, s) Inventory Model with Arbitrary Backordered Demands and Constant Delivery Times.", Operations Research, 20, (1972), 1020-1032. [82] Rosenbaum, B . A . "Service Level Relationships in a Multi-Echelon Inventory Sys-tem.", Management Science, 27, 8, (1981), 926-945. [83] Sahin, Izzet. "On Unit-Demand Inventory Systems.", Working paper, School of Business Administration, University of Wisconsin-Milwaukee. [84] Scarf, Herbert. "Bayes Solutions of the Statistical Inventory Problem.", Annals of Mathematical Statistics, 30, (1959), 490-508. [85] Scarf, Herbert. "The Optimality of (s,S) Policies in The Dynamic Inventory Prob-lem.", in Mathematical Methods in The Social Sciences, (Ed.) Arrow, Karlin, Sup-pes, Stanford University Press, (1959), pp.196-202. [86] Schmidt, Charles P. and Steven Nahmias. "(s-l,s) Policies For Perishable Inven-tory.", Management Science, 31, 6, (1985), 719-728. [87] Schneider, H . "Methods for Determining the Reorder Point of an (s,S) Ordering Pol-icy when a Service Level is Specified.", Operations Research Quarterly, 29, (1978), 1181-1193. [88] Schneider, H. "Effect of Service Levels on Order-Points or Order-Levels in Inventory Models.", International Journal Production Research, 19, (1981), 615-631. [89] Schneider, Helmut and J.L.Ringuest. "Power Approximation for Computing (s,S) Policies Using Service Level.", Management Science, 36, 7, (1990), 822-834. [90] Schultz, C.R., "Forecasting and Inventory Control for Sporadic Demand Under Periodic Review.", JORS, 38, (1987), 453-458. [91] Schultz, C R . "On the Optimality of the (s-1, s) Policy.", Naval Research Logistics, 37, (1990), 715-723. Bibliography 144 [92] Schultz, C R . "Replenishment Delays for Expensive Slow-Moving Items.", Manage-ment Science, 35, 12, (1989), 1454-1462. [93] Schrady, D.A. and V . C Choe. "Models for Multi-Item Continuous Review Policies Subject to Constraints.", Naval Research Logistics Quarterly, 18, 4, (1971), 451-464. [94] Schwartz, L . B . Multi-Level Production / Inventory Control Systems: Theory and Practice, North-Holland, Amsterdam, (1981). [95] Schwartz, L .B . , B .L . Deuermeyer and R.D. Badinelli, "F i l l Rate Optimization in a One-Warehouse N-Identical Retailer Distribution System.", Management Science, 31, 4, (1985), 488-498. [96] Schwartz, L . B . and L. Schrage. "Optimal and System Myopic Policies for Multi-Echelon Production/Inventory Systems.", Management Science, 21, 11, (1975), 1285-1294. [97] Sethi, S.P., Feng Cheng. "Optimality of (s,S) Policies in Inventory Models with Markovian Demand Processes.", Working Paper, (1993), Faculty of Management, University of Toronto, Toronto, Ottawa. [98] Sherbrooke, Craig C. " M E T R I C : A Multi-Echelon Technique for Recoverable Item Control.". Operations Research, 16, (1968), 122-141. [99] Sherbrooke, Craig C. "An Evaluation for the Number of Operationally Ready Air-craft in Multi-Level Supply Systems.", Operations Research, 19, (1971), 618-635. [100] Sherbrooke, Craig C. "Waiting Time in an (s-1, s) Inventory System - Constant Service Time Case.", Operations Research, 23, (1975), 819-820. [101] Silver E .A . and Rahmana M.R. "The Cost Effects of Statistical Sampling in Se-lecting the Reorder Point in a Common Inventory Model.", JORS, 37, 7, (1986), 707-713. [102] Silver E .A . and Rahmana M.R. "Biased Selection of the Inventory Reorder Point When Demand Parameters Are Statistically Estimated.", Eng'g. Costs and Prod. Economics, 12, (1987), 283-292. [103] Silver, E .A . , and S.A. Smith. "A Graphical Aid for Determining Optimal Invento-ries in a Unit Replenishment Inventory System.", Management Science, 24, (1977), 358-359. [104] Simon, R . M . , "Stationary Properties of a Two-Echelon Inventory Model for Low Demand Items.", Operations Research, 19, 3, (1971), 761-773. Bibliography 145 [105] Sivazlian, B .D. "A Continuous-Review (s,S) Inventory System with Arbitrary In-terarrival Distribution Between Unit Demand.", Operations Research, 22, (1974), 65-71. [106] Smith, S.A., "Optimal Inventories for an (s-l,s) System with no Backorders.", Management Science, 23, 5, (1977), 522-528. [107] Srinivasan, R., J . M . Swaminathan. "Managing Individual Customer Service Con-straints under Stochastic Demand.", I B M Research Report No: 20196 (89382), (1995), I B M T.J . Watson Research Center, Yorktown Heights, N Y 10598. [108] Tadikamalla, P.R. "Applications of the Weibull Distribution in Inventory Control.", JORS, 29, (1978), 77-83. [109] Tadikamalla, P.R. "The lognormal Approximation to the Lead Time demand in Inventory Control.", OMEGA, 7, (1979), 553-556. [110] Tijms H.C. , H.Groenevelt. "Simple Approximations for the Reorder Point in Pe-riodic and Continuous Review (s,S) Inventory Systems with Service level Con-straints.", European J. of Operational Research, 17, (1984), 175-190. [Il l] Topkis, Donald M . "Optimal Ordering and Rationing Policies in a Nonstationary Dynamic Inventory Model With n Demand Classes.", Management Science, 15, 3, (1968), 160-176. [112] Veinott, A . F . , and H . M . Wagner. "Computing Optimal (s,S) Inventory Policies.", Management Science 11, (1965), 525-552. [113] Wagner, H . M . Statistical Management of Inventory Systems., Willey, New York, (1962). [114] Waldman, K . H . "On The Numerical Treatment of A Bayesian Inventory Model.", Bonner Mathematics Schriften, 98, (1977), 117-132. [115] Weerahandi, S. "Decision Theoretic Estimation of Optimum Inventory Levels with Natural Invariant Loss Functions.", Statistics and Decisions, 5, (1987), 177-188. [116] Weiss, H.J . "Optimal Ordering Policies for Continuous Review Perishable Inventory Models.", Operations Research, 28, (1980), 365-374. [117] Weiss, H.J . "Sensitivity of Continuous Review Stochastic (s,S) Inventory Systems to Ordering Delays.", European J. of Operational Research, 36, 2, (1988), 174-179. [118] Williams, T . M . "Stock Control with Sporadic and Slow-Moving Demand.", JORS, 35, (1984), 939-948. Bibliography 146 [119] Wolff, Ronald W. Stochastic Modeling and The Theory of Queues, Prentice Hall, Inc., New Jersey, (1989). [120] Yano, Candace Arai. "New Algorithms for (Q,r) Systems with Complete Backorder-ing Using a Fill-Rate Criterion.", Naval Research Logistics Quarterly, 32, (1985), 675-688. [121] Zipkin, Paul. "Inventory Service-Level Measures: Convexity and Approximation.", Management Science, 32, 8, (1986), 975-981. [122] Zheng, Y.S. , A . Federgruen, "Finding Optimal (s,S) Policies Is About As Simple As Evaluating a Single Policy.", Operations Research, 39, 4, (1992), 654-665.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Essays in inventory control
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Essays in inventory control Katircioglu, Kaan K. 1996
pdf
Page Metadata
Item Metadata
Title | Essays in inventory control |
Creator |
Katircioglu, Kaan K. |
Date Issued | 1996 |
Description | This thesis studies four important problems faced in the theory of inventory control. The first chapter addresses the issue of calculating optimal inventory policies in stochastic inventory problems, when unknown demand parameters are estimated from a sample of demand observations. A general framework for combining estimation and optimization problems is developed for a class of inventory problems when the demand distribution belongs to the scale-location family. The results show that biasing the scale parameter estimates gives better inventory policies for both cost minimization and service achievement objectives. The second chapter studies a periodic review, single-product, single facility inventory problem with multiple customer classes, each requiring a different service level. Customer demands are random and independent with a stationary probability distribution. The objective is to find a stock allocation policy among the customers and an inventory replenishment policy so as to achieve target customer service levels with minimum possible inventory holding cost. An easy-to-calculate myopic heuristic allocation-order policy is developed and its performance is tested through simulation. The third chapter finds an optimal inventory policy for a classical single-stage, singleproduct, unit demand, continuous review inventory problem where the interdemand times are independent identically distributed random variables with increasing failure rate. Unmet demand is fully backlogged and orders arrive after a lead time. The costs of backlogging and inventory carrying are linear. The objective is to minimize the long run average cost. If there is no fixed cost for placing an order, it is proven that a Delayed- (s-l,s) policy is optimal. In case of a fixed order cost, a Delayed-(s,S) policy is proven to be optimal. In chapter four, the same problem as in chapter three is studied for a Poisson demand in the case of lost sales. No fixed cost for placing an order is assumed. For this problem, an optimal policy is unknown and it is commonly believed that an (s-l,s) policy is sufficiently good. A new heuristic policy is suggested as an alternative, which uses more information, but is myopic in nature and its performance is compared with that of (s-l,s). |
Extent | 6456686 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-03-16 |
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.0087657 |
URI | http://hdl.handle.net/2429/6057 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration - Management Science |
Affiliation |
Business, Sauder School of Operations and Logistics (OPLOG), Division of |
Degree Grantor | University of British Columbia |
GraduationDate | 1996-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1996-14772X.pdf [ 6.16MB ]
- Metadata
- JSON: 831-1.0087657.json
- JSON-LD: 831-1.0087657-ld.json
- RDF/XML (Pretty): 831-1.0087657-rdf.xml
- RDF/JSON: 831-1.0087657-rdf.json
- Turtle: 831-1.0087657-turtle.txt
- N-Triples: 831-1.0087657-rdf-ntriples.txt
- Original Record: 831-1.0087657-source.json
- Full Text
- 831-1.0087657-fulltext.txt
- Citation
- 831-1.0087657.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-0087657/manifest