OPTIMAL FINITE AND INFINITE HORIZON POLICIES FOR SINGLE-STAGE PRODUCTION SYSTEMS WITH RANDOM YIELDS Candace Arai Yano Department of Industrial &Operations Engineering University of Michigan Ann Arbor, M1 48109-2117 Revised October 1989

OPTIMAL FINITE AND INFINITE HORIZON POLICIES FOR SINGLE-STAGE PRODUCTION SYSTEMS WITH RANDOM YIELDS ABSTRACT We analyze finite and infinite horizon problems for a single-stage production system with deterministic demands and variable yields. It is shown that under certain regularity conditions on costs and the yield rate distribution, the optimal policy is multiplicative. That is the optimal input quantity is a real-valued multiple of the net demand, and for each period the multiplier is independent of the inventory level. We provide sufficient conditions for existence of these multipliers. The conditions for existence are somewhat restrictive. It is shown, however, for the infinite horizon problem that an optimal multiplier exists under much milder conditions. We present computational results for a simple finitn e horizon example which show that the multipliers need not be monotonic as a function of time. We also present results to illustrate the differences between the optimal policy and a commonly-used heuristic procedure. KEY WORDS: Inventory/Production —Reject Allowances

OPTIMAL FINITE AND INFINITE HORIZON POLICIES FOR SINGLE-STAGE PRODUCTION SYSTEMS WITH RANDOM YIELDS INTRODUCTION Most production processes, unfortunately, do not make parts that are completely defect-free. As a result, questions often arise regarding how many parts to input to a process in order to satisfy a demand or a production target. Several variations of this problem for single-stage production systems have been studied to date. Karlin (1958a) shows that a single critical number policy is optimal (under certain mild conditions on costs) for the single period problem with no setup costs. He also derives (1958b) steadystate solutions for cases with specific demand distributions. Giffler ( 1960) addresses the single period problem with a binary penalty for shortage (not per unit, as in most other papers). Klein (1966) and White (1967) study scenarios in which a single demand can be satisfied using multiple production runs and develop associated solution procedures. Silver (1976) develops EOQ-based policies for inventory control under supply uncertainty. Shih (1980) finds EOQ-based production policies, and optimal policies for a single period when the yield rate (fraction acceptable) is invariant with the batch size. Sepehri, Silver, and New (1986) develop heuristics for finding lot sizes when a single demand can be supplied using multiple production runs with setup costs. Gerchak, Vickson, and Parlar (1988) address the finite-horizon problem with random demand and no setup costs, and have found that an order-up-to policy is not optimal. In a related paper, Henig and Gerchak (1988) also show that the finite-horizon dynamic programming value functions converge to the infinite horizon value functions. Mazzola, McCoy, and Wagner (1987) develop optimal and heuristic algorithms for the multi-period problem with setup costs. Their results indicate that heuristics in which lottiming is done first, and production quantities are set equal to yield-adjusted lot sizes, perform quite well. Other papers are reviewed in a survey by Yano and Lee (1989). We examine both the finite and infinite horizon problems with deterministic demands using a dynamic programming approach. There are a variety of circumstances where demands are deterministic, such as make-to-order situations and facilities supplying component parts to assembly facilities which operate at a constant pace. We show that under certain conditions, the optimal policy is multiplicative. That is, in each time period, there is a multiplier such that the optimal input quantity is the net demand multiplied by this multiplier. The results are extended to systems with time-varying costs and demands. We 1

also present results for the infinite horizon problem with constant demands and costs, and with stationary yield rate distributions. One can view our results as providing a relatively simple way of specifying optimal policies over multiple periods under certain conditions (on costs and yield rate distributions) when the lot-timing is already decided or when setup costs are sufficiently small that production runs in each period are economically justified. In addition, unlike some existing procedures, production rules can be specified without full knowledge of future demands (or where applicable, their distributions). Our procedure essentially requires only that demands to be satisfied in the imminent production run be known. This fact, in conjunction with the simple form of the operating policy, make the procedure very easy to implement, in contrast to the complicated procedures required to solve these problems optimally under general conditions. While these procedures cannot contribute directly to increasing the average yield rate or decreasing the variance, using such policies can help to reduce the amount of "fire-fighting" so that time and resources can be dedicated toward improving yields. In the next section we describe and analyze the finite horizon problem with constant demand, and present conditions for existence of optimal solutions. We then extend the results to the problem with time-varying demands. We subsequently study the infinite horizon problem. Results for a simple example are then reported. Finally, we present some conclusions. THE FINITE HORIZON PROBLEM The finite horizon problem has N periods, indexed n = 1,...,N. There is a known demand in each period and all shortages are backordered. Production and inspection are done in batches. It is assumed that all parts are inspected and that the inspection process is perfect. Since all demand must be satisfied eventually, we take the revenue stream to be essentially fixed. Our concern is that of minimizing the cost of meeting these demands. We assume that all defective parts are disposed at no additional cost. A variable cost is charged per unit of input, representing the cost of production and inspection, and a per unit inventory holding cost is charged on inventory remaining at the end of the period. A shortage cost per unit per period is charged, which reflects the cost of maintaining a backorder for one period. At a minimum, this would represent the opportunity cost of delayed revenue. It could also include the loss of customer goodwill due to the delay and the cost of paperwork (or computer work) associated with backorders. 2

For the last period in the horizon, the inventory holding cost and shortage cost are defined differently so as to reflect the true economics more accurately. The inventory holding cost in the last period is the salvage cost (cash flow out due to disposal). If the net salvage value is positive, this cost will be negative. The shortage cost in the last period reflects the revenue lost per unit for all unsatisfied demand at the end of the horizon. Thus, any deviation from the planned revenue is included as a cost. The objective is to minimize discounted expected costs over the horizon. We will assume that it is profitable to produce the product. We assume that the yield rate distribution is stationary over time, continuous, and twice-differentiable. By yield rate we mean fraction of the input quantity which is acceptable. We also assume that it is invariant with the batch size. This assumption is applicable either when the batch sizes are sufficiently large that small changes of the batch size do not affect the yield rate distribution, or when various factors (e.g., quality of the input material, environmental factors, equipment calibrations) tend to affect the entire batch in the same way. For simplicity, we initially assume that all costs and demands are constant over the horizon (except for the last period). Later we explain how the analyses can be extended to time-varying demands and costs. The following notation is used throughout the paper: N = number of periods in the horizon, w = variable cost per unit of input, h = inventory holding cost for periods 1,...,N-1, hN = salvage cost in period N, In = inventory available at beginning of period n, 7i = shortage cost per unit per period in periods 1,..,N-1, TN = shortage cost per unit in period N, d = demand per period, a = one-period discount factor, 0 < a < 1, P = yield rate (random variable), p = yield rate (actual), 0 < p < 1, f(.) = density of the yield rate, F(.) = cumulative distribution of the yield rate, Q p= input quantity in period n, and Qn (In) = optimal input quantity in period n given In. 3

Let us define Cn(In,Qn)= discounted expected cost for periods n,...,N if initial inventory in period n is In and the decision is Qn Cn(I) = minimum discounted expected cost for periods n,...,N = min Cn(In,Qn), and Qn Q*(In) = optimal value of Qn given In The dynamic programming recursion equations for d > In are: Cn(In,Qn) = wQn + f(d-In)/Qn (d-In - pQn)f(p)dp +h Jd.I)/Qn (PQn- d+In)f(p)dp + a l Cn+l (In + PQn - d)f(p)dp, n= 1,...,N-1 and CN(IN,QN) = WQN + 7N (d-IN)/QN (d-IN- pQN)f(p)dp + hN f(d (pQN - d + IN)f(p)dp. The cost functions represent variable production and inspection costs, expected shortage costs, expected inventory holding costs, and for n < N, the discounted expected cost in all subsequent periods. If d < IN, it is not necessary to produce. Since production costs are constant over time, and the yield rate distribution does not change with the input quantity, normally there is no incentive to produce earlier than necessary. We initially assume that this is true, but later develop conditions on costs which guarantee that Qn = 0 if d < In, n = 1,...,N. 4

The problem for period N (assuming d > IN) is to minimize CN(INQN) = QN + N Jd IN)/QN (d-IN - pQN)f(p)dp + h(N)/QN (PQN-d + IN)f(p)dp. The derivative with respect to QN is aCN(IN,QN)/DQN = - IN J(d-IN)/QN pf(p)dp + hN (dN /QN pf(p)dp and QN is the value of QN which equates this to zero. It is easily shown that CN is convex so QN is the unique global optimum. A condition for QN = 0 is aCN /aQN 2 0 for all QN > 0. If d < IN, this is true if w + hNE(P) > 0, or in words, if the variable production cost is greater than or equal to the salvage value of the expected good output. Recall that period N is the end of the horizon, presumably when the product is discontinued. Thus, this condition is not unreasonable. Indeed, if the condition is not satisfied, one would want to produce an infinite amount. Let N3 = (d-IN) /QN(IN), where QN(N) is the optimal value of QN given IN. By substitution into CN (IN,QN), we get CN (IN) = (d-IN)[(N + hN)F([N) - hN]. This is obtained by observing that if aCN /(aQN = 0, it must also be true that Q aCN /aQN = 0. A little algebra leads to the expression above. The reason that the variable cost term does not appear in the optimal cost expression is that it is implicit in the value of N. Note that F(PN) = 0 if IN 2 d, since (d-IN) /QN (IN) = -~~ when IN > d. Thus, this expression is valid even when IN > d. To be precise, however,we will separate the cases of IN < d and IN ~ d in the remainder of the paper. 5

Now IN = IN- + PQN-1 - d, so if QN-1 > 0 (because IN-i < d), we have CN (IN-i + PQN-1 - d) = (PQN- )[O(nn + hN)F(PN)- hN] if p < (2d-IN-l)/QN-1 (i.e., if the actual yield is such that IN < d). Otherwise CN (IN-1 + PQN1 - d) = hN(IN 1 - PQN-l - 2d). If QN-1 =0, we have CN (IN- - d) = (2d-IN l)[(7N + hN)F(PN) - hN] if IN-. < 2d. Otherwise CN (IN- - d)= hN(IN-1 - 2d). We can now write CN (IN-1 + PQN-1 - d) =- P [(:N + hN)F(N) - hN] if p < (2d - IN 1)/QN-1; otherwise CN'(IN-1 + PQN-1 - d) = hNp. where Cn1 denotes the derivative with respect to Qn. For In, n = 1,...,N-1 Cn(In,Qn)/aQn = w - J(d-In)Qn pf(p)dp + h (dI/Q pf(p)dp + ocl c *1 (In + pQn - d)f(p)dp. 6

Therefore aCN1 (IN-lQN-1)/aQN-1 = w - r d-IN-1)/QN-l pf(p)dp -a+hN ) - h] pf(p)dp (d-IN.-1)/QN-l - [(:N + hN)F(PN) - hN (2d-IN-/QN-l pf(p)dp + oa hN pf(p)dp = w + h E(P)- (t + h) J(d-IN-)/QN-1 pf(p)dp -a [(7N + hN)F(N) - hN] f(2d-IN-/QN-l pf(p)dp + a hN pf(p)dp. (1) (2d-INi)/QNl It is easily shown that CN-1 is convex in QN-1, and CN1 is strictly convex for QN-1 > 0. Therefore, if QN-1 > 0 is optimal, the optimal value of QN-1 satisfies the first order condition. Observe that the optimal value of QN-1 depends upon both d-IN.1 and 2d-IN.. As such, we cannot claim, in general, that there exists some N-1 such that QN- = (d-IN 1)/N —1 On the other hand, if we can guarantee that (possibly after some initial transient) In < d for all n, then aCN-l(IN-,QN-l)/aQN- = w - fd —IN-)/QN-1 pf(p)dp + h (1 )/pf(p)dp - a [(0N + hN)F(N)- hN] E(P)N -Oa [(R;N + hN)F(PN) - hN] E(P) 7

and the optimal policy would have the form QN-1= (d-IN-l)/PN- for some unique PN- 1 This would be true because (2d-IN1)/QN-1 would always be greater than or equal to 1, so the last term in (1) would vanish. For IN-1 > d, aCNj /QN l will be non-negative for all QN-1 2Oif w + h E(P) - a [(EN + hN)F(PN)- hN] E(P) 2 0. This condition is that the variable production cost plus the cost of holding the expected good output (fraction of a unit) is greater than or equal to the discounted expected saving from reducing the net demand in period N by the expected output. We also have CN-1 (IN-1) = (d - IN-1)[(: + h)F(fN-1)- h] + a (2d - IN-1) [(ON + hN) F(PN) - hN]. Repeating this process, we find that aCN.j (IN-,QNj)/aQNj = w - Jd-IN-j)/QN-j pf(p)dp +h (d )/QN pf(p)dp J(d-INj)/QN-j j-1 x ack [(t: + h)F(N-k)- h] E(P) k=l - a [(AN + hN) F(PN)- hN] E(P), j = 1,.., N-1 (2) and J CNj (IN-j) = X akl (k d- IN-j)[(n + h)F(N.j+k.l)- h] E(P) k=l + oJ [(j+1) d-IN.j][(i:N + hN) F([N) - hN] Both of these relationships can be proved by induction, but the proofs are straightforward so we do not include them here. It is also easy to show that CNj (IN-j QN-) is convex in QN-j for j = 0,..., N-, so the Q-j,. values are those which equate the first partial derivatives in (2) to zero. 8

If IN-j > d, aCNj/QN.j will be non-negative and Q.jwill be equal to zero if j-1 w + h E(P) - a(k [(4: + h)F(PN-k)- h] E(P) k=1 - Ca [(ON + hN) F(PN) - hN] E(P) > 0. (3) This says that the variable production cost plus the cost of holding the expected good output exceeds the discounted expected saving from reducing the net demand by one unit in period N-j+1 (i.e., the subsequent period) and all future periods. Thus, the condition in (3) can be fairly restrictive for short time horizons and high discount factors (a close to 1), where the effect of tN can make it optimal to produce in anticipation of demand in future periods. There are, of course, other constraints such as production or storage capacity, which might prevent this practice. It is also worthwhile to note that the condition (3) is essentially a condition of no speculative motive for producing and holding inventory. Hence, while it is restrictive in a purely economic sense, in concept, it is not substantially different from assumptions commonly made in the inventory literature. We will show later that this restrictive assumption applies only to finite horizon problems. The solutions would be relatively easy to find under the conditions that In< d for all n. The policy would be multiplicative in that CN is equal to the net requirement, d-In, multiplied by a factor 1/f3n. In the next section we develop and prove the sufficiency of conditions on F(.) that will guarantee In< d for all n. Conditions for Optimalitv of a Multiplicative Policy We need to develop conditions to ensure that (after some initial transient) In< d for all n. If one starts with b > d and condition (3) is satisfied, then the optimal policy would be to set Q = 0 until there is a positive net demand. One only needs to fmnd Qn from that point until the end of the horizon. Suppose that we have In < d for some n. Since In+1 = In + pQn - d, we need In + pQn - d < d or PQn < 2d - In 9

for all In < d. Now Qn = (d- In)/n so we need p(d-In)/3n < 2d- In or P < fn (2d - In)/(d-In). Let p = maximum achievable value of p and p = minimum achievable value of p. Since p is random, the inequality above holds only if p< 2,n(2d - In)/(d-In). (4) Since we do not know fn and In a priori, this relationship must hold for all possible Pn and In. We first investigate the value of (2d - In)/(d - In). This ratio is strictly increasing with In for In < d. Thus, one possible lower bound on this ratio can be obtained by taking the limit as In —> - oo. A tighter bound is obtained by observing that the worst case value of In < O (largest cumulative deficit) occurs when we set P = p and the observed yield rate in each period is p. If we start with IO = 0, a little algebra shows that this smallest value of In is n -d z (p- ) k k=l Taking the limit as n -> oo, we have lim In =-d(p- p)/[- (p- p)]. n -> coo Let r = p - e. Then (4) is satisfied by all In if P < fn (2-r) or Pn > f/(2-r) (5) which are obtained by appropriate substitutions. Clearly, (5) will be satisfied by all (3n if the right hand side is less than or equal to zero. This, however, is a rather strong condition. Observe that we must have 3n > e to ensure that we are not intentionally producing now for subsequent periods. This, in conjuction with (5), can be guaranteed if 10

or equivalently, p 2 p(2+p)/(l+).( (6) We must also impose the condition < 2p. (7) to ensure that we do not completely satisfy demand for the subsequent period by chance if we choose 3n =, and observe a yield of p. Thus, /(2-r) is constrained to lie within a particular range for each value of p. The range, plotted as a function of E, is shown in Figure 1. Recall that these conditions are sufficient, not necessary, and require no additional assumptions about the form of F( ), other than its domain of support. Thus, while they appear to be strong, in practice they may not be problematic. One of the reasons for such a strong condition is that a large number of backorders were allowed to accumulate so as to allow complete generality of our results. Yet, in practice, such a large number of backorders would not be permitted. Thus, much milder conditions would apply in practice. Indeed, it is possible to show (and it follows directly from the above arguments) that in the case of lost sales, we would have In 2 0, and the only condition would be (7), which many real-world yield rate distributions satisfy. Of course, if the 3ns are known, we can check the much milder condition in (4) instead. FIGURE 1 We have thus proved the following theorem: Theorem 1: If conditions (3) and (7) are satisfied, and either (a) there is complete backordering and p(2+p)/(1 +p) < p < 2, or (b) there is complete lost sales, the optimal policy has the form (d-In)/5n if In <d 0 otherwise where 0 < P3n 1. We should note that for the case of lost sales, the shortage costs must be modified to account for lost revenue. Throughout the remainder of the paper, we will assume that 11

the optimal policy has the form described above. We next derive conditions in which the Pn values are guaranteed to exist. Conditions for Existence of the B Values Simplifying (2) and equating it to zero, gives the first order conditions 3PN-j j-1 N pf(p)dp = {w + h E(P) - X ck [(l + h)F(PN-k)- h] E(P) 0 k=l - o [(7rN + hN) F(PN) - hN] E(P)}/(t +h), 0 < j < N-1 (8) and PN f pf(p)dp = [w + hNE(P)]/(N + hN). (9) To demonstrate that the On values exist, we must show that there is a value of On, 0 < An < 1, which solves (8) or (9). Two conditions on costs are needed: (i) w < NE(P), and j-1 (ii) w + h E(P) - X ak [(Xc + h)F(N-k)- h] E(P)- a [(EN + hN) F(3N) - hN] E(P) > 0. k=l The first condition ensures that it is profitable to produce the product. The second condition is a regularity condition on costs. Observe that the left hand side of (9) is less than or equal to E(P) for all ON. It is precisely equal to zero at =N = 0 and equals E(P) at [N = 1. Furthermore, it is monotonically non-decreasing in ON. Thus, for ON to exist, we only need the right hand side of (9) to lie between 0 and E(P). Obviously it is non-negative, so we need w + hN E(P) < (AN + hN)E(P) or w < tN E(P) which is, condition (i) above. We need to show that 3N 2 0, which is equivalent to showing that the term in braces in (8) is non-negative. This is the same as the condition in (3) which ensures that Q-j = 0 if Inj > dn-j. 12

If condition (i) is not satisfied, then a value of PN sufficiently large to satisfy the first order condition for period N does not exist. In other words Q* < d-In, and it is not profitable to satisfy demand. If condition (ii) is not satisfied, a value of PN sufficiently small does not exist and one would want to input an infinite amount. FINITE HORIZON PROBLEM WITH TIME-VARYING DEMANDS AND COSTS In the previous section, we discussed the necessary condition for optimality of a multiplicative policy, i.e., In < d for all n. When demands and costs are time-varying, somewhat stronger conditions are needed. The first condition is that there is no speculative motive for holding inventory: Wn + hn E(P) a c Wn+l (10) where the subscript indexes the time period. This says that it is more expensive to produce now and to hold the expected output than to incur the discounted cost of production in the next period. This condition is clearly needed to ensure that production quantities are limited, so that In < d.n The second condition relates to requirements on F (-) which are similar to those for the case of constant demand. We need In+l = In + PQn - dn < dn+l or pQn < dn + dn+l - In. Substituting Qn = (dn - In) /Pn, we have P < Pn (dn+l + dn - In)/(dn - In). (11) Suppose there is a maximum demand level, dmax, and a minimum level, dmin. Then, by taking the limit of In as n —>oo (as in the previous section) to obtain the smallest possible value of In, and noting that the right hand side of (1 1) is decreasing with dn and increasing with dn+l, it is easy to show that a lower bound on the right hand side of (11) is Pn {dmin [1 - (p- p)]+ dmax}/dmax Since we must have all p less than this value, and 3n 2 I, one of the conditions for In < dn for all n is 13

P < {dmmi [1 - (p - )]+ dmax}/dmax. (12) This condition imposes tighter restrictions on the range of p if dn fluctuates widely from period to period and is identical to (4) when dn = d for all n. As in the case of constant demand, we must also ensure that we do not intentionally produce enough to satisfy demand for two consecutive periods. Thus, we require that (p/ ) dmax < dmin + dmax (13) since otherwise we might choose Pn = 2 in a period in which demand is dmax and observe a yield of p, thereby satisfying demand in the following period if it happens to be equal to dmin. Under conditions (12) and (13), a multiplicative policy is optimal. To ensure that the [n values exist, we also require that (a) wN < 7N E(P) and N-1 (b) wn + hn E(P) > S ak'n [(;k + hk)F(fk)- hk] + aN-n [(EN + hN)F(PN)- hN]) E(P), k=n+ 1 n=1,..,N-1 which are time-varying equivalents of (i) and (ii) in the previous section. If all of the above conditions are satisfied, the optimal values of 3N satisfy PN-J j-1 j pf(p)dp = {wNj + hN E(P) - [(N-k + hN-k)F(PN-k)- hNk] E(P) 0 k=l - i [(nN + hN)F(PN)- hN] E(P)}/ (;N-j + hN-j), = 1,... N-1 and Npf(p)dp= [N + hN E(P)]/ (EN + hN). 0 14

INFINITE HORIZON PROBLEM We examine the infinite horizon problem with constant costs and constant demands. Here, the conditions on costs for optimality of a multiplicative policy are much milder than in the finite horizon problems, and they are discussed later in the section. To find the optimal solution for the first period in an infinite horizon problem, we can take the limit of (8) as N-> oo. We have (3P~,: ~0oo f pf(p)dp = {w + h E(P) - A ak [(a + h)F(p)- h] E(P))/(7 + h) 0 k=l where [ denotes the optimal infinite horizon value. Simplifying, we get f pf(p)dp = {w + h E(P) -[a/(l-a)] [(a + h)F(P)- h] E(P))/ ((t + h). (14) 0 The left hand side of (14) is monotonically increasing in 3 while the right hand side is monotonically decreasing in P. Thus, if two functions intersect, they intersect in a unique value of p. These functions will intersect if the right hand side is less than or equal to E(P) for some 0 < P < 1. Since the right hand side achieves its minimum at P = 1, let us consider this value of P. The condition for a unique optimal value of P to exist is {w + hE(P) - [a/(l-a)][(7 + h)F(P)- h] E(P)}/ (t + h) < E(P). Simplifying this, at 3 = 1 we get (1-a) w < x E(P). (15) This says that the opportunity cost of processing a unit in this period rather than next period (i.e., loss in terms of discounted cash flow) must be less than the shortage cost which would be saved from the expected output. In other words, this means roughly that it is profitable to produce. In general, this is a very mild condition. We next examine when Q = is optimal if I > d To find P, we must solve the first order condition 15

w + hE(P) - [c / (l-a)][([7 + h)F(3)- h] E(P) -(7i+h) J pf(p)dp=0. 0 Let us assume that it is possible to ensure I < d for the remainder of the (infinite) horizon, but that in the current period I > d. In this case P = (d-I)/Q < 0 for all Q 2 0, so the first derivative becomes w + hE(P) - [a / (1-a)] h E(P) > 0. Thus, one does not want to produce. Since this argument applies to all periods, the only economic condition necessary to ensure that I < d is condition (15). We can now state the result, which we have just proved above: Theorem 2: If conditions (6) and (7) are satisfied, and (1-a) w < x E (P), the optimal infinite horizon policy is ((d-In)/ if In < d 0 otherwise where the unique value of P satisfies (14). EXAMPLES To illustrate characteristics of the optimal multipliers, we present examples to illustrate two interesting results. We use a uniform yield rate distribution with E(P) = 0.90, p =.80, and p = 1.0 to facilitate computation. Consider a problem with w = 9, hn = 0.18 for n = 1,..., N-1, hN = -10, An = 0.2 for n = 1,..., N, nN = 18 and a = 0.98. The parameters were chosen to be consistent with a profitable product produced monthly, with no expected gain (or loss) due to salvaging the product at the end of the horizon. Using equation (9), we find AN = 0.80 and F(PN) = 0. Then, using equation (8), we find PN-1 = 1.0, N-2 = 0.991, PN-3 = 0.9986, EN-4 = 0.9996. It is already apparent that the N-j values need not be monotone. This arises principally because of the manner in which discounting affects the right hand side of equation (8). 16

The optimal value of f3 for the infinite horizon problem is approximately 1.0. The solutions for the infinite horizon problem appear to be converging toward this value quickly. It is interesting to note that the optimal solutions indicate that one should simply input the net demand. This arises in spite of the apparent profitability of the product. The discounted expected cost of the optimal solution is $49,000. Twenty-five simulation runs using a rule-of-thumb policy in which one adjusts production quantities for average yield losses give costs having a mean of $50,145 and a standard deviation of $371. While the two costs may not appear to-be significantly different, at least $44,100 of both costs is attributable to non-controllable production costs (i e, the infinite horizon cost of inputting just the stated demand in each period). Thus, using an optimal policy can reduce controllable costs considerably, and the difference between the optimal and rule-of-thumb policy is statistically significant in this example. SUMMARY AND DISCUSSION We have derived the form of optimal finite and infinite horizon policies for systems with variable yield rates and deterministic demand under certain conditions on costs and the yield rate distribution. The general form of the policy is - (dn-In)/n iif In < dn Q = 10 otherwise where (3n = 3 when the horizon is infinite. The policy is multiplicative in that the net demand is multiplied by a factor 1/f3n which is independent of dn and In. Setup costs can be incorporated in a heuristic fashion relatively easily. For an infinite horizon problem with constant demands and costs, we can determine a production interval using average yield rates and then set the time period for the production control problem equal to this interval. For a finite horizon problem, one can determine a lot-timing policy using average yield rates and yield-adjusted costs. Then, by scaling costs to reflect the length of the time periods (where appropriate), one can use the model with time-varying demands and costs to solve the production control problem. These are, of course, heuristics, but are simple to implement. Further work needs to be done to evaluate this proposed heuristic. Since McCoy, et al. have found that sequentially determining lot timing then lot sizes performs well, one might expect that a similar sequential procedure with optimal lot sizing (given the lot timing) would perform even better. 17

Additional work also needs to be done to incorporate uncertain demand. Some recent work along these lines has been done by Gerchak, et al. Unfortunately, the multiplicative property of the optimal policy does not extend to the case of uncertain demand. There are, however, many instances where demand over a finite horizon is firm or there is a deterministic production target in the current period. In these cases, the procedure outlined in this paper can be used to find optimal solutions since it does not require demand information beyond the current period. In addition, further research is needed to extend approaches for single-period, multi-stage systems (i.e., Lee and Yano, 1988) to multiple periods. ACKNOWLEDGEMENT The author gratefully acknowledges the support of the National Science Foundation under grant DMC-8504644. 18

REFERENCES Gerchak, Y., R. G. Vickson, M. Parlar (1988), "Periodic Review Production Models with Variable Yield and Uncertain Demand," IIE Transactions, 20 (2), 144-150. Giffler, B. (1960), "Determining the Optimal Reject Allowance," Naval Research Logistics Ouarterly 7 (1), 201-206. Henig, M. and Y. Gerchak (1988), "Structure of Periodic Review Policies in the Presence of Random Yield," Working Paper, Department of Management Science, University of Waterloo. Karlin, S. (1958a), "One Stage Models with Uncertainty," in Studies in the Mathematical Theory of Inventory and Production, K. J. Arrow, S. Karlin, and H. E. Scarf, Eds., Stanford University Press, Stanford, California. Karlin, S. (1958b), "Steady-State Solutions," in Studies in the Mathematical Theory of Inventory and Production, K. J. Arrow, S. Karlin, and H. E. Scarf, Eds., Stanford University Press, Stanford, California Klein, M. (1966), "Markovian Decision Models for Reject Allowance Problems," Management Science 12 (5), 349-358. Lee, H. L, and C. A. Yano (1988), "Production Control in Multi-Stage Systems with Variable Yield Losses," Operations Research, 36 (2), 269-278. Mazzola, J. B., W. F. McCoy, and H. M. Wagner (1987), "Algorithms and Heuristics for Variable Yield Lot Sizing," Naval Research Logistics 34 (1), 67-86. Sepehri, M., E. A. Silver, and C. New (1986), "A Heuristic for Multiple Lot Sizing for an Order Under Variable Yield," IIE Transactions, 18 (1), 63-69. Shih, W. (1980), "Optimal Inventory Policies when Stockouts Result from Defective Products," Inter. J. Prod. Res. 18 (6), 677-685. Silver, E. A. (1976), "Establishing the Reorder Quantity when the Amount Received is Uncertain," INFOR 14 (1), 32-39. White, L. S. (1967), "Bayes Markovian Decision Models for a Multi-Period Reject Allowance Problem," Operations Research 15 (5), 857-865. Yano, C.A. and H.L. Lee (1989), "Lot Sizing with Random Yields: A Review," Technical Report 89-16, Department of Industrial & Operations Engineering, University of Michigan, Ann Arbor, MI. 19

1.20 1.00 i 0.80 -P 0.60,- - - minp 4 — maxp 0.40 0.20 0.00 I 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Figure 1 Range of p as a Function of p

OPTIMAL FINITE AND INFINITE HORIZON POLICIES FOR SINGLE-STAGE PRODUCTION SYSTEMS WITH RANDOM YIELDS ABSTRACT We analyze finite and infinite horizon problems for a single-stage production system with deterministic demands and variable yields. It is shown that under certain regularity conditions on costs and the yield rate distribution, the optimal policy is multiplicative. That is the optimal input quantity is a real-valued multiple of the net demand, and for each period the multiplier is independent of the inventory level. We provide sufficient conditions for existence of these multipliers. The conditions for existence ae somewhat restrictive. It is shown, however, for the infinite horizon problem that an optimal multiplier exists under much milder conditions. We present computational results for a simple finite horizon example which show that the multipliers need not be monotonic as a function of time. We also present results to illustrate the differences between the optimal policy and a commonly-used heuristic procedure. KEY WORDS: Inventory/Production —Reject Allowances

For the last period in the horizon, the inventory holding cost and shortage cost are defined differently so as to reflect the true economics more accurately. The inventory holding cost in the last period is the salvage cost (cash flow out due to disposal). If the net salvage value is positive, this cost will be negative. The shortage cost in the last period reflects the revenue lost per unit for all unsatisfied demand at the end of the horizon. Thus, any deviation from the planned revenue is included as a cost. The objective is to minimize discounted expected costs over the horizon. We will assume that it is profitable to produce the product. We assume that the yield rate distribution is stationary over time, continuous, and twice-differentiable. By yield rate we mean fraction of the input quantity which is acceptable. We also assume that it is invariant with the batch size. This assumption is applicable either when the batch sizes are sufficiently large that small changes of the batch size do not affect the yield rate distribution, or when various factors (e.g., quality of the input material, environmental factors, equipment calibrations) tend to affect the entire batch in the same way. For simplicity, we initially assume that all costs and demands are constant over the horizon (except for the last period). Later we explain how the analyses can be extended to time-varying demands and costs. The following notation is used throughout the paper: N = number of periods in the horizon, w = variable cost per unit of input, h = inventory holding cost for periods 1,...,N-1, hN = salvage cost in period N, In = inventory available at beginning of period n, C = shortage cost per unit per period in periods 1,..,N-1, 1N = shortage cost per unit in period N, d = demand per period, a = one-period discount factor, 0 < a < 1, P = yield rate (random variable), p = yield rate (actual), 0 < p < 1, f(o) = density of the yield rate, F(o) = cumulative distribution of the yield rate, Qn = input quantity in period n, and Q~ (In) = optimal input quantity in period n given In. 3

Let us define Cn(In,Qn)= discounted expected cost for periods n,...,N if initial inventory in period n is In and the decision is Qn Cn(In) = minimum discounted expected cost for periods n,...,N = min Cn(In,Qn), and Qn Q(In) = optimal value of Qn given In The dynamic programming recursion equations for d > In are: Cn(In,Qn) = wQn + I (d-In)/Qn (d-In - pQn)f(p)dp + h (dIn)/Q (PQn - d+I)f(p)dp + lo Cn+ (In + PQ- d)f(p)dp, n= 1,..,N-1 and CN(IN,QN) = WQN + N (d-IN)/QN (d-IN- pQN)f(p)dp + hN d(PQN-d + IN)f(p)dp. The cost functions represent variable production and inspection costs, expected shortage costs, expected inventory holding costs, and for n < N, the discounted expected cost in all subsequent periods. If d < IN, it is not necessary to produce. Since production costs are constant over time, and the yield rate distribution does not change with the input quantity, normally there is no incentive to produce earlier than necessary. We initially assume that this is true, but later develop conditions on costs which guarantee that Qn = 0 if d < In, n = 1,...,N. 4

The problem for period N (assuming d > IN) is to minimize CN(IN,QN) = WQN + NJ (d -N)/QN (d-IN - pQN)f(p)dp + hNJ(di)/Q (pQN-d + IN)f(p)dp. N (d-IN)/QN The derivative with respect to QN is aCN(IN,QN)/aQ N = w - TN J(dIN)/QN pf(p)dp + hN f) Q pf(p)dp and QN is the value of QN which equates this to zero. It is easily shown that CN is convex so QN is the unique global optimum. A condition for QN = 0 is aCN /aQN > 0 for all QN > 0. If d < IN, this is true if w + hNE(P) 0, or in words, if the variable production cost is greater than or equal to the salvage value of the expected good output. Recall that period N is the end of the horizon, presumably when the product is discontinued. Thus, this condition is not unreasonable. Indeed, if the condition is not satisfied, one would want to produce an infinite amount. Let PN = (d-IN) /Q(IN), where Q(IN) is the optimal value of QN given IN. By substitution into CN (IN,QN), we get CN (IN) = (d-IN)[((N + hN)F(N) - hN1 -This is obtained by observing that if aCN /()QN = 0, it must also be true that Q aCN /aQN = 0. A little algebra leads to the expression above. The reason that the variable cost term does not appear in the optimal cost expression is that it is implicit in the value of 3N. Note that F(PN) = 0 if IN ~ d, since (d-IN) /QN (IN) = -~~ when IN > d. Thus, this expression is valid even when IN > d. To be precise, however,we will separate the cases of IN < d and IN 2 d in the remainder of the paper. 5

Now IN = IN 1 + PQN-1 - d, so if QN- > 0 (because IN-1 < d), we have CN (IN-1 + PQN-1 - d) = (2d-IN- - PQN-l)[@(n + hN)F(JN) - hN] if p < (2d-IN.1)/QN-1 (i.e., if the actual yield is such that IN < d). Otherwise CN (IN-1 + PQN- 1- d) = hN(IN- - PQN- l- 2d). If QN-1 =0, we have CN (IN-i - d) = (2d-IN. )[(0N + hN)F(PN) - hN] if IN < 2d. Otherwise CN (IN- - d)= hN(IN. 1- 2d). We can now write C (IN-1 + PQN-1 - d) = - P [(:N + hN)F(N) - hN] if p < (2d - IN-1)/QN-1; otherwise C (IN- + PQN-1 - d) = hNp. where Cn+1 denotes the derivative with respect to Qn. For In, n = 1,...,N-1 aCn(n,Qn)/aQn = w - (d-In)/Qn pf(p)dp + h d-I)/Q - ~~0 dn)n pf(p)dp + o Cn +' (In + PQn -d)f(p)dp. 6

Therefore aCN-(IN-1,NQN-I)/aQN- = w - 7 f(d-IN-1)/QN-1 pf(p)dp pf(p)dp (d-IN-.)/QN-l - a [(tN + hN)F(PN) - hN] (2d-IN-1/QN-l pf(p)dp + oc hN 1 pf(p)dp (2d-IN )/QN-1 = w + h E(P)- (t + h) (d-IN-)/QN-1 pf(p)dp - [(itN + hN)F(PN) - hN] f2dIN-1/QN-1 pf(p)dp + hN JQ pf(p)dp. (1) (2d-IN 1)/QN.1 It is easily shown that CN.1 is convex in QN-1, and CN_1 is strictly convex for QN-1 > 0. Therefore, if Qj-1 > O0 is optimal, the optimal value of QN-1 satisfies the first order condition. Observe that the optimal value of QN 1 depends upon both d-IN1I and 2d-IN-l. As such, we cannot claim, in general, that there exists some PN-1 such that QN- = (d-IN 1)/N-1- On the other hand, if we can guarantee that (possibly after some initial transient) In < d for all n, then aCN-i(IN- 1QN-i)/QN-1 = w - t (d-IN-1)/QN-1 pf(p)dp + h pf(p)dp - a [(N + hN)F(PN) - hN] E(P) 7

and the optimal policy would have the form QN*1= (d-IN 1)/N- 1 for some unique PN- 1 This would be true because (2d-IN-)/QN-1 would always be greater than or equal to 1, so the last term in (1) would vanish. For IN-1 > d, aCN 1/QN-1 will be non-negative for all QN-1 >Oif w + h E(P) - a [(TN + hN)F(PN)- hN] E(P) O 0. This condition is that the variable production cost plus the cost of holding the expected good output (fraction of a unit) is greater than or equal to the discounted expected saving from reducing the net demand in period N by the expected output. We also have CN1i (IN-) = (d - IN-1)[(/ + h)F(PN 1) - hi + oa (2d - IN-1) [(TN + hN) F(fN) - hN]. Repeating this process, we find that aCNj (INjQNj)/Nj = w- (d-N-j)/Q-j pf(p)dp +h J(dN.I)IQN pf(p)dp J(d-IN-j)/QN-j j-1 i aok [( + h)F(fN-k)- h] E(P) k=1 - J [(N + hN) F(N) - hN] E(P), j = 1,..,N-1 (2) and j CNj (INj) = k= k i (k d- IN.j)[(x + h)F(N.j+kl)- h] E(P) + oi [(j+1) d-INj][(7:N + hN) F(3N) - hN] Both of these relationships can be proved by induction, but the proofs are straightforward so we do not include them here. It is also easy to show that CNj (IN-j QN-) is convex in QN-j for j = 0,..., N- 1, so the QNj, values are those which equate the first partial derivatives in (2) to zero. 8

If IN. > d, aCNj/QNj will be non-negative and Q.jwill be equal to zero if j-1 w + h E(P) - I ak [(7: + h)F(PN-k)- h] E(P) k=1 - aJ [(TN + hN) F(PN) - hN] E(P) > 0. (3) This says that the variable production cost plus the cost of holding the expected good output exceeds the discounted expected saving from reducing the net demand by one unit in period N-j+1 (i.e., the subsequent period) and all future periods. Thus, the condition in (3) can be fairly restrictive for short time horizons and high discount factors (a close to 1), where the effect of IN can make it optimal to produce in anticipation of demand in future periods. There are, of course, other constraints such as production or storage capacity, which might prevent this practice. It is also worthwhile to note that the condition (3) is essentially a condition of no speculative motive for producing and holding inventory. Hence, while it is restrictive in a purely economic sense, in concept, it is not substantially different from assumptions commonly made in the inventory literature. We will show later that this restrictive assumption applies only to finite horizon problems. The solutions would be relatively easy to find under the conditions that In< d for all We need to develop conditions to ensure that (after some initial transient) In< d for all n. If one starts with b > d and condition (3) is satisfied, then the optimal policy would be to set Qn = 0 until there is a positive net demand. One only needs to find Q from tfihat point until the end of the horizon. Suppose that we have In < d for some n. Since n+1 = In + PQn - d, we need In+ pQ - d < d or PQn < 2d - In 9

for all In < d. Now Qn = (d- I)/[n so we need p(d-In)/n < 2d -In or P < Pn (2d - In)/(d-In). Let p = maximum achievable value of p and p = minimum achievable value of p. Since p is random, the inequality above holds only if p < 2n(2d - In)/(d-In). (4) Since we do not know Pn and In a priori, this relationship must hold for all possible [3n and In. We first investigate the value of (2d - In)/(d - In). This ratio is strictly increasing with In for In < d. Thus, one possible lower bound on this ratio can be obtained by taking the limit as In —> - oo. A tighter bound is obtained by observing that the worst case value of In < O (largest cumulative deficit) occurs when we set P = p and the observed yield rate in each period is 1. If we start with Io = 0, a little algebra shows that this smallest value of In is n -d X (p- p)k k=l Taking the limit as n -> oo, we have lim In =-d(p- p_)/[1- (p- P)]. n -> oo Let r = p - E. Then (4) is satisfied by all In if p < [n (2-r) or in > f/(2-r) (5) which are obtained by appropriate substitutions. Clearly, (5) will be satisfied by all [3n if the right hand side is less than or equal to zero. This, however, is a rather strong condition. Observe that we must have n >~ g to ensure that we are not intentionally producing now for subsequent periods. This, in conjuction with (5), can be guaranteed if 10

p/(2-r) > p or equivalently, p > p(2+1)/(l+1). (6) We must also impose the condition P<2p. (7) to ensure that we do not completely satisfy demand for the subsequent period by chance if we choose Pn = p and observe a yield of p. Thus, j/(2-r) is constrained to lie within a particular range for each value of p. The range, plotted as a function of p, is shown in Figure 1. Recall that these conditions are sufficient, not necessary, and require no additional assumptions about the form of F(-), other than its domain of support. Thus, while they appear to be strong, in practice they may not be problematic. One of the reasons for such a strong condition is that a large number of backorders were allowed to accumulate so as to allow complete generality of our results. Yet, in practice, such a large number of backorders would not be permitted. Thus, much milder conditions would apply in practice. Indeed, it is possible to show (and it follows directly from the above arguments) that in the case of lost sales, we would have In 2 0, and the only condition would be (7), which many real-world yield rate distributions satisfy. Of course, if the rns are known, we can check the much milder condition in (4) instead. FIGURE 1 We have thus proved the following theorem: Theorem 1: If conditions (3) and (7) are satisfied, and either (a) there is complete backordering and e(2+p.)/(l+p) < p < 2p, or (b) there is complete lost sales, the optimal policy has the form (d-In)/[n if In <d Q;= 0 otherwise where 0 < 3n 1. We should note that for the case of lost sales, the shortage costs must be modified to account for lost revenue. Throughout the remainder of the paper, we will assume that 11

the optimal policy has the form described above. We next derive conditions in which the 3n values are guaranteed to exist. Conditions for Existence of the n Values Simplifying (2) and equating it to zero, gives the first order conditions PN-j j-1 I pf(p)dp = {w + h E(P) -, ak [(i + h)F(PN-k)- h] E(P) o k=l - i [(EN + hN) F(PN) - hN] E(P) }/(t +h), 0 < j < N-1 (8) and N j pf(p)dp = [w + hNE(P)]/(N + hN). (9) To demonstrate that the f3n values exist, we must show that there is a value of Pn, 0 < Pn < 1, which solves (8) or (9). Two conditions on costs are needed: (i) w < nNE(P), and j-l (ii) w + h E(P)- ck [(: + h)F( k) hi E(P)- c [(N$ + hN) F(,) - hN] E(P) > 0. k=l The first condition ensures that it is profitable to produce the product. The second condition is a regularity condition on costs. Observe that the left hand side of (9) is less than or equal to E(P) for all PN. It is precisely equal to zero at PN = 0 and equals E(P) at AN = 1. Furthermore, it is monotonically non-decreasing in PN. Thus, for 3N to exist, we only need the right hand side of (9) to lie between 0 and E(P). Obviously it is non-negative, so we need w + hN E(P) < (7N + hN)E(P) or w < N E(P) which is, condition (i) above. We need to show that AN 2 0, which is equivalent to showing that the term in braces in (8) is non-negative. This is the same as the condition in (3) which ensures that Q-j = O if Inj > dn-j 12

If condition (i) is not satisfied, then a value of ON sufficiently large to satisfy the first order condition for period N does not exist. In other words QN < d-In, and it is not profitable to satisfy demand. If condition (ii) is not satisfied, a value of ON sufficiently small does not exist and one would want to input an infinite amount. FINITE HORIZON PROBLEM WITH TIME-VARYING DEMANDS AND COSTS In the previous section, we discussed the necessary condition for optimality of a multiplicative policy, i.e., In < d for all n. When demands and costs are time-varying, somewhat stronger conditions are needed. The first condition is that there is no speculative motive for holding inventory: Wn + hn E(P) > ca Wn+l (10) where the subscript indexes the time period. This says that it is more expensive to produce now and to hold the expected output than to incur the discounted cost of production in the next period. This condition is clearly needed to ensure that production quantities are limited, so that In < dn. The second condition relates to requirements on F (.) which are similar to those for the case of constant demand. We need In+l = In + pQn -dn < dn+l or pQn < dn + dn+l - In. Substituting Qn = (dn - In) /Pn, we have P < 3n (dn+l + dn- In)/(dn - In) (11) Suppose there is a maximum demand level, dmax, and a minimum level, dmin. Then, by taking the limit of In as n —>oo (as in the previous section) to obtain the smallest possible value of In, and noting that the right hand side of (1 1) is decreasing with dn and increasing with dn+i, it is easy to show that a lower bound on the right hand side of (11) is Pn {dmin [1 - (p- pE)]+ dmax}/dmax Since we must have all p less than this value, and,3n >2, one of the conditions for In < dn for all n is 13

P < P {dm, [1 - (p- e)]+ dmaxj/dmax. (12) This condition imposes tighter restrictions on the range of p if dn fluctuates widely from period to period and is identical to (4) when dn = d for all n. As in the case of constant demand, we must also ensure that we do not intentionally produce enough to satisfy demand for two consecutive periods. Thus, we require that (p / p) dmax < dmin + dmax (13) since otherwise we might choose Pn = p in a period in which demand is dma and observe a yield of p, thereby satisfying demand in the following period if it happens to be equal to dmin. Under conditions (12) and (13), a multiplicative policy is optimal. To ensure that the 3n values exist, we also require that (a) wN < RN E(P) and N-l (b) wn + hn E(P) > ak-n [(:k + hk)F(fk)- hk] + caNn [(;N + hN)F(PN)- hN]) E(P), k=n+ l n=l,...,N-1 which are time-varying equivalents of (i) and (ii) in the previous section. If all of the above conditions are satisfied, the optimal values of PN satisfy PN- Jj j-l f pf(p)dp = {WNj + hNj E(P) - S ak [(;tN-k + hN-k)F(N-k)- hN-k] E(P) o k= 1 - c (TIN + hN)F(PN)- hN] E(P)}/ (;N-j + hNj), j = 1,... N-1 and I pf(p)dp = [wN + hN E(P)]/ (+N + hN). 0 14

INFINITE HORIZON PROBLEM We examine the infinite horizon problem with constant costs and constant demands. Here, the conditions on costs for optimality of a multiplicative policy are much milder than in the finite horizon problems, and they are discussed later in the section. To find the optimal solution for the first period in an infinite horizon problem, we can take the limit of (8) as N-> oo. We have (3P5,: ~o00 f pf(p)dp = {w + h E(P) - Z cak [(C + h)F(P)- h] E(P))/(i + h) 0 k=l where P denotes the optimal infinite horizon value. Simplifying, we get f pf(p)dp = {w + hE(P) -[a/(l-a)] [(n + h)F(3)- h] E(P)}/ (n + h). (14) 0 The left hand side of (14) is monotonically increasing in 3 while the right hand side is monotonically decreasing in 3. Thus, if two functions intersect, they intersect in a unique value of P. These functions will intersect if the right hand side is less than or equal to E(P) for some 0 (3 < 1. Since the right hand side achieves its minimum at (3 = 1, let us consider this value of (3. The condition for a unique optimal value of P3 to exist is {w + hE(P) - [o/(l-a)][(; + h)F(p)- h] E(P)}/ (n + h) < E(P). Simplifying this, at 3 = 1 we get (1-a) w < x E(P). (15) This says that the opportunity cost of processing a unit in this period rather than next period (i.e., loss in terms of discounted cash flow) must be less than the shortage cost which would be saved from the expected output. In other words, this means roughly that it is profitable to produce. In general, this is a very mild condition. We next examine when Q = is optimal if I > d To find (, we must solve the first order condition 15

v + hE(P) - [a / (l-a)][t( + h)F(3)- h] E(P) -( t+h) j pf(p)dp=0. 0 Let us assume that it is possible to ensure I < d for the remainder of the (infinite) horizon, but that in the current period I > d. In this case 3 = (d-I)/Q < 0 for all Q > 0, so the first derivative becomes w + hE(P) - [a / (1-a)] h E(P) > 0. Thus, one does not want to produce. Since this argument applies to all periods, the only economic condition necessary to ensure that I < d is condition (15). We can now state the result, which we have just proved above: Theorem 2: If conditions (6) and (7) are satisfied, and (1-a) w ~< i E (P), the optimal infinite horizon policy is (d-In) if In <d QO = V0 otherwise where the unique value of P satisfies (14). EXAMPLES To illustrate characteristics of the optimal multipliers, we present examples to illustrate two interesting results. We use a uniform yield rate distribution with E(P) = 0.90, p =.80, and p = 1.0 to facilitate computation. Consider a problem with w = 9, hn = 0.18 for n = 1,..., N-l, hN = -10, Fn = 0.2 for n = 1,..., N, nN = 18 and a = 0.98. The parameters were chosen to be consistent with a profitable product produced monthly, with no expected gain (or loss) due to salvaging the product at the end of the horizon. Using equation (9), we find ON = 0.80 and F((N) = 0. Then, using equation (8), we find PN-1 = 1.0, PN-2 = 0.991, N-3 = 0.9986, N-4 = 0.9996. It is already apparent that the PN-j values need not be monotone. This arises principally because of the manner in which discounting affects the right hand side of equation (8). 16

The optimal value of P for the infinite horizon problem is approximately 1.0. The solutions for the infinite horizon problem appear to be converging toward this value quickly. It is interesting to note that the optimal solutions indicate that one should simply input the net demand. This arises in spite of the apparent profitability of the product. The discounted expected cost of the optimal solution is $49,000. Twenty-five simulation runs using a rule-of-thumb policy in which one adjusts production quantities for average yield losses give costs having a mean of $50,145 and a standard deviation of $371. While the two costs may not appear to be significantly different, at least $44,100 of both costs is attributable to non-controllable production costs (i e, the infinite horizon cost of inputting just the stated demand in each period). Thus, using an optimal policy can reduce controllable costs considerably, and the difference between the optimal and rule-of-thumb policy is statistically significant in this example. SUMMARY AND DISCUSSION We have derived the form of optimal finite and infinite horizon policies for systems with variable yield rates and deterministic demand under certain conditions on costs and the yield rate distribution. The general form of the policy is - I(dnIn)/[n if In < dn QO= 10 otherwise where [3n = 3 when the horizon is infinite. The policy is multiplicative in that the net demand is multiplied by a factor 1/[n which is independent of dn and In. Setup costs can be incorporated in a heuristic fashion relatively easily. For an infinite horizon-problem with constant demands and costs, we can determine a production interval using average yield rates and then set the time period for the production control problem equal to this interval. For a finite horizon problem, one can determine a lot-timing policy using average yield rates and yield-adjusted costs. Then, by scaling costs to reflect the length of the time periods (where appropriate), one can use the model with time-varying demands and costs to solve the production control problem. These are, of course, heuristics, but are simple to implement. Further work needs to be done to evaluate this proposed heuristic. Since McCoy, et al. have found that sequentially determining lot timing then lot sizes performs well, one might expect that a similar sequential procedure with optimal lot sizing (given the lot timing) would perform even better. 17

REFERENCES Gerchak, Y., R. G. Vickson, M. Parlar (1988), "Periodic Review Production Models with Variable Yield and Uncertain Demand," IIE Transactions, 20 (2), 144-150. Giffler, B. (1960), "Determining the Optimal Reject Allowance," Naval Research Logistics Ouarterlv 7 (1), 201-206. Henig, M. and Y. Gerchak (1988), "Structure of Periodic Review Policies in the Presence of Random Yield," Working Paper, Department of Management Science, University of Waterloo. Karlin, S. (1958a), "One Stage Models with Uncertainty," in Studies in the Mathematical Theory of Inventory and Production, K. J. Arrow, S. Karlin, and H. E. Scarf, Eds., Stanford University Press, Stanford, California. Karlin, S. (1958b), "Steady-State Solutions," in Studies in the Mathematical Theory of Inventory and Production, K. J. Arrow, S. Karlin, and H. E. Scarf, Eds., Stanford University Press, Stanford, California Klein, M. (1966), "Markovian Decision Models for Reject Allowance Problems," Management Science 12 (5), 349-358. Lee, H. L, and C. A. Yano (1988), "Production Control in Multi-Stage Systems with Variable Yield Losses," Operations Research, 36 (2), 269-278. Mazzola, J. B., W. F. McCoy, and H. M. Wagner (1987), "Algorithms and Heuristics for Variable Yield Lot Sizing," Naval Research Logistics 34 (1), 67-86. Sepehri, M., E. A. Silver, and C. New (1986), "A Heuristic for Multiple Lot Sizing for an Order Under Variable Yield," IE Transactions, 18 (1), 63-69. Shih, W. (1980), "Optimal Inventory Policies when Stockouts Result from Defective Products," Inter. J. Prod. Res. 18 (6), 677-685. Silver, E. A. (1976), "Establishing the Reorder Quantity when the Amount Received is Uncertain," INFOR 14 (1), 32-39. White, L. S. (1967), "Bayes Markovian Decision Models for a Multi-Period Reject Allowance Problem," Operations Research 15 (5), 857-865. Yano, C.A. and H.L. Lee (1989), "Lot Sizing with Random Yields: A Review," Technical Report 89-16, Department of Industrial & Operations Engineering, University of Michigan, Ann Arbor, MI. 19

UNiVERSTY OF MICHGAN 3 9015 04733 8465 p -,- minp -- max p 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Figure 1 Range of p as a Function of p