HOW MUCH TO STOCK TO MEET A STREAM OF DEMANDS Medini R. Singh Juhwen Hwang Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 93-12 March 1993

How Much to Stock to Meet a Stream of Demands? Medini R. Singh Juhwen Hwang Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109 March 4, 1993 Abstract We consider a cyclic inventory system in which replenishment and selling capacities may be uncertain. Moreover, in the system, selling revenues, inventory costs and demand distributions are assumed to vary seasonally. The objective is to decide optimal selling and replenishment strategy maximizing the expected revenue of the system. The structure of the optimal policy is shown to have a single critical number in any period. We also show the relationship between the critical numbers in two consecutive periods. 1 Introduction In many inventory systems, prices, costs and demands vary seasonally. With this seasonal variation major problems arise, such as how to replenish commodities, how to manage stocks and how to meet demands. Moreover, in recent years, these problems become more and more complicated in involving uncertain replenishment and selling capacities due to increasingly sophisticated market requirements. These uncertainties are influenced by many factors such as machine breakdowns, insufficiency of labor, limitations of transportation capabilities, etc. 1

In this paper we restrict our attention to the systems dealing with a single commodity. Karlin (1960a,b) treats this problem with a number of periods of equal duration. In his model, demands are allowed to vary periodically, but with identical costs. At the beginning of each period, an ordering decision is made before observing the demand. The ordering capacity is always "perfect", i.e., the ordering output quantity is always equal to ordering request. Then, the demand is satisfied as long as stock is available, i.e., there is no control on stock after ordering. This implies that the selling capacity is also perfect, i.e., selling a stock to satisfy an existing demand is always possible. He shows that the optimal ordering policy has a single critical number. Zipkin (1989) extends Karlin's results to the case of cyclic costs as well as demands. Karlin's and Zipkin's models are very useful for managing many inventory systems; however, the ordering (or producing) capability of some products, such as corn, is only available once in certain periods, e.g., 12 months. Moreover, the producing and selling capacities in some systems are not certain. For example, the uncertainties in pumped-storage hydroelectric systems may appear in both pumping (producing) and generating (selling) modes due to leaking tunnels, pump/turbine breakdowns, shortage of water resource,..., and so on. In this paper, we consider such a system involving uncertain capacities and seasonal demands as well as costs. In our model, there is only one chance to replenish the inventory in certain periods instead of every period in Karlin's and in Zipkin's models. Moreover, under uncertain producing and selling capacities, two decisions are made after observing demand: a) how much to order in certain periods, b) how much demand to meet, i.e., how much stock to be leftover, in every period. In the next section we will describe and formulate this problem in an infinite horizon case with certain capacities. Then, we also show that the form of the optimal decision(s) is based on a single critical number in each period. In Section 3 we discuss the model dealing with uncertain capacities and show that a single-critical-number policy is still optimal for both multi-cycle and infinite horizon cases. 2 Perfect Capacities Here, we discuss an inventory system in which demands, selling prices and holding costs of a certain type of commodity repeat every n periods. We consider any consecutive n periods as a cycle. Within a cycle, period n is the first period and period 1 is the last. In each cycle there is only one chance to replenish the inventory through an ordering process. The ordering and selling 2

capacities are assumed to be perfect. Without loss of generality, let the purchasing period be the first period in a cycle. Under the cyclic behavior of demand, price and cost structures, we may define all system parameters within a cycle assuming the optimal strategy also repeats every cycle. Later in this section we will verify this assumption. Now, let Ik be the inventory level at the beginning of period k. In period k, let 0 < cak < 1 be the discount factor and let Qk(Gk) be the demand distribution with p.d.f. qk(Gk). The demand distributions in different periods are mutually independent. At the beginning of period k, a planned initial inventory level, nk, for the next period has to be decided upon based on the observation of,k and Ik. In other words, at period k $ n, Uk is the planned leftover stocks, and at period n, (un - n - In)+ is the purchasing quantity where (d)+ = max{0,d} for any real value d. Notice that the quantity of the actual leftover stock is max{uk, Ik - ~k}. Let u1 denote the optimal value of uk. Several costs and revenues are incurred during each cycle: a) a selling revenue, rk, is associated with each unit of the satisfied demand in period k (all the unsatisfied demands are presupposed to be lost), b) a purchasing cost, w (= 7ro), is associated with each unit of the replenished inventory in period n, and c) a holding cost, hk, is related to each unsold unit of the stock at the period k. All the costs and revenues are assumed to be non-negative. Naturally, the purchasing cost w must be smaller than any selling revenue 7rk. Let Ak represent the marginal revenue within a cycle if we always can sell a product in period k instead of in the next period, i.e., Ak = 7rk + hk - ak7rk- for k $ n and An = w + hn - arn-l. Now, we should recursively define the revenue functions within a cycle. (For convenience, we shall neglect the demand in the purchasing period. Then, let Gn = 0 with probability 1. Later in this section, we will discuss how to incorporate this demand.) Let Rk(Ik, k) be the expected revenue of selling Ik items optimally from period k through period 1, based on the observation of the current demand tk and the inventory level Ik at period k. Then, Rn(In, n) represents the maximum expected revenue to operate a cycle, given initial inventory In at the beginning of the cycle. Therefore, In < un in period n and (Ik - k)+ < Uk < Ik in period k # n. Therefore, Rk(Ik, k) satisfies the functional equations: Rk(Ik, k) = max 7k(Ik, ( k), k n ( Ik-k)+ <k <Ik 3

Rn(In n) = max Y(In, Un), In<un where 71(I, u1i) = 71(I1 - 1i)- - hlI + 1wU1, 7k(Ik, uk) = rk(Ik - Uk)- hkuk + akEk,_[Rk-l(uk, kk-1)], k = 2,..., n- 1, (1) 7n(In, un) = -w(Un - In) - hnUn + anEn-l[Rn-l(Unn-l1)]. (2) Now, we shall prove that there exists a sequence of critical numbers SI, S2,..., Sn such that the system is operating optimally. Furthermore, the form of the optimal policy is stock-up-to at period k $ n (see Figure 1): Ik if Ik < Sk uk = Sk if Sk < Ik < k + Sk (3) Ik - k if Ik> k + Sk, and order-up-to at period n: S if In < Sn (4) u,*_ = ('"'{Iw4) { Iyn otherwise. ik Sk+ 4k................................ Sk t + Y............ y Sk Z- k Figure 1: Optimal Policy at Period k The optimal policy in ordering period says that if the inventory level drops below the critical number Sn, then the inventory level should be filled up to the number; otherwise, no order should 4

be placed. The optimal policy in the other periods says that a) if the inventory level Ik drops below the critical number Sk, then keep all the stock to the next period, i.e., do not satisfy any demand, b) if Ik is in between Sk and Sk plus observed demand Ek, then keep exact Sk units of inventory to the next period, i.e., satisfy Ik - Sk units of demand, and c) if stock on hand is more than the critical number plus observed demand, then satisfy all the demand, i.e., keep Ik - units of inventory to the next period. In order to show the optimal policies with the form (3) and (4), we shall prove that all the revenue functions are concave by induction. Hence, consider the last period in a cycle. Taking the first derivative of y7(I1, ul) with respect to ul, we have aul(1, )- -A, < 0. 9u! Since marginal revenue is decreasing in holding any extra stock, we can define S1 = 0, i.e., we are not trying to leave over anything to the next cycle. Therefore, the optimal policy is (3). As a result, we have R1(I1,1) = l(i, Sl) if S1 < I < 61 + Si t 71(I1, I - l) if I1 > 1 + Sl. Hence, differentiating R1(II, l) with respect to Ii, we have aR1(II,7h ) J 7r if S1 < I1I Cl + S1 aIl -hl + a1w if I > + S1. Clearly, R1 (I, 1i) is concave in Ii. Trying to show the concavity of revenue function 7k(Ik, uk) in decision variable and optimal revenue function Rk(Ik, k) in inventory for all periods, let us recall a useful lemma from Iglehart (1965): LEMMA 1 Let N(x) = min {M(x,y)} = M[x, yo(x)] yo(x) E D(x) and x E C, yED(o) where x and y are k-dimensional vectors, N(.) and M(.,*) are real-valued functions, and D(z) is some domain in k-dimensional space which depends on x. If M(x, y) is a convex function of the 5

2k-dimensional vector z = (x, y), C is convex, and the set {(x, y): y E D(x)} is convex, then N(x) is convex in x E C. THEOREM 2 For all periods, 1. Yk(Ik, k) is concave in Uk. 2. Rk(Ik, k) is concave in Ik. Proof: We have shown that 71(I1, ul) is concave in ul and R1(Ii, 1) is concave in I1. Notice that the first two terms in the right-hand-sides of (1) and (2) are linear in Uk. By induction, suppose that Rk-l(Ik-l,k-1) is concave in Ik-i. Then, 7k(Ik,uk) is concave in Uk. Hence, Rk(Ik,k) is concave in Ik by Lemma 1. Similarly, Rn(In, n) is also concave in In. U By concavity, define Sk such that ak(Ikk=Sk) = 0 for k = 2 to n, i.e., for given Ik, 7k(Ik,uk) has the maximum at Uk = Sk. Then, we shall show that the critical number Sk is independent of inventory level. THEOREM 3 The critical number Sk is independent of Ik for all k. Proof: We know that S1 = 0 for all II. For k = 2 to n, it is clear from (1) and (2) that ak(kk) is not a function of Ik. QED. m Since cost function 7k(Ik, Uk) is concave in decision variable with maximum at Uk = Sk, the optimal policy can be described by the maximal Sk. Moreover, in considering the restriction of the decision variable, the form of the optimal policy is (3) and (4) since Sk is independent of the inventory level. The optimal policy in ordering period indicates that we will never order if and only if Sn < In. Suppose that In, > Sn. Then, within a finite number of cycles, In will be less than Sn by satisfying cyclic demand streams. Consequently, in an infinite horizon problem, the initial inventory In-_ at the beginning of period n - 1 is always equal to Sn and represents a renew point in the long run. Now, recall the case where a demand n occurs in period n. Because the purchasing capacity is unlimited, the inventory level still can be raised up to Sn after satisfying the demand, i.e., En does not affect the optimal decision. 6

3 Uncertain Capacities In the previous section we have shown that the optimal policy for the problem with perfect capacities has a single critical number in each period. First of all, in this section we shall discuss and formulate the problem dealing with uncertain production and selling capacities in a multi-cycle case. Then, in section 3.1 we will prove that the optimal policy is also described by a single critical number in this multi-cycle uncertain capacity problem. Moreover, we have illustrated the relationship between the critical numbers in two consecutive periods. Finally, in section 3.2 we will show that the optimal policy in an infinite horizon case has a cyclic sequence of critical numbers. Now, consider an N-cycle problem. Cycle N is the first cycle and cycle 1 is the last. Let Gk(Xk) represent the selling capacity distribution with p.d.f. gk(Xk) and let F(y) be the ordering (or producing) capacity distribution with p.d.f. F(y). All distributions are assumed to be mutually independent. Two issues allow us to neglect the demands occurring in ordering periods: a) producing and selling processes can not be executed at the same time, for example, pump/turbines in hydroelectric plants allow either pumping or generating phase at a moment, b) the leadtime, the time between placing and receiving an order, is negligible. For convenience, let fn = 0 with probability 1 and let k - 1 = n when k = 1. Due to uncertain capacities, it is not for sure that in ordering periods, the inventory level can be always raised up to a certain level (which is the critical number Sn in the previous perfect capacity problem). Therefore, we should formulate this uncertain capacity problem over whole planning horizon instead of over a single cycle in the perfect capacity problem. Then let the notations Ijk, Uj,,, uJk and Sj,k represent respectively, Ik, Uk, iu and Sk in cycle j. Now, we are in a position to define recursively the discounted revenue functions which form the basis of the analysis. Let Rj,k(Ij,k, k) be the expected revenue of selling Ij,k items optimally from period k in cycle j through period 1 in cycle 1, based on the observation of the demand (k and the inventory level Ij,k at period k. RN,n(IN,nn) represents the maximum total revenue to operate N cycles, given initial inventory IN,n at the beginning of cycle N. Then, the constraints of decision variables during cycle j become Ij,n < ulj, in period n and (Ij,k - )k)+ < uj,k < Ij,k in period ck # n. Therefore, Rj,k(Ij,k, Gk) with a boundary condition Ro,n(Io,n, n) = 0 satisfies the functional equations: Rjk(I,,kk) =. max 7k(IjUjk), k $n, (Ij,kk)+ <ujk <Ijk 7

Rj,n(C^nn)7 max'j^nIjn7Ujn)7 where 7jyl3(Ijl uj,l) = I(Ijl- uj,i){7r(IJ,l - ujl) - hjj + al EnR-l.RI,n(Uj,l nI)]} + j {7rix - hi(II - x) + QaE~.[Rj_,n(Ij,1 - XI n)]} dGl(lx), (5) Jo 7j,k(Ij,k, Uj,k) = Gk(Ij,k - Uj,k)({k(Ij,k - Uj,k) - hkUj,k + AkEkl [Rj,k-1(Uj,k, (k-1)]} + {rkXk - hk(Ij,k - Xk) + akEk_ -[Rj,k-l(Ij,k - Xk, ~k-1)]} dGk(xk), do k = 2,...,n- 1, (6) 7jn(Ini Ujn) = P(Ujn- -n){-w(Ujn - Ij,n) - hnUj,n + nEn-i [Rjn-l(Uj,n 7 n-l)]} + j(1 r { - wy - hn(y + I,,n) + anE7n, i [Rj,.n-(y + Ij, _n-1)]} dF(y). (7) o 3.1 The Multi-Cycle Problem Here, we shall show that there exists a sequence of critical numbers {Sj,k} for all j, k such that the system is operating optimally. Similar to the perfect capacity problem, the form of the optimal policy is Ij,k if Ij,k < Sj,k uk = S,k if Sj,k < Ij,k < k + Sj,k k # n, (8) Ij,k- Ck if Ij,k > g + Sj,k and =~ S,,n if ij,,n < Sj,n ( Ij,n otherwise. However, in the following discussion, we have found that the revenue function 7j,k(Ij,k, Uj,k) is no longer a concave function of decision variable uj,k. The non-concave property essentially complicates in analyzing the problem. But, we are able to show that the optimal revenue function Rj,k(Ij,kk) is still concave in inventory level through induction. In order to characterize the behavior of the revenue functions, let us consider the revenue function in the last period of the last cycle. Taking the first and the second derivatives of the revenue function with respect to decision variable, we have respectively 8-G~(I(, - u,l)(K1 + hi) < O, Ou~l,l

and 921, (1,1, u1,j) aL( lul) = -9f(0,1 - ulj)(7r + hi) < 0. Since the revenue function is decreasing in decision variable, we can define S1,1 = 0, i.e., we are not trying to leave over any stock. Then, the form of the optimal policy is (8) since rl,l(I,, u1,1) is also concave in ul,1. As a result, the optimal revenue function becomes R 1, ) ii(IIi, Sl,1) if S1,1 < I,1 < 6 + Si, 1 71,,1 (I,, I,, -7 1) if Il, > 61 + S,,1. Hence, taking the first and the second derivatives of R1,1(Il1,,f1) with respect to 1i,1, we have respectively R,1_(/1,,1 ) _ <7r11(Ili - S1,i) if S1,i < Il,i < ~6 + S1,1 0Ih, l -hi if I,I >1+ S1,1, and a2R1,1(/1,1, I1 ) _ J — ilgl(Il, - Sll) if S1,1 < Il,1 < + Si, OI2,l 1 0 if Ii > l + Si,'. Clearly, R1,1(I,,1 1) is concave in 1,i1. Now, we have proved the concave property of R1,1(I,, 7i) in I,,.i Then, we need to show that if the optimal revenue function in a period is concave in inventory level, then the optimal policy in the previous period is described by a single critical number. THEOREM 4 Assume that Rj,k-l(Ij,k-i, k-1) is concave in Ij,k-1. Then, the form of the optimal policy in period k of cycle j is (8) when k $ n and (9) when k = n. Proof: For k $ n, we have the first and the second derivatives of yj,k(Ij,k, j,k) with respect to Uj,k as follows, k(j,, (uiik) = Gk(Ij,k - uj,k)pj,k(uj,k), and 92.j,k(Ij,k, Ujk) (\ ajk k(Ij,k-,k)pIk(ujk) + (k Ujk)pjk-U,), 9

where Pj,k(uj,k) = -7k - hk + akEk [aRJk-(Uj k-1)], ouj,k PJ k(Uja) = u 2t Rj,k- (Uj,k, Gk-l1) o~,k Pj,k(uk) Q kEEk..l-[ a-R-,k — (u — k, Define Sj,k such that Pj,k(Sj,k) = 0. Clearly, Sj,k is independent of Ij,k. Since Rj,k-1(Uj,k1-, k-1) is concave in Uj,k-, pj,k(') is decreasing. Therefore, 7j,k(Ij,k, Uj,k) is decreasing in uj,k > Sj,k, and is increasing and concave in ujk < Sj,k. Hence, the minimum at uj,k = Sj,k is the global minimum. Therefore, the form of the optimal policy is (8). For k = n, taking the first and the second derivatives of yj,n(Ij,n, uj,n) with respect to uj,n, we have respectively, ^7,j.n(Ij,n, ) j =,) auj,n- j,.nPj,.n and a27jn(In u,,'n ) = F( -,)pj(uj,) - f(u,,n - j,n)Pj,n(U,) au2 3J, where pj,n(ujn) = -w - h\ + a,,E,_ [ ORin-l(ujn', n-1)] Pjn(U,n) = anE-W-n+0-^,i[ M- -, auj,7, 9u3,n Pj~n(Ujn) = ^tn~t [ — j,. - - (-j,, ~.- 1 )]. Define Sj,n such that pj,n(Sj,n) = 0. Clearly, Sjn is independent of Ijn. Since Rj,n-.l(j,n,,1,n-i) is concave in Uj,n, pj,n(*) is decreasing. Therefore, ujn(Ij,n,(^'j,n) is decreasing in Uj,n > Sj,n, and is increasing and concave in uj,n < Sj,n. Hence, the minimum at Ujn = Sj,n is the global minimum. As a result, the form of the optimal policy is (9). U In order to perform the proof by induction, it is necessary to show the following theorem before hand. THEOREM 5 If Rjk-1(Ij,k-1, k-1) is concave in Ik_1, then Rj,k(Ij,k, k) is also concave in Ij,k. 10

Proof: For k $ n, since Rj,k-l(Ij,k-l, k-1) is concave in Ij,k-1, the form of the optimal policy for period k in cycle j is (8) by Theorem 4. Therefore, we have |(j,k(Ij,k,Ij,k) if Ij,k < Sj,k Rj,k(Ij,k,k) = 7 j,k(Ij,k, Sj,k) if Sj,k < Ij,k < Gk + Sj,k 7j,k(Ij,k, Ij,k - k) if Ij,k > Gk + Sj,k. Taking the first derivative of Rj,k(Ij,k, k) with respect to Ij,k, we have 9Rj,k(Ijk, k) aIj,k -hk + akEk._ [I- (1I'kk1)] if Ij,k < Sj,k a lj(k I ak -Sj, EE k_ [ ajI-'k - ] dGk(Xk) +7rkGk(I,k - Sj,k)- hkGk(Ik - Sj,k) if Sj,k < Ij,k ~< k + Sj,k (10) ak re Eth - ['Rj}-laje dGk(xk) -hk + QkGk((jk))EZ-_ [ai, -l( - ] if r-k > k - SIk Taking the second derivative of Rj,k(Ij,k, k) with respect to Ij,k, we have a Rj,k(Ij,k,k) _ aic if, < ckE~l_[Rjak-l-lj (,'k —l) ] if Ij,k < S/,k c rk0-S, E. [2ak- (-jk -k,-)] dGk(xk) -(rk + hk)gk(Ij,k - Sj,k) if Sj,k < Ij,k < ~k + Sj,k aAk 2Ogk EE(1[jlk —-k 4 ] dGk(xk) +QckGk((jk)E^k.. [ 2Rk-l(-.1(k J -G l)] if Ij,k > Ek + Si,kSince Rj,k'_-(Ij,k, k-1) is concave in Ij,k, Rj,k(Ij,k, k) is concave in Ij,k belonging to three intervals, (0, Sj,k), (Sj,k, k + Sj,k) and ((k + Sj,k, oo) respectively. Moreover, by using the first order condition pj,k(Sj,k) = 0, it is easily to show that the limitations of aRia( i'( at I,,k equal to Sj,k and equal to (k + Sj,k respectively, exist. This guarantees the concavity of Rj,k(Ij,k, k) in all Ij,kt 11

For k = n, since Rjln(Ijn-i Xn-i) is concave in Ijn,-, the form of the optimal policy for period n in cycle j is (9) by Theorem 4. Then, Rjn(Ijnn) = | j7j,n(Ij',n, Sjn) if Ijn < Sj,,n 7j,n(Ij,n, Ij,n) otherwise. Taking the first derivative of Rj,n(Ij,n,,), we have a n fSj'"- " E_[ aRl "-l( + "'-l)] dF(y) ORj,n(Ij,n,) +w-F(Sjn - I,n) if Ij,n < Sj,n Ij3,n an Enlt R,(In nn- )]-hn otherwise. Taking the second derivative of Rj,n(Ij,n,,n) and then by pj,n(Sj,n) = 0, we have { f sj-b Ea f_[a Rn'"-(y+t'"'(-)n] dF(y) if Ij,,n < Sj,n a Rj,n(Ij,n, (n)_ n aia - n [anEtn-l_ I2, ('n'("')] otherwise. Since Rj,n-l(Ij,nl, n-l) is concave in Ij,n-1, Rj1n(Ij,,nn) is concave in Ij,,n E (0, Sj,n) and Ijn E (Sj,n, oo). Again, we can show that the limitation of aRj atlnn) at Ijn = Sj,n exists. Therefore, Rjn(Ijn, )n) is concave in in Ij,. By induction, the following corollary is ready to perceive. COROLLARY 6 The form of the optimal policy for period k in cycle j is (8) when k 5 n or (9) when k = n. So far, we have shown the structure of the optimal policy described by a sequence of critical numbers. Now, we shall show several properties of these critical numbers. THEOREM 7 Sj,I = 0 for all j. Proof: From (10) and (11), we have P(O\1 h +- tlE_[R3j,k-l(Ujk = Sj-l,n,k-l)] Pjl(O) ~ -7h-1+ alE+k,._[ = — 1 - hi +a w < 0. 12

The proof is done by decreasing property of pj,i('). QED. * Theorem 7 indicates that to sell a product in the last period of a cycle is always more beneficial than to carry it over the next cycle. In the following theorem and corollaries, we characterize the behavior of the critical numbers influenced by the marginal revenue Ak. If it is profitable to sell a product in period k instead of in the next period, then we try to keep less inventory in period k than in the coming period. On the other hand, if it is less beneficial to sell a product in period k instead of in period k - 1, then we try to keep more inventory over the next period. THEOREM 8 If Ak < 0, then Sj,k > Sj,k-1; otherwise, Sj,k < Sj,k-1. Proof: From (10), we have OR'(IkS ) = irk- by pi,k-j(Sk-1) = 0 for all j, k. Hence, Pj,k(Sj,k-1) = -Ak for all k. Notice that pj,k(') is decreasing. Therefore, if Ak < 0, then Sj,k > Sjk-1; if Ak > 0, then Sj,k < Sj,k- otherwise. a Theorem 8 is very useful for searching critical numbers in reducing unnecessary computational burden. For example, if the marginal revenues in all periods are greater than zero, then all critical numbers are zero. Therefore, it is not a profitable problem since Sj,n = 0, i.e., it is not a benefit to order any product. On the other hand, if the marginal revenues in all periods are less than zero, then Sj,n > Sj,n_1 >... > Sj,1 for all j. 3.2 The Infinite Horizon Problem Let us consider an infinite horizon version of the uncertain capacity problem. It is clear from (5), (6) and (7) that in any cycle, the one period revenue is 4j,k(Ij,k, Uj,k) = [rk(Ij,k - j,k) - hkUj,k]Gk(Ij,k - Uj,k) + Ik [rkZk - hk(Ij,k - Xk)] dGk(xk), k $ n, Jo and.n(Ijn ujn) = -(jn - wn + h n)(,n - Ijn) - f''" -" (wy + hny + hnIj,n) dF(y). Jo 13

Then, the function to be minimized is given by N n n J,g(IN,,) l= im [(JI a) j Z 5j,m (uj,m)], j=1 1=1 m=l where Jm(IN,n) denotes the revenue associated with an initial inventory IN,n and a policy ={UN,,n..., UN,1,... Ul,n,..., 1,1}. Indeed, consider a stationary policy i = {u, u,...}, where ii is defined by u(Ij,k) = j,k, Vj, k. It follows that the inventory stock Ijk is always equal to 1N,n when i policy is used. Now, differentiating'>j,k(Ij,k, Uj,k) with respect to uj,k, we have 9'j,k(Ij,k, Uk) = -(7rk + hk)Gk(Ij,k - Uj,k) < 0, k $ n, 9uj,k and oj,n(Ij,n, jn) _-(w + hn)F(u1j, - Ij,n) < 0, auj,,n i.e., kj,k(Ij,k, Uj,k) is decreasing in Uj,k for all j, k. Assume that the ordering capacity is bounded above and E[Y] < oo. Furthermore, we have lm Oj,n(Ij,n, j,n) = -(w + hn)E[Y] - hn,n uj,n -00 Since (Ij,k - tk)+ < uj,k < Ij,k and Ij,n <L j,n, we get -hkIlj,k < 4j,k(Ij,k, Uj,k) < [k(Ij,k - (Ij,k - k)) - hk(j,k - k)]Gk(j,k - (Ij,k -k)+) + jk(I ) [-rkXk - hk(Ij,k - Xk)] dGk(zk) rkIj,kGk(Ij,k) + fo' [rkXk - hk(I,k - Xk)] dGk(Xk) Ij,k < k -[rkGk + hk(I,,k - k)]Gk(Gk) + f[7kzk - hk(I,k - Xk)] dGk(xk) Ij,k > k, and -(w + hn)E[Y]-hnljn < >j.n((Ipj,, u,n ) < 0. 14

Hence, the revenue per period incurred when i(Ij,k) is used is bounded, and in view of the presence of the discount factor we have maxJp(IN,n) > J(rIN,n) > -00. Then, from Bertsekas (1987), the optimality equation reduces to the system of n equations: Rk(Ik, k) = max 7k(Ik,uk), k n, (Ik -k)+ <uk <Ik Rn(In, n) = max in(Inn), rn<Un where 7k(Ik,Uk) = Gk(Ik - Uk){(k(Ik -'k) - hkUk + akEkl [RRk1(Uk, Gk-1)]} i k — U k + {(kXk - hk(Ik - Xk) + akE,_ [Rk-l(Ik - Zk, X k-l)]} dGk(xk), k $ n, o n(In Un) = F(Un - In){ - w(Un - In) - hnUn + nERnl [R-n-l(un i n-l)]} + { - wy - hn(y + In) + anrE- [Rnl (y + In, n-l)]} dF(y). Furthermore, an optimal periodic policy, p* = {21(Il),..., iu(n),..., i(11),..., (In)}, is guaranteed to exist. Therefore, the optimal policy jA* satisfies the following n first order conditions: Gk(Ik - i;(Ik)){ - rk - hk + akEk,_, [ Ikk-l(Uk -- A;(Zk), k-1), k, (12) (*(In) - In ){ - - +.E._[Rnl(Un = n (.)] (13) Clearly, the function inside the brackets of (12) and (13) are independent of inventory levels. Therefore, there exists a sequence of numbers {S1, S2,..., Sn} to satisfy these n first order conditions. Since Rj,k(Ij,k, k) are concave in inventory level for all k, the limit functions Rk(IkAk) is also concave in inventory level. Therefore, we can show that for all k, kk(Ik, uk) is increasing in Uk E [O,Sk] and is decreasing in Uk E [Sk,oo) through the similar analysis in Section 3.1. Furthermore, consider the decision variable constraints (Ik - gk)+ < Uk < Ik for k # n and In < un. As a result, the structure of the optimal policy is Ik if Ik < Sk uk = < Sk if Sk < Ik < k + Sk k n, IIk -k if Ik > k + Sk 15

UNIVERSITY OF MICHIGAN 3 9015 04735 0239 and = Sn ifIn < Sn n, - { In otherwise. Reference BERTSEKAS, D. P. 1987. Dynamic Programming: Deterministic and Stochastic Models. PrenticeHall, Inc. Englewood Cliffs, N.J. IGLEHART, D. L. 1965. Capital Accumulation and Production for the Firm: Optimal Dynamic Policies. Mgmt. Sci. 12, 193-205. KARLIN, S. 1960a. Dynamic Inventory Policy with Varying Stochastic Demands. Mgmt. Sci. 6, 231-258. KARLIN, S. 1960b. Optimal Policy for Dynamic Inventory Process with Stochastic Demands Subject to Seasonal Variations. J. SIAM. 8(1960b), 611-629. ZIPKIN, P. 1989. Critical Number Policies for Inventory Models with Periodic Data. Mgmt. Sci. 35, 71-80. 16