Release Control Policy for a Production System with Random Yield Walid R. Abillama Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109-2117 December 1993 Technical Report 93-34

Release Control Policy for a Production System with Random Yield Walid R. Abillama Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 December 2, 1993 Abstract We consider a single product, single stage, multiple periods production system with random yield that minimizes the total quantity released over the planning horizon while keeping a high probability of meeting the demand in each period. We present the optimal finite horizon policy, discuss the single assumption underlying it and present some examples using specific yield distributions. 1 Introduction We consider the problem of releasing a quantity of a certain kind of raw material at the beginning of each of n future periods in a single stage production system. We assume that demand is deterministic and known for the entire planning horizon, and that the production outcome is a random fraction of the input release quantity. This random 1

fraction, better known as yield rate, has a very large variability and upper management is having great difficulty estimating an accurate measure for the unit shortage cost per period. However, upper management does require that the demand be met in each period with a prespecified confidence level and that any unmet demand be backlogged and become due the next period. The objective therefore is to minimize the total quantity released over the planning horizon subject to meeting the demand in each period with a high probability. The tradeoff between acheiving a high service level and minimizing the amount of raw material released is clear. Releasing huge quantities of raw material in a particular line increases the chances of starving other lines in the plant which use the same raw material and will therefore hinder the overall production capacity of the plant. Quantities released must be kept at a minimum, only to satisfy in each period the service level requirement set by upper management. One possibility would be to decide at the beginning of the planning horizon on all the release quantities that should be made in each period, without waiting to see subsequent levels of production yield. However a clearly better choice would be to postpone the release of the kth quantity until the beginning of period k, when the inventory level at the beginning of that period would be known. This mode of operation involves information gathering and sequential decision making based on information as it becomes available and lends itself to Dynamic Programming techniques. It implies that we are interested in finding an optimal rule for choosing at the beginning of each period a release quantity for each possible value of inventory level that can occur. Mathematically the problem is one of finding a sequence of functions, which will be referred to as a control law or policy, mapping the inventory level at the beginning of each period into the release quantity so as to minimize the total quantity released in all future periods while keeping a high probability of meeting the demand in each period. We refer to such a problem as the multiple periods service level random yield model. The practical importance of taking into account yield randomness in analyzing production and inventory models was addressed by, among others, Karlin (1958 Sections 4-8) who considered a multilple periods problem where ordering is restricted to a fixed amount. Lee and 2

Yano (1988) considered a single period serial system, Sepehri, Silver and New (1986) considered a single period model with multiple setups, Yao (1988) considered a single period assembly system, Gerchak, Vickson and Parlar (1988) considered a multiple periods cost based model and showed that the solution is neither myopic nor order-up-to. Multiple products models were considered by Singh, Abraham and Akella (1990) and Tang (1990) in a single period setting. Yano and Lee (1989) reviewed the lot-sizing problem when the yields are random and reported finding little research done on multiple periods problem. This paper analyzes a multiple periods service level model and is organized as follows. In section 2, we define our notation and formulate the problem mathematically. In section 3 we study the structure of the optimal policy by considering the first and the second period problem separately, and then by showing the optimal release policy for a more general n periods problem. We show that this policy holds under one particular assumption that we will define later in the section. In section 4, we discuss our assumption and show that it is valid for all practical yield rate distributions and service level values. In section 5 we present some examples using specific yield rate distributions. Finally, we conclude in section 6 by suggesting some new directions for research. 2 Terminology and Formulation In this section we define the terminology that we use throughout the paper and present the dynamic programming formulation. We use backward recursion to explore the structure of the optimal policy. Therefore the last period, n, becomes the first period to be analyzed, period n - 1 becomes the second period and so on. Let d be the demand that needs to be met at the end of each period with a prespecified level of confidence y. More specifically, the service level constraint in any period k is defined as: P[Ik +UQk-d > 0] > (1) 3

where Ik is the on-hand inventory at the beginning of period k, U is the yield rate, a continuous random variable between 0 and 1 with stationary cumulative distribution F (Fk = F Vk), and Qk is the quantity released in period k. Equation (1) can be rewritten as: P[U dk] ~7 Qk F-11 —] (2) Let Jr (Ik) be the value function, that is the minimum total quantity released to meet the service level, given the inventory level Ik and assuming that the best decision is taken in the current as well as in all the future periods. Finally let Q* (Ik) be the optimal quantity to be released at the beginning of period k, given Ik. Denote the ith period problem by P(n - (i - 1)), that is the problem of solving an i periods problem. We want to solve P(l). For a general period k, P(k) is formulated as follows: Jk (Ik)= Min Qk+ E [Jk+l (Ik+l)] P(k) s.t.t TQk - F-l] iflk< d Qk > if Ik d An interpretation of this formulation is the following. To solve an n - (k - 1) periods problem, we minimize the sum of the amount of material released in the current period k, plus the expected amount of material that might be released in the following n - k periods given the beginning of period on-hand inventory Ik+1, which in turn is related to Ik, the on-hand inventory at the beginning of period k, through the production outcome UQk and the demand d in the current period. In other words we are assuming that capacity is never binding but at the same time we are allowed exactly one trial per period. As a result, lead time is not more than one period and the relationship between the state 4

variables Ik and Ik+1 is nothing but: Ik+1 = Ik + UQk - d (3) The service level constraint defined in equation (2) becomes active only if the current on-hand inventory level is less than the demand. Otherwise, the release quantity should only satisfy the non-negativity constraint. Substituting equation (3) in P(k) we get: 1 Jk (Ik) = Min Qk + J+ (Ik + uQk-d) f ()du 0 P(W) ifslk<d s.t. { >- -_ if Ik <!- d Qk > O if Ik > d We analyze in the next section the optimal finite horizon policy. 3 Structure of the Optimal Policy 3.1 First Period Problem With Jn+, (In+,) = 0 VIn+1, the optimal decision in the first period is simply to release the minimum amount of material required to satisfy the service level constraint in that period. Clearly we do not release any material if the on-hand inventory at the beginning of that period exceeds the demand. The first period problem is defined as: Jn = (I) Min Q d-In P(n) s.t. Qn F-(1-^] if In < d Qn > if, > d The first period policy is given by: Q (In) = J (In) = F-11-] (4) 0 if I > d 5

3.2 Second Period Problem The objective function of (Pn-l), Jni (In-_, Qn-_) is convex in Qn-i since J (In ) is convex in In. (Pn-l) first order condition is given by 2d —In_1 dJn-j (In-l Qn-i) - 1 Qn-i dF (u)O (5) dQn_1 F-1 [1-] Jo 3.2.1 Second Period Policy Proposition 1 The second period policy is given by d-'In- if In-1 < Y1 d-In-1 Q~ l (In-1)={ d — if y < In-, <2d (6) 0 if In-,_l > 2d where yl < d and F-1 [1 - ] < rl 1. Clearly for I_, > 2d, we have that Q*i (n-11) = 0 since the left hand side of (5) is positive. For In-_ < 2d and assuming that E [U] > F-1 [1 - ], we get from (5) that Q_-1 (In-l) = (2d - In-,) /r7_ where J- udF (u) = F [1 - (7) and hence r -_1 < 1. Furthermore from equation (7), we have that F-1 [1- ] < r/*-1 since rF-1[1-] F-[1- ] uf (u) du =-,(l - ) F-1 [1 - 7]- F (x) dx < F-1 [1 -] (8) 0 0 As a result, there exists In_1 = y, < d below which the service level constraint is binding and y, is obtained by solving 1 d- y, (2d- y) = F1 [1 67n-1 F-l [1 - y(

Figure i shows a plot of Q-1l (In-,) versus In_1. We leave the second period policy with three observations: 1) The production quantity required to meet the demand (set by the reorder point) is augmented due to random yield, we say we are'overproducing' (Qn-\ (In-l) > 2d- In-_), which is a common feature of random yield models. 2) We are'increasingly' overproducing with decreasing initial stock levels. This can be seen in proposition 1 where dQn_1 (In-_) /dnl_1 < -1, which is to be expected since there is no limit on backlogging and capacity is not binding. 3) The reorder point is equal to the total demand in all future periods, also expected since there is no penalty for early production. Assumption 1 E [U] > F-1 [1 - 7] Note that this second period policy is valid only if E [U] > F-1 [1 - 7], which implies that there exists 71- <K 1 that satisfies (7) and hence Q,-\ (In-_) > 2d - In-, for In_- < 2d. For the time being we will neglect the case when E [U] < F-1 [1 - 7] since it is reasonable to assume that the service level will always be high enough so that E [U] > F-1 [1 - ] will always be true. In a future section, we will show that this assumption holds for all practical yield distributions and service level values y. 3.2.2 Second Period Value Function Clearly J, (In-) = 0 for In,_ > 2d. For y, < In-, < 2d, the value function is obtained by substituting Q*,l (In,_) in the objective function of (Pnl). Doing this, we get that Jr_, (I,-,) is given by Q 1- (I-) F- [I- -] 1l (In-1 + UQ 1 (In-,) - d) f (u) du (10) For In_ <~ yI, the value function is obtained by substituting in (10) Q_, (In,_) by 7

(d-In-1) F-I[1-,]' Proposition 2 J l, (Inl) is convex. From (10), the value function is linear for y <_ I-_1 < 2d since dJl (In-) _ dQn-I n) 1 1 d ( + (dn-l dIn-l dIn-_ F-1 [1 -7] / dIn- d&(In-[1 - F- [1 - y] f (u)du F-1 [1 - y] Differentiating Jn_ (In-,) for In-_ < y1 we get: - 2d-In-1 F-1 [1 —y] -1+ 1- F-l[l_]) f (u) du d~n*- (In-,) 0 d Jn~l (n__ 1 ) = _ F-1 [1- 1] thus J_ (In_-) is differentiable at In,_ = yl using (9). Furthermore J:_, (In,_) is convex for In_, < y, by differentiating (11) one more time. As a result, Jn, (In-_) is convex. Figure 2 shows a plot of Jn, (In_) versus In-,. Finally, we close this section by noting from (11) that limIlo dJnl (In-,) /dInl =-(1 + p) /F- [1 - y] where /.F-1 [ —] p = -y] F (u) du/F- [1 -] 3.3 General Period Policy Proposition 3 Jk (Ik, Qk) is convex in Qk, k =1,..,n. It is true for k = n and n - 1. We will show it for 1 < k < n - 2. To do that, we will assume that the value function for a n - k periods problem is convex in?k+1, show that 8

the objective function for a n - k + 1 periods problem is convex in Qk, and then show that as a result, it implies that the value function for a n -k + 1 periods problem is convex in Ik. Suppose that J*+l (Ik+1), the value function for a n - k periods problem, is convex in Ik+i. It implies that for a n - k + 1 periods problem, Jk (Ik Qk) is convex in Qk since Jk (IkQk) = Qk+E[J+l (Ik +UQk -d)] (12) dJk(IkQk) +E U dJ (Ik (13) dQk dlIk+l d2Jk (Ik Qk) E'[U2d d2J*k+) (14) dQ2 dIk2+Therefore Qk (Ik), the unconstrained optimal policy for a n - k + 1 periods problem is obtained by setting (13) to zero and solving for Qk. Now suppose that there exists a unique point Ik = Yn-k below which the service level constraint is binding. That is suppose that the optimal policy for a n - k + 1 periods problem is defined as follows: Q_._ Q- (/{ k) if Ik > Yn-k &k ( /d)- (15) F-I [1 otherwise As a result, the value function in a n - k + 1 periods problem is given by Jk (Ik) = Q (Ik)+ E [Jk+ (Ik + U7Q (Ik)- d)] if Ik > Yn-k (16) Fl[l1- y + E [Jk+ d) ( - F-4 k _))] otherwise The first derivative of the value function is given by d~;(z~) + E If if Ik > Yn-k dJk (k) _ dlk dIk dk+l ] - (17) dk F-l[ +E [(i F-[-]) d Ik+ otherwise Clearly the value function is differentiable at Ik = Yn-k. For Ik > Yn-k, the second derivative of the value function is given by d2 J (Ik) _ d2; (hIk) \[ cd2Qk (Ik) dJ*+ (Ik+l) 1 dIl = dI + F U dlJ dlk+1 9

E ( rJ (k> + Uk J) k(I+ l k+l) E I+ U dIk dl+1 F E [(1~+ud Q~-(Ik)2 d2J*+l (Ik+l)]1 =E + dlk dIl2+1 d 2-Wk / ([ d J 4 (Ik+l)'] d2 (Ik)1 + E U dlk+l dI zero by (13) = EI(l Ukv (IUk) 2d2J*+l (Ik+l) (18) E + dIk d+1 >0 Finally, if the service level constraint is binding, then from (17) the second derivative reduces to d2J (Ik) =E (1 u- F 11 - dJI [ Fl[1[I - Y]2 d1k+1 > (19) Therefore Jk* (k) is convex and we are done. However, it still remains to be shown that Q% (Ik) is defined as in (15). To do this, it is sufficient to show that Qk (Ik) is convex and limIk O dQk (Ik) IdIk > F-i1- ]. The following is a series of propositions that prepare the ground for showing this and provide more insight on the structure of Qk (Ik). Proposition 4 Q, (Ik) = 0 for Ik > (n- k + 1) d, k - 1..n. It is true for k = n and n - 1. We will show it for 1 < k < n - 2 using the same kind of inductive argument as in Proposistion 3. Suppose that for some 1 < k < n - 2, we have J*+, (Ik+1) = 0 for Ik+l > (n-k)d. Then substituting for Ik+1, we get J+i (Ik + UQk - d) = 0 for Ik > (n -k + 1)d - UQk and hence for Ik > (n- k+ l)d w.p. 1. ThereforeE [Jk*+ (Ik + UQk - )] = 0 for Ik > (n-k +1) d and (12) becomes Jk (Ik, Qk) = Qk. As a result, Qk (Ik) = Qk (Ik) = Jk (Ik) = O for Ik > (n-k + 1) d and we are done. 10

Lemma 1 If E [U] > F-l [1 - ], then the set of equations fk uf (u) du = Ak+l k = 1,...,n - 1, where Ak+= f (u) du and A = F- [1 -] kof+ f(u) du has for unique solution F-1 [1 - 7] < I 7_ <... -< 7' < 1. The proof to the lemma is very simple. It is true for k = n - 1 from (7) and it is easy to see that for 1 < k <n - 2 k+ f (u) du < Ak+ = f (u) du => r1+l < ~k dO 30 and lim,,,oo r = 1. Proposition 5 Q( (Ik) - = -k+) ( n- ) n - 1) d + y _< Ik < (n - k+ 1)d, k = for,..,n-1. It is true for k = n- 1. We will show it for 1 < k < n- 2 using the same kind of inductive argument as in Proposistion 3. Suppose that for some (n - k - 2) d+yl < Ik+1: (n - k) d we have li:k+1 F h7* Jk+1 (k+1) = -1 [ 7] [(n - k) d - Ik+1] Then for (n - k - 1) d + Y1 < Ik < (n - k + 1) d, setting (13) to zero results in d&I (Zk Qk) =l 1 - 1 F ] f0-k+l)ddJk (Ik, Qk) Fi=k+l fF ] k uf (u) du 0 dQk F-1 [l-y Jo Therefore, -k (Ik) Qk (Ik) = [(n - k + 1) d - Ik] /r where u" f (u) du = F- [ - 1y A+ fJo Hl= o-+1 F [r/, ] if and only if there exists such k < 1. In other words, if and only if E [U] > Ak+1. The 11

inequality is satisfied as equality for 77+l = 1. Therefore it is sufficient to show that the first derivative of the right-hand side with respect to 71k+ is non-negative and we are done. In fact: rk+1 k+l dAkt+l _1k +l f(/k+l) f f(u)du-f(r l+l) f uf(u)du k^^fe+l ko o 77+1 f(nR+l) f (r+l,-U)f(u)du 0 >>0 [F[,+ 1]] > Substituting Qk in (12) by Q; (Ik) = [(n - k + 1) d - Ik] /7/, we get for (n - k - 1) d + Yi < Ik < (n - k + l)d J- (Ik) = [ [(n - k + 1) d- Ik] (20) F-1 _11_ - and we are done. Proposition 6 dQk (Ik) /dIk < -1 for k = 1,.., n. It is true for k = n and n - 1. Recall that 7k (Ik), the unconstrained optimal policy for a n - k + periods problem is obtained by setting (13) to zero and solving for Qk. Hence the equalities dJk (lk,Q) d<Jk (I,l)2 dQJ dJk (Ik,d) (dQ d dQkdIk dIk dQk dk dJk(IkQk) [ d Ik+l _1 ddQk* d+1 dIk E2 [UdJ Ik U2 k+l] Lemma 2 F-1 [1 - y] < /3k, k = 1,.., n- 1 where / is given by Pk n-k-1 -1 Juf(u)duF=1 -[1 [ E Py 12

The proof is the following. We can write k= F [1 -uf() d Fn-k- [1- - uf(u)du uf(u)du by (8) > F [I - p' J.i=o = F-1 [1 - 7](I - p) = F-1 [I - ] - [ uf (u) du > F- [1-a] F- 1l-] > j uf (u)du by (8) 0 and hence 3 > -1/F-1 [1 - 7]Proposition 7 limk- OO dQ (Ik) /dIk = / for k = 1,.., n - 1. It is true for k = n - 1. Suppose that for some 1 < k n - 2, we have that -+l (Ik+1) is convex and that limIk+l,,,- dk+l (Ik+l) /dIk+l = 03+r. Since +,l > /3k by definition, then by (2) these two assumptions imply that the optimal policy for a n - k periods problem is defined as follows: Q Q+ (Ik+l) if k+1 yn-k-1 (21) Qk+1 (d+kl) = d (+21 t F=-ll otherwise F-1 [1 —] Suppose furthermore that y,-i < d +,n-i-i, i = k + 1,..,n- 1 (where yo = d), then from (17) we get that in a n - k periods problem, limIk+lO dJk+ (Ik+l)/dlk+ is equal to [i m + ~ -— o d+Yn-k-2 —k+l F-1[l_,y] MuIk+l- daI.k+d1 [ ~ ~ ~ ~ ~~r1 (- ir-, 7 —1' f (U) du _ F-1 [1 -- ]

1 pI,n-k-2 pi n-k-1 pi F-l [1 -[ ] F- [1- y] Note that (22) is true for k = n - 2, thus we are assuming that it is true for some 1 < k < n - 3. Therefore marching one period in time backwards (i.e considering a n - k + 1 periods problem) and setting (13) to zero we get,. dJk{(Ik, Qk} -- S V [^n —k-1 i O lim dJk (k, Qk) =1 - - P k uf (u) du = O Ik -o- dQk F-1 [1 - ] J0 where /3 = limk,_-c (d + Yn-k- - Ik) /Q (Ik). Therefore limlk-,o dQk (k) /dIk = l//l3 because limk-o0 Qk (Ik) = oo by proposition (6). Using lemma (2) and invoking the assumption that AQk (Ik) is convex, it implies that there exists a unique Ik = Yn-k < d + Yn-k-1 below which the service level constraint is binding for k = 1.., n - 1. Yn-k is obtained by solving -* d - yn-k Q (Yn-k) =F- [- (23) and thus Q* (Ik) - Qk (Ik) if Ik > Yn-k Qk (1k) = dF-[lk] otherwise F-11(1-'7] Finally, as a check to (22), we get that in a n-k+ periods problem limik-, dJk (Ik)/dlk is equal to 14

Bk —w d-1k F-L -y] rl+ n-k-i i (I - ) d () l -F-l[1 - Y] [p=O1 ro1pt F1[1-](1- - F-[[-]] f (i) d]1 F-1 [1 - y] 1+pZn-k-1 pi kpi (24) + E-= f 1 -- F ET f =O (24) F-1 [1 - 7] F-1 [I - ] F [ 7] It still remains to be shown that Qk (Ik) is convex and we are done. If this is true, then the optimal policy Q* (Ik) for a n - k + 1 periods problem, k = 1,.., n is defined as in (15) and proposition (3) is true. We do this in the next proposition. Proposition 8 Q* (Ik) is convex in Ik, k =1,.., n. It is true for k = n and n - 1. For 1 < k < n - 2, the second derivative of Qk with respect to Ik is given by 2 d2 Jk (IkQ) d3Jk IkQk) d2Jk(Ik) d3Jk (k) dQk - [ dQ-k* dQkdI dQ-dIk dQk3 d l d dQ —'2 d+(Ik k d+J~IQk J diE~l+1 — u E [[IZ - E ^^^(^i+)]~ E U2d^IdQ2 [d2Jk+l Ik+1) E dU2 d Jk+, (Ik+l)_ E [U J+l(Ik+) E U dIk+l1) Suppose that for a n - k periods problem, we have that the second order condition is satisfied, i.e. that E [U d2J I(+] E [U2 d3Jj+l+) - E [U2d2Jd+ (Ik+l) ]E[d3J +(lk > k (25) 15

and thus d2Q*/dIk2 > 0. We want to obtain an expression for the third derivative of the value function for a n - k + 1 periods problem. From (17), _____ dQ (I,,) (i f Iy - dJk (Ik) j [ dJ (k+l )] + dk(1k) +( E d ]) if Ik > Yn-k (6) [dJk+l(Ik+l) (26) Edh ~V E [ dI - F-1I[,a] (1 + E [U, d' ]) Eotherwise and d 2jk (Ik) |E I( + U4 dlk 1) l ] if Ik > Yn-k — ________ -- d,+1 (27) dIk2 F-l[ ]) k+l(+)] otherwise d (Ik) F d d2d 1 (Ik+l E 1 + U d(lk ) ] + [ dI ] [ dk J [ dl l d+ 1 Substituting (18) and (28) in (29), we get for Ik > Yn-k E [U (1+ udj(+) dI2 J [U3 dl d+2 ()] + F [U (l ~Ud G( ))^ 1 I24(I+)1] FE [U2 (1 + U d(())2 kd+3 J (I+l)1 > [ d k / dI 3 _ d2jkJ+ dk d1k J [ 1k ) kd2+l [Lk k d lJ ] F ( [U2) 2 * dkU 2 d1k iF [u>d%2u Substituting (18) and (28) in (29), we get for/Ik >_ y~-k E[ (1 Ud q(Ik)) 2Jk+l (Ik+l)] E U (1 (Ik))\ d3J+1 (Ik+l) > dIk,d 1 EU i+U dJ L Ik F [U(12dlk1 L E dIkJ+ dI+1 j (1+ ud(I) d(2J.+ (I+)2] [ d-2od ~*,.+ ~J1 ([+1) 1 u + d _ (L) 2 ( ) lt4

since d2 k/dIk > 0 and (25) is true. A similar argument is used to show that (29) is satisfied for Ik < Yn-k- Substituting (19) and (28) in (29), we get for Ik < Yn-k E UiC I F- 1 d2J-+ 1(]k+l)], E - (i F3 d3JZ+l (Ik+l) E U (1 - F U [1 ] E U[ F-F [1 - ]r ) dI J E U (1 F-1 [1 d3J Ik (30) To show that (30) is true, it is sufficient to show that (28) is non-negative for Ik < Yn-kBy (22), limIk __co d3Jk (Ik) IdIk = 0. Furthermore from (28) and the induction argument we have that d4j(Ik) - U 4d4J+l(Ik+]) dik E F1 F- [] d3k+ > (+l (31) hence (28) is non-negative for Ik < Yn-k and we are done. We have shown that the unconstrained optimal solution Qk (Ik) is convex in Ik, k= 1,..,n - 1. Figure 3 shows a plot of the optimal policy Q* (Ik) in a n - k + 1 periods problem versus Ik. 4 Justification of Assumption 1 At this juncture, we would like to digress in order to justify assumption (1). We claim that assumption (1) holds for all practical yield distributions and service level y. Assumption (1) can be rewritten as y > 1 - F [E [U]]. Consider the Beta distribution with parameters a > 1 and b > 1, whose density is given by: U1 -(l- U) — if 0 < u < 1 f (u)=^ r O B(alb) b- otherwis: (32) 17

where B (a, b) is the beta function. The Beta distribution is mainly used to model the distribution of random proportions such as the proportion of defective items in a shipment. Therefore it is the most appropriate among the standard probability distributions to use in conjonction to our model. Furthermore, it is a very general distribution that can take various shapes according to its parameters. Therefore showing that assumption (1) holds for all Beta distributions (with a > 1 and b > 1) and for all practical service level 7y is sufficient for all practical reasons to justify the validity of assumption (1). Our goal is to find the highest value y* for which assumption (1) holds for a > 1 and b > 1, i.e to find *= Max{a'>l,b>l} -F[a b] } If 7* is reasonably high then we are done. In practice, typical values of 7y range from 0.9 and above and it would be encouraging for the usefulness of the model to obtain a* below this range. y* occurs when a = 1 and b is very large, thus lim F 1 -limfl b (1 _-u)b- du b-o [l +b 6oo B(1, b) b+l I iim bl1 - u)I+b lim u) 10 b-+oo b = b +1 [1( b )bl 1-li im +b) = 1-exp-1 0.64 7* - 0.64 is by no means a restrictive value, hence assumption (1) is valid. 18

5 Examples Suppose that the density of the yield rate U is given by aua- if 0 < u <1 f (u) = (33) I0 otherwise which is a special case of the Beta distribution for b = 1. We are interested in the cases when a > 1. Solving the set of equations in lemma (1), we get for k = 1,..n - 1 r — [(a+)(1)(-^ (34) Solving the set of equations in lemma (2), we get for k = 1,.., n - 1 kn-k-1 1, pk = { k }(rw)(35) Ei=O 1[+aj J and lim = 1 {(+ a (36) n —+oo a. Note that 7/_ 1 = 1-. This is due to the fact that in a two periods problem, the unconstrained optimal policy is linear as can be seen in figure 1. Hence proposition (5) and (7) are identical in a two periods problem. However this will not be the case for k < n - 2. Consider for example a three periods problem, that is k = n- 2. Proposition (4) states that Q*-2 (I-2) = 0 for In-2 > 3d and proposition (5) states that Qn-2 (In-2) = (3d -In-2)/rln-2 for d + y < In-2 < 3d where 7n- 2 is given by (34). Moreover, proposition (8) states that _n-2 (In-2) is convex and proposition (7) states that Q (T) _ i n-2 (n-2) if In-2 > y2 = d-{,iI2 otherwise 19

where y2 < d + yl is given by d - Y2 Qn-2 (y2) = F-1 [1 ( 7) Finally, by proposition (7) we have that lim_-2.o dQn-2 (I-2) /dIn-2 =!3n-2 where /3n2 is given by (35). Figure 4 shows a plot of the optimal policy for a three periods problem. In a three periods problem, -l/rn*_2 is the'limiting slope' of the portion of the optimal policy comprised between d + Yi and 3d, while -1//3n2 is the'limiting slope' of the portion of the optimal policy comprised between Y2 and d + yl. When the planning horizon is larger than three periods, say four periods, -l/1773 becomes the'limiting slope' of the portion of the optimal policy comprised between 2d + Yi and 4d, and -1//3_3 is the'limiting slope' of the portion of the optimal policy comprised between y3 and d + Y2. We want to get an expression for the'limiting slope' of the portion of the optimal policy comprised between d + y2 and 2d + yl. We denote this'limiting slope' by -1/(n2. Consequently, T7 n _3 -* 71 n- 3 3 -2 7*1 13_n- - /Tn-2 and 3_-1 = tn7-1 -7 r/7l However, before doing that we would like to get an expression for J-2 (In-2), the value function for a three periods problem. By proposition (4), equations (18), (19), (20) and (24), it is differentiable everywhere except at In-2 = 3d and convex. It is given by 0 In-2 > 3d *1 (m-2) d + yj <InI <:3d Jn-2 (In-2}= ( = Y2 2 d+y_ Jn-2((n_2) Y2 < In-2 d+Y1 Jn 2(In-2) In-2 Y2 where lim dJ'L2 (In-2) F [n] F [nIn,_2 —oo dIn_2 F-l [1 - 7] 20

li dJ-2 (In-2) [ 2(1 + p) in-2 —c0 dIn-2 F-1 1 -- ] lim im dJ3-2(I-2) (1+P+p2) In-2-00c dIn_2 F-1 1 [-] and where limd_2,_oo dJn22 (In-2) /dIn-2 is obtained from (26) and is given by lim im J_2 — ~~ n 2 (I~-n) lim- f (u)du n dJ2 (I-) f m-2-Q [d ( In-)]( In-2 —00C dIn2 Jo In-2 —-o dI_-1 (1+ p) -2 f (u) d [dF -2 ] (1 + p) F-1 [1-] oF- [1 J- () We now return to determining -1/72_3, the'limiting slope' of the portion of the four periods problem optimal policy comprised between d + Y2 and 2d + yl. Setting (13) to zero we get for d + y2 < In-3 < 2d + y1 2d+ yl In-,3 *J72 / T \ 1 dJn-3 (In-3 Qn-3) Qn-3 n (In) uf (u) du + n-3 L. dIn-2 J(u) 4d- In3 rd*l (In-2 -Q-3 dJ - 2 (I2) u(u) du = 0 (39) Qn-3 Therefore Q_-3 (In-3) for d + Y2 < In-3 < 2d + Y1 solves (39). Hence 2d+y -In rn (I2) 1 +O Z-3n-3 3(In3) lim dn d 2 (In-2) 10 In-3 -00L dIn_2 J n-d dJ,2 (In.2) -1 => uf (u) du= -{ limi ud (u I ] ]J F [?n- 2] (1 + P) For the specific yield rate distribution defined in (33), we get for a four periods problem, i.e. for k = n - 3: 1k { l ~i- 1 -[ t) 1 for j = 1,..,n-k (40) 21

Figure.5 shows the optimal policy for a four periods problem. It can be shown that (40) is true for 1 < k < n - 4. Furthermore, it can be shown that for a general distribution we have for n > 2, k = 1,..,n -1 and j = 1,..n -k: ok jf0 u (u) du= A+3 (41) where f+ uf (u)du ^k+l *j ffk+ f (u) du and 3j _ F-1 [1 - 7] A(n-j+ 1 pi Naturally, (41) reduce to (40) when the yield rate is distributed as in (33). Table 1 provides a way to interpret the output of (41). The number of demand periods n increases vertically and Ik, the beginning of period k inventory level in a n - k + 1 periods problem, increases from left to right. 7ri are the limiting multiplicative coefficients obtained after solving (41). Next we present numerical examples to illustrate (40) (example 1,2,7,8,9,10) and to illustrate (41) using a Beta distribution with more general parameters (example 3 to 7, 11 to 18) for n > 2, k = 1,.., n - 1 and j = 1,..,n - k. These numerical examples will provide us insights on the impact of the two state variables, namely the number of demand periods and the beginning of period inventory, on the optimal release quantity that must be decided upon at the beginning of the planning horizon. The examples will be for n = 8 and y = 0.95,0.99. The following are tables that list rjk for k = 1 to 7 and j = 1,..,8-k. 22

7 6 5 4 3 2 1 0.3122499 0.55879325 0.74752475 0.86459516 0.92983653 0.9642895 0.98217189 1 0.3122499 0.55879325 0.74752479 0.86459598 0.92985425 0.96466162 2 0.3122499 0.55879331 0.74752621 0.86462892 0.93057204 3 0.31224996 0.55879544 0.74758317 0.86596432 4 0.31225234 0.5588806 0.74989421 5 0.31234752 0.56234133 6 0.31622777 7 Table 1: a =, b =1 =0.95 0.14106736 0.37558935 0.61285345 0.78284957 0.88478787 0.940632 0.96989964 1 0.14106736 0.37558935 0.61285345 0.78284958 0.88478856 0.94070531 2 0.14106736 0.37558935 0.61285346 0.78285079 0.88492647 3 0.14106736 0.37558936 0.61285536 0.78309486 4 0.14106737 0.3755917 0.61323756 5 0.14106912 0.37606031 6 0.14142136 7 Table 2: a = 1, b= 1 y = 0.99 0.467986 0.664428 0.786323 0.860675 0.907152 0.93708 0.957045 1 0.467986 0.664428 0.786323 0.860675 0.907161 0.937404 2 0.467986 0.664428 0.786323 0.860688 0.907658 3 0.467986 0.664428 0.786345 0.861471 4 0.467987 0.664463 0.787613 5 0.468042 0.666552 6 0.471280 7 Table 3: a = 2, b = 2, 7 = 0.95 23

~~7 6 5 4 3 2 1 0.340313 0.577729 0.733404 0.828249 0.886711 0.923812 0.948049 1 0.340313 0.577729 0.733404 0.828249 0.886711 0.923859 2 0.340313 0.577729 0.733404 0.82825 0.886784 3 0.340313 0.577729 0.733405 0.828366 4 0.340313 0.57773 0.733596 5 0.340314 0.578041 6 0.340745 7 Table 4: a = 2, b= 2, - = 0.99 0.515613 0.679584 0.778068 0.840332 0.881982 0.911109 0.932367 1 0.515613 0.679584 0.778068 0.840332 0.881988 0.911411 2 0.515613 0.679584 0.778068 0.84034 0.882411 3 0.515613 0.6795848 0.77808 0.840957 4 0.515613 0.679604 0.779024 5 0.515647 0.681138 6 0.518224 7 Table 5: a = 3, b = 3, = 0.95 0.421832 0.623169 0.743767 0.818214 0.866944 0.900463 0.924418 1 0.421832 0.623169 0.743767 0.818214 0.866944 0.900504 2 0.421832 0.623169 0.743767 0.818214 0.867002 3 0.421832 0.623169 0.743768 0.818299 4 0.421832 0.623169 0.743901 5 0.421833 0.623391 6 0.422195 7 Table 6: a = 3, b = 3, y = 0.99 24

7 6 5 4 3 2 1 0.69091667 0.88404674 0.95975064 0.98639941 0.99544578 0.99847999 0.99950063 1 0.69091667 0.88404674 0.95975064 0.98639946 0.9954469 0.99850263 2 0.69091668 0.88404674 0.9597508 0.98640279 0.99551461 3 0.69091669 0.88404719 0.95976051 0.9866041 4 0.69091774 0.88407402 0.96034825 5 0.69098066 0.8856992 6 0.69479831 7 Table 7: a = 2, b = 1 7 = 0.95 0.53073826 0.80964281 0.93203271 0.97681065 0.99220968 0.99739647 0.99913292 1 0.53073826 0.80964281 0.93203271 0.97681065 0.99220973 0.99740102 2 0.53073826 0.80964281 0.93203271 0.97681078 0.99222332 3 0.53073826 0.80964282 0.9320331 0.97685091 4 0.53073827 0.80964381 0.93214798 5 0.53074023 0.80994324 6 0.53132928 7 Table 8: a = 2, b= 1 = 0.99 0.83454507 0.95578993 0.98875937 0.99717792 0.99929373 0.99982342 0.99995661 1 0.83454507 0.95578993 0.98875937 0.99717793 0.99929388 0.99982646 2 0.83454507 0.95578993 0.9887594 0.99717853 0.99930601 3 0.83454507 0.95579004 0.98876178 0.99722692 4 0.83454547 0.95579926 0.98895372 5 0.83457767 0.9564164 6 0.83717359 7 Table 9: a=3, b = 1 = 0.95 25

7 6 5 4 3 2 1 0.73163798 0.92485588 0.98066012 0.99512956 0.99878016 0.9996949 0.99992387 1 0.73163798 0.92485588 0.98066012 0.99512956 0.99878017 0.99969551 2 0.73163798 0.92485588 0.98066012 0.99512959 0.9987826 3 0.73163798 0.92485588 0.98066022 0.99513929 4 0.73163799 0.92485624 0.98069848 5 0.73163913 0.92500058 6 0.73209597 7 Table 10: a = 3, b = 1 y = 0.99 0.166643 0.320559 0.466781 0.586955 0.680147 0.751112 0.805766 1 0.166643 0.320559 0.466781 0.586956 0.680177 0.752055 2 0.166643 0.320559 0.466782 0.586996 0.681419 3 0.166643 0.32056 0.466833 0.588619 4 0.166645 0.320619 0.468889 5 0.1666995 0.32300 6 0.16892 7 Table 11: a = 1, b2, y=0.95 0.0723905 0.20334 0.358563 0.499123 0.61235 0.699536 0.765922 1 0.0723905 0.20334 0.358563 0.499123 0.612351 0.699676 2 0.0723905 0.20334 0.358563 0.499124 0.612534 3 0.0723905 0.20334 0.358565 0.499358 4 0.0723905 0.203342 0.358844 5 0.0723914 0.203621 6 0.0725771 7 Table 12: a = 1, b = 2, y = 0.99 26

7 6 5 4 3 2 1 0.11351 0.223525 0.334649 0.432939 0.515482 0.583731 0.640885 1 0.11351 0.223525 0.334649 0.43294 0.515510 0.584677 2 0.11351 0.223525 0.33465 0.432974 0.516657 3 0.113511 0.223526 0.33469 0.434356 4 0.113511 0.223569 0.33631 5 0.113549 0.225319 6 0.115094 7 Table 13: a =, b3 = 3,y = 0.95 0.0486773 0.139141 0.251609 0.360300 0.454725 0.53533 0.598713 1 0.0486773 0.139141 0.251609 0.360300 0.454726 0.533664 2 0.0486773 0.139141 0.251609 0.360301 0.454884 3 0.0486773 0.139141 0.25161 0.360488 4 0.0486773 0.139142 0.251818 5 0.048678 0.139339 6 0.0488038 7 Table 14: a = 1, b = 3, y = 0.99 0.639767 0.806498 0.891131 0.936216 0.961579 0.97644 0.985472 1 0.639767 0.806498 0.891132 0.936216 0.961582 0.97658 2 0.639767 0.806498 0.891132 0.936222 0.961817 3 0.639767 0.806498 0.891141 0.936629 4 0.639767 0.806516 0.806516 5 0.639804 0.807943 6 0.64263 7 Table 15: a = 3, b = 2, y = 0.95 27

7 6 5 4 3 2 1 0.534911 0.752826 0.863585 0.921244 0.953021 0.971369 0.982324 1 0.534911 0.752826 0.863585 0.921244 0.953021 0.971389 2 0.534911 0.752826 0.863585 0.921244 0.953055 3 0.534911 0.752826 0.863585 0.921304 4 0.534911 0.752827 0.863697 5 0.534912 0.753046 6 0.535333 7 Table 16: a = 3, b = 2, y = 0.99 0.352983 0.522535 0.642144 0.725568 0.785254 0.829266 0.862966 1 0.352983 0.522535 0.642144 0.725568 0.785265 0.829778 2 0.352983 0.522535 0.642144 0.725584 0.78595 3 0.352983 0.522536 0.642167 0.726525 4 0.352984 0.522569 0.643501 5 0.353029 0.524492 6 0.355664 7 Table 17: a = 2, b= 3, 7 = 0.95 0.251065 0.444668 0.587941 0.687579 0.757849 0.808896 0.847109 1 0.251065 0.444668 0.587941 0.687579 0.757849 0.808966 2 0.251065 0.444668 0.587941 0.68758 0.757944 3 0.251065 0.444668 0.587942 0.687711 4 0.251065 0.444669 0.588131 5 0.251066 0.444939 6 0.251399 7 Table 18: a = 2, b= 3, y = 0.99 28

All examples show that rk are converging rapidly with the planning horizon. Using this and the fact that limn_ rj1- = 1, then one might suspect that the long run effect of adding one more period is quickly reached especially in the vicinity of low values of beginning of period inventory. Therefore the effect on the optimal policy of adding one more period when inventory is low.is simply increasing the release quantity by an amount equal to that period demand. True, this is a result of no holding cost considerations. However, the model is not intended to be used in infinite horizon situations. We are modelling finite horizon situations and holding cost considerations are not important in such cases, especially when the optimal policy is converging rapidly as suggested by the numerical examples. To get a feel how fast the optimal policy is converging, consider equations (40) for k = 1. We have I )(n-j) rl1 r( i =) (I - -y) \} ( r "*J= r{ [() -a] }for j =,..,n -1 (42) -- 1- -"+a' As n increases, the effect of adding one more power dominates the effect of adding one more term to the sum in the denominator that converges rapidly especially for large values of a. Thus r7l approximates 773 + i l - (1 - a) a (-j 771 {(l + )} } forj = 1,..,n- 1 (43) This is shown in tables 1, 7 and 9 where each row becomes identical to the row below it except for one additional term close to 1. How large is the error in the optimal values of the release quantities when holding cost is considered and exactly how long should the planning horizon be for the holding cost effect to'kick in' and truncate the forecast horizon are the topics of an ongoing research. Other useful observations in the numerical examples are that the optimal release quantities increase with the service level, increase as the distribution is skewed to the left as seen in tables 9, 15, 5,17 and 13, and increase with the variance of the yield rate as seen in tables 1 through 6. 29

6 Conclusion We have analyzed a multiple periods service level constrained model of a production system with random yield in a finite horizon setting. The objective was to determine the optimal release quantity in the current period, given a certain inventory level, that minimizes the total input quantity throughout the planning horizon while keeping a high probability of meeting the demand in each period. We have showed that under the mild assumtions of the model, the reorder point in any period is equal to the total remaining demand in all future periods (including the current period) and that in any period, we release a quantity higher than the amount that brings our inventory up to the total remaining demand in all future periods. Furthermore, we showed that the optimal policy is convex with the initial inventory level and that there exists in each period a value of the initial inventory level below which the service level constraint is binding. Although there is no simple way to compute the optimal policy, we derived expressions for the limiting slopes of various portions of the optimal policy in each period. These limiting slopes provide us insights on the impact of the yield rate distribution, the service level, initial inventory level and the addition of another demand period as was shown in the numerical examples. Future research involve the study of the effect of holding cost on the optimal release quantity in a finite horizon setting, and determining infinite horizon policies in the presence of holding cost. References 1. Bertsekas, D. (1987), Dynamic Programming: Deterministic and Stochastic Models, Prentice-Hall. 2. Gerchak, Y., M. Parlar and R. G. Vickson (1986) Periodic Review production Models 30

With Variable Yield and Uncertain Demand, HIE Transactions, 20, 144-150. 3. Karlin, S. (1958) Steady State Solutions, In Studies in the Mathematical Theory of Inventory and Production, K. J. Arrow, S. Karlin and H. Scarf, Stanford University Press, Stanford, Ca. 4. Karlin, S. and H. M. Taylor (1975), A First Course in Stochastic Processes, Academic Press. 5. Lee, H. L. and C. A. Yano (1989) Lot Sizing With Random Yields: A Review, Technical Report 89-16, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor. 6. Lee, H. L. and C. A. Yano (1988) Production Control in Multistage Systems With Variable Yield losses, Operations Research, 36, 269-278. 7. Sepehri, M., E. A. Silver and C. New (1986) A Heuristic for Multiple Lot Sizing for an Order Under Yield Variability, HIE Transactions, 63-69. 8. Singh, M., C. Abraham, R. Akella (1990) Planning for Production of a Set of Components when Yield is Random, IEEE Transactions on Comp., Hybrids, and Manufacturing technology, 36, 359-367. 9. Tang, C. (1990) Composing Batches With Yield Uncertainty, Operations and Technology Management Working Paper #7-90, The John F. Anderson Graduate School of Management, University of California, Los angeles. 10. Yao, D. (1988) Optimal Run Quantities for an Assembly System With Random 31

Yields, IE Transactions, 20, 399-403. 32

|yI +(1-k)d y + (2- k)d y) + (n-k-3)d y, + (n - k -2)d y + (n- k-)d #of <k<1 < I1k <sIk< k demand y2 + (2-k)d Yn-3+(3 - k)d y2+(n-k-2)d y, +(n-k-)d (n-k+ )d PeodS *(n-1) (n-2) *3 2 1 l ll ll l I n (n -2) 3 2 1nqf2 q~ q12 12 12n*3 * 2.1 qn-3'n3 n-3 4 *n-2 n-23 Tabl 1n-1 2 Table 1: limiting multiplicative coefficients. for n > 1, k=l,..,n-1, j=l1,..,n-k

Qn-l(In-l) n- l(In-l) Service level constraint d- Iri\ I I I,_1 n- l Id 2d n n1, d 2d Yn-1 d 2d y-1 d 2d Figure 1: Optimal policy Figure 2: Value function for a 2- periods problem for a 2-periods problem when E[U] F-l[ - ] when E[U] - F-[ - ]

Qk(Ik) Service level constraint d-Ik F\ 1[1-y] Slope -1/ k ISlopea\,\\ Slopes-1 _Y-__k(-k+)Ik Yn-k (n- k + l)d Figure 3: Optimal policy for a (n - k + 1) periods problem

service level constraint d-In-3 \/ F- [1I-y] -1 limiting slope= *3 fln-3 n-3 -1 < \ ---- lim ^iting slope = *2 In-3 Y3 d+Y2 2d+y1 4d Figure 5: optimal policy in a 4 - periods problem Q-2(In-2) d-In 2 n-1 limiting slope = 2 ln-1 slope = -l* -'I ~ \ I~'~ I^^^^~ In-2 Y2 d+y1 3d Figure 4: optimal policy in a 3- periods problem

UNIVERSITY OF MICHIGAN 11111111 111111111111 11 311111114 3 9015 04735 3647