Optimal Starting Times and Suppliers Delivery Dates in a Stochastic Assembly System Walid R. Abillama Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 December 2, 1993 Abstract We consider the problem of quoting delivery due dates to various suppliers in an assembly system with random processing times. Assume that an order for a project has been accepted and a due date for the completion of the project has been set in advance. Furthermore assume that the suppliers are perfectly reliable and that the suppliers delivery due dates must be quoted before any processing occurs in the system. Once the delivery due dates have been quoted and processing has begun in the system, it becomes necessary to determine the optimal starting time at every stage in the assembly system, due to the randomness in the processing times at the various stages. We show that the optimal starting policy at each stage calls for no intentional delay whenever outside supply parts arrive at that stage and that the optimal delivery due dates can be determined analytically. If the outside parts delivery dates were preset, the optimal starting time at each stage is described by a simple wait-until policy, where the manager waits until the greatest of the delivery 1

date and the beginning of the optimal cumulative planned processing time of all downstreams stages to begin processing. Thus the optimal starting policy at each stage is completely determined by a critical number, the optimal cumulative planned processing time of all downstream stages, showed to be the minimum of a convex function. We also consider the particular case when the ouside supply parts at each stage are available at no additional cost and characterize the wait-until policy that completely determines the optimal starting time at each stage. Finally we generalize by considering the case of unreliable outside suppliers. 1 The Model Consider an assembly system with stochastic processing times as the one depicted in figure 1. The system consists of N production stages in series where outside supply parts are needed at each stage in order for processing to start at the following stage. Let stage 1 be the most downstream stage and let ri be the processing time at stage i with distribution function Fi, i = 1,..., N. Assume that an order for a certain project has been accepted and a due date for the completion time of this project has been set at IN time units from now. Naturally, the processing at each stage cannot start unless supply parts are delivered and processing at the prior stage is completed. There is a penalty p per unit of time for missing the project due date and a holding cost hi per unit of time for holding the semi-finished project at the outlet of stage i. Outside supply parts needed for stage (i -1) are held at cost hi per unit of time at the outlet of stage i, i = 2,..., N + 1. We assume quite realistically that hi + hi < h(i_1), with h(vN+) and h(N+i) > 0. We also assume that the suppliers are perfectly reliable, that the delivery due dates must be quoted before any processing occurs and that once processing occurs at a stage, it must be completed. However, due to the randomness in the processing time at the various stages in the system, once df, the optimal delivery due dates at stage i = 1,..., N have been quoted and processing has started in the system, it becomes necessary at the time processing is 2

completed at each stage to determine the optimal starting time at the next stage, given the remaining time till the delivery due dates at the downstream stages and the project completion due date. Let yn (li, Xi1,..., X1) be the optimal waiting time between the time stage i is ready to be processed and its actual starting time, given that the project due date is 4i units of time away from now, Xi1 units of time away from the delivery date of the outside supply parts needed for stage i, X(i._1) units of time away from the delivery date of the outside supply parts needed for stage (i - 1) and so forth. Let J* (l, Xi,..., X1) be the minimum cost of scheduling the processing at stages i throing ugh 1, given similar data as in y$ (li, Xi,...,X1). Also let YN be the waiting time between the time stage N is ready to be processed and its actual starting time. Finally let JN (yN, XN1,..., X1) be the minimum cost of scheduling the processing and quoting the delivery due dates of the outside supply parts at stages N through 1, given that the project completion due date is INV time units away from now. 2 Two-Stage Model for Determining Delivery Dates and Starting Times Suppose that N = 2. We will use backward stochastic dynamic programming (SDP) to determine y* (I1,X1) in the first SDP stage, and y, X2 and X1 in the second SDP stage. The first SDP stage is triggered when job 2 is done processing. Figure 2 depicts the time advances in a two-job model. The first SDP stage problem is defined as following: J1 (11, X1) =Min h2 (l1-X1)+ + (h2 + 2) Y1 + I (11-Xl)+-Y1 hl -11 1 [(I1 - i + -X Y-)-t] fi (t) dt + P_(,-x,+_~ [t - (-(11 -X)+ -)] fi (t) dt (1) s.t. y1 > 0 3

It can be easily checked that J1 (I1,Xi) is convex in yi by differentiating it twice. Therefore, the optimal solution y* (I1, X1) to the first stage problem is obtained by differentiating equation (1) with respect to yi and setting to zero. Doing this we get the following waituntil policy, where we wait 11 - (11 - X1)+ - X~ units of time before processing the job if 11 (11 - X1)+ - - > 0, and process immediately otherwise: lI - (i= - X1) - X; if I -(11 - Xl -X)+ > X y; (l,iX1) = (2) 0 otherwise where X1 = F- [(p + h + h+ h(p hi)] is called the optimal planned processing time for stage 1 given 11 and X1. Figure 2 shows that 11 = X21 - Y2 - T2. Hence the second stage problem is defined as following: Min J2 (y2,X21,X1) = h2 [u - (X21 -2 - X)] f2 (u) du + (3) 21 -Y2-X1 h3 (12 - X21) (h3 + 7h3) y2 + E [J (X21 - y2 - r,X1)] s.t. Y2 > 0, X21 > X1 > Where the first term represents the cost of holding the outside supply parts needed at stage 1, given that they have arrived before processing at stage 2 has been completed. To find the optimal solution to the 2-stage problem, we will show that the point Xo = (Y2*, X2, X1 that satisfies the necessary condition VJ(Xo) = 0 is feasible, satisfies X' < X<, and that the Hessian of J2 (y2, X21,X1) is positive-definite for X1 < X7. As a result, Xo is the optimal solution to the 2-stage problem. To solve the set of first-order conditions, we substitute 11 by X21 -Y2-2 in Jj (11, X1), apply the expectation operator, differentiate (3) 4

with respect to Y2, X21 and X1 and set to zero. Substituting (2) in (1), we get (h2 + h2) (t1 - X)-~h (11 - Xt+ + h,;i (i - t) f, (t) dt+ p - (t - x) fi (t) dt x < II - (1 - X)+ J7:(/i.Xi)=< J (117, x) - h2 (ll - X1)+ + hi'-(1l-xl)+ [11- (1- X)+ -t] fi (t) dt+ Pf1- (l1-x1)+ [t - 1 + (11 - X)+] fi (t) dt X, > I1 - (1 -Xl)+ (4) We differentiate between two cases: 1) X1 >_ X, 2) X1 < X*. Case 1: X1 > X1 In this case, for r2 < X21 - Y2 - X1, the value function becomes J; (X21- y2- T2, X1) = h2 (X21 - 2 - T2 - X) + h2 (X1 - X) + h, ( - t) f, (t) dt + p (t - ) fi (t) dt for X21 - Y2 - X1i < 72 < X21 - Y2 - we get J1 (X21 - 2- 2, X) = (h2 + 2) (X21 - Y2-2 — for X21 - Y2 - <1 ~ 12 ~ X21 - Y2 we get r X21 -Y2-T2 J1(X2i-y2-T2, Xi) = hj J (X21 - Y2 - 2-t) fi (t) dt + r00 p YT [t- (X21 - Y2 -r2)] fi (t) dt X21 -y2 — 2 and finally for r2 > X21 - Y2 we get J (X21 - Y2 - 72, X1) - p [ -(X21 - 2 - T2)] 5

hence in case 1, the 2-stage problem becomes: - 00 MinJ2 (y2, X21, X1) = h2 [ - (X21 - 2 - X)] f2 (u) du + 21 -y2-X1 h3(12 - X21) + (h3+ h3) Y2 + j -Y2-X [h (X2l - Y2 - T2 - X) + h (1 - X) + hi J X (X - t) fi (t) dt + p (t - X) i (t) f2 (u) d + JX-Y2-X [(h2 + h2) (X21 - Y2 -u -) + hiJ ( - t) fi (t) dt + p - fi (t) dt X21-Y2 X21-Y2-U 1 X2-y2-X1 [h) (X2 Y- Y2- - t) fi (t) dt+ p I [t-(X21 -2-u)] fi (t)dt f2 (u)du + JX21 -Y2-u roO P JX- - X21 + Y2 + U) f2 () du (5) X21 -Y2 s.t. Y2 >,12 > X2 1 XI 0 Case 2: X1 < X1 In this case, for r2 X21 - Y2 - X1, the value function becomes J1 (X21 - Y2 -2, X1) = h2 (X21 - Y2 - 2 -X) + hi / (X t) h(t)dt+p (t- x) fi (t)dt for X21 - Y2 - X1 < r2 X21 - Y2 we get X21 - y2 —2 1 (X21 - Y2 - 72, Xl) = hji (X21 - Y2- -2 -t) f (t) dt + 00 P / [t -(X21 - Y2 - r2)] fi (t) dt 2J X-Y2 — 2 and finally for r2 > X21 - Y2 we get J; (X21 - Y2 - 2, X1) = p [ -(21 - Y2 - 2)] 6

hence in case 2 the 2-stage problem becomes: MinJ2(y2,X21,Xi) = hl2 [ - (X21 -y2- X)] f2 () du + h3 (12 - X21)- (h3+ 3)y2+ oX21 -Y2-X1 j oX2- 2-X 2 [h2 (X2l - X1 - ) + hi (Xi - t) fi (t) dt + p (t - Xi) fi (t) dt f2 (u) du + X21 -Y2 [ 1X2-y2-u X21-Y2-UX L -y2-X j [hf ]Z (X21 - Y2 - u - t) fi (t) titY2 t - (X21 - Y2 - u)] fi (t)dt f2 (u)du + 21-Y2-U ~00 p ((lu - X2 + y2 + u) f2 (u) du (6) J 21 — Y2 s.t. Y2 >, 12 > X21 > X1 >_0 Differentiating with respect to Y2 we get V X1: SJ2 (Y2, X21, Xi) J2 (Y2, X21, X) -- Y2-_ -X21- _ --- T_ ---- + h3 = h3 > 0 (7) &Y2 6X21 hence y* = 0 provided UJ2 (y2,X21, X1)/6X21 = 0 at X21 = X2. Differentiating with respect to X1 we get for X1 > X7: 5J2 (Y2, X21, XI) _ h2 -Xi (yX =, X 2) -x f2 (u) du h2 2 f2 (u) du h2 > (8) SXT1 Jx21-XI and for X1 < X.: 5 J2 (y2, X2i, Xi) J2 (y2, X21,) = h2 - L (X1) F2 [X21 - X1] (9) where L (X1)= [(2 + + + - (h + p) F1 [X1] > 0 for X1 < X. Therefore if X1 > XA, then XA must be at most equal to XI. Differentiating with respect to X21 we get for 7

X1K < 6J2 (Y2, X21, X1) X21 21 yX21,'(hX P) )21-X fi (t) f2 (u) dtdu + SX21 _X — Xu ^0 (h2 + + p) j f2 (du - (h3 +h2 +) (10) Suppose X*1 < Xl. Then (9) implies X* = X = 0 and (10) implies X2* Xl = 12: contradiction, hence X* > Xl. Similarly, suppose Xl < 0, then it must be from (9) that (h2+h2 +p)F2 [X1] h2 (11) However, substituting X1 by zero in (10) gives (2 + h2+p) F [X1*] = (2 + h3+p) contradicting (11), hence Xl > 0. It remains to show that the Hessian is positive-definite for X1 < X1 and we are done. It fact, differentiating (9) and (10) we get <2~$,2 X21 X1) y /, x,. 2Xl) r / 62J2 (X2 = (h+ p) fi (Xl) J f2 (u) du + L(Xi) (12) 52J2 (y2, X2, X1) 62J2 2 X1 = -L (X1) f2 (X21 - X) (13) SX15X21 52J2 (Y2, X21, Xi) fX 6 J2 (y2 X21 ) (h P + p) I21 f2 (u) fi (X21 - ) du + L (X1) f2 (X21 - XOL4) 5`X21 21 where L (X1) > 0 for XA1 < Xi. Therefore the minor determinants are non-negative and thus the Hessian is positive-definite for X1 < X<. As a result (y2, X2*, X where X* vanishes (10), X; vanishes (9) and 0 < X <_ Min {X2,X}, is the optimal solution to the 2-stage problem. Since X' < X1 then y- = 0 w.p. 1 and the optimal policy calls for immediate processing whenever the outside supply parts needed at stage 2 are delivered, and for no intentional delay whenever the outside supply parts needed at stage 1 are delivered. To conclude this section, we must mention that the analysis presented here assumes that the project due date is sufficiently far in the future that there is enough time 8

to plan for delivery of outside supply parts. However, there may be instances when the supplier at stage i requires that the order for the ouside parts be placed at least Ai units of time in advance. In such situations, schedule the delivery date for the outside supply parts needed at stage 1 at X1 if X1 < 12- Al, and at 12- Al otherwise. Similarly, schedule the delivery date for the outside supply parts needed at stage 2 at X21 if X21 < 1 - A2, and at 12- A otherwise. However, we showed that X21 > X1. As a result, if X1 > 12 -A2, then schedule the delivery date for the outside supply parts needed at stage 2 at 12 - A2 since in this case X21 > 12 - A2. 2.1 Effect of the Processing Time Variance at Stage 1 In this section, we study the effect of the processing time variance at stage 1 on X2 and X, the optimal delivery dates of the outside supply parts needed at stage 2 and 1 respectively. To do this, we will use a simple mean-preserving transformation of a random variable. This transformation was first used by Baron [1], Rothschild and Stiglitz [3] and Sandmo [4] in Economic Theory, and was first used by Gerchak and Mossman [2] in Iventory Theory to show the effect of the demand variance on the optimal solution to the classical Newsvendor problem. With r7 as the processing time at stage 1, the transformation is 71i = a (71 - 1i) + p1 (15) where p1 is the processing time mean at stage 1. It is clear that (15) implies E [T1] = E [ri1] and Var [ria] = a2Var [ri]. Hence we increase or decrease the processing time variance at stage 1 by assigning values for a larger or smaller than 1 respectively. After making the substitution X2 = X21 - X1, equation (10) set to zero can be written as (hi + p) Pr [r > X2,rT2 +r < X2 + X1] + (h2+ h2 + p) Pr [r2 < X2] = h3+h2+p (16) 9

and hence (hl + p) Pr [72 > X2a, T2 + TIe < X2a + Xia (h2 + h2 +p) Pr [r2 ~ X2] = h3 + = h2 +P which, after substituting for rla from (15), can be rewritten as X2a+X1a+m/1(c-1) x2 +x-a -u+ul (hi + p) x fi (t) f2 (u) dtdu+ (h2 +h2+P) JX f2 (U) du = h3+ h + p (17) Similarly, equation (9) set to zero can be written as ( 2+ h2+p) -( +p) /i (t) dt f2 (u)du=hx (18) Differentiating (17) with respect to a we get (hi + p) /X2a+Xla+l (a-) dX2a) dX/ ) -l - - C2 JX2 da dac (X2c + Xl - 1i - )] i X2a + xU +12 (u) du dX2cj XiaS Al 1 + dc f2 (X2a) (h2 + h2 +p)-(h +p) f (t) dt 0 (19) and differentiating (18) with respect to a we get da f2 (Xa)[(2+ h2 + p) -(h + p) J f, (t) dt (hi + p) dXf Xi, - i \, [X2a -q - (h p [Cd (a (Xc-L)] fi (i- + f (u)du = 0 (20) a2 da aJO Suppose that for some a, we have dX2a/da = 0. Equation (20) implies that either one of 10

the following three statements are true: 1) X2a =0 2) Xi, =, (l-a) 3) dX, _ (X1C -1l) da Xa 3) d - -- -- 4) a = 0 Equation (18) indicates that 1) leads to a contradiction. If 2) is true and a > 0, then (18) and (17) imply F2 [X2a] = h h2 (21) h2+ h2+ P and [ \Y]d h2 + h3 + p F2 [X2a] - hr h-+p (22) h2 + h2 + p respectively: contradiction. If 2) is true and a = 0, then (18) and (17) imply X2ce IKc0== F~-' (23) h2+ h2 +P and da =- (hi +p) (2+ h+p) respectively. If 3) is true, then (19) implies /2(U - X2a) fi (2 + 2 ()- du = 0 (25) which in turn implies either 2). Moreover, the fact that 2) is true and a = 0 agrees with the fact that X1 = IL1 when the processing time at stage 1 is deterministic. As a result of this analysis, we conclude that dX2a/dca = O only at a = 0, which implies that (23) and (24) are true, and at a = oo by 4). Suppose dX2a/da > 0 for 0 < a < oo, then 11

limc o X2c = cc since X2, is continuous in a. This leads to a contradiction in (17) since h2 > h3. Therefore dX2,/da < 0 for 0 < a < oo. Equation (18) implies that X1 < ca (X-1 - 1i) + u1 since equation (9) implies that SJ2 (y2,Xi X ^) i Xlce 6 XJ2 (=X2 X(x; —lX)+l = h2- L (1) F2 [X2C] = 2 > 0 (26) Therefore, having shown that X\ > (X, -,u) /ac +,1, we rewrite (20) as dX2a h / v F F rT"*1 j? \^c ~ 1 __ - 1i (h + p) dX f2 (X2a) [F1 [X F1 [Xa- + ] ] (hi + p) dX i ( -Pi. \ X2a o (hl -P) [da- (Xic - 1i)]i f /2 (u) du = 0 (27) a2 da a As a result, for equation (27) to be true, it must be that dXla X< i - Pi (28) da a Suppose that for some a, we have dXl,/da = 0. Equation (28) implies that X1,, >~ ui. Therefore, X1,> is strictly decreasing in the region Xl, < p1. Finally, as a approaches co, equations (17) and (18) become /*00 /Xla+A61 / - x2a (hi + P) Ji fi (t) f2 (u) dtdu + (h2 +h2 +p) f2(u) du = (h3+ h2+ P) (29) and [(2+h2+p) -(hl+p)j| f1 (t) dt f2(u) du= h2 (30) where X2a = lim' ooX2c and Xi, = lim oodX1/ da. After solving equations (29) and (30), we get lim-ooX2a =- F2' [1- -h (31) 12

lim a _ d = Fi Ih3 + P1 -i (32) dca hi+p If (24) is negative, then X1, is strictly decreasing in a. If (24) is positive and (32) is negative, then X1a increases as uncertainty is introduced, only to decreases towards Xi, = p/i as a keeps on increasing. After hitting X1, = pi, X1, strictly decreases as a - oo. If (32) is positive, then Xi, is increasing with a, and lim,,_odX1,/da is given by (32). In conclusion, X2a is decreasing with ca with X2,l,=o given by (23) and lim,,oX2, given by (31), while X1, is increasing (assuming (24) is positive) in a with dXc1/dcaJ=o given by (24) and limo,_odXl,/da given by (32). 3 Two-Stage Model for Determining Starting Times with Preset Delivery Dates Suppose that the delivery dates of the outside parts needed at stage 2 and stage 1 have been preset at X21 and XI respectively, together with the project due date at 12. In this case it is necessary to determine y (12, X21,X1) as defined in section 1. However, with this information structure in mind, the relationship between the state variables is now 11 = 12 - (12- X2)+ - Y2 - 72 (33) depending on whether the present is located before or after X21, and y2 (12, X21,X1) is obtained by solving the following problem: J2(12, X2, X) =Min h2 J_ [u - (2 - (2 - X21)+ - Y2- )f2 (u) du + l22-(12-X21)'{1-y2-X - h3(12 -X21)+ + (h3 +h3) Y2-+ E [J1 (12- (12 - X21) - Y2 - T2, X)] (34) s.t. Y2 >0 13

Now that X21 and X1 are data, we may have either X1 < X1~ or X < X. If X1< X1, then the last term in (34) is expressed as in (6) (but with 12 - (12 - X21)+ instead of X21), and as in (5) otherwise. Our goal is to show that in both cases, (34) is convex in Y2. If X1 < X*, then differentiating (34) twice with respect to Y2 gives 82 J i X,21iXi) r2-(12-X1)y+-Y 2 f 2 1 - (h1 + p) f2 (u) i -12(12 - X21)+ - Y2 -u) du 6Y2 J22-(2 -X2)+ -y2-Xi +L (X1)f2 (/2 - (12 - X21)+ - y2 - Xi) > 0 (35) since L (X1) > 0 for X1 < X-. On the other hand if X1 > X-, then differentiating (34) twice with respect to Y2 gives -62-j2(12 - X -21, = (hl + p),-(1 (U) fi (12 - (2 - X21) - Y2) du fY2 f12-(12-X21)+-Y2-X J X (h+) fi (12 - (12 - 1)+ )Y2 - r/ (2 X1+-Y2 (hi + p) 2 -(2-2)+-Y f2 (u) fi (12 - (12 - X21) - Y2 - u)du 2 - (12 -X21)i -y2 -X7 since L (~) = 0. Therefore making the substitution X21 = 12- - 2 X21)+ - Y2, we get that Y2 (12, X21, X1) is defined by a wait-until policy where we wait 12 (12 - X21)+ -X1 units of time before processing the job at stage 2 if 12 - (12 - X21)+ -X1 i 0, and process immediately otherwise: Y (12 X21 X1) 12= - (12 - X21) - X1 if 12 (12 - X21)+ > X21 (36) y2(12, X21,X1) = - (36) 10 otherwise X21 is the optimal cumulative planned processing for stages 2 and 1. If X1 < X1, X21 solves U22(12 X21, X1) Xz21 X21i J2 (12,X2,X)- = (h + P) jX f (t) f2 (u) dtdu + (h2 +h+2p) 1g21x f2 (u) du -(h3 + h3 + h2 + p) = 0 (37) 14

and if Xi > Xl, X21 solves 6J2 (12, X21, X) x 21 2 X-21? =(h,+ p) [ - f (t)f2 (u) dtdu+ (h2+ h2 + p)J 1 f2 (U) du - (h3 + h3 + h2 + p) = O (38) Note that we may have from (37) that X1 < Xi, in which case it must have been that 6J2 (12,X21,X1) X (h V X1 -u X X21 Xi (hi +p) f (t) f2 (u) dtdu > (h3 + h3 + h2 + P) that is X1 F-1 h3 + h3 + h2 + - hi +p X21= F-1 [h3 + h3 + h2 + P] XAi21 21 ---- h 1 Similarly, we may have from (38) that X2 < X;, in which case it must have been that = F_1 [h2~h+p +>F1 [ h3 +p ] =F* p>1 h3 + h3 + h2 + P] 2 h 21 —', h +p X*21 = F~- [ hi + p ] < Xi hence y* = 0 w.p.1 and stage 1 is processed immediately when processing at stage 2 is completed. 4 Case when h3 = h2 = Suppose that the outside supply parts needed at each stage can be made available at no additional cost. Assume furthermore that these parts are actually available at the time 15

the order is accepted. Then the problem reduces to the one considered in Yano [5]. In the framework of our paper, the wait-until policy at stage 1 is given by: - if i > l X y;(l) -= (39) [0 otherwise where X- = F{-1 [(p + h2) / (p + hi)]. To determine y* (12) we solve J;(12) =Min h32+E[J1(12 -Y2 -r2)] (40) s.t. Y2 > 0 Our goal is to show that J2 (12) is convex in Y2* The expectation operator conserves convexity. Thus suppose that J' (1i) is convex, then we are done. Our goal is to show that the Hessian of Jjl (I1, X) is positive-definite. Substituting (39) in (1) (with h2 = 0 and X1 > 11), we get h2 (11 - X +) + hi-t) f ((t) dt+ J1* ( pf) - p P (t -tX f) fi (t) dt T < 1 (41) lh, 1 (1 ( - t) fl (t) dt + p ft (t - 11) f, (t) dt T> 1 Differentiating (41) a first time with respect to 11 we get: d [J (11)] _ h2 11 > X (42) dl1 (hl + p) fol fl (t) dt - p X-T > 41 Differentiating (41) a second time with respect to 11 we get: d [JT (11)] (hi + p)fl (11) C > 11 (43) adl~ 0 otherwise It is easy to see from (41) and (42) that (41) is continuous at /1 = X-. (4) is also differentiable at l, = XC by using the fact that X =- F-1 [(p + h2)/ (p + hi)]. We have 16

shown that J' (li) is convex in 11 and thus J2 (12) is convex in Y2. To determine y' (12), we substitute 11 by 12 -Y2- T2 in (40) and get: 12-Y2-X1'J (12) = Miny2>o h3y2 + h2 12 - 2 - u - X) f2 (u) du + hlJ'f (u)duJ (X-t)f1(t)dt h 12-f 2 -l2-y2-u + hJ f2 (uduJ ( - t) f ( t)dt + hP (2 - u - t)f (u) f2 (t) dtdu 2-Y2 rl2-Y2 ~~oo + JP Y J0- (t + u - 12 + Y2) f2 (u) f (t)dtdu (44) J12-2-X 12 -y2-u Therefore substituting in (44) 12 - Y2 by X21, we obtain y2 (12), the optimal waiting time before production is started at stage 2 given that we are 12 periods away from the due date. y* (12) can be written as: Y2 (12) = (45) 0 Yotherwise To compute X21, we differentiate (44) after substituting 12 - Y2 by X21 and set it to zero. Further manipulations result in the following first order condition: (hI + P) Jx21'-x 1 fi (t) f2 (u) dtdu+(h2 + p) 2 f2 (u)du-(h3 + p) 0 (46) we may have from (46) that X- < X<, in which case it must have been that dJ2 (12).21 (h p)f01 f0'-U dl12) x21=T = (hi + p)j fi (t) f2 (u) dtdu > (h3 + p) that is h +. - hl"+p = F l+p] 21 hZ+ 17

X> A21 2, 1 h3 + P iX 1 hl4phence y = 0 w.p.1 and stage 1 is processed immediately when processing at stage 2 is completed. 4.1 Effect of the Processing Time Variance at Stage 1 In this section, we study the effect of the processing time variance at stage 1 on X2 and X7, the optimal planned lead times at stage 2 and 1 respectively. To do this, we will use the simple mean-preserving transformation of a random variable defined by (15). As a result, we get X, = a (i - 1) - + I (47) After making the substitution X2 = X21 - X, using the transformation defined by (15) and substituting X1i from (47), equation (46) becomes X2' + Cx a X2a -U +; x (hi + p) JX2 J + f (t) f2 (u) dtdu + (h2 +p) j f2 (u) du (h3 + p) (48) Equation (48) gives X2alc=O = F7-' [(p + h3) / (p + h2)]. Differentiating (48) with respect to a we get (hia+ [aX 2(X2 dXa (X2-U (hl +p) X2+Q a~x ( -u)] f + X) f2 (u) du 2 J2Xa [ dca a + dX f2 (X2a) (h2 + p) - (h + p) J i () dt] = 0 (49) and hence (h1 + p) JXa+ax [ dX2a (50)X - 2) JX2-+ a f2 (u) du = 0 (50) 18

Suppose there exists a for which dX2,/da = 0. This implies that either a = 0 or a -D o. As a -* oc, (48) gives h2 = h3: contradiction. Therefore dX2,/da = 0 only at a = 0. For a > 0, dX2,/da < 0 for (50) to be true. Finally, X2I = 0 implies from (48) that ao, the amount of variance at stage 1 that is required to pool the two stages into a single stage whose processing time distribution is the convolution of the two stages, satisfies (hi +p ) ] fi (t) f2(u) dtdu = h3 + p (51) Recall that for a = 1, X2 > 0 only if F21 [X] < (p + h3) / (p + hi), hence the same is true for a* > 1. For a > a*, X2, = 0 and X1O is given by (hI + p) Pr [7r1, + T2 < X] = h3 + p (52) Using (15), (52) becomes rXl~a+m (-i) oX:-I~-"' +,m (hi + p) ] fi (t) f2 (u) dtdu = h3 + p (53) It is clear that (53) reduces to (51) at a = a*, with Xl, = a (X - 1) + pi. Differentiating (53) with respect to a, we get (hl +:p)C l (-l) d* jie Y,U (hi p) ll (1 — a -- - (X - u)] i ( + p1i 2 () du = 0 a2 da a (54) Finally, as a approaches oo, equations (53) gives dXia h3 + lim -a1 [h +p - (55) da Lh +Pi For equation (54) to be true, it must be that dXa < Xi - (56) da a 19

Suppose that for some a > a*, we have dXl,/da = 0. Equation (56) implies that X1, > /Ml. Therefore, X1l is strictly decreasing in the region Xl, < /l. Therefore, if a is increased more than a* and (55) is negative, Xia increases first, only to decrease with higher a and to hit Xi, = li at some a > a*. After that, it strictly decreases with a limiting slope given by (55). If a is increased more than a* and (55) is positive, X1, increases first, there does not exist a > a* such that Xl, = /p1, and lima _oodXl1/da is given by by (55). We shall derive a quite restrictive sufficient condition for having dXl,/da > 0 for a > a*. (hI + p) Pr [a(7r1- - p) + 1 + T2 < Xo] = h3 +p (57) Define a' as 721l' = C' (721 - 21) + 21 = a (71 - ) + 1l + T2 (58) where T21 = r2 + rT. As a result, (57) becomes (hl + p) Pr [a' (721 - Y21) + /21 < Xla] = h3 + p (59) and hence Xla. = at G21 h3 + P J21) + p21 (60) where G21 is the distribution of r21. Therefore G-1 [(h3 + p) / (hl + p)] > P21 implies that dXl,/da > 0 since (58) gives 2 Var (2) + Var(r) (61) (61) Var (r2) + Var (r1) and hence dXc= 0dX d (62) da da' da 20

if G21 [(h3 + p) / (hi + p)] > 21. As a corollary to this result, we get G-1 h3p + 1 h3 P 2 [h > P 21 = F h > (63) 21 h -+p U2 hi+p since the opposite would contradict dXIl,/da > 0 for a > a*. 4.2 Case when h2 > h3 > 0 Revisited We want to shown that in the case of h2 > h3 > 0, we also have the sufficient condition for dXl,/da > 0, a > 0, that is G-1 [(h3 + p) / (h1 + p)] > U21 implies dXl,/da > 0. Substituting in (17) from (18) we get JX2a+Xa+Al(Ca-1) X2cj+X-'l-A U,1 /I ~ ~ J/, fi (t) f (u) dtdu+ X2a ~ / fi () dt f2 (X h3 +p (64) Jo J Jo hi + p which can be rewritten as,-Al -+l 2a +Xi -e-at+ul (Ce-1) +h3 +p j a /+j jX2c+Xia-t+(a-)f2 (u) fi (t)dudt = h (65) hi +p and equivalently as X^r+Xi O-J1 -U + X2t+Xc,-Ct+Al(a- 1) j~/ +glA jX~+Xf2 (u) fi (t) dudt= (66) X2ocXl a l [X2a +XI a -tt+A(a1) h3 +p oX2f+l~-l-"+~l fX2+Xlo-Ct+~l(c-l) h,+0 / -,, xl) f2 (u) fi (t) dudt + h + p a -Jx^- JJ2 J hi $ As a result, if G2-1 [(h3 + p) / (hl + p)] > t21, then the right-hand side of (67) is also at least equal to f21. Therefore dXla/da > -dX2l/da > 0. 21

5 Generalization with Uncertain Delivery Dates Suppose that the outside suppliers are unreliable and it is required to quote, before any processing occurs, the delivery dates for the outside supply parts needed at stage 2 and 1. Suppliers unreliability is captured by defining 72 and r71 as the time elapsed between the quoted delivery date and the actual delivery dates at stage 2 and 1 respectively. We assume r72 and 71i to be continuous random variables with distributions G2 and G1 respectively. The first stage in the SDP is triggered whenever outside supply parts arrive at stage 1 or whenever processing at stage 2 is completed, whichever occurs last. The optimal starting policy at the first stage is still a wait-until policy given by ll - ~-X if /I > Xyl (1) =if 1 (67) 0 otherwise where XF = F- [(p + h2 + h2 / (p + hi). To determine y*, X1 and X we solve Min J2(y2,X21,X) = h3(12 — X21+ E[2])+(h3+h3)y2+ (68) oo r00oo h2 J [w - - (X21 - Y2 - X)]( w) g (v) dwdv + ~o, v+X21-y2-X1 h2 j -[(X - Y2 - X1) + v - w] g (w) gi (v) dwdv + Jo Jo Pr [X21 - Y2 - T < X1 - r71] E [J1 (X21 - Y2 - )] + Pr [X2l - Y2 -r > X1 - r71] E [J1 (X1 - r1)] s.t. Y2 > 0,X21 > 0,X1 > 0 where 77 _ 772 + 72 with distribution G. Differentiating with respect to Y2 we get V X1: 6J2 (Y2, X21, Xl) 6J2 (y2, X21 X) +X21, X 0 SY2 eX21 22

hence y2 = 0 provided J2 (Y2, X21, X1)/6X21 = 0 at X21 = X21. Equation (68) becomes Min J2 (X21, X) = h(12 -X21 + E [12]) + (h3 + h3) Y2 + (70) 2 [w - - (X2t - X)] ~w (w) ) dwdv + +O +X21-X 2 / +x [(X21 - Xi) + v - W] g (W)gl (v) dwdv + 1X1 jv+X2-Xi [X -v / / h X [(X,- v)- t] f, (t) dt+ JX1-x; JO Jo r00 p [It - (X - v)] fi (t) dt] g (w) g (v) dwdv + x1 —V st *v+X21-X1 rX21 -+2(XZ1 -jX1 ) f f -W /xX Jo22 Jo3 (X2-w-t + /hi I 0(X - )(X) fi ( t) dt (gl (v)(w) dwdwv + rX2 -1 -w-( l -X) X21-W h _ /h 1 / (X2 W <i - -t f(t) t+ J^21 ^1 PX21-Xi W-(X12-X\) J2 ~ (X-X o 2'1X ) i /2 hi [ h ( - t) fip (t) dt+ 91 (v) (w) dvdw s.t. X21zi > 0, X1 > O After further manipilations, differentiating with respect to X21 and X1 gives E2V2 ( = hp x; /;+X~lo'i(t)g(w)^(vdwd+ (71) A2 (X2 i Xi) rX1-Xi X21 X2 1 < -w (hl + p) AI - x2-i (t) g (w) gl (V) dtdwdv + JXo J-X21 -X2 J 23

0- _ v+X21 -Xi 1 (h2 + h2 + P) IxT J g (w) ig (v) dwdv + _- -Xl X2.. - - (h2 + h2 +p) j Xg1(w) g (v) dwdv - (h + h + ) = 0 and 5J2 (X21, X1) X1 v+X2 l-Xi X-v X2, - (hi + P) -J (h + Jo 1 fi (t) g (w) gl (v) dtdwdv (72) c)Ai )Jx -Xi o Jo / 00 rV+X21-X1 - (h2 + h2 + P p) X x g(w)gl (v)dwdv + h2=0 It can be shown that the Hessian of J2 (X21, X) is positive-definite by differentiating (70) twice, hence X2x and Xl are indeed given by (71) and (72). Note that in the case of unreliable outside suppliers, there are instances where X1 >_ X~. Therefore, the realization of the delivery date for the outside supply parts needed at stage 1 may be such that parts arrive while the remaining time till the due date is still larger than the optimal planned lead time at stage 1. And if, in addition to this, processing at stage 2 has already been completed, then some intentional waiting time at stage 1 is induced until the remaining time till the due date becomes equal to the optimal planned lead time at stage 1 for processing at stage 1 to start. This extra waiting time represents the additional cost due to quoting outside supply parts delivery dates earlier than the beginning of the optimal planned lead time at stage 1, as a protection against suppliers uncertainty. 6 Conclusion We considered the problem of quoting delivery due dates to various suppliers in an assembly system with random processing times. We assumed that an order for a project has been accepted and a due date for the completion of the project has been set in advance. We also assumed that the suppliers are perfectly reliable and that the suppliers delivery due dates must be quoted before any processing occurs in the system. Once the delivery 24

due dates have been quoted and processing has begun in the system, it was necessary to determine the optimal starting time at every stage in the assembly system, due to the randomness in the processing times at the various stages. We showed that the optimal starting policy at each stage calls for no intentional delay whenever outside supply parts arrive at that stage and that the optimal delivery due dates can be determined analytically. We also showed that in the case of the system consisting of two stages in series, the difference between the optimal delivery date of outside supply parts needed at stage 2 and the optimal delivery date of outside supply parts needed at stage 1 decreases with increasing processing time variance at stage 1, while the optimal delivery date for outside supply parts needed at stage 1 is advanced under mild conditions with increasing processing time variance at stage 1. If the outside parts delivery dates were preset, the optimal starting time at each stage is described by a simple wait-until policy, where the manager waits until the greatest of the delivery date and the beginning of the optimal cumulative planned processing time of all downstreams stages to begin processing. Thus the optimal starting policy at each stage is completely determined by a critical number, the optimal cumulative planned processing time of all downstream stages, showed to be the minimum of a convex function. With increasing processing time variance at stage 1, the optimal planned lead time at stage 2 decreases and the optimal planned lead time at stage 1 increases under mild conditions. We also consider the particular case when the ouside supply parts at each stage are available at no additional cost and characterize the wait-until policy that completely determines the optimal starting time at each stage. Finally we consider the case of unreliable outside suppliers and show that there are instances where the optimal delivery date for outside supply parts needed at stage 1 is quoted earlier than the planned lead time for stage 1 due the uncertainty in the actual delivery date, hence inducing some intentional waiting time in case processing is completed at stage 2, the ouside supply parts have been delivered and the remaining time until the due date is still larger than the planned lead time at stage 1. 25

References 1. Baron, D.P. (1970), "Price Uncertainty, Utility and Industry Equilibrium in Pure Competition.", Int. Econ. Rev. 11, 463-480. 2. Gerchak, Y., and D. Mossman (1991), "On the Effect of Demand Randomness on Inventories and Costs.", Ops. Res. 21, 804-807. 3. Rothschild, M., and J.E. Stiglitz (1970), "Increasing risk I: A Definition.", J. of Econ. Theory 2, 225-243. 4. Sandmo, A. (1971), "On the Theory of the Competitive Firm Under Price Uncertainty". Am. Econ. Rev. 61, 65-73. 5. Yano, C.A. (1987), "Setting Planned Lead Times in Serial Production Systems with Tardiness Costs", Management Sc. 33, 95-106. 26

h~ A h2 r h, h Due Date h3 h2 hi Stage 2 --- Stage 1 Figure 1 - - - - 12- - - - - - - - - - - _ I. I -- I - --- -X1 - ---- -! ~-I l - Y2 + -T2 - -1 ~~~~I I I I I Due date Due date Y 1 - 1 +- -- 11.-., Figure 2

UNIVERSITY OF MICHIGAN 3 901 5 04735 0635