RELEASE CONTROL POLICY FOR A PRODUCTION SYSTEM WITH RANDOM YIELD Walid R. Abillama and Medini R. Singh Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 92-30 May 1992

Release Control Policy for a Production System with Random Yield Walid R. Abillama Medini R. Singh Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 May 1, 1992 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 and propose a lower and an upper bound on the optimal release quantity. We discuss the conditions under which these bounds are tight in a finite horizon setting, which leads us to the special case of the uniform distribution of yield. We also show that the upper and the lower bound converge to the optimal policy as the planning horizon increases. Finally we assume that material is discounted as time goes on and show that in this case the optimal release policy is myopic. 1 Introduction We consider the problem of releasing a quantity of a certain kind of raw material at the beginning of each of n periods in a single stage production system. We assume the demand to be deterministic and known for the entire planning horizon, and the production outcome to be a 1

random fraction of the input release quantity. Upper management requires that the demand be met in each period with a prespecified confidence level. Any unmet demand is backlogged and becomes due the next period. The objective 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 achieving 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 when it comes to solving such problems. It implies that we are interested in finding an optimal rule for choosins 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 periods while keeping a high probability of meeting the demand in each period. 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 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 2

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 proving 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 derive lower and upper bounds on the optimal release policy, we discuss the conditions under which these bounds are tight in a finite horizon setting which leads us to the special case of the uniform distribution of yield in section 6. We also show in section 5 that the upper and lower bound converge to the optimal policy as the planning horizon increases. In section 7 we discuss the discounted case, show that the optimal release policy is of the extended myopic type and determine an upper bound on the forecast horizon. We conclude in section 8 by proposing some new directions for research. 2 Terminology and Formulation In this section we define the terminology that we will 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 a. More specifically, the service level constraint in any period k is defined as: P[Ik + UQk -d >O] > (1) 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> ]> a 3

=> Qk > F-1i[ (2) Let 6 be the discount factor with 0 < 6 < 1 and Jk (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(1). For a general period k, P(k) is formulated as follows: J (Ik) = Min Qk + 8E [J+l (Ik+l)] Qk> d-Ik P (k) S.t. F-l[l-c if Ik < d Qk > 0 if k > 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 6 -discounted expected amount of material that might be released in the following n - k periods given the beginning of period on-hand inventory Ik+l, 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 lead time is less than one period and as a result, the relationship between the state variables Ik and Ik+l is nothing but: Ik+l = 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 + 6f J +1 (1k + uQk -d) f (u)du 0 1P(k) s.t. Qk > F-l[l-k] if Ik < d Qk > 0 if Ik > d We will first assume that 6 = 1, that is we will assume that raw material does not devaluate as time goes on. We will analyze the optimal finite horizon policy in this case. Next (keeping 6 = 1) we will derive lower and upper bounds on the optimal release policy in a finite horizon problem. Lastly we will assume that 6 < 1 and find out the effect of discounting on the optimal release policy. 4

3 Structure of the Optimal Policy 3.1 First Period Policy With J*+. (In+l) = 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 (In) = Min Qn d-In fl. <d P(n) s.t. Qn F- [l-a] fn Qn > O if In > d The optimal solution to problem P(n) is given by: d-InQJ{n < d Qn (I, ) y,* (In) {F-[1-l] ifIn < d Q* - * Jn - (4) 0 if In > d note that Q* (In) and Jn* (In) are convex functions. Convexity of these two functions in subsequent periods will be a key argument for proving our results for general horizons. 3.2 Second Period Policy We would like to solve P(n-1), our first task is to obtain an expression for the value function Jn (In-i + UQn-1 - d). Such an expression is obtained by substituting In in equation (4) by its expression in equation (3). Doing this we get: F2d-[1 i if U < Min (1 2d-1n) Jn (In-1 + UQn-1 - d) = F' [-] Qn-1 (5) 0 otherwise Since U lies between 0 and 1, we therefore identify from equation (5) 3 cases in the second period problem, depending on the value of In-i: In-i > 2d, d < In-l < 2d and In- < d. In the rest of this section, we will analyze each case in order to conclude about Q*_1 (In-1) and Jn*l (In-i). 5

3.2.1 Case I (In_1 > 2d ) Here, equation (5) gives Jn (In-i + UQn_1 - d) = 0 and hence P(n-1) becomes Min Qn-1 s.t. Qn-i > 0. Therefore as expected, no release should ever take place in a two periods problem (J-1 (7In-i) = Qol- (In-i) = 0) if the on-hand inventory at the beginning of the current period exceeds the total demand in both periods. 3.2.2 Case II (d < In-I < 2d) The service level constraint is still not active in this case since In-i > d. However, after substituting equation (5) in P(n-l), the objective function is no more described by the same function for all non-negative values of Qn-1. Mathematically, P(n-1) becomes: 2n-1 Jn- (I Min Qn-i + 2d- In - uQn- f (u) du F-1 [1 -] where f 1 if 0 _ Qn-1 < 2d- In-1 1n- = 1 2d-nn- 1 ni 2d-n- if Qn-1 > 2d - In-l The objective function of P(n-1), Jn-i (In-i), is the sum of two functions. It suffices to show that both functions are convex to conclude that Jn-1 (In-i) is a convex function. While Qn-i is clearly convex, we therefore only need to show that the second function, which is nothing but E [Jn (In-1 + UQn-i - d)], is convex. In fact, if 3n-i = 1, then d2E [Jn (In-1 + UQn-1 - d)] - Jn J(.) E [U2] dQ2 d()2.ince J" i \;- rr~n~r~v rr~m ~nii~t~r~n /2d-ln then since J* (.) is convex from equation (4). On the other hand, if 1n-l = Q -l then +n-1 dE [Jn (In-i + UQn- - d)] dJ uf (u) du dQn-i d(.) 0 6

since Jn (d) = O. Hence since d < 0 and dv7nj- < 0. As a result, Jn-i(In-i) is convex. next, we differentiate d(.) - d/n-1 - Jn-i (In-l) with respect to Qn-1 to find the minimum. Doing this we get: On-1 dJn[1 (In-1) 1- U _f(u) du dQn-l "1 I F-1 [ -a]f(')d 0 Therefore we conclude the following: E [U] < F-1 [1- a] < Qn (In = 0 and E[U] > F-' [1 - a] Q_1 (In- ) solves the following integral equation: Pn-1 uf(u)du = F- [1 - a] (6) 0 where * = n2d1-l < 1. Call the solution to equation (6) Q 1 1n (n-i), then Q 1 (In-) = 1 (2d - In-) where n-l is a function of only a and F. Furthermore from equation (6), we can write n-i F-[1-~] uf (u)du = F-1 [1 - a] > uf (u) du 0 0 The last inequality stems from the fact that: fuf(u)du = zF(z)-fF(x)dx 0 0 F-1 [1-a] F-' [1-ct] f uf (u)du = (1-a) F- [1-a]- f F (x) dx 0 0 < F-1[1-a] Therefore we can write: = F-1 [1- a] < /?-_ < 1 (7) This latter result will be used in case III. Assumption 1: E [U] > F-' [1- a] 7

For the time being we will neglect the case when E [U] < F-1 [1 - a] since it is reasonable to assume that the service level will always be high enough so that E [U] > F-1 [1 - a] will always be true. In the next section, we will show that this assumption holds for all practical yield distributions and service level ca. 3.2.3 Case III (In_- < d) As mentionned above, the service level constraint becomes active in this case. Recalling that Q-1 1 (In-) is the optimal solution to the unconstrained problem and using the result in d-In-1 equation (7), the optimal order quantity becomes nothing but F-[l-~] for In,- < Yn-l and ~2Fl[-2F-1ci]di Q1 1 (In-l) otherwise, where Yn-1= -P _ F-'[1-cl] d is the unique solution to the equation 1_ d- Yn-1 Qn1l (Yn-1) = i (2d - Yn-i) = -1 -] (8) Pt* F-1 [1- a] A plot of the optimal order quantity versus the initial inventory in a two periods problem is shown in figure 1. 3.2.4 Properties of the Value Function Before ending this section on the second period policy, we would like to study the properties of the value function of the second period problem since these properties will be useful in carrying the analysis for the third period policy. We shall denote the value function by J1 1 (In-1) for Yn-1 < In-i < 2d, and by J2 (In-i) for In-i < Yn- (In-) is obtained by replacing Qn-i by Q11 (In-l) in the objective function of P(n-1) as defined in case II for Qn-i > 2d-In_1. Doing this and differentiating JnlI (In-1) with respect to In-_ we get: - d 1- _ _ ___n __ (u)du dJ,-(In-1) - dQ (In-1) 13 1-[1 f (u)du dIn-1 -- din- 1 - F-1[1-[la] [1 + u dn_1 f u dQ*l (In-i) [ n- U ____ d —n -1 [ F — - 1- F- F- [1-c] 0 _, 8

Therefore from equation (6) we can write dJnL (In-i) [F [n-1i] dln-i F-1 [1 - a] (9) Jn2 (In-i) is obtained by replacing Qn-1 by Fl[1 in the objective function of P(n-1) also as defined in case II for Qn-i > 2d - In1. Doing this and differentiating J21 (In_) with respect to In-i we get: dJn2 1 (In_) 1 dIn-i F-1 [1 -ca] 2d-In-1 F-1.[l-] j - F(1 -F a]) f (u)du (10) o~~~~~~~~~~~~~~~~~~~~~~~~~~. The following are properties of Jn21 (In-1): ^dJnl (In-1) dJ2 (In_,l) a) dJ(In-1 dJnl( - 1) at In-1 =- n-1 -b) d2j- -n — > 0. c) lim — 00dJ2 1(In-1) 1 + c)Mlim/n-l_1_~o d/n-1 -- F-1[1-,] F-1[1-c] (1 -F- [i-_]) f(u) du. Property a is true from equation (8) since 2d nF- 1 [1- a] = -1 d - Yn-1 Property b falls by differentiating equation (10) one more time and property c falls directly from equation (10). A plot of the value function versus the initial inventory of a two periods problem is shown in figure 2. 3.3 General Period Policy Suppose that for a general n (n > 3) periods problem, the optimal release quantity at the beginning of period i + 1 (n - 2 > i > 0) is defined as follows: 9

0 Qi+l (hi+i) Qi+ (Ii+i) Ii+1 > (n - i)d Q*+l (Ii+i) = [n - (i + 2)]d + Yn-l < Izi+ < (n - i) d [n - (i + k + 1)]d + Yn-k < li+l < [n - (i + k)] d + Yn-(k-l) ifk = 2,., n-(i + 1) Ii+l < yi+l (11) Qi+l (I+l), k = 1, 2,..., n - (i + 1) is the unique solution to 1 + / d (.) J= r/(+l) (12) where 7iq+1 - (n-i)d-Iil Qi+ Q [n-(i+j)]d+Yn-(j -1)- Ii+ Qi+l 0 if j= 1 if j = 2,..., k if j = k+ 1 and (n-)d-Ii+ 1l [n-(ti+j)]d+Yn-(j-l)-Ii+ Qi+1 if j = 1 ifj =- 2,..., k *j = li+l (13) 0 if j = k + 1 and Yn-k is the unique solution to QnIk (Yn-k) d - yn-k F-1 [1 - a] (14) 10

Furthermore, let the value function be such that 0 Ii+l > (n - i)d J*+1 (+,) [n - (i + 2)] d + Yn-1 < Ii+l < (n - i)d J+l (Ii+) = Jil (Ii+l) [n - (i + k + 1)] d + Yn-k < Ii+l < [n - (i + k)] d + Yn-(k-1) if k = 2,.., n-(i + 1) 1I J*-i) ( Ii+1 < Yi+i (15) where JP1 (Ii+) let: is a continuous, differentiable and convex function, for i+1 < (n - i) d. Finally dJi 1 (Ii+1) _ 1+ F [;'] (16) d (1i+1) F-1 [1 -a] and (17) Yn-k,] fim dJkl, (i+l,) I F- [ J1; - if k = 1,2,..., n - (i + 1) lim d1 — -- -i-1 - fk[1 -h.+i^-oo dhi+l:_o- if k = n - i F-1[1- 1-c where F-l [1- ] p = 1+ (- F- [1- ]u)du 0 (18) and fik-= lim rk V k = 1,..., n-(i +1) J 7 --- - oo (19) Before showing that the optimal release quantity at the beginning of period i is also defined as in equation (11), we would like to study some properties of the optimal release quantity Qi+ (Ii+,) as defined in equations (11). We do this in the following set of propositions. 11

Proposition 1: Q*i+ (hi+1) that solves equation (12) uniquely is a convex function in the interval where it is defined in equation (11). Proof: The proof is by induction. For k = 1, we get 1 + d (.) f () 1~ f T1d(.) uf(u)du=0 (20) From equations (13) and (16), the unique solution to equation (20) is clearly a linear, hence a convex function, for Ii+i < (n - i) d and therefore in the interval where it is defined in equation (12). now suppose that for k = m, the unique solution to equation (12) is a convex function in the interval where it is defined in equation (11). That is suppose that the unique solution to the following equation is a convex function for [n - (i + m + 1)] d + Yn-m < h1+i < [n - (i + n)] d + Yn-(m-1) m i dJ*j3( 1+E d(.) uf(u)du =0 (21) =1 *0+1) We would like to show that this is also true for k = m + 1, i.e. that the unique solution to the following equation is a convex function for [n - (i + m + 2)] d + Yn-(m+l) < i+4 <~ [n -(i + m + 1)]d + yn-m *3 m+l d/ * 3 1+E 7 J+2 ()f(u) d =O (22),(j+i) 77,+1 From equation (21) we know that the second derivative of the solution to equation (22) is non-negative at i+1 = [n - (i + m + 1)] d + Yn-m since 7 = 0 at that point and thus equation (22) reduces to equation (21). Furthermore, it is clear that the solution to equation (22) is a linear function only when Ii+l approaches -oo, since lim + =- lim dQ+l =k 1,.., m + 1 I+1i-'-oo i,+ - -oo di+ ai 12

and therefore equation (22) reduces to 3*(m+l) + Pi m dJ*(m+) ( ) 1d+ lim uf(u)du = 0 (23) Ii+I-oo d(.) whose unique solution results in Qj 1 +l) (Ij+1) being a linear function, since the integrand is independent of Ii+1 from equation (17). Therefore the unique solution to equation (22) is convex for Iji+ < [n - (i + m + 1)] d + Yn-m, and hence in the interval where it is defined in equation (11). Proposition 2: Qi+1 (Ii+l) as defined in equation (11) is a continuous convex function, differentiable everywhere except at Ii+l = Yi+l Proof: The proof falls directly from Proposition 1 and the fact that at Ii- = [n - (i + k)] d + Yn-(k-l) Vk = 2,.., n - (i + 1), we have from equations (12) and (13) that i (+) Q*(k-1) (dQ_(Ii~i) dQj' (h+- ) ( l ) (li+l) and hence ddhI(+) =,+dl ( at that point. On the other hand, at Ii+1 = Yi+1, we have from equation (14) that Q*(n-(i+l)) (Yi+) = d - Yi+1 F+ -1 [1 - a and therefore Q*+l (Ii+1) is continuous at that point, but the derivative at the right of that point is not the same as at its left. We will show later that it is actually greater or equal. The next step is to show that the optimal release policy in period i is also defined as in equation (11). That is, we would like to solve P(i) defined as follows: J (Ii) = Min Qi + E [Ji+1I (Ii + uQi - d)] d-L if I<d P(i) Qi F-[1_] if i d Q. > 0 if Ii > d We would like to solve P(i), our first task is to obtain an expression for Ji*+ (Ii + uQ - d). 13

Such an expression is obtained by noting that JP1 (Ii+i) is defined as in equation (15). As a result, Ji+ (1i + uQ2 - d) is defined differently depending on the yield realization in period i. More specifically in P(i) we get: j+ 1(-) (i + UQi - d) if U < Min (1, t-i)) ^Ji~ (7i + uQ. -d) =,| Ji1kj (Ii + uQ -d) if Min (1, k+l) < U < Min (1, 24) for k = l,..,n-(i+ 1) 0 otherwise we therefore identify from equation (24) n - (i - 1) cases in P(i), depending on the value of Ii the beginning of period on-hand inventory (The last case arises when the service level constraint becomes active.): a) Ii > [n- (i- 1)] d b) [n - (i + l)] d + yn-_l < i < [n - (i- 1)] d c) [n-(i+k)]d+yn-k < Ii < [n - (i + k - l)] d + yn-(k-l) Vk = 2,., n - (i+ 1) d) d < Ii < d + yji+ e) Ii < d 3.3.1 Case a Here, equation (24) gives Ji+1 (IJ + UQi - d) = 0 and hence P(i) becomes Min Q, s.t. Qi > 0. Therefore as expected, no release should ever take p eriod i problem (Ji* (I) = Q (Ii) = 0) if the on-hand inventory at the beginning of the current period exceeds the total demand in all future periods. 14

3.3.2 Case b Similarly to the second period policy, P(i) becomes: 1 J* (Ii) = Min Qi + f Ji1 (Ii + Qi - d) f (u) du o I Ji1 1 (Ii + 21Qi - d)], The objective function of P(i), Ji (I?), is the sum of two functions. It suffices to show that both functions are convex to conclude that Ji (i) is a convex function. While Qi is clearly convex, we therefore only need to show that the second function, which is nothing but E [J+l (Ii + UQi - d), is convex. In fact, if ri7 < 1, then.1 dE [Jl.1 (Ii + UQi - d)] = dJi1 (.) E + dQ = dJ (.) uf (u) du dQi d(.) since JTl ((n - i) d)= 0 from equation (15). Hence the second order derivative is also non-negative if > 1 () is convex next, we differentiate Ji (Ii) with respect to Qi to find the minimum. Doing this we conclude the following: n-1 E [U] H F [jl] < F-1 [1 -a] Q (Ii) = (25) j=l+i and E [U] HnI+ F _I ] > F' [1 - a] < Q' (In-2) solves the following integral equation: uf (u)du = F-1 [1 - ] (26) 0 Hj=l+iF [P1] where rl =I [n-(i-1)]-i < 1. Call the solution to equation (26) Q1 (Ii), then Qi' (Ii) = 1[n - (i - 1)] d - Ii where rjl1 = /3,1 is i a function of only and F. Therefore if we can show that equation (25) can never occur, then we would have shown that Q'1 (Ii) is the same as in 15

equation (11). We do this in the next proposition. Proposition 3: E [U] ln-1+i F [l'] > F-1 [ - a] Proof: Recall that we assumed that Q*+1 (Ii+i) is obtained from equation (11), i.e. that 1-= +F-1 [1 -a] uf(u)du = F - 1a] (27) =2+ [n;21] therefore it must have been that E[U] F-'[1 - c] E [U] l Therefore what we need to show is that for tI31 < 1, we have 1i+1 f uf(u)du E[U] > Al (28) o ~~ - -1 (28) 3*1+ f f (u)du 0 Moreover, the inequality is satisfied as equality for I*? = 1. Therefore it is sufficient to show that the first derivative of the right-hand side of the inequality is non-negative and we are done. In fact: 3*1.t*1 dAl+1 0 0 dl t+ln(.+ l) "f f(Udu-f(0l) r uf(u)du *d1l - - *1 ]]2 [F[1 [F [1]].1 f(, ) f (,+,1-u)f(u)du = r rR o >0 Thereforef we have shown that Q'* (i) is the same as in equation (11). The next set of propositions result in properties of Q (Ii) V i = 1,..., n - 1, in terms of?1. UIVIVIIVLLUU1V I) YIV~~UIL~ V1 L~Si.)Iir VLIIIO VI z 16

Proposition 4: H3i1 are unique solutions to the following set of equations: P*1 uf (u) du = Al+i for i - 1, 2,...n-1 where A = F- [1 -a] 0 Proof: It is true for i = n - 1 from equation (6), (where _ n- -/ n 1) and true for a general i from proposition 3. Proposition 5: F-1 [1 - a] < flI1 _< ~n12 <.. 1. Proof: It is true for i = n - 1 from equation (7) and it is easy to see that for i < n - 1, /3:*^1 /~i+1 uf (u) du = Ai+1 J uf (u) du = f1 > 3i+1 0 0 and limno p31 = 1. Therefore, Assumption 1 is sufficient to establish that in period i, for [n - (i + 1)] d + Yn-i < Ii < [n - (i - 1)] d, we must release a quantity larger than [n - (i - 1)] d - Ii (we say we are overproducing). By the end of this section on the General Period Policy, we would have shown that the optimal release quantity in any period is convex in the beginning of period on-hand inventory, hence releasing up to the total demand in all future periods is a lower bound on the optimal release quantity. 3.3.3 Case c In this case, P(i) becomes for k = 2,.., n - (i + 1): k *J Ji (Ii) = Min Qi + E f J+ (I +uQ-d) f (u)du j=lf,(+i) Similarly as in Case b, the objective function of P(i), Ji (I), is the sum of two functions. It suffices to show that both functions are convex to conclude that Ji (Ii) is a convex function. 17

While Qi is clearly convex, we therefore only need to show that the second function, which is nothing but E [Ji*1 (Ii + UQi - d)], is convex. In fact, V k = 2,.., n - (i + 1). if ir < 1, then dQ Z dJ+ $ uf(u)du (29) j-1 (3+1) since a) r/!j+l) appears as the upper bound and as the lower bound of two consecutive integrals and we assumed that the value function is continuous for Ii+i < (n - i) d in equation (15), and b) Jt+1 ((n - i) d) = 0 from equation (15). Hence the second derivative becomes nothing but: d2E [J +1 (Ii + UQi - d)] k d2Ji+l ( ) dJ*l ) l d dQ2 =,+Z I d()2 uf (u) du + -f() rji - > 0 s=1 a + ). since a) r1j+l) appears as the upper bound and as the lower bound of two consecutive integrals and we assumed that the value function is differentiable for I+.1 < (n - i) d in equation (15), d2 *J() b) -t.+- > 0 since we assumed that the value function is convex for Iji+ < (n - i) d in equad(.) 2 tion (15), and c) dJ*1 < 0 from equation (16) and d~- < 0 by definition. Clearly the second d(.) - dQ0t - order derivative is also non-negative if q,! > 1. The same argument applies if for some j > 1, we have r7i > 1. As a result, J (Ii) is convex. i I 1-. l~r ) )C ~, dJ, 't Q~ - [. - (i- 1)] dNext, we need to find the optimal order quantity Qi (Ii). Consider d^f) at Qt = [n - (i - 1)] dIi. Since Ji (Ii) is convex in Qi, then if and only if we can show that the derivative at this point is negative then the optimal order quantity Q* (Ii) is the unique solution to the objective function of P(i) for ri = [n-(i-1)]d-I, which is nothing but equation (29) added by 1. Qi k t dJ ( 1+ d(J ()uf(u)du= (30) j=1.+1) 77. In fact, at Q = [n - (i - 1)] d - Ii, we get: dJ,(I,) = k1I1 + t(u)d r+1 d () (+) dQ, 1 = 2. f d(.) d(.) uf(u)du (+1):2 t/[+~ r /i 18

1 dJ*1 ( < 1 + f -. uf (u) du since we assumed that Ji*+ (Ii+1) is a continuous, 0 differentiable and convex function for Ii+1 < (n - i) d n —1 F\, 1I = 1- nl~[l_=] E[U] < O from Proposition 3 Call the solution to equation (30) Qtk (Ii). The following are properties of Q*k (Ii) V k = 2,..,n- (i+ 1): a)dQ (I-')(z') dQ.(I,) a) d I= ' at i = [n - (i + k- 1)] d + Yn-(k-l) dl- dl b) -h — > 0. c) Letting = limi,_go - = limi_-ood then /k solves the following equation: equation' u0 i + l..+..- oo d (.) j 0 d - F-1 [1- a] n-lF+i F [;k] k-1o p *=1+.=0 2 Pj= I from equation (17) (31) Property a is true since we assumed that Ji+1 (Ii+1) is a continuous and differentiable function for Ii+1 < (n - i) d, property b is true from proposition 1 and finally property c falls by taking the limit of equation (30) as Ii - -oo. 3.3.4 Case d In this case, P(i) becomes: *3 n- Ji (i) = Min Qi + j=l *(j+i) 77( Ji+l (i + uQi - d) f (u)du 19

To show that Ji (Ii) is convex, we use the same argument as in case c but for k = n - i. By the same argument, we conclude that Q? (Ii) solves -t d* +1 j (. ( 1 + -^ I (u) d = 0 (32) 3=1 *0 + 1)d(.) 74 Call the solution to equation (32) Qt(ni) (Ii). The following are properties of Q (n-i) dQ\ dQ_ [ _ S __ i. r _ J. a) d-(+ ))(I) d I at Ii d + Yi+l dli - d a d2Q;("-')(I.) b) Q ( > 0. c) Letting 11 = limi-oo -1- = lim('e -, then -(i) solves n-i r) d the following equation: /* d/iJ uf (u)du = - lim dJi+ J +l —+-oo d(.) 0 F-1 [1- a] = - [,+) ] from equation (17) (33) -n- (i+1) pJ _.j=O p Property a is true since we assumed that J*+1 (+i)i is a continuous and differentiable function for Ii+1 < (n - i) d, property b is true from proposition 1 and finally property c falls by taking the limit of equation (32) as Ii -oo. 3.3.5 Case e As mentionned above, the service level constraint becomes active in this case. Recalling the properties of the unconstrained optimal solution Q* (Ii) in section 3.3.4, the next question that we would like to answer is whether there exists a value for Ii below which the service level constraint becomes binding. We answer this question in the following proposition. 20

Proposition 6: 3*(n i) > F1 [1- a]. Proof: From equation (33), we can write p*(n-i) f uf (u)du 0 = F1 [1- a] [Z-1= 1 ([ ( - F1l[lo]) f(u) du o L i~~~~~~~~~3 F-' [1-a] ) > F-1 [1 - a] E~=o f 1 - - ) f (u)du 0 [- = aF-1 [1- a] + F-'[1-a] I uf(u)du 0,*(n-i) F-[-a] F-l[1-a] uf (u)du > aF-1 [1 - a] /*(n-i) > F-1 [1 - a] Therefore, the optimal order quantity becomes nothing but -Ji for Ii < yi and Q (Ii) otherwise, where yi is the unique solution to the equation Q*(n-i) (i) = d- yi i (y.) F-' [1- ca] (34) We have thus proved that QT (Ii) is defined as in equation (11). A plot of the optimal order quantity for P(1) versus the initial inventory is shown in figure 3a for a four periods problem where the point of intersection between the service level constraint and Q3 (I1) is denoted by yl. The next task is to show that this optimal policy implies a value function Jt* (Ii) defined as in equation (15). We do this in the next section. 21

3.3.6 Properties of the value function J7 (Ii) = 0 in Case a. We shall denote the value function by J.jl (7I) for Case b, J1*k (7i) for Case c, d and e for k = 2,..., n - (i - ). J*1 (Ii) is obtained by replacing Qi by Ql' (Ii), given in equation (26) in the objective function of P(i) as defined in case b for Qi > [n - (i - 1)] d - Ii (i.e. Tl1 < 1). Doing this and differentiating Jj1 (Ii) with respect to Ii we get: dl = d l F11 [l J+] J u)Lu Using equation (26) and the fact that 3*1, (1. J*k (Ii) for k = 2,..., n-i is obtained by replacing Qi by Q..k (Ii) in the objective function of P(i) as defined in case c for Q2 > [n - (i - 1)] d-Ii (i.e. Ti]} < 1). Doing this and differentiating j7*k (Ii) with respect to Ii we get: dI (d()1 + J dJ* uf (u) du " l f(u)du ddIj F - Ij^ -aT F-1 d1-a( dj'=() + i ) F0+)l F dli^) F-1 [1 - Jt] The () following are properties of ( i) for k = 2, for Q [n - (i - 1) d I adj,* (I,) dQJ; k (~I,) k d)i*dd = $(i+ '( + * + +(1) which, from equations (30) and (32), becomes: dli - dl d (.) f() d u J*+3 Ef (u) du a) dJ(k-)Ii) -- IdJ k i) at Ih = [n - (i + k - 1)] d + Yn-(k-l)' di dli 22

b) lim~i,-. tdJik(I) = _ n2, F[;k]Zk= pJ b) dli - F- [1-a] 2)dja(I,) C) > 0. Property a is true since rk = 0 for k = 2,...,n - i, Property b is true from equations (13) and (17) and Property c is true by the same argument that the derivative of equation (29) is non-negative. Finally, J(-(( -1)) (i) is obtained by replacing Qi by F-[1-] in the objective function of P(i) as defined in case d for Qi > [n - (i - 1)] d - Ii (i.e. l) < 1). Doing this and differentiating J^(n-(i-1)) (/I) with respect to I/ we get the following properties of,*(n- )) (I)' a) L d- l at 1, ) i n -3 b) limi,__-oo --- 7 = F-l-] d2 j*(n-(i-1))(Ii c) dI > 0. Property a is true since rT1(n (i1)) 0, Property b is true from equations (13) and (17) and Property c is true by the same argument as Property c for k < n - (i - 1). We have just shown that the optimal policy defined as in equations (26), (30), (32) and (34) implies a value function Ji' (Ii) defined as in equation (15). 4 Discussion 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 a. Assumption 1 can be rewritten as a > 1 - F [E [U]]. Consider the Beta distribution with parameters a > 0 and b > 0, whose density is given by: {a-l 1_(lZb-l if 0 < < 1 f(x) otherwise 0 otherwise 23

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 proving that Assumption 1 holds for all Beta distributions (and for all practical service level a) is sufficient for all practical reasons to justify the validity of the Assumption. Our goal is to find the highest value a* for which the Assumption still holds irrespective of the values a and b. If this value a* is reasonably high then we are done. Typical values of a range from 0.9 and above and it would be very useful to obtain the sought after a* below this range. To find out the value of a*, we will take the limit of 1 - F [E [U]] as E [U] approaches 0. For the case of the Beta distribution where E [U] = -, it is the limit of ( )a 1-F [ a as b becomes very large compared to a, or equivalently the limit of 1-F [-] as b approaches infinity. For the particular Beta distribution corresponding to b = 1, this limit can be computed easily. It is the limit of (b —) as b approaches infinity, which is nothing but e-1. Therefore it suffices that a be larger than e-1 for our Assumption to hold! However, when a = b clearly a should be greater than 0.5 for our assumption to hold, which is greater than e-1 and which violates our previous result. Intuitively, a value of b that is very large compared to a would lead to a distribution skewed heavily to the left, therefore inciting for the release of large quantities even if the beginning of period on-hand inventory in multiple periods problem is relatively large. On the other hand as the values of a and b becomes equal, or even better as a becomes very large compared to b, the yield distribution becomes skewed to the right. As a consequence of this fact, only relatively large values of a (surely larger than 0.5) would require that some quantity be released when the beginning of period inventory in a multiple periods problem is relatively large. Therefore what we should actually check is the limit of 1- F -[a as a becomes very large compared to b, or equivalently the limit of 1- F [-a] as a approaches infinity. For the particular Beta distribution corresponding to a = 1, this limit can be computed easily. It is the limit of 1- (a-) as a approaches infinity, which is nothing but 1-e'1. Therefore it suffices that a be larger than 1 - e-1 for our assumption to hold. a* = 1 - e1; 0.64 is by no means a restrictive value, hence Assumption 1 is valid. 24

5 Bounds on the optimal policy We are now ready to derive a lower and an upper bound on the optimal release policy based on the properties derived in section 3. 5.1 Lower Bound From propositions 2, 5 and 6, a lower bound on the optimal release quantity at the beginning of a finite horizon problem of n periods is the following: LB (Q (I1)) = 0 ifil > nd Q*1 (I1)_ =d-I1 f ify < IInd Frd- Ilc <if I < y F-11[1-ce]I where yl solves Q1 (y;) = F-l5.2 Upper Bound For a finite horizon problem of n periods, we found in section 3 that Q* (I,), the optimal release policy at the beginning of the planning horizon (i = 1), is a continuous function for i, < nd, and differentiable everywhere in this range except at II = yi. Furthermore, we found that the limiting slope of Q*k (11) for k = 1, 2,..., n - 1, -~ = - im _ 1oo - i, solves equations (26), (31) and (33). Finally in proposition 6, we showed that the service level constraint is binding for 1, < yl. As a result, an upper bound on the optimal release quantity is defined as: 0 11 > nd Q ik (I) ) UB (Q*k (I1)) UB (Q* (1I)) = (n- 2)d + Yn-i < /+1 < nd [n - (k + 1)] d + yn-k < I1 < (n - k) d + Yn-(k-1) ifk = 2,..,n- 1 (36) I1 < Yl 25

where UB (Qk (1,)) is a line with slope v-1 and yk solves equation (14) fork =,..., n -. Figure 3b depicts the upper bound for the case of n = 4. We are interested in computing the coefficients gk for k = 1,..., n -1 and a certain n. By the same arguments as in propositions 3, 4 and 5, we compute the coefficients 3lk for k = 1,..., n - 1 by rewriting equations (31) and (33) as: Prk uf (u)du = +(37) 0 where A =IF —l = I ', i=,..., n - k, which implies that n-(k-1) k1 Fk-1[- a] < k < < < k....< Ik < < 1 and lim -k = 1 Vk Ej=o P3 n-O In order to compute /?k for a certain n and k, we need to solve equation (37) for i = 1,...,n - k. As n approaches infty, 3;k approach 1 for any finite k. Therefore for large inventory levels and large planning horizons, the upper bound and the lower bound will merge together to result in an optimal policy that calls on releasing up to the total demand in all future periods. However, since the lower bound on the release quantity will approach infinity for any finite inventory level as the planning horizon increases, therefore the optimal policy will be one in which we release the most we can and release again in the next period after a demand d is withdrawn. Clearly from renewal theory, the long run average amount of material released per period in this case will be Add independently of the amount of quantity released at the regeneration point (release point). Therefore the infinite horizon problem is trivial, and thus we will restrict ourselves to the finite horizon case only. We would like to find under which conditions are these bounds tight. Clearly, for i = 1 and a finite horizon n we have F-1 [1 - a] < 3;(n-1) <.... < 32 < f31 < 1 and lim?1 = 1 Vk n — oo is obtained by solving equation (37) for i = 1 and k = n - 1. The solution to this 26

equation implies that F-1 [1- a],(n-l) t - (1 - p) F-1 [1 - a] < F -A < - 1 < 1 Ej-o - Therefore the closer is (1 - p) F-1 [1 - a] to 1, the tighter are the bounds. Substituting for p and making further manipulations, we get F-1 [1-ca] c- = F-1 [1 - a] - F (x) dx < l(n-1) < 1 The shaded area in Figure 4 represents To. Clearly the closer is Ha to 1, the tighter are the bounds. At the limit, as 'I!a approaches 1, the yield density becomes concentrated at 1 and the finite horizon problem becomes trivial. When this happens, our finite horizon bounds merge and our optimal release policy is one in which we release up to nd - I. We are interested in situations where a, is not close to 1. Such cases can arise when either the yield rate density is concentrated at some low value, or when the yield is highly variable. If the yield rate is concentrated at some low value, then production losses due to low yield can be compensated by scaling the production quantities suitably. In practice, it is the yield variability that causes yield to have a disastrous effect on production decisions, therefore we may assume that the yield density is distributed with a high variance. It is from that perspective that our model is useful, in that it provides a means for making sequential production decisions in the presence of highly variable random yield. Consider for example the Beta distribution who is widely used to model the distribution of random proportions such as the proportion of defective items in a shipment. We are interested in the bell-shaped class of Beta distribution (a > 1, b > 1) plus one other special Beta distribution: the case when a = b = 1 which is nothing but the uniform distribution. Any other values of the parameters a and b would result in a very unrealistic yield distribution. Luckily, the variance of the uniform distribution is larger than for any Beta distribution whose parameters a > 1 and b > 1. The next question that comes to mind is the following: How good are the upper and the lower bound that we just proposed for a finite horizon problem, in case of a highly variable yield whose distribution is uniform between 0 and 1? In the next section we shall focus on the uniform distribution and consider numerical examples to compute the worst 27

case error between the upper and lower bounds. It is easy to see that the worst case error occur at the point where the lower bound intersects the service level constraint, namely yj. 6 Special Case: the Uniform Distribution If the yield rate is uniformly distributed, then in an n periods problem, we get from equations (26), (31), (33) (assume i = 1 to denote that the decision is being taken at the beginning of the planning horizon) and for k = 1,..., n - 1: xk= 2(n-*'"k-)1 -c) 1 = (I (38) As can be seen from equation (38), flk converges faster for a high service level as the plannning horizon increases, V k = 1,...,n - 1. Denote by R1 the ratio of the upper bound to the lower bound (see figure 3b for the case of n = 4). Then R1 is defined as: zn-1 d+Yn-(i-l)-Yn-i i=l 13BL R1 -- (39) nd-y[ P;1 where yn = d and yi = yj (not to be confused with yi defined as the intersection of the service level constraint with Q(1) (II)). Therefore for a > 0.9, /31 can be treated as constant for say n > 3 and can be approximated by /*ti l:2(n -/-) (40) Hence R1 will approach 1 as n increases since yi is finite for i = 1,....,n. The higher is a, the slower is the rate of convergence. To illustrate R1, we consider two numerical examples and compute R1 for n = 4 and a = 0.9, 0.95. Doing this, we find R1 to be 1.23 qnd 1.29 respectively. In other words, the worst case error is 23% and 29% for a service level of 0.9 and 0.95 respectively in the case of a uniformly distributed of yield between 0 and 1, in a 4 periods problem. In practice however, planning horizons are typically longer than 4 and the yield distribution has 28

a variance smaller than the uniform distribution since we usually possess a general idea as to where the density might centered, and consequently use a bell-shaped distribution to model the yield variability. Therefore, the suggested upper and lower bound provide a good approximation to the optimal release quantity. 7 Discounted Case (0 < 6 < 1) We would like to study the case when material is discounted as time goes on and determine an upper bound on the forecast horizon. The forecast horizon is defined as the number of future periods (including the current period) that we need to take into account in order to make a decision on the quantity released in the current period. To determine the forecast horizon, we will proceed with the same analysis as in section 3, i.e. using backwards recursion. We will do this until we arrive at a horizon length that will stop increasing as we continue on moving backwards and making decisions in the current period. Doing this for the first few periods, we observe that there exists a period i, i.e. a horizon n - (i - 1), for which Proposition 3 (in its discounted version) does not hold anymore. That is 6nT-i I F [p3] < E [1 (41) I=l+- E [U] Inequality (41) implies that it is not optimal in period i to release for [n - (i + 1)] d + Yn-1 < Ii < [n - (i - 1)] d and hence for (n - i)d < hi < [n - (i - 1)] d. It follows that in period (i - 1), it is not necessary to release for (n - i) d + Yn-I < 1i < [n - (i - 1)] d since the analysis for that period results in: n-(i-l) H F *1] <F ] 1+i Fl] — E [U] Therefore the condition that we need to check in this period turns out to be n-2 F-1 [1-a] 6n-i (1 + 8p)f F [fl2] FE[] (42) If inequality (42) is true, then it is not optimal to release in period i-1 for [n - (i + 1)] d+yn-2 < 29

li,- < (n - i) d+ Yn-l and our forecast horizon remains (n - i) periods. Otherwise, our forecast horizon increases by one period and we move to check if the following condition is true in period (i - 2): n-2 [ ] a- - l 6n-(i-l)(1 6p) ( 1 F [*2] <F (43) /=-i-1 - -E [U] Therefore there exists a period j < i, i.e. a horizon n- (j + 1) in which it is not optimal to release for Ij > [n- (j + 1)] d. 6n-(j+1) (1+ 6p) rI F [f*2] < F-[] (44) /=j+l ( 4 Continuing in this manner, one can see that there exists a period k < j < i, i.e. a horizon n - (k + 2) in which it is not optimal to release for Ik > [n - (k + 2)] d. n-3 F-1 [1 - a] n-(k+2) (1 + 6p + (6p)2) 1I F [ < E [1] <(45) I=k+1 E[U] Therefore the condition that we need to check in period k - 1 turns out to be 6"-(k+2) Z (6P)m I F [33 < 1 - a](46) m=O 1=k -E [U] If inequality (46) is true, then it is not optimal to release in period k- 1 for k-I > [n - (k + 2)] d and our forecast horizon remains (n - (k + 2)) periods. Therefore it is easy to see that an upper bound n* to our forecast horizon is the smallest n that satisfies the following inequality: bn 00 ^ m 6 F-1 [1 - a] 6n 1 (5sp)m = d/ <F [-a] (47) m=O 1 -p - E[U] Stated differently, we should never release any quantity if our beginning of period inventory exceeds n*d. Notice that when 6 = 1, inequality (47) is never satisfied since (1 - p) F-1 [1 - a] Ta < E [U] from figure 4. 30

8 Conclusion We have considered a multiple periods production system with random yield and deterministic demand. We used a service level constraint to model product shortages. There exists other types of service levels in which product shortages can be modeled. It would represent a valid direction for future research to study the effect of different types of service levels on the behavior of the optimal policy. For example, the line manager may be required only to satisfy a proportion a of the total demand of the whole planning horizon, as opposite to a proportion a of the demand in each period as considered here. In this case, he or she may find himself or herself doing so well during the first periods so that he or she would be able to shut the line at an early stage, rather than wait until the end of the planning horizon to do it. Another direction for future research may be one which involves multiple products as opposite to a single product as considered here. One in which researchers would study the dynamic interaction between yield rates of different components that must be present in the final set in certain prespecified proportions. Acknowledgements We wish to thank Izak Duenyas and Juhwen Hwang for their helpful comments, which have led to improvements in the exposition of this paper. References 1. Bertsekas, D. (1987), Dynamic Programming: Deterministic and Stochastic Models, PrenticeHall. 2. Gerchak, Y., M. Parlar and R. G. Vickson (1986) Periodic Review production Models With Variable Yield and Uncertain Demand, IIE Transactions, 20, 144-150. 3. Karlin, S. (1958) Steady State Solutions, In Studies in the Mathematical Theory of Inventory 31

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. Law, A. M. and W. D. Kelton (1982), Simulation Modeling and Analysis, McGraw-Hill. 6. 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. 7. Lee, H. L. and C. A. Yano (1988) Production Control in Multistage Systems With Variable Yield losses, Operations Research, 36, 269-278. 8. Sepehri, M., E. A. Silver and C. New (1986) A Heuristic for Multiple Lot Sizing for an Order Under Yield Variability, IIE Transactions, 63-69. 9. 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. 10. 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. 11. Yao, D. (1988) Optimal Run Quantities for an Assembly System With Random Yields, IIE Transactions, 20, 399-403. 32

Q'-I( l- ) J.-1( A-I ) d - I-I \ F-'(t-a) \ Service level constraint \ \ QlJ^_tJ Slope l -1 In-I Yn-1 d 2d ynFigure 1: Optimal order quantityfor a Figure 2: Vt two periods problem when twl E[U]> F4 (l-,a) F( x) a 1-a:-2( I _) in-I aluefunctionfor a o periods problem when E[U] F'(l - a) I x F' (I - a) Figure 4

Q;*(/) d-II F-\l(-a) ~~\ " ~ ~ Service level constraint \ I I I I Q;2(J,) < 1 I / I */:~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I (I) 1 I1 -~~~~~~~~ YI d+y2 2d 2d+y3 4d e;(,) \ K Figure 3a: Optimal order quantity vs initial inventory for i = 1 and n =4 d- 1 ^ ^ F-(1l-a) Service level constraint UBQ*(;',)] \ UB[Q] (I,)] II J1 I,) I, Yl y dd+y2 2d 2d+y3 3d 4d Figure 3b: Upper and lower bound on the optimal order quantity for i = 1 and n = 4