OPTIMAL ASSIGNMENT OF DUE DATES AND STARTING TIMES TO IDENTICAL JOBS ON A SINGLE MACHINE WITH RANDOM PROCESSING TIME Walid R. Abillama Medini R. Singh Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 93-13 March 1993

Optimal Assignment of Due Dates and Starting Times to Identical Jobs on a Single Machine with Random Processing Time Walid R. Abillama Medini R. Singh Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 March 24, 1993 Abstract We consider the problem of assigning optimal due dates and optimal starting times to a set of identical jobs on a single machine when processing time on the machine is random. There are N identical jobs ready to be scheduled in the facility. Processing time at the machine is random with known distribution and raw material is available at no additional cost. There is an earliness cost for holding a finished job an extra unit of time and a tardiness cost for being short an extra unit of time past the due date. There is also a cost for quoting an uncompetitive due date for each job in the set, this cost being zero if the quoted due date does not exceed a certain "acceptable" value A. The objective is to minimize the expected total cost of quoting the due dates and scheduling the jobs in the set. The optimal due dates 1

and the optimal starting times are determined analytically. They are the unique solutions to a set of first order conditions. We show that there exists an optimal solution where the due date of each job is at least equal to A, with the exception of the first job to be processed. The optimal starting time for a particular job in the set is described by a simple wait-until policy. This optimal policy is completely determined by a single critical number, which represents the optimal planned lead time for that job. We show that the optimal planned lead times are non-increasing with the position of the job in the sequence, with the exception of the planned lead time of the first job to be processed being the smallest. Finally we show that adding another job results in quoting earlier (or the same) due dates to the jobs in the preexisting set. 1 The Problem 1.1 Introduction A set of N identical jobs are ready to be scheduled for processing on a machine. The optimal due dates for these identical jobs need to be quoted before any processing occurs on the machine. There are no other jobs in the facility, raw material is available at no additional cost and the machine cannot process more than one job at a time. The jobs consist of projects that must be completed once started in order to be delivered to different customers, hence preemption is not allowed. Job N is the job with the earliest due date, hence the job to be started first since all jobs are identical. The processing time r at the machine is random with known distribution F. Once the due dates d, i = 1,.., N of the jobs have been quoted, it is required to determine the optimal starting policy y (li, di_,..., dl), i.e. the optimal waiting time before starting the processing of job i, i = 1,..., N, given that di is 4i units of time away and given the previously quoted due dates di_l,..., d. Obviously, y (IN, dvNl,..., d) = O. This observation stems from 2

the fact that having assumed job N is ready to be processed, we would like to quote its due date as early as possible, hence IN dN. The objective is to minimize the cost of quoting the due dates and scheduling jobs N through 1. A holding cost h per unit time is incurred if a job is completed before its quoted due date and a shortage cost p per unit time is incurred otherwise. The cost of quoting an uncompetitive due date is C (.), assumed to be a strictly increasing function of the due date, convex, continuous, twice differentiable, and zero for a due date no greater the acceptable limit A (Jones [10]). A is a value determined by the market and by the customer conception of how long is she willing to wait before her order is delivered. 1.2 Background Considerable research has been done on assigning optimal due-dates for the single machine scheduling problem with earliness/tardiness penalties. In their surveys, Baker [1] and C(heng [3] report of no analytical work done with the machine having random processing time. Further work with deterministic processing time have been done by De, assuming a given common due date in [7] and assigning distinct due dates in [8], and by (Cheng [4] assigning the same time window (flow allowance) to all jobs. Random machine processing time has been considered in conjunction with random due dates as in De [6] and Emmons [9] with the objective of minimizing the weighted number of tardy jobs. We are not aware of any past research that considers random processing time and assigns distinct optimal due dates with earliness and tardiness penalties. Cheng [5] describes a model that assigns optimal due dates in the presence of tardiness/earliness penalties, and in which the due dates are random. In his model, di = pi+ ki for each job i, where di is the due date, pi is the random processing time and ki is a job waiting allowance, a decision variable. Cheng assumes in his model that the distribution of wi, the time elapsed until the start of job i processing time, is given. This model suffers from two serious deficiencies which prevents it from addressing and analyzing the problem that the author has set to. 3

The first deficiency is that one cannot quote a random due date. The second deficiency is that if job i is processed before job j, then the distribution of Wj depends on pi and ki, hence a) the search for kI must be carried using sequential decision making i.e. using the information given by the realization of pi and b) fj (wj) is not data but rather a function of ki. This paper is organized as follows. In section 2 we analyze the case when N = 2, i.e. determine the optimal due dates d* and dt and the optimal starting policy y* (11) for job 1. We also analyze the case when N = 3 to illustrate the derivation of the optimal starting policy when there is more than one remaining job to be processed, a situation that is not present when N = 2. Hence for N = 3 we determine Y2 (12, d1), y* (11), d3, d and d;. We show in this section that for N = 2 there exists an optimal solution where the due date of the second job to be processed is at least equal to A and that for N = 3, there exists an optimal solution where the due date of the second and the third job to be processed is at least equal to A. We also show for N = 3 that, a) the optimal planned lead time (that completely determines the optimal starting policy) of the second job to be processed is at least equal to the optimal planned lead time of the third job and that b) adding the third job results in quoting an earlier (or the same) due date for the second job than the one quoted in the case when N = 2, i.e. when the second job was the last job to be processed. We discuss in section 3 the economic interpretation of the first order conditions that give rise to the optimal due dates and to the optimal starting policy in sections 2. We also discuss in section 3 the managerial insights provided by the practical results obtained in section 2. We generalize in section 4 for N > 3. Section 4 may be skipped if the reader is not interested in the mathematics. We conclude in section 5 by suggesting some further directions in research. 4

2 Dynamic Programming Formulation 2.1 Two-Jobs Model Suppose that N = 2. We will use backward stochastic dynamic programming to determine d., dt and yl (11). The first stage is triggered when job 2 is done processing. Figure 1 depicts the time advances in a two-job model. The first stage problem is defined as following:.J] (1l) = Miny,>oh [(i, - yi) t] fi (t) dt p p [t - (11- Y1)] fi (t) dt (1) where the first term is the first term is the expected holding cost and the second term is the expected shortage cost. It can be easily checked that J1 (1i) is convex in Yl by differentiating it twice. Therefore, the optimal solution y* (11) 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 wait-until policy, where we wait 11 - X* units of time before processing the job if 11 - X* > 0, and process immediately otherwise. y ()11 1 - X 1 > X (2) 0 otherwise where Xl = FT1 [p[h] is called the optimal planned lead time for job 1. Figure 1 shows that 11 = 12 + r1 -r2. Hence the second stage problem is defined as following: rd2 Min J2(d2,r) = C(d2)+C(d2+ri)+h (d2-u)f2 (u)du+ r00 (u - d2) f2 (u) du + E [J (12+ ri - T2)] (3) J2 s.t. d2, r1 0 ()ur goal is to show that the Hessian of J2 (d2, rl) is non-negative. The Hessian of the first four terms is non-negative by assumption and from the first stage analysis. Suppose 5

that Jj (11) is convex in 11, then we are done. Our goal is to show that J; (11) is convex in 11. Substituting (2) in (1), we get h h; (X - t)f (t)dt + pfSx (t - X) fi (t) dt,1 > X ( h fo (l1 - t) fi (t) dt + p fl (t - 11 ) fi (t) dt X* > 11 It is easy to see that (4) is continuous and differentiable at 11 = X*. Finally, differentiating J1 (11) twice shows that it is convex in 11 and hence the Hessian of J2 (d2,r) is non-negative. To determine d* and rt, we substitute 1i by (d2 + rl - r2) in (4), apply the expectation operator, differentiate (3) with respect to d2 and rl and set to zero. Doing this we get d2 +rl d2+rl-u E [J (d2 +'1 r2)] d= h l (d, - u -t) fi (t) f2 (u) dtdu + Jd2+ri-X J rd2+ri roo P J r J {/ (t + u - d2 - r) fi (t) f2 (u) dtdu + Jd2+ri-X; Jd2 +ri-u roo P (1l + - d2 - rl) f2 (u)du + d2 +rl [h J (X - t) fi (t) dt+ 00oo d2 +r-X* (t - X) fi (t) dt f2 (u) du (5) and hence tJ2 (d2,'1) =C' (d + 1) +[ h (X - t)f (t)dt+ 07'1 = O p (t - X')f f (t) dt f2(d2 + ri -X ) + rd2n +rl rd2+rl-u h/d2+rl X; L fi (t) f2 (u) dtdu - d 2+rl -X hf2 (d2 + 71 - X1) / t - X ) fi (t) dt - 7J &d2+ril 1-X Jd(-Iri-u JO (11I d 11 I'. f (' ~ I -6 (t) t f/2 (d2 + rl - t x r (

P + fL (u) du - plj2 (d2 + ri) = 0 (6) d2+rl 5.1.2 (d2,,'1) ) 2 00 J2 ( () = 7' (d2)+ h f2 (u) du - p f2 (u) du = O (7) d2 2 which reduce to 6SJ2 (d2, 11) d2+rl d2+rl -u C'((d2 + 7.1) + h ( f (t)f2(u) dtdur61 Jrd2+ri-X Jo rn2+rl roo roo P 2d ) +ri- fi (t) f2 (u) dtdu - p f2 (u) du = 0 (8) Jd2+rTl-Xi J2+rl-u J2+rl — 2 C' (d2) + Jh () f2 (u) du - p f2 (u) du + 1 =0 (9) [Y-C -- *] i (10) p+^ 2 eIt can be een that er sessineg ri by O in (8) gives 2 (2 f d2 2 { < C (d2) + (h + p) + (u) du J2 (d2+ 7r1) = h CJ fi' (d2) + h -u)2 f, (t) f2 (u ) d(du -X frd+ri rXf 7 2 f, (t) f2 (u)~& d-u p (-() d

+P J f2 (d + ri - X1*) fi (t) dt + pf2 (d2 + r - X ) fd +rl (h + p) + fi (d* + r - u) f (u) du > 0 J ) +ri -X 2 Hence C2 (d* + <1) < 0 W1 > 0. Note also that C' (d + ri) = 0 for ri < A-d*. Therefore letting d1 = d2 + r 1 we get * z, z E [T+ X1,A]} if 7+X < A; =- - (11) > A otherwise 2.2 Three-Jobs Model Before extending the problem to N jobs, it is necessary to analyze the case when there are three jobs in order to illustrate the computation of y (12, di) Y* (12, rl) where rl = d -d2. Ill a three jobs problem, job 2 is not started immediately as in a two jobs problem. Suppose its due date has already been set and cannot be changed. Hence its starting time must depend on the remaining time till its due date and the due date of job 1 at the time job.3 is done processing, since this is when stage 2 is triggered. As a result, it also depends on the optimal planned lead time of job 1. Figure 2 depicts the time advances in a three jobs problem. In a three jobs problem, the decision variables are d3, r2 and ri at stage 3 (where 7r2 = 2- d3), Y2 at stage 2 and Yl at stage 1. y* is given by the optimal starting policy defined in (2). To determine y*, we solve 12 -Y2,J] (12, r1 ) = Miny2>o h [(12 - Y2) - t] f2 (t) dt + P - [t-(12 - Y2)] f2 (t) dt + E [J* (11)] (12) To solve (12), we substitute by (2- Y2 X2 To solve (12), we substitute 11 by (/2 - Y2 + rl - r2) in (4), substitute 12 - Y2 by X2 in (12), differentiate (12) with respect to X2 and set it to zero. Note that convexity in X2 is conserved since the Hessian of J2 (d2, rl) is non-negative in a two jobs problem and 8

( (.) is convex (equation (3)). Doing this, we obtain a first order condition similar to equation (7), but with X2 instead of d2 and without the due date cost terms. dJ( )- =hJ f2 (u) du - p f2 (u)du + (X2 + ) (13) dX2 2 and hence y* is given by the following wait-until starting policy: 1 (2 - X2* if 12 > X* y. (1,,') 2 - 2 (14) 0 otherwise where X2, the optimal planned lead time of job 2, satisfies (13). Note that X2 > X1 since substituting X2 by X1 in (13) gives 2 (12 Ix2=x; = h J| f (u)(u du -p f2 (u)du+ I (Xl + ri) But we have shown previously that V' (d* + rL) < 0 Vri > 0. Using the same arguments, we also have that I} (Xl + r7') < 0. As a result X* > Xl. To determine d3, r and r, we solve Min J3 (d3,r2, r1) = C(d) + C(d + r2) + C (d3+ r2+ r1) + rd3 roo h (d3-v) f3 (v)dv + p (v-d) f3(v)dv + E [J* (d3 + r2- r3, r )] (15) s.t. d3, r2, r > 0 Our goal is to show that the Hessian of J3 (d3, r2, ri) is non-negative. The Hessian of the first five terms is non-negative by assumption and from the first stage analysis. Suppose that the Hessian of J' (12, r1) is non-negative, then we are done. Our goal is to show that 9

the Hessian of J2 (12, 1) is non-negative. Substituting (14) in (12), we get h fo 2 (X - u) f2 (u) du + p f^2 (u - X) f2 (u) du+ J (, ) E [.J* (X; +,1 - 12)] 12 > X 12 (/, ^,' )= (16) h fl2 (12 - u) f2 (u)du + p f2 (u -12) f2 (u) du+ E [Jl (12 + ~r1 - 72)] X2* > 1 Using (13), it is easy to see that (16) is continuous and differentiable at 12 = X.. Since J* (11) is convex, then the Hessian of J2 (12, r) is non-negative and therefore the Hessian of J.3 (d3, 72, 71) is non-negative. To determine d3, r* and r*, we substitute 12 by (d:3 + 7'2 - T3), apply the expectation operator, differentiate (15) with respect to d3, r2 and r1 and set to zero. Doing this we get rd3+r2-X2 fX2 E [J (d3 + r2 - T3,,)] = h (X2 - u)f2 (u) f3 (v) dudv + "d3 +r2 — X2 /; 1P J~ X2 J (u - X2) f2 (u) f3 (v) dufdv + d2 d3+r2-v h 3+r2-X2 (d3 + r2 - - u) f2 (u) f3 (v) dudv + d3 +r2 r00 P d2 (u + - d3- r2) f2 (u) f3 (v) dudv + P d3+r2-X2 d3+r2-v p (/2 + V- d3- r2) f3 (v) dv + 3 +Tr2 rd3+r2 -X2 E [Jj (X2 + r, - 2)] + f3 (v)dv + o00 I3+ 2 E [J (d3 + r2 + ri - v -r2)] f3 (v) dv (17) Jd+r+r -X2 and hence SJ3 (3, r"2, r) c'(d3+,r~r1) E'[Jj (X2+r - \ f)t\'-2 S1~1 - f3 (v) dv qX E' [J'1 (d3 + r-2 + r - T2 - V)] f3 (v) dv rf3+-r2-X2 But E' [Jj (d. +.i - r2)] = J2 (d] + ri) as defined in a two jobs problem. Substituting 10

we get 6d3.:3(da.7'2 I' d3 +r2 - X2 6:(d, 1 ) = (' (d3 + 7'2 + 7'1) + 2 (X2 +') f3 (v) dv + (18) fd3 +2 +rl-X1 d3 +r2 +r1-v fd3 +r2+rl-u-v h J fi (t) f2 (u) f3 (v) dtdudv + Id3 +r2 +r1 X d3 +r2+r+i-v d3 +r2 +ri -u-v f d3+r2+ri-Xj fd3+r2+rl-Xv fIh J+r2 -X* 1d X 1d+ fi (t) f2 (u) f3 (v) dtdudv - j3+r2+ri-Xj JO JO fd3+r2+rl -X d3+r2+rl -v oo P +r2 -X2 I + r2+-xi* fi (t) f2 (u) f3 (v) dtdudvJd3g +T2-X 2 Jd3 +T2 +r1 -X;-v Jd3 +2 +r -U-v d3+r2+rl -X* 00 p ++X f2,() f 3 (v) dudvJda +r2-X2 3 +r2 +rl -v r3 +2 +rl + rd3 +r2+rl v - oo P J d3r - i (t) f2 (u) f3 (v) dtdudv - a3+r2+ri -XJ 3 d +r2+rl-u-vu d3 + r2+rl 2oo 0oo p I +r-X 2 f2 (u) f3 (v) dudv- f3 (v) dv = 0 J3+r2+rl-X!~* Ed3+r2+Trl-v) Jd3+r2+rl Also 6J3 (d3, 1'2,?'1) 3(3'2 r1)=C' (d3 + r2) )+ C (d3 + r2 + rl) + rd3+r2 rd3r2-v Jh +r2-X2 ~ f2 (u) f3 (v) dudv - (d3 3+r2 fOO r00 P d +r2 - X2 3+r2 f2 (u) f3 (v) dudv - p u f3 (v) dv + d 3 +T, 2- X2 d3 +r)2-' 3 + -+r2 roo +r2-X2 E' [J (d3 + r2 + r1 - 72 - v)] f3 (v) dv = (19) d^3 +T2-X2 and finally *d is obtained from (20). r.*, r and X2 are determined simultaneously using (13) and the following set of first-order conditions: 3 ( d3i2i1 ) = C' (d3 + r2 + rl) + V (X2+ r ) 3 f3 (v) dv + SJ3 ((13,,'2,' =) ( =0+r2,+r2+ri)=~ (21) 3(,21)=C'(d3 +, r) + C'1(d + r2 + r) + 32 (d3 + r2) + 1 (d + r2, d + r2 + rl) = 0 (22) 11

where LI@ (d + rd2,d +'2 + zr1) and I3 (d3 + r2) are as defined in (18) and (19). Clearly d* is equal to the due date of the first job to be processed in a two jobs problem, hence d* < X < X*. We want to show that r2 > 0. To show this, equation (19) can be rewritten as 6J3 (d3, 1'2, 7'1) -— J3 (d3,, 1'1) = (/ (d3c( + r) + ri( + + 67'2 rd3 +r2 rd +r2-v hd/ 32I f2 (u) f3 (v) dudvPJd++r2-v f2 (u) f3(v) dudv -p f3 (v) dv + J3 (d3 r2, r) C'+ --' -rl-C (d3 + r2 +- rl) - d3 +r2-X2 2 (X2 + ri) 3J f3 (v) dv = 0 (23) Substituting r2 by 0 in (23) and using the fact that d3 < X* we get 13 (d3,'2, r1)2 =' (d3) + h f2 (u) 3 (v) dudv - 1P j f2 (u) f3 (v) dudv -p f3 (v) dv C' (d*) + (h + p) /3 3 f2 (u) f3 (v) dudv - p JO JO C'(^0;)+(h~p)~Q~l~(~)dv-p SJ3 (d3, r2, rl) < C' (d3) + (h + p) f f3 (v) dv p = J3 (d3, r2, ri) d3=d 0 —,JokVJVP ~Sd33 We want to show that r* > O. Substituting rl by 0 in (21) and C' (d* + r*) from (22) we get SJ3 (n3, n) ^^T1) ^ C'/( ^ + r;3'+r*~-X 2 3 (d, 2, i) I=0 C (d3 + r2) + I (X2) J f3(v) + (d + r, d + r) 6-1 2- 2(X3j2 3 -2 d* +r* — X2 = 2, (X2) 3/o 2 -f3 (v) dv + C (d3; + r2, d3 + r) - kV (d3 + r2) But we have show previously that + r). Using the same arguments 12

we also have 1' (X2) < 0. Therefore it is sufficient to show that TP (d* + r2*, d + 7'r) <:' (d3 + r7) and we are done. In fact comparing the holding cost coefficients in both expressions we get d3 +r*-X* d +r2-v pd*+r2*-u-v J3X2 1 3 2X 3 2I f, (t) f2 (u) f3 (v) dtdudv + Jd;+r2-X2 Jd3+r*-X*-v JO d*+rT*-X; fjd+r2-v d +r2-u-v Jd+2 3 i j 2 fi (t) f2 (u) f3 (v) dtdudv + *d,+r*-X2 JO 3 2 + dr +T *-X1dr-v 0 d*+r-u-v J3+r /jd+ 2 +- fl (t) f2 (u) f3 (v) dtdudv < * +r* - X2 JO d*; +r d~r+-v dr +r-u-v 2 3 2 jd3 fr (t) f2 (u) f3 (v) t dudv d +r2 —X2 Jo ('omparing the shortage cost coefficients, the terms with single and double integrals cancel and only the terms with triple integrals in 1 (d] + r*, d + r*) remain. Therefore 1 (^d + 7, d3 + ^r2) K< l' (d3 + r2*) and r7 > 0. Equations (21) and (22) can be rewritten (C' (d + r~2+ )=- + =f f- 3 (vd + r2,d +r2+ r) (24) and (C/ (d+ 7'2)+ C' (d + r-2 + r) = -I (d + r2) - -' (d + r2, d+ r2+ ri) (25) I)enote by R3 and R3 the right-hand side of (24) and (25) respectively. Differentiating R3 with respect to r1 and using the fact that X' = F-' [p/ (p + h)] we get = - (hp r d r+r +l-X* rd +r2 +r-v f 33 = -(h + P) \ +r2 -X2 d+r2+l- fi (dX + r2 + 1 - f+2 (u) f3 (v) dudv+ ++,-x 0 fi (d3 j+ r2 + rl -u -) f2 (u)f3 (v) dudv'1 (X +,) j3 f (v+r) -X 13

Differentiating R1 with respect to 7'2 we get R3 =- SR +' (X2 +,.) f3 (d3 + r2-X2) - I(X2+ ri) f3 (d3 + r2 - X2) 0 Differentiating R2 with respect to 72 and using the facts that X' = F-1 [p/ (p + h)] and X. satisfies (13) we get R2 /d*+r2 2 = -(h+p) 3 f2 (d3 + r2 - ) f3 (v)dv S7h2 Jd+r2-X2 d *+r2+ri-X; d3 +r2+rl-v - (h+P) + jd+r2-X r2+r x fi (d3 + r2 + r - u - v) f2 (u) f3 (v) dudv+ [ *(^-r2-A2 * +r24-rl-X* -v fd*+r2+rl rd +r2+rl -v d3+ fi (d3 + r2 + rl - U - ) f2 (u) f3 (V) dudv < 0 Jd*+r2+rl-Xj JO Note that R1 and R2 vanish at d*+r2+rl > 27+X, d*+r2 > T+X2* and rl > r+X*-X*. Note also that X* < + T+X since substituting X2 in (13) by T+Xi gives h > 0. Consider figure 3 and the fact that equation (25) can be rewritten using equation (24) as C' (d3 + r 2) = -I (d3 + r2) + I (X2 + r) 2 f3 (v) dv (26) where i.1 (X2 + r1) < 0 and (d3*+ ) = r (h +p) 3 f2 (d3 + r2 -v) f3(v) dv > 0 3 *^+rz-X2 From figure 3, if A > 2T + Xj then there exists r* = A- d3 and r7 = A- d - r. If T+ X* < A < 2T+ X* then r >A- d - r* and there exists r* = A - d3. Otherwise, >*2 > A - d and 71* A - d3 - r*. Letting d1 = d3 + r2 + rl and d2 = d3 + r2, we have that if A > 2T + Xi, then there exists d* = A and d\ = A. If 7 + X2 < A < 27 + Xi* then dT > A and there exists d = A. Otherwise, d2 > A and d = A. Before leaving 14

the three jobs problem we want to compare the optimal due date of the second job to be processed in a two jobs problem to the optimal due date of the second job to be processed in a three jobs problem to study the effect of adding a third job on the optimal due date of the second job to be processed. In a two jobs problems, r' is given by C' (d + r1) = -' (d2 + ) (27) where T2 ( d + 1) (h + p) Id fi (d2 + ri - u) f2 (u) du > 0 (28) J2+rl -X1 as was shown previously. In a three jobs problem, r* satisfies equation (26). As can be seen in figure 4, the right-hand sides of (27) and (26) are equal at r1 = 0 and r2 = 0 respectively since d- = d <_ X1 < X2. Furthermore, the derivative of the right-hand side of equation (26) is steeper than the derivative of the right-hand side of equation (27), that is d*+r2 -(h+p) 3 f2 (d3+r2- v) f3 (v) dv + (X2 + ri) f3 (d + - X) < /d* +rl - (h +p) fi (d + ri -u) f2 (u) du J dz+rl-X 2 since d: = d3 and X1 < X2. As a result, the right-hand side of (26) intersects C' (d + r2) at a smaller value than the one at which the right-hand side of (27) intersects C' (d* + r-1), i.e. 1r* < r'* and hence the optimal due date of the second job to be processed in a two jobs problem is at least equal to the optimal due date of the second job to be processed in a three jobs problem. 3 Economic Interpretation In this problem, the due dates must be quoted before any processing occurs on the machine. However, due to the randomness in the processing times, once the due dates have 15

been quoted and processing has started, then the starting time of the next job in the sequence lmust be determined given the set of predetermined due dates of the jobs remaining to be processed. In this section we shall provide an economic interpretation to the firstorder conditions that give rise to the optimal due dates (equations (22), (21) and (8)) and the optimal starting times (equation (13)), in the two and three jobs problems analyzed in the previous section. 3.1 Optimal Starting Times Consider the three jobs problem. Suppose that there remains one job that has not been processed yet and whose due date have been already set. Then its starting time is determined by (2), determined completely by the solution of the classical Newscat problem which balances the tardiness cost p and the earliness cost h to find the optimal starting time X*. The problem is more complicated when there remains two unprocessed jobs whose due dates have already been set. As in the previous case, the starting time for the next job is determined by (14), determined completely by the solution to (13). Equation (13) has a very appealing economic interpretation. It can be rewritten as dAJ22 =-1 h [Pr {2 < X2} + Pr {r2 > X2 - X; + rT,rT1 + T2 X2 + r,}] - dX2 p[Pr {r2 > X2} + Pr {T2 > 2 - X-X + ri,1 + 2 > X2 + r}] = 029) It illustrates the combined impact of the marginal costs associated with each of the two jobs, on the decision to determine the optimal planned lead time X, i.e. the time window inside which the next job (job 2 in our case) must be processed. Again, the effect of job 2 is the one of the Newsalien problem, indicated by the first probability term inside the marginal holding and shortages cost brackets in the middle side of (29). The effect of the second job (job 1) on the current decision is less myopic in nature. Marginal savings in holding cost due to waiting an extra unit of time before starting job 2 are 16

acheived only if the processing time of job 2 continues past the predetermined starting time of the next job and job 1 processing time did not end past its due date. While the second condition is a reminder of the savings achieved in the newsgirl problem, the first condition complicates the non-myopicity of the decision process, in the sense that no marginal savings in holding cost of job 1 due to waiting an extra unit of time before starting job 2 are acheived if some slack time is realized between the completion of job 2 and the start of job 1. Similarly, the marginal increases in shortage cost of job 1 due to waiting an extra unit of time before starting job 2 occur only if the processing time of job 2 continues past the predetermined starting time of the next job and job 1 processing time (does end past its due date. Equivalently, no marginal increases in shortage cost of job 1 due to waiting an extra unit of time before starting job 2 are incurred if some slack time is realized between the completion of job 2 and the start of job 1. This information agrees with the intuition that job 1 has no impact on the starting time of job 2 if it is certain that some slack time will be realized after the completion of job 2. If X. <K X - r1, then it is predetermined a priori that no slack is allowed between the two jobs and job 1 is rushed immediately after the completion of job 2. In that case Pr {y1 < 0} =Pr {r2 > X - (X- r)} = 1 For a three jobs problem, we have shown that X2 > X >_ X1 - rl hence we never decide a priori to rush the next job and X2 is indeed determined by (29). This property can be generalized for larger number of jobs. We prove it for any number of jobs in the next section. 3.2 Optimal Due Dates Equations (22), (21) and (8) also have an appealing economic interpretation. They can be rewritten respectively as C(' (d + r.2) = -hPr {3 > d - X2 + r2, -32 < d + r2} + 17

pPr {r3 > d - X2 + 7'2, 732 > d + r2} (30) (' (d + + 72 +.,1) = -hPr {T3 > d,2 - X2 3 +., 32 + + - X, -31 < dt +1 rl+ + pPr {r3 d_> d- X2 + r2, r32 > d + 2 + rl- X;, 31 d + r + 72} (31) (' (d2 + r1) = -hPr{T2 d2 - X2 + ri,T21 r d2 +r1} + pPr {Ir2 > d - X* + rl, 21 > d2 + rl} (32) The marginal costs associated with the first job to be processed are obvious as illustrated in (9) and (??) for a two and three jobs problem respectively. Determining the optimal due date for the next job in the sequence is slightly more complicated. Consider (30). For a three jobs problem, the marginal increases in holding cost associated with job 2 due to quoting a due date one unit of time longer are incurred only if job 3 is completed past the predetermined starting time of job 2 and job 3 is completed before its quoted due date. In other words, no marginal costs in holding cost are incurred due to delaying delivery one unit of time if some slack is realized after the completion of job 3. On the other hand, marginal savings in shortage cost associated with job 2 due to quoting a due date one unit of time longer are acheived only if job 3 is completed past the predetermined starting time of job 2 and job 3 is completed after its due date. For each job, the combined marginal effects of increases in holding cost and savings in shortage cost is negatively decreasing with increasing values for the quoted due date of that job, as the positively decreasing right-hand side of equations (30) and (31) indicate. In other words, the tardiness argument is stronger than the earliness argument for job 2 and 1. Consider job 2 and equation (30). This is due to the fact that marginal savings and marginal increases occur jointly, only when there is no slack after the completion of job 3. Moreover, savings occur only if the processing time of job 2 exceeds its due date, while increases occur only if it does not. As a result, the rate of the marginal savings is positive and the rate of marginal increases is negative because the higher the due date of job 2, the more likely the processing time of job 2 will exceeds it if no slack is going to be realized after the completion of job 3. 18

Equation (30) and (31) illustrate the intuitive fact that if there was no cost for quoting an uncompetitive due date, then one would quote due date values at least equal to + X2 for job 2 and 27+X* for job 1. However if that cost exists and Max{A, 27 + Xl,T + X } = A, then 7T+ X2 <d < A and 2T+ Xl <~ d\ < A. These ranges of multiple optimal due date values represents the guaranteed slack that the manager will have after the completion of job 3 and after the completion of job 2 respectively under the optimal starting policy. We assumed the marginal effect of uncompetitive due date cost to be positively increasing with increasing values for the quoted due date of that job. In instances when A is sufficiently small so that the latter does not apply, the quoted due date must be larger than A if the combined marginal effects of the three costs is negative at A, and exactly A otherwise. As a result, if the cost of quoting an uncompetitive the due date is linear to the right of A with slope c, it is more likely to quote A when c is high. Several additional observations canl be made from equations (30) and (31). The higher is p and the smaller is h, the slower is the rate of negatively decreasing combined marginal effects of savings in holding cost and costs in shortage cost, hence the more likely that it is higher in abslolute value than C' (A) and the further is the due date. Furthermore, the larger is the processing time variance, the higher is the term containing p and the less likely is that the due date is A. Therefore, the tradeoffs are that high p/low h and high variance increase the quoted due date, force us to produce early and keep a high chance of introducing slack time between the processing of consecutive jobs, while the cost of quoting an uncompetitive due date have the opposite effect and ensures that jobs are rushed without any slack in between. Finally, the analysis presented shows that r* > O, i = 1,..., N -1 and hence quoting a common due date for all the jobs is suboptimal in single machine problems with random processing time and earliness/tardiness costs. 19

4 Extension to N-Jobs Extending the problem to N > 3 jobs, the problem becomes for 1 < i < NN - 1:,li-yi, Ji (lr, i-,..., ri) = Minyi>o h J [(i - yi) - t] fi (t) dt + p [t - (li - yi)] fi (t) dt + E [JiL1 (l - y, + rii - -Ti, ri,..., ri)] (33) and for i = N: Mill JN (dN, rN-l,..., 7'1) = ((dN) +C(dN +rN-1) +... + C (dN +rN- +... +rl) + odN 00 h (dN -t) fN (t)dt + p (t-dN)fN(t)dt+ N E [JN1 (dN + rN_-1 - rN, rN2,..., r)] (34) s.t. dN, rN_,...,rl 0 where ri = di - di, i = 1,..., N - 1. Proposition 1 y* (li, dil,..., dl) y* (li, ri_,..., rl), the optimal waiting time before processing of job i is started, given that di is li units of time away and given the quoted due dates di1,..., dl, is expressed by li Xt ifli > X* y (l, r'i-1,..., ri) l - (35) 0 otherwise where Xi, the optimal planned lead time of job i, solves dJi (l, ril,..., ri) /dXi = 0 (after subtituting li - y by Xi). It is true for i = 1 and 2. To prove this for 3 < i < N. we assume that Ji* l (li-1, r_2,..., ri) is convex in 1;_I, hence (35) is true for job i, and show that this implies J* (, ril,,'1) is convex in ls, hence (35) is true for job i + 1. In fact, substituting y (li, ril,..., ri) in 20

(l, r-1,..., l), we get h Sox (Xi - t) f, (t) dt + p fX (t - X?) fi (t) dt+ E [j1 (Xi + ri_- - ri, ri-2,..., r1)] 4i > Xi J (li,' i-,...,' ) = J (Xi + yi, i,...,') fyi=,Xi= (36) h f' (li - t f(t)dt p ffr (t - 1( ) fi (t) dt+ E [Jl (li + ri_1 - ri, l'i-2,..., r1)] i < Xi It is clearly convex in li for li < X* since the first 2 terms are convex in 4i and we assumed that J*-, (li-i,7 ri-2,...'1) is convex in lil-, hence convex in li. Furthermore dJi* (li, r_1,..., 7r1) /dl = 0 at li = Xi since we assumed that Xi* solves dJi (li, r 7,., r1) /dXi = 0 (after subtituting li -yi by Xi), hence solves dJi (Xi + yi, ri_1,..., ri) I{y,=o,x,=li}/dl = 0. Proposition 2 X*, 1 < i < N - 1 solves the following equation (after subtituting li- yi by Xi): dJ. (Iiji r 1-1 ~~, 7 1 i- i-1 Xh,Pr < E rk + Xi, E > E <rk + Xi- Xj, dX. j=l k=j k=j k=j+l k=j ZE rk> E rk + Xi-+,.... - k=j+2 k=j+l ) i t i-1 i i-1 p EPr{ k rk + Xi, rk + Xi,-X, j=1 k=j k=j k=j+l k=j i i-1 E Tk> E rk + Xi -X,..... = 0 (37) k=j+2 k=j+l It is true for i = 1 and 2. To prove this for 3 < i < N - 1, assume that it is true for i. J* (li, r1il,..., r) is given by (36) and J?+1 (l+,I r,...,rl) is given by (33). Substituting li by li+1 - yi+ + ri - ri+1 in (33), letting li+ - yi+ = Xi+1, differentiating (33) with respect to X*1, setting it to zero, and after doing further manipulations we get dJi+1 (li+ i,, rl) = hPr {ri+1 < Xi+1} - pPr {ri+l > Xi+ } + dXi+l 2[ dXi1+ (38) 21

biut from (36), we have that dfJi (Xi+l + r - ri+1, 7-l_,..., r) J 0 if ri+1 < Xi+l + 1ri - X dXi+1 a (,_l,-l, ) li=xi+ +i-,, otherwise (39) For ri+l > Xi+l + 7i- X*, it is given by the middle side of (37) evaluated at Xi = Xi+1 + ri - ri+1. Substituting this latter in (38) gives the following first order condition: i+l i i+l i. E hk > P +k Xi+l -+ X+, E r E r+Xk + Xi+ll,()d =j+=l k=j L k=j+2 =j oo i+1 p Pr {r /I+ > Xi+,7 - X Pr{ Erk > Z'rk + Xi+1, (j=l Xi+l+ri-X k=j k=j i+1 Z i+l i X+1 l k > E k + Xi+ -X, E I- E rk + Xi+-X.. fi+l (u) du =0 k=j+l k=j k=j+2 k=j+l which reduces to +dJ-+ (4+1,r,-,r) = hPr {ri+l < Xi+ } -pPr {i+1 > Xi+1} + dXi+l i ri+l i i+l i hEPr E rk< E rk+Xi+l, E T> E rk+Xi+l -X;, j=l 1k=j k=j k=j+l k=j i+l i {: 7 > E rk + Xi+l - X....k=j+2 k=j+l i ri+l i i+1 i hEPr rE k E rk +Xi+l, E Tk ~ rk +X+l-X3, j= k=j k=j k=j+l k=j i+1 i E Tk > rk+Xi+l - X+l.... = ck=j+2 ck=j+l 22

and finally to d.l 1;l (I1+ ri - i+1 i i+l dJ+ (l+,...,. = h, Pr Z< T k< rk + Xi+l, Tk > r + +Xi+1 -X, dXi+ j=l k=j k=j k=j+l k=j i+l i 1 E Tk E rk+ Xi+l - Xj+1 - k=j+2 k=j+l i+l fi+1 i i+1 i h Pr E Tk > rk + X+1,i+ Tk > Zrk + Xi+1 - X3, j=l k=j k=j k=j+l k=j i+1 Tk >E rk +Xi+l-X.... = (40) k=j+2 k=jl J and we are done. Proposition 3 X* > Xi*, i = 2,..., N -1 Proposition 4 r'i, i = 1,.., N - 1 satisfy the following set of first-order conditions: ( N N-1 n N-1 C7 (d + 7(N-1) +...+) = -hPr E k < rk + dN, rk E r + dN - Xi k=i k=i k=i+l k=i n N-1 E rk > E rk + dN - Xi+1, ^ k=i+2 k=i+l N N-1 N N-1 +pPr E rk E rk + dN, E rk > E rk + dN- Xi k=i k=i k=i+l k=i N N-1 rk >T E rk + dN - Xi+1. = ~ (41) k=i+2 k=i+l The proof is by differentiating (34) with respect to ri and noting that JN (dN, rN-1,.., ri) /67S is nothing but the due date cost terms plus the terms containing ri in (37), for i 1,..., N-1. Proposition 5 d7N is given by: C' (dN) = -hPr {Tv < dN + pPr {rN > dN} = 0 (42) 23

The proof is by differentiating (34) with respect to dN and noting that JN (dN,rN1, i..., r ) /SdN is nothing but the due date cost terms plus the terms containing XN in (37). Proposition 6 Denoting by (ri,..., rN, X2,..., XN_) the right-hand side of (41), we get for i = 1,...,N - 1:, x E [(N - i) T + X - dN -E=+ r;, A dN - -k-=i+l kI if (N - i) + Xi < An to r. is negative for i = 1,..., N - 1, and that it vanishes at r. = (N -i)T + X7 - d^ - *Proposition 7 Let d* be hie quoted due date for job i in an N > A and N-1 - N (A- d- k=i+l k..., rN, X2,,., XN-1) < C' (A) We have considered t peotherwise (43) The proof is by showing that the derivative of VN (ri_.., rN, X2, ~~~, XN-I) with respect to 7'i is negative for i = 1,..., N -, and that it vanishes at ri = (N -i) + Xi* - d-,N-1 il* k=i+l k' Proposition 7 Let di* be the quoted due date for job i in an N jobs problem. d(+l)* < )iN, i=,..., N. 5 Conclusion We have considered the problem of assigning optimal due dates and starting times to a set of identical jobs ready to be processed. We have shown that optimal quoted due dates 24

date one unit of time longer. The optimal due date shave been shown to be at least equal to A, the "acceptable" value set by the market or by the cutomer conception, below which any quoted due date will be assigned without any extra cost. We have also shown that once the due dates are quoted, optimal starting times of subsequent jobs in the sequence can be also obtained analytically by balancing the marginal effects of holding and shortage costs, due to waiting an extra unit of time before starting the job with the earliest due date. The issue of sequencing the jobs was not raised because we assumed the jobs to be identical with same processing time distribution on the machine and same cost structure. However, a future direction on research could be one in which this assumption is relaxed. Hence it would be required to find the optimal sequence in which the jobs must be processed on the machine, their quoted due dates and the optimal starting time policy once processing has started. It would be interesting to determine necessary conditions on the cost structure and/or processing time distributions and parameters that will allow for some specific sequences to be optimal and to question whether these conditions are reasonable. Another direction in research may be the generalization of this model to serial production lines and flow shops. References 1. Baker, K.R. and G.D. Scudder (1990), "Sequencing with Earliness and Tardiness Penalties: a Review", Operations Research 38, 22-36. 2. Bertsekas, D.P. (1987), "Dynamic Programming: Deterministic and Stochastic Models", Prentice Hall 3. Cheng, T.C.E. (1989), "Survey of Scheduling Research Involving Due Date Determination Decisions", European Journal of Operations Research 38, 156-166. 25

4. (Cheng, T.C'.E. (1991), "Optimal Constant Due-Date Determination and Sequencing of n Jobs on a Single Machine", International Journal of Production Economics 22, 259-261. 5. Cheng, T.C.E. (1991), "Optimal Assignment of Slack Due-Dates and Sequencing of Jobs with Random Processing Times", European Journal Of Operational Research 51, 348-353. 6. D)e, P., Ghosh, J.B. and C. E. Wells (1991), "On the Minimization of the Weighted Number of Tardy Jobs with Random Processing Times and Deadline", Computers and Operations Research 18, 457-463. 7. De, P., Ghosh, J.B. and C. E. Wells (1991), "Scheduling to Minimize Weighted Earliness and Tardiness About a Common Due-Date", Computers and Operations Research 18, 465-475. 8. De, P., Ghosh, J.B. and C. E. Wells (1992), "Optimal Due date Assignment and Sequencing", European Journal of Operations Research 57, 323-331. 9. Emmnons, H. and M. Pinedo (1990), "Scheduling Stochastic Jobs with Due Dates on Parallel Machines", European Journal of Operations Research 47, 49-55. 10. Jones, C.H. (1973), "An Economic Evaluation of Job Shop Dispatching Rules", Management Science 20, 293-307. 11. Yano, C.A. (1987), "Setting Planned Lead Times in Serial Production Systems with Tardiness Costs", Management Science 33, 95-106. 26

I 1^ ~ x2I I I,_....- -12 - - -, I I I I I I I ~ —T - i 41 - 1 -T-2 - - -- -- - I I 2d*1 i - Figure 2 XI 14- -d - - d — -* - -i - -- -r - - _ r_ I~ - - - -- - ---- - - - - -- d; - - I! I I- - - -1 -pJ_ e- - - - - I.3pI Figure 1

A-d3 A - d3 2t +X -d3 T+X1 -X2I + - +X2 -d -- c 2 + X Figur —de Figure 3

-% (d2) -(d*d + rl)'I~I C' (da +r1) -3 P(ds) RHS of (28) \/ C'(d;+r2) I I rg I I 0 No. ~0 A-d * r2 Figure 4

UNIVERSITY OF MICHIGAN 9011111111111111111111104735 II353011111111111 3 9015 04735 3530