I Research Support University of Michigan Business School OCTOBER 1998 OPTIMAL AND NEAR-OPTIMAL DECISIONS FOR PROCUREMENT AND ALLOCATION OF A CRITICAL RESOURCE WITH A STOCHASTIC CONSUMPTION RATE WORKING PAPER #98019 BY ASHOK KUMAR GRAND VALLEY STATE UNIVERSITY AND SHELDON H. JACOBSON VIRGINIA POLYTECHNIC INSTITUTE AND STATE UNIVERSITY

Optimal and Near-Optimal Decisions for Procurement and Allocation of a Critical Resource with a Stochastic Consumption Rate Ashok Kumar Eberhard Center, Room 510 Seidman School of Business Grand Valley State University 301 W. Fulton, Grand Rapids, MI 49504 Phone: (616) 771 - 6522 Fax: (616)771-6515 E Mail: Kumara@gvsu.edu Sheldon H. Jacobson' Department of Industrial and Systems Engineering Virginia Polytechnic Institute and State University Blacksburg, VA 24061-0118 'The second author is supported in part by the National Science Foundation (DMI-94-09266, DMI-95-1-0124). and the Air Force Office of Scientific Research (F49620-95-1-0124). The computational results are obtained with support from the Simulation and Optimization Laboratory in the Department of Industrial and Systems Engineering Virginia Polytechnic Institute and State University.

to Optimal and Near-Optimal Decisions for Procurement and Allocation of a Critical Resource with a Stochastic Consumption Rate ABSTRACT Manaoement of critical resources having uncertain consumption rates is perhaps the most common challenge encountered by businesses in discharging their numerous functions, e.g., inventory distribution, marketing, finance, production, personnel, etc. It involves making two key decisions optimally: (1) How much of each critical resource must be procured (replenishment quantity decision), and, having procured, (2) How much of each resource should be allocated among the competing entities (allocation decision). The finance/inventory literature thus far has addressed the allocation decision in an optimal fashion using certain ranking algorithms. However, the optimal replenishment decisions have not yet been addressed optimally except under a restrictive assumption called the allocation assumption. Using the illustration of a periodic-review, stochastic-demand, fixedroute, centralized, multi-echelon distribution system in this paper, we propose a non-ranking allocation policy that is faster than those existing in the literature and also develop an optimal replenishment algorithm that is independent of the allocation assumption. Furthermore, we allow our distribution system a greater flexibility than that allowed in the literature thus far - we explicitly permit fixed delivery routes, arbitrary demand distribution parameters, nonidentical delivery leadtimes simultaneously with a positive order leadtime. The major empirical contribution of this work is to demonstrate, through an extensive simulation study, that a computationally efficient heuristic, called the hybrid heuristic, performs close to optimal, even for the systems with high demand uncertainty. Intriguingly, the bottom line finding of our computational experiments is that while the probability of violation of the allocation assumption itself is very sensitive to the system demand uncertainty, it is relatively insensitive to the expected system inventory costs in the vicinity of the optimal region. We also develop hand- computable theoretical lower and upper bounds on system replenishment quantity and expected system cost per period that require a single Normal distribution table look-up. MULTI-ECHELON, PERIODIC-REVIEW, CENTRALIZED, FIXED-ROUTE, DISTRIBUTION SYSTEMS, ALLOCATION ASSUMPTION, INVENTORY IMBALANCE

I 1. Introduction This paper addresses a periodic resource allocation and replenishment problem when the consumption rate of the resource is stochastically known. Such problems are encountered in numerous business applications. For instance, finance managers periodically raise investment capital and allocate it among competing portfolios; marketing managers generate and allocate advertising budget among competing products and media; production managers allocate machine time and other resources among competing jobs; warehouse managers procure and allocate inventories among competing retailers. The allocation and replenishment problem is also encountered with significant regularity in defense applications. For instance, competing defense options require an optimal allocation of budget; limited search times needs to be expended judiciously to maximize the probability of finding targets. There is little doubt that the resource allocation and replenishment problem studied here is among the most common in business and defense applications. The basic structure of the replenishment-allocation model analyzed here is as follows: A system or organization consists of an executive entity and a known number of subordinate entities (subentities). Each subentity consumes a critical resource in each period (a managerially convenient or economically viable discrete unit of time of arbitrary length) consistent with an arbitrary but known probability distribution. Furthermore, each subentity incurs a penalty (reward) in any given period based on the initial resource level and the subentity-specific penalty/reward structure. The total system reward (penalty) is additive - i.e., equals the sum total of the rewards (penalties) earned by its subentities. The system objective is to optimize, i.e., to maximize (minimize) average reward (penalty) per period over the infinite horizon. The executive entity performs two distinct but related functions: (1) Replenishment of the critical resource at fixed time intervals. This involves determination of the replenishment quantity, placing an order at an outside supplier, and receiving the order after the lapse of a known time interval (henceforth, replenishment leadtime), and (2) Allocation of the ordered quantity, upon receipt, among competing subentities. The allocation quantity for any subentity is based on the distribution of its resource consumption rate, shipment leadtime (i.e., the time between the instant of allocation and availability of the resource at the subentity), and penalty/reward structure at the subentity. The objective of the analysis here is to determine replenishment as well as the allocation policies that optimize the stated system objective. Despite the general applicability, we believe that the operation of the allocation and replenishment policies presented here will be best illustrated by focusing on one specific area of application, namely, the inventory distribution systems. This is because a significant part of this work is focused on the relaxation of an assumption called the allocation assumption: a term that was first coined in inventory theory (Eppen and Schrage 1981). The transformation of this analysis to other areas is relatively straightforward. Indeed, our optimal allocation policy is an outgrowth of an allocation policy developed originally in the finance literature in the context of portfolio allocation (Luss and Gupta 1975). Consistent with the problem structure outlined above, we model the operation of a One-Warehouse NRetailerfixed-route' system operating in a periodic review mode. The system operates as follows: At the beginning The fixed-route feature is not germane to our analysis, but is included in the interest of obtaining greater applicability of the policies. Indeed, the systems in which the warehouse ships inventory directly to each retailer have one to one equivalence with fixed-route systems provided the allocations are restricted to static ones.

I 2 of each replenishment cycle consisting of one or more periods, the warehouse places an order for a certain replenishment quantity (decision variable) at an outside supplier. The entire ordered quantity arrives at the warehouse after a fixed replenishment leadime. Immediately upon receipt, the warehouse determines static allocations [such allocations, as opposed to dynamic allocations, are determined at the time the delivery vehicle leaves the warehouse and remain unchanged thereafter regardless of the system inventory state; see Kumar et al. (1995) for details] for each retailer. A delivery vehicle then sets out to ship the allocations to the retailers along a pre-determined route. The shipment leadtimes between the warehouse and the first retailer as well as between successive retailers on the route are known deterministic constants. The cost (penalty) structure of the system is typical: There is a proportional or convex holding (shortage) cost assessed at each retailer at the end-of-period inventory (backorders), a fixed ordering cost associated with each system replenishment, and a variable cost associated with the quantity ordered at the outside supplier. Fixed shipment cost between successive retailers is set to zero without any loss of generality. Note that in a finance setting, the holding cost would represent the cost of a dollar not used for investment and a shortage cost would represent the opportunity cost of a dollar that could not be applied to a profitable portfolio. The demands for the commodity occur only at retailers and are drawings from independent, possibly non-identical, normal distributions, across retailers. The "fixed-route" characterization implies stationarity of the delivery routes over time - i.e., each delivery vehicle begins its route at the warehouse, delivers the predetermined allocations to retailers in a predetermined sequence, and returns to the warehouse. Real-life instances of such systems would include distribution systems that supply products to convenience stores, grocery stores, stsgasoline stations, and petro-chemical outlets. The fixed routes systems offer several advantages over the systems that require variable routing, e.g., reduced scheduling effort, elimination of the need to optimize routes on day to day basis, fixed time-windows for delivery at retailers permitting pre-planning, greater driving emanating from familiarization with the routes, and better teamwork between the distributors and retailers. These advantages are offset by the reduction in flexibility in the use of resources (vehicle and drivers), and the fact that the fixed route may not be dynamically optimal over time from the standpoint of the stated system objective. In a recent manuscript (Unknown, 1995), it was shown through simulation that the "Expected distance of the fixed routes is within 10% of the average distance of the daily recomputed [optimized] routes for a large range of customer demand variances when both are computed using heuristics of comparable quality. This penalty decreases further to 5% when the number of customers on a route is larger than six". One can, therefore, plausibly argue that the fixed-route systems present an attractive alternative to variable-routes systems, particularly in repetitive delivery operations. Over the years, relatively few works have appeared in the literature that analyze fixed-route systems [Clarke and Wright (1964), Christofides (1971), Dror and Trudeau (1989), Dror et al. (1989), Stewart and Golden (1983)]. Dror et al. (1989) provide an excellent summary of the progress in this area. In essence, these works are devoted to the development of a solution methodology that generates efficient fixed routes for a given system parameters. Our analysis, in contrast, assumes that such "optimized" fixed-routes have already been determined, perhaps using one of these methodologies, and deals essentially with the issues of inventory ordering and allocations amnong retailers. We also assume that, the warehouse operates in a "centralized" manner, i.e., it determines the system replenishment quantity, frequency of system replenishments, and inventory-allocations consistent with the system objective of minimizing long-run expected system inventory cost.. Before proceeding further, we establish a simple but critical equivalence, For a given fixed route, let bI be the delivery leadtime between the first retailer and the warehouse, and let bj be the delivery leadtime between the a

I 3 )st and jth retailer for j = 2,..., N. Now define, Xi =- bj, which is the cumulative shipment leadtime from j=1 warehouse to retailer i for the given route. Then, for the purposes of determining cost-optimal static allocations (argument breaks down for dynamic allocations), a fixed-route centralized system is equivalent to a "directwarehouse-to-retailer-shipment" system, i.e., a system in which each retailer is shipped directly from the warehouse and the ith retailer is located at a shipment leadtime Aj away from the warehouse, i = 1, 2,..., N. Note that such a system would incur higher delivery cost than the fixed-route counterpart but that is irrelevant from the inventorycosts optimization standpoint. This equivalence is significant in the sense that it allows a significant body of distribution systems research to correspond to our analysis; multi-echelon distribution systems comprised of a centralized agency and an arbitrary number of stocking points that "pull" an arbitrary order quantity periodically from an outside supplier and "push" (allocate and ship upon receipt) to retailers have received considerable attention in the literature [see, e.g., Simpson (1959), Clark and Scarf (1960), Eppen (1979), Eppen and Schrage (1981)[E&S, henceforth], Federgruen and Zipkin [F&Z, henceforth] (1984a), F&Z (1984b), Zipkin (1984), J6 nsson and Silver [called J&S, henceforth] (1987a,b), Jackson and Muckstadt (1989) [J&M, henceforth], Erkip et al. (1990), McGavin et al. (1993), and Kumar et. al. (1995), Bitran and Gilbert (1996), Graves (1996)]. Most of these works either employ an assumption, called the allocation assumption (E&S are credited with this nomenclature) to obtain analytical tractability in the development of the distribution policies for their respective models, or use creative heuristics in determining the allocations. The allocation assumption stipulates that, in each allocation period, an ideal configuration of retailer inventories (namely, equalization of the derivatives of the appropriate retailer's cost functions evaluated at post-allocation inventory levels) can be achieved by making nonnegative allocations from the available order quantity. However, in a stochastic-demand, positive order-leadtime setting, the simultaneous occurrence of this ideal configuration and non-negativity of allocations can not be guaranteed with probability 1.0. Consequently, policies contingent upon the allocation assumption require, with a positive probability, that negative allocations be made to some retailers, i.e., inventory be withdrawn from one retailer and given to another, free of cost, so that the optimal configuration of retailer inventories be attained. Since withdrawal of inventory from retailers is not permitted in most realistic system operations, a violation of the allocation assumption renders the corresponding distribution policies infeasible, and, therefore, unimplementable. In this context, simulation results reported in at least two prior works (E&S, and Kumar et al. (1995) indicate that the allocation assumption cannot be taken for granted, particularly for systems with large demand uncertainties. Specifically, E&S report that for a system with the coefficient of variation of retailer demand, c/t = 2.0, and eight retailers, the allocation assumption holds with a probability of 0.016 only. Kumar et al. (1995) report that the static allocation assumption (the allocation assumption modified to suit the systems using static distribution policies) holds with a probability of 0.1344, and the dynamic allocation assumption (the allocation assumption adapted for systems using dynamic distribution policies) holds with a probability of only 0.0498. Zipkin (1984) does not report a similar probability but makes the following related observation: "The systems tested [in F&Z (1984a), etc.]. however, have rather small variances, and the current results suggest that imbalance [a measure of the degree of invalidity of the allocation assumption] can be significant, even using myopic allocations, when variances are lar2e.". We conclude that the distribution policies contingent upon the validity of the allocation assumption cannot be implemented in their present form, especially for systems with high demand uncertainty. This concern is the

I 4 primary motivator of this work; the development of optimal and near-optimal distribution policies that do not depend on the allocation assumption, constitute the main focus of this paper. Despite such low probabilities of the allocation assumption holding for systems with large demanduncertainty, the issue of its non-tenability has received relatively little attention [only Zipkin (1984), J&M, J&S (1987b), and McGavin et al. (1993), to our knowledge]. Of these, Zipkin (1984) is the most relevant work from our standpoint; its modeling of the retailer demands and cost functions resembles ours and it is the most exhaustive investigation of the impact of imbalanced inventories on the system cost available to date. Using a special case of the system for which all shipment and order leadtimes are set to zero, Zipkin develops an approximate system cost function that accounts for the imbalance in retailer normalized inventories. His approach consists of dividing the total system cost into two components: (1) an easily-computable lower bound on system cost [= E&S's optimal system cost], and (2) an additional cost component resulting from the imbalance of normalized inventories, i.e., resulting from the failure of the allocation assumption to hold. The focus of the article is to find close approximations for the second component. This is accomplished through a two-stage sequence of approximations. In the first stage, a measure of systemwide imbalance after allocation (= weighted variance of normalized inventories) is approximated as a function of the total quantity to be allocated and of the systemwide imbalance prior to allocation. In the second stage, the additional cost component is approximated as a function of the total system inventory and the approximate post-allocation systemwide imbalance computed at the first stage. Allocation and replenishment policy issues are not addressed per se, although approximate withdrawals can be determined through a single dimensional search over a "fractile" type parameter. The approximate total expected cost is demonstrated to be close to its simulated optimum value. In another work (J&M) that develops allocation and replenishment policy parameters for a two-echelon system over a two-period horizon, the possibility of an imrbalance of retailer inventory under an optimal allocation scheme [Zipkin (1980)) is recognized at the second allocation opportunity which arises at the beginning of the second period. All leadtimes are assumed zero. Their treatment remains approximate by virtue of the fact that the first allocation of inventory is still contingent upon the validity of the allocation assumption. Numerical results are not reported. In a model rooted in servicelevel/backorder setting, J&S (1987b) develop an approximate system replenishment policy for an m-period replenishment cycle. Considering low-variance systems (cr/t 0.4) and identical retailers with normally distributed demands, they approximate the expected number of retailers that get positive allocations at the second opportunity, i.e., in the penultimate period of the cycle. Simulation results indicate that, for a given service level, substantial reduction can be obtained in the total system-stock as a result of stock redistribution. Finally, McGavin et al. (1993) develop a near-optima! two-interval allocation heuristic for a one-warehouse N-retailer system that minimizes lost sales/retailer. The term allocation policy in their case has more general connotations than in most other works. It requires determination of the number of withdrawals from warehouse stock, interval between successive withdrawals, quantify of stock to be withdrawn from the warehouse in each withdrawal, and allocation of the stock among retailers in each interval. Graves (96) introduced a new method for allocating stock among retailers termed "virtual allocation". Under this scheme, each unit demand at a retailer, triggers a unit order on its supply chain. In response, each site on the supply chain immediately commits or reserves a unit (virtual allocation) to replenish its downward site. The physical shipment of the unit only occurs at the scheduled shipment instants. Their virtual allocation policies yield near-optimal results. Bitran and Gilbert (1996), in a non-inventory setting, use efficient heuristics methods to address the problem of room allocation in the hotel industry on a dynamic basis. A key observation in respect of the research published on allocation-replenishment models thus far is that an approximate approach is taken to capture the effect of the imunbalanced inventories on the objective function of

I 5 interest. In contrast, the primary analytical contribution of this work is in addressing the issue optimally. The distribution policy for a multi-echelon distribution system developed here is optimal regardless of the allocation assumption holding: no surrogate or approximate measure, is used to account for the imbalance in post-allocation retailer inventories. Our approach, an entirely different one from those previously adopted, consists of first determining the optimal retailer inventories using a non-ranking algorithm [Kumar, 1992] that is computationally faster than the ranking algorithms available in literature ( e.g., Luss and Gupta (1975), Zipkin (1980)) and then projecting these across the order leadtime. The exact expected system cost function so derived is shown to be convex in the system replenishment quantity and requires a single dimensional search to yield the optimal replenishment policy. In order to provide a focused view of where this work stands vis a vis some of the other significant works that are related to our modeling and analysis, we present the following table: Table I goes here In summary, this work may be viewed as an extension of Zipkin (1984) in permitting the following generalities in the system model: (i) Non-identical shipment leadtimes, (ii) Non-zero order leadtime, (iii) Arbitrary parameters of retailer demand distribution, and (iv) Fixed-route distribution systems. Furthermore, our analysis allows: (i) A quick computation of the optimal allocation and replenish-ment policy for the case of zero order leadtime and arbitrary non-negative shipment leadtimes, and (ii) An exact estimation of the cost-impact of the imbalance of retailer inventories on the cost function. However, our model is more restrictive compared to Zipkin (1984) in that: (1) We consider only myopic allocations while Zipkin actually uses a dynamic programming approach to demonstrate that such allocations are close to optimal, and (2) We do not consider any correlation between retailer demands. Comparisons with other relevant works can be found in Table 1. Our major empirical contribution lies in extending previous findings with regards to the sensitivity of the allocation assumption for a more generalized set of distribution systems, including the systems with fixed-routes. Perhaps, the most intriguing finding of our simulation experiments is that while the probability of violation of the allocation assumption rises rapidly as the system uncertainty increases, the effect of even gross violations seems to be minimal on the expected inventory costs incurred by the system. In other words, even the high-uncertainty systems are relatively cost-robust with respect to the imbalance of inventory. To test the impact of the allocation assumption on system cost, we employed the following distribution policy: Determine the retailer allocations at each allocation epoch using an optimal non-ranking algorithm [Kumar (1992)], and use the lower bound on the base-stock (same as in E&S or F&Z (1984a) for the detenrmination of the system replenishment quantity. In so far as simulation is concerned, this policy will differ from that in F&Z (1984a) and to a partial extent in F&Z(1984b) only in the manner (ranking vs non-ranking methodology) the optimal myopic allocations are determined. The attractiveness of this policy follows from its quick-computability; however, its true strength lies in its fine cost performance. Based on a simulation of 90 system parameterizations that included high-variance, fixed-route systems (0.8 < cr/ < 1.0), the hybrid heuristic performed within 2% of the lower bound on all optimal policies. For low-to-medium variance systems (0.2 < cr/p C 0.8), the heuristic performed within 1% of the same lower bound. In addition to the main contributions outlined above, this work also contributes the following analytical results: (1) Lower and upper bounds on the optimal replenishment quantity. Our lower bound on the replenishment quantity equals the optimal replenishment quantity of E&S; our contribution is in providing a proof of this non-trivial proposition. (2) Lower and upper bounds on the optimal system cost. Again, our lower bound is

I 6 the same as in E&S, or in F&Z(1984a); our contribution lies in deriving a simplified form that allows its computation with a single normal distribution table look up. (3) An exact expression that yields an unconditional probability of the allocation assumption holding for any arbitrary inventory state of the system. This measure, we believe, is of greater practical importance for managers than those reported previously [E&S] because it can be computed when it is most useful, i.e., at the time of placing the order. Finally, (4) We allow means and standard deviations of retailer demands as well as the shipment leadtimes to take arbitrary values across retailers in our model. As a final remark, we point out that this model can also be appropriately employed in alternate production/assembly systems such as those discussed in Zipkin (1982). This paper is organized as follows: In Section 2, some preliminary results pertaining to a single retailer and the allocation assumption are presented. In Section 3, an optimal distribution policy is developed. Section 4 develops upper and lower bounds on the optimal replenishment quantity and expected system cost. Section 5 develops an exact analytical expression for computing the probability of the allocation assumption holding. Section 6 presents empirical results of pursuing a hybrid distribution policy described above and Section 7 concludes the main findings of this work. 2, Preliminaries We introduce some preparatory material in this section (notations, assumptions, terminology), and provide a brief analytical background of the allocation assumption. Some results related to the "Newsboy" type singlelocation model with delivery lag [Arrow et al. (1958)], and the distribution policies contingent upon the allocation assumption (introduced in E&S) are also presented in a "unified" framework of "lag-adjusted-normalized inventory" to facilitate subsequent exposition. Notations i = Index of retailer, i 1,2,..., N. I = Set of all retailers; I = {1,2,..., N}. T Outside supplier to warehouse delivery leadtime = order leadtime. m = Number of periods between replenishments. K = Fixed component of system ordering cost. p = Unit shortage cost assessed at the end-of-period net-inventory. h = Unit holding cost assessed at the end-of-period net-inventory. Q = Replenishment or allocation quantity. 6i = Random demand at retailer i in any arbitrary period with cdf (i and pdf 4i(.). We assume Si - N(pi, Oi 2), only for replenishment policy analysis. fii = -period random demand at retailer i. 5i j- 'i, i.e., r-fold convolution of (i. Also, D T T T &)j,5,...,S5N ). 5 A standard normal random variable with cdfN(0,1) [= ((.)] and pdf 4(.).

7 i. = Warehouse to ith retailer shipment leadtime, = br,j, where r is the index of the delivery route j=l on which retailer i is located, br I is the delivery leadtime between the first retailer on route r and the warehouse and brj, j = 2,... is the delivery leadtime between the (j-l)st and jth retailer on route r ifj 2. qi = Inventory allocation to retailer i. Wi = Inventory position of retailer i prior to allocation (= net-inventory + inventory in pipeline from the warehouse); W Vector (Wj, W2,..., WN) at a given instant (t = 0 or t =T). Yi = Inventory position of retailer i after allocation = Wi+ qi. Li(Y) = Expected Cost incurred by retailer i in an arbitrary period, starting with a net-inventory Y. (= E [h (Y- ) + + ( Y- ) ) p (Y- ], where E is expectation over hi; (X)+ = max {X,0} and (X)' - min {X,O)). As above, we use E[.] as expectation of. over the appropriate random variable(s), throughout this work. m L3 i(Y) = Expected cost incurred at retailer i having beginning-of-cycle net-inventory Y. H = An arbitrary allocation policy (also see definition, later in this section). Zr(W,Q) = System cost associated with the allocation of a quantity Q amongst N retailers in accordance with the allocation policy n, given pre-allocation W. Cr(W,T, Q) = Expected Cost associated with ordering a quantity Q at t = 0 when the retailer inventory position is W and allocating it at time t = T, in accordance with an allocation policy I. Qn = Optimal replenishment quantity associated with the allocation policy n. * * Cn = Optimal expected system inventory cost associated with ordering Qp at t = 0 and allocating it in accordance with policy nl at t = T. z = )- 1 [p-h(m-l)/(p+h)] wher, -wh, (x) = {y: ((y) = x}. Assumptions: The analysis depends on several assumptions which have been made rather commonly in the inventory literature: All holding and shortage costs are identical across the retailers. (e.g., in E&S, Zipkin (1984), Schwarz (1989)). * All retailer demands are independent across time periods. (e.g., in most works discussed in the previous section).

I * All demands are independent across retailers (e.g., in F&Z (1984a, b). E&S, J&S (1987a, b), Schwarz (1989)). * There is only one outstanding order in the supplier-warehouse pipeline (e.g., in J&S (1987a,b), Schwarz (1989) and Schneider (1981). ~ Backorders occur only in the last period of the m-period cycle (e.g., in E&S, J&S (1987b), Schwarz (1989). * All demands are completely backlogged. (Nearly all works in inventory theory!) ~ Retailer period-demands are assumed normally distributed (e.g., in E&S, Zipkin (1984), F&Z (1984a, b), Schwarz (1989), J & S (1987a,b), for a part of this work related to the development of the optimal replenishment policy. * Shortage cost > linear shipment cost at each retailer so that shipping based on possible shortages is economically justified. However, we do not explicitly build shipment costs into the model as their effect can be captured by redefining the holding cost and the shortage cost, if necessary. Terminology: We now define several terms that will be used throughout the rest of the paper: Lag-Adiusted Normalized Inventory A generalized version of Zipkin's (1984) normalized inventory concept that provides adjustment for warehouse-to-retailer (shipment) leadtime, given by Ri = (Wi - pi(m+ Xi))/ciT- m+iTi ). Other variants of this concept occur, for example, in E&S and J&M. Allocation Cycle: An allocation cycle for retailer i consists of periods Xi+T+l through X1+T+m, i.e., the periods in which the allocation made to retailer i at t = T will affect the system cost, prior to the arrival of the next allocation. This definition is consistent with the myopic allocations considered in E&S, F&Z (1984a), and others. Distribution Policy The term distribution policy refers to a complete specification of the (1) optimal allocation policy, (2) optimal system-replenishment quantity, and the associated (3) optimal system cost. We formalize the definitions below. The Optimal Allocation Policy: An allocation policy is a procedure/algorithm that determines allocations of an arbitrary quantity Q amongst N retailers such that the sum of the expected inventory (shortage + holding) cost incurred at all retailer during their respective allocation cycles is minimized. Such allocations are called the "myopic" allocations. See F&Z (1984a), and Zipkin (1984) for a discussion and justification of myopic allocations. Consider the following allocation problem, AP: Zi,(W,Q) = Mim L(Wi+qi) (1) i= I

I 9 N s.t. qi =Q (2) i= l and qi 0 for i= 1,2,...,N. (3) The allocation problem that ignores constraints (3) is called the allocation problem dependent on the allocation assumption holding and denoted AP(aa). The corresponding allocation policy that solves AP(aa) optimally is denoted Iaa. This is addressed in E&S, F&Z(1984a), among others. The allocation problem that does not ignore constraints (3) is called the allocation problem independent of the allocation assumption holding and denoted AP(ua. The corresponding allocation policy that solves AP(i) optimally is denoted FIa. The Optimal System-Replenishment Policy: An optimal replenishment policy corresponding to an allocation policy n finds the value ofQ, denoted QII, that minimizes C-1(W, T, Q). System Cost: The minimum cost associated with an optimal replenishment and allocation policy, given by Cin, = Cn*(W,,T, Qj*). Throughout the rest of this work, we assume, without loss of generality, that the current instant is t = 0 when an order for quantity Q is placed on an outside supplier. This order will be myopically allocated amongst N retailers upon arrival at t = T. Our objective is to find 1n*, QrI*, and Cri* for the case when the allocation assumption does not hold. The Allocation Assumption: The allocation assumption is characterized by the following three observations: (1) It significantly reduces the analytical complexity of AP, (2) it yields the equality of the lag-adjusted normalized inventory across retailers at optimality, and (3) its breakdown implies infeasibilty of the associated allocation policy (via negative allocations). We briefly demonstrate these characteristics. The Kuhn-Tucker conditions for the AP yield: m d/dqi [Li(Wi+qi)] = + Yi for all i (4) where 0 (non-restricted in sign) is the Lagrange's multiplier for constraint (2) and yi 0 areLagrange's multipliers for (3). Noting that the allocation assumption is equivalent to relaxing constraints (3), we have all yi's O0, so that m d/dqi [Li{(Wiqi)]= 0 for alii (5) which eliminates N (,is ) variables from consideration. Now, if the inverse mapping gi: dm 1. * q[LXi(Wi+qi)] = -qi = gi() can be easily obtained, the problem of determining qi, reduces to solving for a N * single variable 0 in Z gi(O)= Q [from (2)], and then recovering the optimal allocations from qi = gi(0*), for each i= 1

I 10 i. For normally distributed retailer-demands, further simplifications occur, yielding a closed-form solution. Indeed, the sequence of operations just described leads to (Wi + qi - i(Xi+m)) /UiqThi-m= Ri = (Q+ (Wj - pi(ki+m))/k ii;) (6) i-l i=l Thus, the allocation assumption enables a closed-form solution to AP. The second characteristic follows from (6). To see the third characteristic, let Rmax = max{Ri}. Then, for any Q such that Q c< i x im [Rmax - Ri] } one or more allocations will be negative, since Q is inadequate to bring each Ri to Rmax. The Single Retailer Analysis: Consider an arbitrary, "Newsboy" type, independent retailer that replenishes in a periodic review mode. It determines and places its own replenishment order every m periods which arrives after X periods. Its period-demand is normally distributed with N(g,a), and it incurs proportional costs p (h) respectively on the end-of-period negative (positive) net-inventory. For consistency and succinctness in the development of the distribution policy for the system, define a (hypothetical) unit-normal retailer with shortage and holding cost p and h respectively, and period-demand 6 - N(0,1). Let L(.) be the single-period expected cost function of this hypothetical retailer. Proposition 2.1 a. The optimal replenishment policy for the "Newsboy" type retailer is a base-stock policy, with the critical number, Y*, given by Y* = II (X+m) + CT J(T.+m) * z. (7) b. Suppose at the beginning of an arbitrary period t, the retailer inventory position is W. The expected inventory cost, incurred during the cycle X+t through X-t-rm-l, L2 (W), at this retailer, is (1/2) h m(m-l) k + cr.mi. ~ [h(m-l)R+ L(R)] (8) where R = (W - a(X+m))/cJ-i —, and L(R) = - p R+ (p+h), (R cD(R) + +(R)]. c. The average inventory cost per cycle associated with the replenishment policy described in a. is L* = (1/2) h m(m-l) p+ + (p+h) cr a4(.+m) * (z). '(9) Proof: The result in part a. is an adaptation from Arrow et al. (1958). To prove part b., m L'(W))= Z E [ h- (W - &+t): p. (w - +t) +] t= m-1 = E [ h- (W - a+t)]+ E [ h-(W- W -A+m) + p (W- 6m)] t=l

I 11 since backorders are assumed to occur only in the last period of the cycle. Now, the first term in the surrmand equals h (m-l)(W - tX) - h p (1/2) m(m-l) = (1/2) h p m (m-l)+ h (m-l) R ofmiX. Furthermore, the last term in the summand equals (after some algebra), omiiiTXA L(R). Combining the two components, we obtain the result. Finally, L(R) = -p R + (p+h) * (u) du - p R+ (p+h) * [R <(R) + +(R)], -ac for a standard normal density/distribution function. For deriving the result in part c, simply note that the minimum of L(R) can be shown, using basic calculus, to occur at R = z. The result follows by substituting for R in (8). Note that L* can be computed quickly, involving a single normal distribution table look-up (to evaluate z). We conclude this section by noting that part b of the proposition plays a significant role in the development of the optimal distribution policy. 3. The Optimal Distribution Policy Recall that Haa (flm) is the optimal allocation policy when the allocation assumption holds (does not hold). We discuss the determination of the corresponding distribution policies below. The Optinmal Distribution Policey with the Allocation Assumption Holding: The allocation and replenishment policies have been developed in E&S. We reproduce their results for the (m, Y*) policy in the format of the lag-adjusted normalized inventories. The special case of order-every-period follows by substituting K = 0 and m = 1, and adjusting for non-identical shipment leadtimes. The Allocation Policy. faa: The optimal allocations can be determined from the following equality: qi = aiJKi+m (R - Ri) (10) N N where RS = (Q+ Z W + pi(Xim) ) ai4Tim )can be viewed as the, lag-adjusted normalized inventory for the system. The Replenishment Policy: The optimal value of the systemwide base stock, Ynaa' is given by: +T+m)) Z i(;-i+T+m)) + vS- z (l1) i=l where aS = [ clai V T T Z oi Therefore, the optimal replenishment quantity can be computed from

I 12 Qnaa = Max (Yaa -W)0. where WS is the total system inventory inclusive of the inventory in order pipeline. The following corollary describes simplified results for special cases. Corollary: (i) When all pi = I, cij = a, Xi = X, (e.g., in E&S) it can be shown that: Y aa- = N p (X + m + T ) + z cr qN (X+mh) + 1 (ii) When all pi =, cr = a, and retailers are equidistant on a route, i.e., all b; b, it can be shown that: Yaa= N l { m+T+b + }+S z Where oS =cr A 4+(i-l)b+m + NT System Cost, Cln: Since, the system reduces to a single location model when the allocation assumption holds, we can use analysis parallel to that in Proposition 2.1 to show that *~t N Caa = K + (1/2) h m (m-l) i + oS (p + h) ) (z) (12) i=l Simplicity and speed of computation of this exact expression compares very favorably with the equivalent functions in E&S (p. 66). The Optimal Distribution Policy with the Allocation Assumption Relaxed: We now turn attention to the main objective of this research. namely development of the policies that are independent of the allocation assumption. The analysis pertains to a single allocation-and-repenishment cycle in view of the myopic allocations considered here. The Allocation Policy, fn-: When the allocation assumption does not hold, there is no closed form solution to AP, since equalizing Ri's may lead to negative allocations. However, ranking methods which involve ranking of Ri's and then allocating so as to maximize the minimum Ri's [see Luss and Gupta (1975), Zipkin (1980)] can be adapted to yield optimal allocations, qi. We, however, recommend using the following non-ranking algorithm [Kumar (1992)] that is computationally faster than its ranking counterpart: The Non-Rankina Allocation Algorithm. 1-1r Input: Pre-allocation Ri values, quantity Q to be allocated. Step 1: Allocate quantity Q amongst retailers in set I using (6).

I 13 If: qi >0, for all iI, stop. The optimal allocation policy is to allocate: qi for ieI, and 0 otherwise. Else: Let E { i: qi < 0, iEl} I - I \ E (i.e., delete elements of set E from set I). Repeat Step 1. Proof of optimality and computational comparisons of non-ranking algorithms with the ranking algorithms is available in Kumar (1992). We point out that this algorithm can be modified to apply to more generalized systems, e.g., those having non-identical shortage and holding costs, arbitrary demand distributions, etc,. by appropriately transforming the Ri's. Indeed, since Li is a convex function of the beginning-of-period net-inventory, the non-ranking algorithm would work with each Ri replaced by the derivative of the corresponding Li function. The Optimal Replenishment Policy: Due to a particularly simple and quickly computable form of the optimal replenishment policy and the associated system cost, we first treat a special case of distribution systems, namely, systems with order leadtime equal to zero. Case 1: Order Leadtime = 0: The following proposition outlines the remaining components of the optimal distribution policy (the allocation policy has already been described) for this special case. Proposition 3.1 a. Let Yi be the optimal base-stock for retailer i [see (7)]. Then, Qn [ max '{Yi - Wi},]. (13) i=l b. Let set A { i: Wi < Q )}. Then, the optimal system cost, Cn, is N Kit +(1/2 ) m(m-1) ~ pi hi +Y (pi+h) 'i;(ii ~)(z) + i-l A Z(PiRi + (Pi+hi) [Ri'i(Ri) + 4i(Ri)]) c* miJf iEl\A where q is the indicator function allowing K to be charged only when Q-la.> 0. Proof: When the order leadtirne is zero, thereis no risk-pooling over the order leadtime. The dallocation problem therefore, separates in each i. The optimal system replenishment is, therefore, equal to the sum of individual retailer's optimal replenishments. The result in part a. follows from (7). To prove part b, simply note that, at time T, the retailers in set A will have their inventory position built up to the optimal value given in (7), while retailers not in set A will have their inventory position unchanged. Hence, the associated cost for each retailer in set A will be

I 14 given by (9) and for retailers not in set A, by (8). The total cost in (14) is the sum of the retailer inventory costs in the corresponding sets.. Several observations are worth noting in regards to the system model on hand: First, due to the separability of the allocation problem over retailers, the results are applicable to more generalized systems. Specifically, nonidenticality of holding costs (hi), shortage costs (pi), and demand distributions ((Di) across retailers [e.g., in F&Z (1984a, b)] can be easily incorporated. Second, due to the same reason, an easily computable expression involving a single normal distribution table look-up, allows us to compute the optimal cost. Third, it follows that neither the optimal cost nor the optimal ordering policy is a function of total system inventory (unless, of course, the allocation assumption holds, when A = I). Fourth, and perhaps the most important, note that it.would never be optimal for the warehouse to hold any inventory. In case, however, the warehouse does have a certain amount of inventory, say W, a simple withdrawal policy [term used in the sense of Zipkin (1984)] that withdraws min {W, Qn } will be optimal. Finally, note that, if we let hi= 0 for all i, this model reduces to the special case analyzed in Zipkin (1984). The simplicity and computability of our optimal results is noteworthy. Case 2: Order Leadtime > 0: The development of the optimal replenishment policy for the general case of T > 0 will need the following property of the optimal allocations that follows from (4) and (5) Theorem 3.1 Let I, be the subset of retailers who get a positive allocation from an arbitrary quantity Q > 0 under policy fll Then, there exists a constant K(Q), such that: Ri K(Q) for Vi E Ir Ri > K(Q) for V i e I r I \ where Ri is the optimal value of Ri after allocation of Q. Theorem 3.1 is central to the derivation of the optimal replenishment policy for the general case of T > 0. Let Ar be defined as the event which results in positive allocations to all retailers in set Ir - {i1 i2 jir, and no allocation to retailers in the complement set Ir {i+lr ir+2..., iN} under the optimal allocation policy nHa. Existence of the set Ir is not an issue since Q > 0 must be allocated to at least one retailer in I. Also note that Ar is completely and uniquely defined by Q and W - D as the optimal allocation property (Theorem 3.1) takes its course. Let A be the set of all such events Ar consisting of a total 2N- possible subsets Ir Note that the case of [ji,! = 0] obtains when the allocation assumption holds. From the total law of probability, Cnr(W,T, Q)= KrT + E[Zn=(W-D,Q) ]

I 15 = Kr + E[Z nl(W -D,Q)IAr ] Pr(Ar) (15) AIEA To simplify this expression, we analyze the two components of E[Z- U(W-D,Q) IAr]: (1) expected inventory cost incurred by the retailers in set Ir and (2) expected inventory cost incurred by retailers in set I r. More explicitly, Expected system inventory cost associated with E[ZF7 AV -5,Q)mAr I optimally allocating a quantity Q at t = T amongst E[Zi(WDQ)]iAr = retailers in set Ir in accordance with policy nHa [ Expected system inventory cost associated with 1 + allocating nothing at t = T amongst retailers in set Ir (16) The first term on the RHS of (16) is obtained directly by combining the analysis in Proposition 2.1 part b, and E&S's analysis for allocating an arbitrary quantity Q, and computing the associated expected cost. From (12) this equals: (1/2) h m (m-1) i+4- [aa[h(m-1)Ra + L(Ra)]] (17) i E Ir where a = - E i i7jTi 1M + T EZ i2, and Ra = ( [Wi - pi(m+T+ Xi)]+Q)/ua. i E Ir i E Ir i E Ir For the second term, note that each retailer i E I r contributes its share of the expected cost incurred in its allocation cycle (a cycle ofm periods beginning in period T+Xi+l and ending in period T+Xi +m) having a current net-inventory of Wi. Therefore, using Proposition 2.1, part b., the expected cost incurred by all retailers-in set I r in their respective allocation cycles are: Z hm(m-l) i + [ [h(m-1)R + L(Rb)]] (18) iEIr b b b where ai = cijpfii mT+ and R= (Wi- pi(m+T+ Xi))/b, also from (12). We can combine (17) and (18) and simplify to obtain: E[ZnH (W-D,Q) IAr ] = h m(m-l) ~ Mi + i=l

I 16 aSh b Rb + b (19) [c a[h(m-I)Ra+ L(Ra)]] + Z ai [h(m-1)Ri + L(R[ )J]. (19) Note that, despite its somewhat formidable appearance, (19) is a closed-form, fairly easy to evaluate expression, since, for normally distributed demands, L(x)= - px + (p+h) - [x M(x) + 4(x)]. We now compute Pr{Ar} which is a more challenging task. Let Ri be the m-period lag-adjusted-normalized inventory position of retailer i at time T (a random variable), i.e., RT { (Wi- 6- i(m+Ti))/ci i } for all i e I. T Also, let: imax imax Max (Ri i and imin: Rimin.I {.i large enough to bring the m-period normalized inventory of each retailer in Ir to Rima, and (ii) Q is not large T enough to bring the m-period normalized inventory of each retailer in Ir to Rimin. Hence,. Pr {A, = Pr (Rmin RT )i mTji > Q R RT) (20) i e Ir i E Ir T if V'T T which reduces to Pr Ar}=Pr Rimin> + Rt i R c i miTi i i qTT > Ri max i Ir) i )Ir T 1r T F iir S_.' T Recognizing that the cdfof Rima is l Gi(x), cdfofRimin is L - 1n (I - Gi(x)). andcdfof Ri cri.Jmii Ir is N [ N[Wj- tj (m+T+Xj)], T I Gcj2, Pr{Ar} can be computed. Hence, (19) and (20) together allow us to ilr i E I evaluate E[ZI-T(W-D,Q) ] in the RHS of (15), and, therefore, Cni(W,T,Q) QH, can then be determined through a single-dimensional search. In the next section, we show that Cn (W,T, Q)is convex in Q and develop bounds on Qr, to limit this search. There are two significant observations that follow from the preceding analysis. First, the optimal replenishment quantity, Qra, is not a function of the total system inventory, since Ir s I with probability 1.0. This, in turn, has the implication that when K = 0, systemwide base-stock policies are not optimal, and, when K > 0,

I 17 (s,S) policies are not optimal, either. Second, the computations of Qn requires O(N!) operations, which can be computationally burdensome, for large N. We pursue this latter observation in Section 6. 4. Bounds on Optimal Replenishment Quantity and System Cost In this section we develop lower and upper bounds on the optimal replenishment quantity, each of which can be computed simply with a single normal distribution table look up. These bounds, in conjunction with the proof of convexity of system cost (also presented in this section), take special significance as they serve to contract the region of the search for Qna significantly. Also presented are upper and lower bounds on optimal system cost, where each of these bounds can be computed with a single normal distribution table look up. Theorem 4.1 CrH (W,T, Q) is strictly convex in Q. Proof: Since Cn (W,D,Q) = Kr + E[Zn.(W-D,Q) ], it is sufficient to show that Zni-(W-D,Q) is strictly convex in Q. * N From (1), Z,(W-D,Q) = Min jE [ Lwi(Wi+qi-6i ) subject to (2) and (3). i=l r m T i Wiq- i (m T + Xi) Now, we can show that E Lki(Wi+qi-5i )jci m 4 +i + F L I n -L + i- + - + -i is strictly convex in qi, which yields: d2/dq2 E Li(Wiqi-i )> 0 for each i (21) Also, from constraint (2), 6qi/6Q = 1 for each i (22) m T Using the chain rule, and writing Z for Zrlw(W-D,Q), and Fi for LXi(Wi+q1-5i ), for brevity, N N N Z = 56Z/6qi -~ qi/6Q =,6Z/5qi /6qi Fi= /iFi /6qi i=l i=l il= il i=l Another application of the chain rule and the fact that &b/qj(5Fi/5qi) = 0 for i j, yields d2Z/dQ2 = 5 2Fi/qi2. Hence, from (21), d2Z/dQ2Z > 0, proving the theorem. i=l

I 18 In order to develop bounds on the system replenishment quantity and expected inventory cost, we consider a third allocation policy (ndc, dc for decentralized) in which retailer i is T+ hi leadtime away from outside supplier and replenishes its inventory independent of others (similar to the decentralized system of E&S or system I of Schwarz (1989)]. Note that this policy is identical, in a mathematical sense, to that in Section 3.1, with every occurrence of Xi replaced by Xi+T. All the observations made in regards to that policy, including simplicity, closedform, easy-computability, etc,. apply to this policy, as well. Theorem 4.2 below describes upper and lower bounds on the optimal replenishment quantity. Theorem 4.2 Given p > h(2m-l), * * * a. Q aa - < Q1m < Qridc. b. Q dc Qlaa AQ where AQ - Z- c (Ai++m) - E i i2 + T ai2 (23) _i= 1Liel iEl I Proof: See Appendix 1. Theorem 4.3 below describes lower and upper bounds on the optimal system cost. Theorem 4.3 Given p > h(m- ), a. LB E[Zi-(W-D,Q) ], UB, 1N [~2 where LB = lhm(m-l) pzi + [ q>aiV+ m +T. i2 (p+h) +(z) I i=l i=l and UB= -hm(m-l) pZi + t/i(ji+l+m)(p+h). (z) i=l i=l b. UB - LB = AC ii= riAi+'-la+m) _ |[ E CTi +T Goi2 * (p+h) (z). i -= 1 LiI ieI. Proof: See Appendix 2. 5. An Exact Expression for the Probability of the Allocation Assumption Holding, PA In this section, an exact expression for the probability of the allocation assumption holding is developed when a quantity Q is ordered at time t = 0 and allocated at t = T.

I 19 T Tthe Let R[], i 1,..., N be the increasing order statistics of R i,= 1,..., N. The probability that the T allocation assumption will hold at t = T, given Q, W and D, is the probability that each of the R[i] is brought up to R[N] by the available quantity Q. Since, it takes a quantity (R - Rj) crjJm+TTjto raise the normalized inventory of retailerj from Rj to R, PA = Pr Q > Fj R[N]] L Rj j4mi I Lj=i J j= I Pr{ Q at- }), (24) where a =~ j m+j, J = RjN], and = RUi] Ojvim+Tj. j=l j=l T From' (20), Rl] cGjimTj is distributed N(Wj - sj(T+m+Xj), T j2 ), so that P is distributed N r [Wj - pj (m+T+Xj)], T 2, say, H(.). Furthermore, from the theory of order statistics, a has the cdf j=l j=l ) i=N T G(x) n.i=l Gi(x) where Gi(x) is the cdf of Ri, i.e., Gi(x) N((Wj - j(T+m+kj)/Cj-mTij), (T/(m+Xj)). Therefore, from (24), PA = H(Q + at) dG(t) (25) - o Thus, PA can be computed using (25). The following observations relate to the E&S's measure of PA vis a vis ours. (1) E&S's PA applies to the penultimate period of the allocation cycle. Our measure applies to the instant when the allocations actually take place, i.e., at time t = T. This permits timely modification of the replenishment policy, in case PA is too low, (2) E&S's analytical expression provides a lower bound on PA while our measure provides the exact value, although, their measure can be computed readily by hand. However, their exact measure is estimated using simulation. (3) E&S's analytical lower bound is applicable to retailers Nwith identical demand means, standard deviations and shipment leadtimes across retailers. Our exact measure applies to systems with non-identical demand distributions and shipment leadtimes across retailers. Finally, (4) E&S's PA is based on a base-stock replenishment policy. Our measure of PA is valid for any arbitrary replenishment policy. 6. A Computationally Efficient Hybrid Distribution Policy To reduce the computational effort involved in computing the optimal policy while maintaining close proximity to optimality, we propose a heuristic procedure that is feasible/implementable for all inventory configurations. The heuristic, termed, "Hybrid" policy is implementationally simple: it uses the non-ranking algorithm (Page 12) to determine optimal allocations and the lower bound Q*n to determine the system

I 20 replenishments. The design of the computational experiments and findings are summarized next. Use of the allocation algorithm guarantees non-negative allocations. Experimental Design and Computational Results Tables Design Our investigation of the cost and robusiness-to-inventory-imbalance performance of the Hybrid heuristic is based on an extensive simulation of a total of sixty-eight system parameterizations. Tables 2 through 6, and Figures 1, 2a, and 2b contain the results of our simulation experiments. Columns 2-7 of each table contains the values of the system parameters (N, T, m, cr/p, b, and p/h), Columns 8 and 9 report respectively the base stock and the lower bound on expected inventory cost per cycle. These are theoretically computed for the given system parameters using Equations (11) and (12) respectively. Columns 10 reports the simulated expected system cost per cycle resulting from the use of Hybrid policy and Column 11 reports the simulated probability (relatively frequency) of the allocation assumption holding. Column 12 is simply the percentage deviation of the simulated heuristic cost with respect to the lower bound in Column 9. Simulation Experiment Desian: Parameters Generation First sixty parameterizations, indexed 1-60 in Table 2 were selected to study the effect of varying system uncertainty through variations in a/ti (coefficient of variation of retailer demands), inter-replenishment interval (m), number of retailers (N), warehouse-to-supplier's leadtime (T) and warehouse-to-retailer leadtimes (1, X2,..., AXN). Specifically, the c// was set at five levels [= 0.2, 0.4, 0.6, 0.8 and 1.0], m was set at two levels [= 2, 4], N was set at two levels [=5, 10], T was set at two levels [=2, 4] and the shipment leadtimes were also set at two levels. In the first set consisting of thirty systems, all Xj's were set equal to 2 (equivalently, X1 = 2. and sequential leadtimes = 0). As is readily apparent, this set simulates the "Depot" system of E&S. The second set of thirty systems, Xj's are set at 2, 3,..., N+l, which simulates retailers-on-a-delivery-route system of Kumar et al. (1995) (listed in Table 2 with KI = 2 and b = 1). All combinations of these levels were generated except those resulting from m < T, as they would violate the single-order in the warehouse-to-supplier pipeline assumption. This yielded the sixty parameterizations of Table 2. The parameter values are placed in columns 2-7. Table 3 contains the simulation results for lowvariance systems defined in this paper as those systems having c/p < 0.6. Table 4, in contrast, contains the simulation results for high-variance systems having 1.0 cr/p < 0.8. Table 5 reports results of extreme variations in p/h ratio 1000 > p/h > 200 (Systems 61-65). Table 6 contains the simulation results of systems (indexed 66-68) with extremely high variance (1.0 <c o/}i < 3.0) and is designed to evaluate the heuristic in a zone where not only the inventory imbalances are excessive, the normal distribution assumption itself breaks down. The simulations were carried out as follows: Each system was simulated to operate (allocate and replenish) in accordance with the Hybrid policy for 200,000 consecutive periods. The optimal replenishment quantity, Qja was determined using a stochastic optimization algorithm [Robbins and Monro (1951)] as modified in [Kesten (1958)]. Gradients were estimated in 1000 iterations, using forward finite difference with step size = 0.01, at each iteration. Discussion of Results Table 2: The most salient observation from this table is that the expected system inventory cost per cycle associated with the Hybrid policy registered a maximum percentage deviation of 0.778% with respect to the

I 21 analytical lower bound, LB, despite a significant variation in the parametric values. This is particularly noteworthy since 24 of the 60 systems included in Table 2 are high-variance systems (a/C > 0.8). It can be argued that the Hybrid policy is significantly robust with respect to the retailer-demand variance. Furthermore, in these sixty systems, the maximum probability of the violation of the allocation assumption (I - Column 11) is 0.4121. We conclude, based on these simulation tests, that the inventory imbalance is excessive enough to trigger the violation of the allocation assumption as many as 58.79 % of the 200,000 routes and yet the adverse cost impact of such violation on the system cost is negligible (maximum 0.778%). The impact of individual system parameters was studied in terms of the change in their respective average value. The results are placed in Figures 2a and 2b. Figure 2a contains the average value of the probability with which the allocation inassumption was violated (-P(A)) at two different levels of each parameter. Similarly, Figure 2b contains the average value of the percent deviation of the simulated cost with respect to the lower bound (%A) of the cost at two different levels of each parameter. The average values were computed by selecting systems such that these systems differed only in the level of that parameter. For instance, for j = 1,2,..., 30, system j and j 30 differ only in the value of N (N = 5 forj but N =10 forj+30). Therefore, average values of P(AA) and % were computed for systems I through 30 for N = 5 and 31-60 for N 10. Similarly, for comparing P(AA) and %A at two levels of b, systems j+1l through j+5 were considered forj = 0, 10, 20,...,50 (b = 0), and systems j+l through j+5 were considered forj = 5, 15, 25,..., 55 (b = 1). Then, the average values of 1-P(AA) and %A were computed for each of these two sets separately for comparison purposes. From Figure 2a, we notice that l-P(AA) increases as N increases, decreases as m increases, and remains relatively constant as T and b are increased. Looking at Figure 2b, we notice that the %A decreases with increases in N, T, m, and b, albeit at different rates. Indeed, decreases in %A for T as well as b are almost flat (less than 0.02%). Thus, the directions of change in Fig 2a and 2b are concomitant in three parameters - m, T, and b. However, 1 - P(AA) increases as N incerases but %A decreases as N increases. This is counterintuitive since we expected that the %A and 1-P(AA) will be positively correlated. There are three possible explanations: First, increase in N results in larger rate of increases in base stock compared to increases in b, m or T. This is not readily apparent in (1 1), but may follow from the concave part of the RHS of (12). Second, the %A is computed based on lower bound and not optimal cost, and third, despite very large sample size used here, this could wvell be an instance of sampling error. However, to the extent that these counterintuitive observations are subsumed in the larger picture in Figure 1 (explained later). we skip fuirther discussion on this point. It needs to be added, however, that these are not absolute trends, indeed, the impact of other parameters is confounded in each of these trends. Table 3 reports simulation results of the performance of the Hybrid heuristic for 36 low-variance systems. To no surprise of ours, we found that the worst %A was 0.146% and the average %A was only 0.046%. Correspondingly, the average P(AA) was 0.9916 with the lowest value at 0.9093. It is safe to assume that for systems with cs/t c 0.6, the heuristic is remarkably close to the optimal value. Table 4, on the other hand, reports simulation results of the performance of the Hybrid heuristic for 24 high-variance systems. For such systems, we see that the worst %A was 0.778% and vet the average %A was only 0.160%. Correspondingly, the average P(AA) was 0.8364 with the lowest value at 0.4121. As expected, there is a greater departure in these high-variance systems from the optimality as reflected in higher average and maximum values of the %A and lower P(AA)s. Noticeably however, the cost performance of the heuristic is within 0.778%, notwithstanding a significantly low P(AA) of 0.4121 for at elast one system. It can be concluded that even for highvariance systems, the Hybrid heuristic's cost performance is excellent.

I 22 Table 5, tests the cost efficacy of the heuristic under a wide variation of p/h ratio (200 < p/h < 1000). We see that the P(AA) is almost insensitive to the variations in p/h, staying put at about 0.789. Despite the low P(AA), however, the worst case %A is only 0.12%, with an average of 0.092%. Combing the results of Tables 2 through 5, it can be concluded with reasonable confidence that the cost perfonnance of the Hybrid heuristic is very close to optimal within a wide-ranging variation of the system parameterizations. Thus, we conclude, within the simulation error, that the hybrid heuristic, with its dual benefit of neamess-to-optimality and speed-of-computations, presents an excellent choice for inventory managers to employ for the determination of the replenishment quantity and the allocations in muti-echelon distribution systems. Figure 1 shows the relative movement in the coefficient of variation (c/.), Probability of violation of the allocation Assumption (l-P(AA), and the percent deviation %A for the sixty system parameterizations of Table 2. In order to make the charts comparable, the data in Table 2 was modified as follows: First, all data was sorted in increasing ratios of cT/p increasing values of (l-P(AA) (second key), and increasing values of %A (third key). Furthermore, each of these data was normalized by multiplying the numbers by I/maximum value in their respective column, so that all values are normalized on a 0-1 scale. The chart shows how these three values change as we move from systems 1-60 (newly indexed. The l-P(AA) is virtually unchanged at zero until ao/l reaches the value of 0.6. Beyond this value of a/a, however, there is a significant chance in the rate of increase in the values of -p(AA) as well as ell as %A This shows that at about /l = 0.6, the increases provided by Equation ( 1) in the order quantity begin to lag behind those required for averting the inventory imbalance during allocation process. The result is a sharply rising l-P(AA) and %A. Fortunately, and remarkably, the increases in %A are still below 0.78%, making it very attractive for use by inventory managers. Table 6 reports results of simulation of some system parameterizations having extremely high demand variances, i.e., the a/i ratio is varied (1.0 < Cr/L < 3.0) way beyond that allowed realistically by the Normaldistribution-of-demand assumption. To see the absurdity of this range, just note that when a/p is 2.0, the probability of a negative demand is 30.85%. and when a/p is 3.0, the probability of a negative demand is 37.07%.! Despite such pathological extremes in variance, the Hybrid heuristic registered a respectable value of %A - 4.26% at c/pk = 2.0 and 11.65% at c7/p = 3.0. Notice that at such severe conditions of variance, the P(AA) was as low as - 034 and.005, indicating pathological levels of inventory imbalance. To sum up the findings of this section, the performance of the Hybrid policy specifically with respect to the high-variance systems (a/u > 0.8) is intriguing. In terms of Zipkin (1984)'s remarks: "... and the current results suggest that imbalance can be significant, even using myopic allocations, when variances are large," our computational results support the observation (as reflected in the sharply rising values of 1-P(AA) in Figure 1. However, our empirical results go a step further and demonstrate that the impact of this deteriorating value of the probability of the allocation assumption holding is minimal on the system costs. Some possible reasons for this cost-insensitivity of the inventory-imbalance are the following: (I) the mechanism of determining myopic allocations using policy F works towards minimizing the imbalance betwveen the lag-adjusted normalized inventories, and, therefore, towards minimizing system cost in the subsequent period, (2) Systems with large demand uncertainties also have larger optimal system base-stock which allows a better shot at balancing normnalized inventories across retailers. and finally, (3) the structure of the replenishment policy helps minimize the effect of varying p and h. For example, when p is increased (decreased), the replenishment quantity increases (decreases) and, therefore, the expected system shortages decrease (increase). Thus, the total shortage cost does not change

I 23 proportional to the change in p. A similar argument can be extended to variations in h. It is perhaps this "dampening" of the effect of changes in p and h on system cost that limits the change in total system cost. 7. Conclusion Periodic replenishment and allocation of a critical resource is a common problem encountered in numerous managerial and defense disciplines. Methodologies that have thus far appeared in the inventory/finance/marketing/military literature have employed approximate methods to determine the optimal allocations and replenishments. Typically a simplifying assumption, called the allocation assumption is used to obtain the policies. In this work, we develop general allocation and replenishment policies using the context of inventory distribution systems that are independent of the allocation assumption. Such policies are critically needed since the policies contingent upon the validity of allocation assumption are unimplementable, specifically for systems with large uncertainties in the consumption rates. In order to mitigate the computational effort involved in the determination of the optimal replenishment policy, a hybrid distribution policy is also proposed. Computational experiments conducted on a number of system parameterizations encompassing a wide range of parameters indicate that such a policy is managerially very attractive due to its simplicity, quick computability and close proximity to the optimal distribution policy in terms of the cost performance.

I 24 REFERENCES Arrow, K., J., Karlin, S. and Scarf, H. (1958), Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, Stanford California. Bitran, G.R., and Gilbert S.M., (1996), "Managing Hotel Reservations With Uncertain Arrivals," Operations Research, Vol. 44, No. 1, p. 35-49. Christofides, N., (1971), "Fixed Routes and Areas of Delivery, "International Journal of Physical Distribution, Vol. 1, p. 87-92. Clark, A. and Scarf, H. (1960), "Optimal Policies for a Multi-Echelon Inventory Problem", Management Science, Vol. 6, No.4, p. 475-490. Clark C., and Wright, J.W., (1964), "Scheduling of Vehicles from a Central Depot to a Number of Delivery Routes," Operations Research, Vol. 12, p. 569-581. Dror, M., Laporte, G., and Trudeau, (1989), "Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks," Transportation Science, Vol. 23, p. 166-176. Eppen, G.D. (1979), "Note-Effects of Centralization on Expected Costs in a Multi-Location Newsboy Problem", Management Science, Vol. 25, No. 5, p. 498-501. Eppen, G.D. and Schrage, L. (1981), "Centralized Ordering Policies in a Multi-Warehouse System with Lead Times and Random Demands", in Multi-Level Production/ Inventory Control Systems: Theory and Practice, p. 163-193, Edited by Leroy B. Schwarz. North-Holland, Amsterdam. Erkip, N., Hausman, W.H., Nahmias, S., (1990), "Optimal Centralized Ordering Policies in Multi-Echelon Inventory Systems with Correlated Demands," Management Science, Vol. 36, No. 3, p. 381-392. Federgruen, A. and Zipkin, P. (1984a), "Approximations of Dynamic Multilocation Production and Inventory Problems", Management Science, Vol.30, No. 1, p. 69-84. Federgruen, A. and Zipkin, P. (1984b), "Allocation Policies and Cost Approximations for Multilocation Inventory Systems", Naval Research Logistics Quarterly,. Vol.31, p 97-129. Graves, S.C., (1996), "A Multiechelon Inventory Model with Fixed Replenishment intervals," Management Science, Vol.42, NO. 1,p. 1-18. Jackson, P.L., and Muckstadt, J.A., (1989)"Risk Pooling in a Two-Period, Two-Echelon Inventory Stocking and Allocation Problem, Naval Research Logistics Quarterly, Vol. 36, p. 1-26. Jonsson, H. and Silver, E.A. (1987a), "Analysis of a Two-Echelon Inventory Control System with Complete Redistribution", Management Science, Vol. 33, No. 2, p 215-227. Jonsson, H. and Silver, E.A. (1987b), "Stock Allocation Among a Central Warehouse and Identical Regional Warehouses in a Particular Push Inventory Control System," International. J of Production Research, Vol. 25, No. 2, p 191-205. Kesten, H., (1958), "Accelerated Stochastic Approximation," Annals of Mathematical Statistics, Vol. 29, p. 41-59. Kumar A. (1992), "Ranking and Non-Ranking Allocation Algorithms for a Multi-Echelon Inventory System With Service-Level and Storage Constraints," Working Paper, Weatherhead School of Management, Case \Western Reserve University, Cleveland, Ohio. Kumar A., Schwarz. L. B. and Ward J. E. (1995), "Risk-Pooling Along a Fixed Delivery Route Using Dynamic Inventory Allocation Policy," Management Science, Vol. 41, No. 2, p. 344-362. Luss H., and Gupta, S., (1975) "Allocation of Effort Resources Among Competing Activities," Operations Research, Vol. 23, p. 360-366 _ McGavin, E., L.B3. Schwarz, and J.E. Ward. (1993)" Two-Interval Inventory Allocation Policies in a OneWarehouse N-ldentical-Retailer Distribution System," Management Science, Vol. 39, No. 9, p, 1092-1107. Robbins H., and Monro, S. (1951), "A Stochastic Approximation Method," Annals of Mathematical Statistics, Vol. 22, p. 400-407. Schneider, H. (1981), "Effect of Service Levels on Order-Points or Order-Levels in Inventory Models," Int. J of Prod. Research. Vol. 19, No. 6, p. 615-63 1. Schwarz, Leroy B. (1I 98 1), Ed., Multi-Level Production/Inventory Control Systems: Theory and Practice, NorthHolland Publishing Company, Amsterdam.

25 Schwarz, L. B. (1989), "A Model for Assessing the Value of Warehouse Risk-Pooling: Risk-Pooling over Outside Supplier Leadtimes", Management Science, Vol. 35, No. 7, p. 828-842. Simpson, K. G. (1959), "A Theory of Allocation Stocks to Warehouses", Operations Research, Vol. 7, No. 6, p. 797-805. Stewart W., and Golden, B., (1983), "Stochastic Vehicle Routing: A Comprehensive Approach," European Journal of Operations Research, Vol. 14, p. 371-385. Unknown (1994), A Manuscript Submitted for Review for a Possible Publication in the Journal of Business Logistics. Zipkin, P. (1980), "Simple Allocation Methods for Allocation of One Resource," Management Science, Vol. 26, No. 1, p. 34-43. Zipkin, P. (1982), "Exact and Approximate Costs Functions for Product Aggregates", Management Science, Vol. 28, No. 9, p. 1002-1012. Zipkin, P. (1984), "On the Imbalance of Inventories in Multi-Echelon Systems", Mathematics of Operations Research, Vol. 9, No. 3, p. 402-423.

I 26 Appendix 1 Proof of Theorem 4.2 First, let us prove some intermediate results that will be needed. Define two allocation problems at t = T: (1)AP(Haa): ZJaa (W-D Q) min E [Li(Wi+qi- i s.t. (2) i=l (2) AP(II ): ZnI(W-D,Q) min E [L(Wi +qi- 6 ) s.t. (2) and (3). i=l Lemma 1 Z aa(W -D,Q) < Zni(W-D,Q) with probability 1.0. Proof: Follows from the fact that AP(Haa) is a relaxation of AP(Hrg )for any realization D. Lemma 2 E[Z1 (W -D,Q) ] E[Zun(W-D,Q) ] for all Q, where expectation is over the demand vector D. Proof: Follows from Lemma 1. Lemma 3 Zi,(W,Q) is convex in Q for arbitrary W. Proof: Follows from Theorem 4.1 We now prove part (i) of Theorem 4.2. First note that for any given W and D, and for all Q > Q [ R[N - R[i]] cj TTm j, either policy (1aa or Hai ) will yield the same optimal allocations. Hence, at Q, J=1 E[ZnI (W -D, Q)] = E[Zni (W-D, Q)] (Al-l) d d and E[Z[naW -D, Q ) =E QE[Znr(W-D, Q) ] (Al-2) I=Q IQ=Q * * Hence, to show QHaa < Qn, it is sufficient to show (see figure A -I), d E[Z (- Q) E[Z] for all Q Qi.e, iQ) is sE[Zii(-D Q for all Q,t i.e., it is sufficient to show that

I 27 d [ZIn (W -D,Q)] > Q [ZIn(W-DQ) ] for all Q with probability 1.0. or, equivalently, to show d 3 Q[Zrla(W,Q)] ~ > [Zjla(W,Q) ] for any W. Ui a U 1 - (A 1-3) Expected Cost I Q Q Q aa '~aa _, 1 Replenishment Quantity Figure A 1-1 We prove (Al-3) for the case of two retailers. The general case follows from the property of the optimal allocations described in Section 3. Consider a system of two retailers, i = 1 and 2 with unequal net-inventories Wi, i =1,2. To ascertain the validity of (Al-3), the difference Q = d/dQ[Zr (W,Q)] - d/dQ[Znr(W,Q) ] needs to be evaluated. Assume retailer 2's net-inventory is sufficiently in excess of retailer l's net-inventory so that Q+AQ is not sufficient to equalize the derivatives in (A1-5). For, if it is not so, Q = 0 and equality holds in (Al-3). Now, under the allocation policy Iaa, [Za (W,Q+AQ)] - [Zn(w,Q)] = Li(Wi+qI+Aq ) +L2(W2+q2+Aq2) - Li(Wj+ql) - L2(W2+q2) (A 1-4) where ql+Aql and q2+Aq2 are optimal allocations from Q+AQ and ql and q2 are optimal allocations from Q, under policy Iaa and satisfy (A 1-5) through (A 1-8) below. dLl(x) x x=Wl+q1+Aql -dL2(x) x x = W2+q2+Aq2 (Al-5)

I 28 ql+Aql+ q2+fAql = Q+AQ (A 1-6) dLI(x) dL2(x) -dx - Id W (Al-7) dI 'x = W +q I x = W2+q2 ql +q2 = Q (AI-8) Now, for Aql, Aq2 sufficiently small, the RHS of (A 1-4) can be written as 5 L 1(W +q 1)/q I Aq + 5 L2(W2+q2)/5q2) Aq2 5 L1(WI+q1)/8ql ) (Aq + Aq2) from (A -7). LI (Wl+ql)/5ql) AQ (AI-9) Letting AQ -+ O and Aq 1]- 0, (A 1-4) and (A l-9) yield d - d Qf [Zrlaa(W,Q)] = aql(Wl+q l) (AO-10) However, when allocations are made in accordance with tIh, the entire quantity Q or Q+AQ will be allocated to retailer I since Q is not enough to equalize retailer 1's derivative of the cost function to that of retailer 2. Therefore, [ZnM(W,Q++AQ) ] - [Z ( ) = L(WI+Q +AQ) - LI(WI+Q). (Al-I 1) In the limit, AQ -+ 0, (Al-l 1) reduces to d d TQ [ZnM(W,Q) ] =QL (W +Q), (A1-12) As L1(.) is a convex function and Q < ql (this inequality is critical since allocation to retailer I under policy Ill is the entire Q plus some quantity from retailer 2 to equalize the derivatives.), dL(Wi+Q) dL1(Wl+ql) d- - <- dq ---. Therefore, from (Al-10) and (Al-12) d/dQ[Znra(W,Q)] > d/dQ [ZIT(W,Q) ] (Al13) * * But this is the required condition in (Al-3) for Qnaa< QnI aa- - aa* To show the second inequality, simply note that the third policy (dc) has no opportunity for risk-pooling at t = T whereas the optimal policy derived here, does. Therefore, it must be the case that Q < Qndc * * Part b follows from the fact that AQ = Qdc - Qnaa and by substituting appropriate expressions as in (11) and (13), with Xi replaced by for Xi+T.

I 29 Appendix 2 Proof of Theorem 4.3, Part a We have, E[Zaa(W -D, QrIaa )] E[Znaa(W-D, Qn ) by the definition of E[Zaa(W -D, Qnaa ] * $ and E[Z aa(W-D, Qn ) ] < E[ZI (W-D, QI) ] from Lemma 2 in Appendix I. * * Hence, LB = E[Zn (W -D, Qnaa )] < E[Zn1 (W-D, Qna) ] Furthermore, note that UB = E[Zn- (W-D, QIja)] is the expected cost associated with the distribution policy dc which has no opportunity for risk-pooling. Therefore, it must be that UB > E[Zn- (W-D, QInQa ] * Proof of Part b N Follows from (12), LB = K + 1/2 hm (m-l) E i + aS (p+h) * (z), i=l and from (9), UB = K + 1/2 hm (m-I) > Ai + cai (m+Xi+T) (p+h) 4 (z), and the result follows. = i=l

Table 1: Comparison of Selected Models and Allocation Analyses Legend: Arb = Arbitrary, Non-Id (Idntcl) = Non-identical (identical) across retailers I r E&S I I Zipkin (1984) 1 F&Z (1984a) F&Z (1984b) - 1r J&S (1987b) I J&M (1989) Erkip Et al. (1990) F McGavin cL al. Tllis Paper (1981) (1993) L Number of Retailers Arb ArbAr b b Arb ) Arb Ar b A rb.inulber of Periods in Horizon Infinite Finite Finie Infinite 2 2 Infinite2 Infilitw Unit Holding & Shortage Costs Idntcl Idntcl Non-id Non-id - Idntel Idntcl - [Idntcl Fixed Order Cost' > 0 0 0 0 0 0 0 0 0z Order Lead-time:0 0 ~0 0 0 0 0 0 > 0 Shipment lead-times Idntcl,~0 0 Idntcl,>0 Jdntc],> 0 Idntcl,>0 Idntcl,>0 ldntcl,>0 Ildnlcl, 0 Retailer Demand Distribution Normal Normal Normal Nor General Normal Normal Generar l Normal Retailer Demand Correlated? No yes No No No Yes Yes No No Demand Parameters* Yes Yes No Yes Yes Yes Yes Yes No Constrained? equal /la equal NIlc| equal I, equal p/c equal ullo equal loa equal pl/c _ Nature ofAllocations Myopic Myopic Myopic Myopic Myopic Myopic Myopic Myopic Myopic Allocation Assumption Used? Yes No Yes Yes No No Yes No No Accounting for Imbalance of Approxi- Approxi- None None Approxi- Approxi- None Approxi- Exact Inventory in System Cost Function mate mate mate mate Inate Modeling Permits Delivery Routes? No No No No No No No No Yes System Objective (Minimize) Cost Cost Cost Cost [nitial stoc Cost Cost Lost sales Cost.............~~~ ILI.-. I. _II__

I T;ble 2: Sensitivity of the An;I.l ix. if the Perrormancv of thr I1> hrill I leurirtic fKrJA 1.0- I I 0 l. X 2, h 1)..* '.:.*. -c:- i~i.::.R6L3,:r.*.|: -.q.e.t' 9.0 t ':. —.... s tjwnl.. xrd nOmrderrct. fProabl.. N'Wcm t jid —....:...' i.:.d;: ~.i.-o.k.) i k:.~::-.: ';Sa w.i"..~.);-.:... '::-'-,;'N.'p.To. ut w.th url.. ist.b A umikim(,.-.( y:.:.'..:.T:..'.. "..:::...... '.... %Ai:. 1 5. $ ~~~~~~~~2 ~~~2 0.2 0 20.0 327.46 124..59 124. 6 1.0000 0.024 ~2 ~~5 ~ 2 2 04 0 20.0 354.92 ' '1 8. 199.3 ' 0.9990 0.085..:Crni..R~ti1 ____,__ _______ 3 5 2 2 0.6 0 20.0 32 3. 2"_3 _-_73.5 _ 0.955 0.029 4 5 2 2 0.8 0 20.0 409..9 3448.36 349.22 0.813' 0.247 5 5 $ ~2 2 1.0 0 20.0 437.31 422.95 426.24 0.6393 0.778H 6 5 2 2 0.2 1 202.0 432.90 139.3 139.48 1.0000 0.090 7 5 2 2 0.4 1 20.0 465.79 22.71 22.7 0.9939 0.000 9 S " 2 2 0.6 1 20.0 498.6)9 31~06 31n. 53 09549 0.146 9 5 2 2 0.8 1 20.0 531.59 407.42 40. 15 0.8117 0.179 10 t 21.0 20.0 564.49 496.77' 499.64 0.6371 0.577 11 5 2 4 0.2 0 40.0 432.78 4-8.-7 47x.99 1.0000 0.046 12 5 2 4 0.4 0 40.0 465.55 657.54 65.14 1.0000 0.091 13 5 2 4 0.6 0 40.0 49X-33 H36.32 837.00 0.9977 0.082 14 5 2 4 0.8 0 40.0 531.10 1015.09 1016.28 0.9698 0.118 15 5 2 4 1.0 0 40.0 563.8 1193.86 1195.10 0.8899 0.104 16 5 2 4 0.2 1- 40.0 537.41 504.03 504.41 1.0000 0o075 17 5 2 4 0.4 1 40.0 574.81 708.07 70S. 17 1.0000 0.014 18 5 2 4 0.6 1 40.0 612.22 912.10 912.95 0.9978 0.093 19 5 2 4 0.8 1 40.0 649.63 1i16.14 1116.13 0.9690 0.000 20 5 2 4 1.0 I 40.0 687.04 1320.1'7 1321.40 0.900 0.093 21 5 4 4 0.2 0 40.0 533.7 4S4.27 484.37 1.0000 0.020 22 5 4 4 0.4 0 40.0 567.57 668.55 668.87 1.0000 0.048 23 5 4 4 0.6 0 40.0 601.35 852.82 853.59 0.9977 0.090 24 5 4 4 0.8 0 40.0 635.14 1037.09 1037.69 0.9697 0.057 25 5 4 4 1.0 0 40.0 668.92 1221.37 1222.28 0.8848 0.075 26 5 4 4 0.2 1 40. 638.29 508.' 509.02 1.0000 0.029 27 5 4 4 0.4 1 40.0 676.59 717.74 71t.05 1.0000 0.043 28 5 4 4 0.6 1 40.0 714.88 926.6 927.0 0.9978 0.050 29 5 4 4 0.8 40,0 753.19 1135.49 1136.3 0.9685 0.079 30 5 4 4 1.0 1 40.0 729.48 1344.36 1344.7. 0.8851 0.031 31 -10 2 2 0.2 0 20.0 653.66 245.7 245.76 1.0000 0.004 32 10 2 2 0.4 0 20.0 707.32 391.g0 391.71 0.9978 0.054 33 10 2 2 0.6 0 20.0 760.9H $37.25 537,74 0.9109 0.091 34 10 2 2 0.8 0 20.0 814.64 683,00 64.55 0.6655 0.227 35 10 2 2 1.0 0 20.0 68.30 2."5 H30.74 0.4148 0.240 36..10 2 2 0.2 1 20.1)0 1126. " 306.63 306.65 10000 0.006 3" 10 2 2 0.4 1 20.0 1202.15 513.26 513.30 0.99'8 0.007 3, 10 2 2 0.6 1 20.0 12". 22 "'19.90 '20.09 0.9093 0.027 39 1I) 2 2 0.8 1 20.0 1354.30 ) 926.53. 292..2 0.6626 0.247 40 10 2 2 1.0 1 40.0 1531.3" 1133.16 1137.90 0.4121 0.418 41 10 2 4 0.2 0 40.0 964.52 951.91 952.16 1.0000 0.026 42 10 2 4 0.4 0 40.0 929.U4 1303.83 1304.32 1.0000 0.038 43 10 2 4 0.6 0 40.0 993.5t, 1655.74 1656.19 0.9959 0.027 44 10 2 4 0. 0 40.0 105H.O8 200".65 200.01 0.933 0.018 45 10 2 4 1.0 0 40.0 1122.60 2359.56 2363.94 0.7930 0.181 46 10 2 4 0.2 t 40.0 1333.95 10o7.8s" 105..65 1. 000 0.074 47 10 2 4 0.4 I 40.0 1417.89 1515.4 " 151652 1.0000 0.051 4. 10 2 4 0.6 1 40.0 1i01.84 197'3.62 1974. "9 0.9957" 0.059 49 10 2 4 0,. 1 40.0 1585.78 2431.49 2433.29 0.9382 0.074 50 0 t 2 4 1.0 1 40.0 1669.73 28,9.36 2.890... 0.791 0 0.053 51 10 4 4~ 0.2 0 40.0 1065. 5 95-.54 95 "7. 55 1.0000o 001 52 10 4 4 0.4 0 40 0 1131.10 1315.09) 1315.10 1.0000 0.001 53 10 4 4 0.6 0 40.0 119665 16t2.63 1673.1. 0.9960 0.033 54 10 4.4 0.8 0 40.0 1262.21 2030.1- 2031.34 0.9390 0.057 55 1 0 4 4 1.0 0 40,0 1327.76 238'.-2 239) 1.9 ' 0.'899 0.162 56 10 4 4 0.2 1 40.0 1534.74 1062.21 1 ) 62.39 1.000 0.017 57 10 4 4 0.4 1 40.0 1619.48 1524.43 1 v25.1(1 1.0000 0.044 ~598~11 4 4 0.6 1 4i.) 1704.22 1]96.44 19.26 0.)960 0.031 59 10 4 4 0.8 1 40.0 1788.99 244.8c, 2449 ' 0.93"4 0.046 60 1!0... 4 4 1.0 1 40.01 I-.3.-l 211 - 2 '.2 n T 0.7 9 0.055 I _r.ra._c 1 0.91 83..:j:i: - _r -t _. I. -.tH.,,- - t..- Ulu n- - LOOOO - I _

I Table 3: Simulated Evaluation of the Performance of the Hybrid Heuristic for Low/Medium Variance Systems (c/p < 0.6, I = 10,. = 2, h = 1) P,,.r::. ';::.': "Ou': tsidc R:epi:.c+i" Re.ier...:Sequ"ntI. ' Ut..:: '. it.::..:ob ii:.: Exp'cfed:: S.nioatel.PUroblA"ityUf:Prc&itTc Ietinri Nl!wkber 14p1 jj ^s:^* Inler Sh1^ ^ rtag O^rde Opptial] Expetctd. orAlloc. *vifiaioa..1...10~...4...1 0.0':..40. 1065.5 957.1 957.5:.::'':.1.0000 " ',[:i:::0.001.. ':.:..::'.'':::::.'.::::........ "':~...... '" 'i0........ 4........... I I 0 4 4 0.2 0 0 1065.55 957.541 957.55 1.0000 o.00l 2 10 2 2 0.2 0 20 653.66 245.75 245.76 1.0000 0.004 3 10 2 0.2 1 20 1126.07 306.63 306.65 1.0000 0.006 4 10 4 4 0.2 1 40 1534.74 1062.21 1062.39 1.0000 0.017 5 5 4 4 0.2 0 40 533.78 484.27 484.37 1.0000 0.020 6 s 2 2 0.2 0 20 327.46 124.59 124.62 1.0000 0.024 7 10 2 4 0.2 0 40 864.52 951.91 952.16 1.0000 0.026 8 54 4 0.2 1 40 638.29 508.87 509.02 1.0000 0.029 9 5 2 4 0.2 0 40 432.78 478.77 478.99 1.0000 0.046 10 10 24 0.2 1 40 1333.95 1057.87 1058.65 1.0000 0.074 11 5 24 0.2 1 40 537.41 504.03 504.41 1.0000 0.075 12 5 2 2 0.2 1 20 432.90 139.35 139.48 1.0000 0.090 13 5 0.4 1 20 465.79 228.71 228.71 0.9989 0.000 14 10 4 4 0.4 0 40 1131.10 1315.09 1315.10 1.0000 0.001 15 10 2 2 0.4 1 20 1202.15 513.26 513.30 0.9978 0.007 16 5 2 4 0.4 1 40 574.81 708.07 708.17 1.0000 0.014 17 10 2 4 0.4 0 40 929.04 1303.83 1304.32 1.0000 0.038 18 5 4 4 0.4 1 40 676.59 717.74 718.05 1.0000 0.043 19 10 4 4 0.4 1 40 1619.48 1524.43 1525.10 1.0000 0.044 20 5 4 4 0.4 0 40 567.57 668.55 668.87 1.0000 0.048 21 10 24 0.4 1 40 1417.89 1515.74 1516.52 1.0000 0.051 22 10 2 2 0.4 0 20 707.32 391.50 391.71 0.9978 0.054 23 52 2 0.4 0 20 354.92 199.18 199.35 0.9990 0.085 24 52 4 0.4 0 40 465.55 657.54 658.14 1.0000 0.091 25 10 2 20.6 1 20 1278.22 719.90 720,09 0.9093 0.027 26 10 24 0.6 0 40 993.56 1655.74 1656.19 0.9959 0,027 27 2 2 0.6 0 20 382.38 273.77 273.85 0.9555 0.029 28 10 4 4 0.6 1 40 1704.22 1986.64 1987.26 0.9960 0.031 29 10 4 4 0.6 0 40 1196.65 1672.63 1673.18 0.9960 0.033 30 5 4 4 0.6 1 40 714.88 926.61 927.08 0.9978 0.050 31 10 2 4 0.6 1 40 1501.84 1973.62 1974.79 0.9957 0.059 32 2 4 0.6 0 40 498.33 836.32 837.00 0.9977 0.082 33 5 4 4 0.6 0 40 601.35 852.82 853.59 0.9977 0.090 34 10 2 2 0.6 0 20 760.98 537.25 537.74 0.9109 0.091 35 5 2 4 (.6 1 40 612.22 912.10 912.95 0.9978 0.093 36 5 2 2 0.6 1 20 498.69 318.06 318.53 0.9549 0.146 - - I - l I- - -...Il I.... I: m. I\::Axir'a'j. I' - '::L ' '::0.464 \:......146'.,s I

I Table 4: Simulated Evaluation of the Performance of the Hybrid Heuristic for High Variance Systems (o/J >0.6,11 = 10,. = 2, h = I) *~ er^^^kS^II'^ ^^: *Y~i1^^ ^"^ ** r:'iii Deag4 I': er^;;:}pftlmul Eipecfeca..o[ 4Iloc,^ dcviaj3Qbn'l:i-.::AG Oi *... ',j _ _ -: ',,i, I i:!!.?..i~:'i,,,,,,i!:,~i: i':'''..~::: ~.....:,.........::.:Z'.-:..,...:..1:. 37 5 2 4 08 1 40 649.63 1116.14 1116.13 0.9690 0.000 - n III I I I — l -. — -ll[ - -lI 38 10 24 0.8 0 40 1058.08 2007.65 2008.01 0.9383 0.018 39 10 4 4 0.8 1 40 1788.97 2448.86 2449.97 0.9374 0.046 40 5 4 4 0.8 0 40 635.14 1037.09 1037.69 0.9697 0.057 41 10 4 4 0.8 0 40 1262.21 2030.17 2031.34 0.9390 0.057 42 10 2 4 0.8 1 40 1585.78 2431.49 2433.28 0.9382 0.074 43 5 4 4 0.8 1 40. 753.18 1135.49 1136.38 0.9685 0.079 44 5 2 4 0.8 0 40 531.10 1015.09 1016.28 0.9698 0.118 45 5 2 2 0.8 1 20 531.59 407.42 408.15 0.8117 0.179 46 10 2 2 0.8 0 20 814.64 683.00 684.55 0.6655 0.227 47 5 2 2 0.8 0 20 409.85 348.36 349.22 0.8137 0.247 48 10 2 2 0.8 1 20 1354.30 926.53 928.82 0.6626 0.247 49 5 4 4 1.0 1 40 729.48 1344.36 1344.78 0.8851 0.031 50 10 2 4 1.0 I 40 1669.73 2889.36 2890.88 0.7917 0.053 51 10 4 4 1.0 1 40 1873.71 2911.07 2912.68 0.7879 0.055 52 5 4 4 1.0 0 40 668.92 1221.37 1222.28 0.8848 0.075 53 5 2 4 1.0 1 40 687.04 1320.17 1321.40 0.8900 0.093 54 5 24 1.0 0 40 563.88 1193.86 1195.10 0.8899 0.104 55 10 4 4 1.0 0 40 1327.76 2387.72 2391.58 0.7899 0.162 56 10 24 1.0 0 40 1122.60 2359.56 2363.84 0.7930 0.181 57 10 2 2 1.0 1 40 1531.37 1133.16 1137.90 0.4121 0.418 58 5 2 2 1.0 20 564.49 496.77 499.64 0.6371 0.577 59 5 2 2 1.0 0 20 437.31 422.95 426.24 0.6393 0.778 60 10 2 2 1.0 0 20 868.30 828.75 830.74 0.4 4148 0.240 57~~~~~!iii,_ I, I i 1 =_3.3 I~3,6 i...... ii.......I _ I _1 I r **r^ gf i-.$S83 64:.. ':n: ':... I L-,... J:...:: '., - 'U -.:.. v I 0 0.:.

Table 5: Simulated Evaluation of the Performance of the Hybrid leuristic for High p/h Ratios (m = 10,1= 2, h = 0.1) ___ _ _______ _.. ~..-. i...._ __ ____.;:. "::-". 't.::.."-.- - '. '.. -.- *,** N- 1,.-,.,*: '.. /;'.,,^ j t,..:........-..- 1;*:NW~~~.... ''::''..N.. Tcdh-"'.'-::-'... 1:-.~: '':.i:.i-:.:.-:: i:: "~s 'j ~::: ~'i':A. 61 10() 4 4 1.0 1 100(.0 2024.06 342.35 342.743 01.789.114 (61 62 10 4 4 1.0 i 80.0 1989.90 330.52 '330.914 0.78)9 ().1 20 62 63 10 4 4 1.0 1 60.0 1943.70 314.68 314.857 0.788 0.057 63 f e ye"I".. A........ I l l I ~ ~ ll ~ II II ~ 64 10 4 4 1.0 1 40.0 1873.71 291.11 291.268 0.788 (.1055 64 65 10 4 4 1.0 1 20.0 1736.54 246.66 246.936 0.789 0.113 65 -f a ' a6 -v'' a:':i a~ J' aR -g a ai - ----------..a-....aa Table 6: Simulated Evaluation of the Performance of the Hybrid Heuristic for Extremely High Var iance Systems...... -~ ~p!C~i ~ ~...L (/L.> 1.0, L. =10, 2, h = 1) tlilfi:: ~ -' B:.:i;~i:... —:-:.'- '. ' ', 6zt1nr 41: {Shk4nivnt) 4(0 yr 1 Ijw20Cr0 342l35 tkudst3 A'supti9 ( t1j114: 61 Index ~IE ller; Ldatime1 Timc-I Ddadoen l^eaddmc (cio > iQua nIII ildin iiii Co1sl idig I I1t i ' 67 10 2 2 2.0 1 4.0 1197.22 1222.5 1274.556 0.[134 4.25$ 67 68 10 2 2 3.0 1 4.0 1270.83 1783.75 1991.489 0o.o05 11.646 6 a. -. _ - _ _ ____ a a_ a a a a _ __.-.._ = _._ w.. = = = __.. = w.,,.,,, _. _ r..,I..... 68 10 2 2 3.0 1 4.0 1270.83 1783.75 1991.489 0.005 11.646 68~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'~-~1: -:.:~::~r..::. ~~r~L:~ '..i:.t*i'.- I I:^.I 1.:'.:.5i.3.. ~~ ~;~ r~AA...r.,...0...... -.. -- - - - - - - -,- -

Figure 1: Inter-relationships Between the Probabiltiy of Violation of Allocation Assumption, Coefficient of Variation of Demand, and Percent Deviation of Expected Cost With Lower Bound 1.0000 -|-Normalized Probability of Violation of 0.9000 Allocation Assumption - Percent Deviation of Simulated Cost from o.xooo the Lower Bound A 1 A i | —' Coefficient of Variation of System Demand 0.7000 0.6000, 0.5000 0.4000 0.3000 0,2000 0. 1000 O.0000 r ----T — r-.r-T — * -_ System Index -0.J

I Figure 2a: Impact of System Parameters Change on the Probability of Violation of the Allocation Assumption 0.0591 0.1043 0.0416 0.0425 0,1609 0.0416 0.0814 0.0820 Impact of No. of Retailers on the Impact of Supplier's Leadtime on Probability of the Violation of the Probability of the Violation of the Allocapton Assumption the Allocation Assumption 0.2000 -..............2 -:::!wi^ii,:i;:!;i 0.05 000.14 0046 0.0000.0 0.84j002 N=5 N=10 T=2 T=4 Impact of Order Cycle Time on Impact of Shipment Leadtime on the Probability of the Violation of the Probability of the Violation of the Allocation Assumption the Allocation Assumption 0.2000 -. '...........'...'0.2'*............::.....:. 0.10000 O.1000,'"':v:'''.::;'.: ' ':' 0.0500 0=0500 I-='' b=S bO'0 05 o.0oooo 000. OO.0. 000 m=2 m=4 b=0 b=1 U U, II.;I M