Optimal Assignment of Due Dates and Starting Times to Identical Jobs on a Single Machine with Random Processing Time Walid R. Abillama Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109-2117 December 1993 Technical Report 93-35

Optimal Assignment of Due Dates and Starting Times to Identical Jobs on a Single Machine with Random Processing Time 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 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 on the machine and processing time on the machine is random with known distribution. We assume that the same raw material is required for all jobs to start and that it is available at no additional cost. There is an earliness/tardiness cost for finishing a job one unit of time past/prior to its 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 and the optimal starting times are determined analytically. They are 1

the unique solutions to a set of first order conditions. We show that there exists an optimal solution where the due date of the last job to be processed is at least equal to A. We also show that 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 also show that the optimal planned lead times are nonincreasing 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 a job to a preexisting set of jobs results in quoting earlier (or the same) due dates to the jobs in the former 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. We assume that the same raw material is required for all jobs to start and that it is available at no additional cost. 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 treo different customers, hence preemption is not allowed. Since all jobs are identical with the same cost structure, they will be scheduled in an Earliest Due Date (EDD) sequence. Denote by job N the job with the earliest due date, hence the job to be started first. The processing time r at the machine is random with known distribution F. Once the due dates df, i = 1,.., N of the jobs are quoted, it is required to determine the optimal starting policy y' (li, di-1,..., dl), i.e. the optimal waiting time before starting job i, i = 1,..., N, given that di is i units of time away and given the quoted due dates di_,..., di1. Obviously, yN (IN, dN-1,..., d1) = O. This observation stems from the fact that 2

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 than the acceptable limit A (Jones [10]). A is a value determined by the market and by the customer conception of how long is he or 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 Cheng [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] considers a model with random due dates and tardiness/earliness penalties. However, the model does not assign optimal due dates and neither does it determine optimal starting times on the machine for the different jobs in the set. The objective of our paper is to develop a methodology for determining optimal starting times and optimal due dates for a set of jobs ready to be processed on a single machine, in order to minimize the total production and due dates quoting costs in a random processing time environment. This paper is 3

organized as follows. In section 2, we analyze the case when N = 2. We determine the optimal due dates d* and dt and the optimal starting policy y* (1i) for job 1. 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 it is bounded by the sum of the highest realization of the processing time on the machine and the optimal planned lead time of the second job to be processed. In section 3, we analyze the case when N = 3 to illustrate the derivation of the optimal starting policy whenever there is more than one remaining job to be processed, a situation that does not occur when N = 2. Hence for N = 3, we determine y* (12, d1), y* (1i), d*, d* and dt. We show in this section that the optimal planned lead time of the second job to be processed, which completely determines the optimal starting policy of that job, is at least equal to the optimal planned lead time of the third job to be processed. We also discuss the effect of adding a third job on the optimal due date of the second job to be processed and show that it decreases (or stays the same). In section 4, we discuss the economic interpretation of the first order conditions that give rise to the optimal due dates and to the optimal starting policy and we discuss in section 5 the managerial insights provided by the practical results obtained in sections 2 and 3. We generalize in section 6 for N > 3. Section 6 may be skipped if the reader is not interested in the mathematics. We conclude in section 7 by suggesting some further directions in research. 2 Two-Jobs Model Suppose that N = 2. We use backward stochastic dynamic programming to determine d*, dt and y* (1l). The first stage is triggered when job 2 is done processing. Figure 1 depicts the time advances in a two-jobs model. The first stage problem is defined as following: J; (lI) = Miny >oh j [((l - yl) - t] fi (t) dt + p j [t - (I, - y)] f, (t) dt (1) 4

where the first term is the expected holding cost and the second term is the expected shortage cost. It can be easily checked that J1 (ll) is convex in y, by differentiating it twice. Therefore, the optimal solution yl (1) 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 - XA units of time before processing the job if 11 > X1, and process immediately otherwise. Y (I)= - X if 1l > X1 y1 ={ (2) [0 otherwise where X1 = F~' [p/ (p + h)] is called the optimal planned lead time for job 1. Figure 1 shows that 11 = di - r2. Hence the second stage problem is defined as following: rd2 Min J2 (d2, d1) = C(d2)+ C (di) + h (d2- u) f2 (u) du + ~00 p (u - d2) f2 (u) du + E [J; (di - 2)] (3) s.t. dl > d2 > 0 Our goal is to show that the Hessian of J2 (d2, d1) is non-negative. The Hessian of the first four terms is non-negative by assumption and from the first stage analysis. Suppose that J1 (1i) is convex in 11, then we are done. Our goal is to show that J1 (11) is convex in 11. Substituting (2) in (1), we get hX; (X - t) fi (t)dt + p fx (t - Xl) fi (t) dt 11 > X* J1* (lI) - ({4) h h {f1 (1 - t) fl (t) dt + p f1 (t - ll) f, (t) dt X > 1 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, d1) is non-negative. To determine dr and dt, we substitute 1i by (d1 - r2) in (4), apply the expectation operator, differentiate (3) with respect to d2 and d1 and set to zero. Doing 5

this we get cdi rdl-u E [J1 (di - r2)] h= ] (dl - u - t) fi (t) f2 (u)dtdu + (5) d roo p X t (t + u - di)f, (t)f2 (u)dtdu + Jd1-X* J1d-u Pd (/1i + u - di)f2(u)du+ 1 d X [h x (X* - t) f, (t) dt + p j (t-X) f (t) dt f2 () du and hence -J2 (d2, d1) = C (di) + E[J (di -T2)] 3d1 = C' (d) + h jx (X - t)f, (t)dt + p J (t-X ) f, (t)dt f2 (dl - X)+ odi odJ-u X; h 1 x dl (t) f (u) dtdu - hf2 (dl - Xf j' (X -t) f, (t) dt - PJd -X fi (t) f2 (u) dtdu + pf2 (di) tfi (t) dt - Pf2 (dl - X) (t - X) fi (t) dt-p f2 (u) du - pf2 (d) = (6) 62 (d2, 1) = C' (d2)+h f2 (u) du -p f2 ( )du = (7) d2 2 which reduce to J2 (d2, d1) C (dl)+ E'[J (d) - 2)] /du P~ (d,)+h Jd\-X; JO-u C'(di) + )hd fi (t) f2 (u) dtdu - di 00 P / fi (t ) X f2 (u)dt f2 (u) du = 0 (8) J-X* Jd\-u Jd\ J2 (fd2(dX) =d2: 52(d2 ) C (d2)+h f2 (u) duup f )du= (9) w nol P ~'f2 (u) du 0 (7) d* > O can be determined easily from (9). d* satisfies 2 ph ] - (10) 6

Proposition 1 d >) d2 Proof: To show that d' > d*, we substitute d, by d* in (8). Doing this we get 5d,2(d,)=d1 v ~ Jod; Jfo;-' 2(216J)2 = C (d2) + 2 f, (t) f2 (u) dtdu - 5d2 p 2 f (t) f2 (u) dtdu - p f2 (u) du = c (d2) + ( + P) 2 2 f x (t) f2 (u) dtdu - p <' (d;) + (h + p) f2 (u) du - p -J2 di- 1d2 2= Proposition 2 There exists an optimal solution with d* > A. Proof: E' [J' (di - r2)] is non-decreasing in dl and E' [J{ (d, - r2)] = 0 for d, > T + X* where T is the largest realization of the machine processing time. This can be shown by differentiating E [J* (di - r2)] twice with respect to di. Doing this we get S^ 1[J1 (di - T2 )] = h i fi (di - u) f2 (u) du - h f2 (di - X ) f, (t) dt +P d x; fi (di - u) f2 (u) du - p f2 (d - X*) fn (t) dt +P JX f (di - X) f (t) dt + Pf2 (dl - X) (h + P) f-X ft (di - U) f2 (u) du > O Hence E' [J! (dl - r2)] < 0. Note also that C' (dj) = 0 for dl < A. Therefore (= {xx e [7+Xi',A]} if T+X <A < A > A otherwise 3 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 derivation of y~ (/2,dl). In a three jobs problem, 7

the starting time of job 2 depends on the optimal planned lead time of job 1. Figure' depicts the time advances in a three jobs problem. In a three jobs problem, the decision variables are d3, d2 and d1 at stage 3, Y2 at stage 2 and yi at stage 1. y* is given by the optimal starting policy defined in (2). To determine Y2, we solve 12 - Y2 2 (12, d1) = Miny2>o h f [(12 - Y2) - t] f2 (t) dt + Pj [t - (12 - y2)] f2 (t)dt + E [J (1)] (12) J2- Y2 To solve (12), we substitute 11 by (12 - Y2 + d1 - d2 - T2) 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 J1 (11) was shown to be convex in 11 in a two jobs problem and the first two terms are convex. Doing this, we obtain a first order condition containing all the integral terms in (9) and (8), but with X2 and (X2 + di - d2) instead of d2 and dl respectively. That is dJ ( d h f2 (u) du - p f2 (u) du E [J* (X2 + d - d2- 2)] (13) drX2 X2r h f2 (u)du - p f2 (u) du + h JOX+di- jX2 fiJ(tf2(u)dtdufX2+dl-d2 fX2 +di-d2-u I I f (t) f2 (u) dtdu - JX2 +d-d2-X; o rX2+dl-d2 roo JX2+dl-d2-X JX2 +dl -d2 -u P I f2 (u) du = 0 (14) J X2+dl —d2 and hence Y2 is given by the following wait-until starting policy: 12 - X2 if 12 > X2*(15) Y2 (12 i di)=- (15) p f c0 otherwise where X2, the optimal planned lead time of job 2, satisfies (14). 8

Proposition 3 X < X2 _< ~ + X' Proof: This proposition is true since substituting X2 by X* in (13) gives dJ2 (12d = hf f2 (u)du-pJ f2 (u)du +E'[J (X +di-d 2)] dX2 X=1 = d = E' [J (X; + di - d2 - T2)] < Hence X* > X*. Also, X* < r+Xi since substituting X2 by (T + X;) in (14)gives h > 0. To determine d3, d2 and dl, we solve Min J3 (d3,d2, d) = C(d)+ C (d) + C (d) + h j (d3 - v f3 (v) dv + p (v- d3) f (v) dv + E [J* (d2- r3, d)] (16) s.t. dl > d2 d3 > 0 Our goal is to show that the Hessian of J3(d3,d2,dl) is non-negative. To show that, we substitute d2 by (d3 + r2) and di by (d3 + r2 + rl) and show that the Hessian of J3 (d3, r2, ri) is non-negative. This implies that the Hessian of J3 (d3, d2, dl) is non-negative by Theorem 3.4 in Rockafellar [12]. After making the abovementionned substitutions the problem becomes Min J3 (d3,r2, ri) = C (d3) + C (d3+ r2) + C (d3 + r2 + ri) +;. h (d3 -v) f3 (v)dv + p (v - d3) f3 (v) dv + E [J2* (d3 + r2 - 73, r)] (17) s.t. d3, r2, rl > 0 Our goal now becomes to show that the Hessian of J3 (d3,r2, ri) is non-negative. Clearly 9

the Hessian of the first five terms is non-negative. Suppose that the Hessian of J2 (12, r1) is non-negative, then we are done. To show that the Hessian of J (12, rl) is non-negative we substitute (15) in (12) and get h f2 (X* - u) f2 (U) du + p fSx (U - X) f2 (u) du+ E [J' (X* r1 - T2)] J2 (l2,) 12 2 (18) h f12 - u) f2 (u) du + pfu1 (U - 12) f2 (u) du+ E [Jj (12+ r -T2)] X2 > 1 Using (14), it is easy to see that (18) is continuous and differentiable at 12 = X*. Since J1 (hi) is convex, then the Hessian of J2* (12, r1) is non-negative and therefore the Hessian of J3 (d3, r2, r1) is non-negative. As a result, the Hessian of J3 (d3,d2, d) is non-negative using Theorem 3.4 in Rockafellar [12]. To determine d*, d* and dt, we substitute 12 by (d2 - T3), apply the expectation operator, differentiate (16) with respect to d3, d2 and d1 and set to zero. Doing this we get d2-X2 oX2 E [J2 (d2 - 3, di)] = h j jo (X2 - u) f2 (u) f3 (v) dudv + d2-X2 /~ p J d X2I, (u - X2) f2 (u) f3 (v) dufdv + rd2 /d2-v h j (d2 - v - u) f2 )3 (v) dudv + d2-X2 ~ /d2 r00 P (u +v - d2) f2 (u) f3 (v)dudv + d2-X2 d2-v r00oo P J (2 + v -d2)f3 (v)dv + 2 d2 -X2 E [J; (X2 + di - d2 - T2)]j f3 (v) dv + 2 E [Jr (d-v -r2)] f3 (v) dv d2-X2 and hence 8J3'(d3d2 di)= C'(dl)+ E'[J (X +- d -d,-r)]jd2 f (v) dv+ ~d1~roo J E' [J; (d -r2 -v)] f3 () dv (19) Jdz2 -X2 10

Substituting we get 6J3 (d3 d2, di) [rX2 +di-d2 X2+dl -d2-u 6d1 C' 2 (di)+ [h 10 fi (t) f2 (u) dtdu6di [ Jx2 + d -d2-X; Jo rX2+dl-d2 - oo P X2+-d2-X -2 fi (t) f2(u)dtduJX2+dl-d2-X* J2+dli-d2-u roo d2 — X2 P \+d f2(u)dul f3(v) dv + 2+di -d2 fd\-X; rd -v fd\-u-v h \_x jd1\x- u v fi (t) f2 (u) f3 (v) dtdudv + Jd2-X2 Jdl-X*-v Jdl rdl-V odl-u-v hj 1 1 fi (t) f2 (u) f3 (v) dtdudv - did-X* dl-v poo P - -- f (t f2 () f3 (v) 3 dtdudv - Jd2-X2 Jd-X-v d-u-v rdl-X roo PJ f2 (u) f3 (v) dudv - Jd-X2 Jd-v PdX / /__ fi (t) f2 (u) f3 (v) dtdudvJdi JO 00 P Jd - X f2 (u)f3 (v) dudv -p f3 (v) dv =0 (20) J d-X1 Jdi-v Jd1 We also have J3 (d3, d2,dl) (d2) hd-X2 Sd2 CI (d2) +h 2-X2 f2 (u) f3 (v) dudv - 5d2 roo r P f2 (u) f3 (v) dudv - P f3 (v) dv - 2 -X2 2-v 2 d2-X2 E' [J; (X2 + di - d2 - T2)] j f3 (v) dv d2 d2 -v C' (d2) +h d2X2 f2 (u) f3 (v)dudv - rd2 roo roo P ZJ - X ) f2 3 (u) f(v) dudv -p f3 (v) dv - X2 +dl -d2 X+dl-d2-u h X2+dd fi (t) f2 (u) dtdu2 dl - d2-d2 J +d -d f2 (u) du f (v) dv = 0 (21) 11

and finally 5J3 (d3, d2, di) dC' (d)+h J3(d3,d2 ) = C'(d3) + h f3(v)dv - p f3(v)dv =0 (22) d3 is obtained from (22). Clearly d3 is equal to the due date of the first job to be processed in a two-jobs problem, hence d3 < X* < X. d2, dt and X* are determined by solving simultaneously (14), (20) and (21). Proposition 4 d3 < d2 < T + X* Proof: To show that d3 < d, we substitute d2 by d3 in (21) and use the fact that d3 < X*. Doing this we get -- AA —d2 ) = C' (d) + ho j f2 (u) f3 (v) dudv - d* oo roo P d f2 (u) f3 (v) ddv -p f3 (v) dv JO d 3-vv = C'(d3) + (h + p) f2 (u) f3 (v)dudv - p.< C' (d3) + (h + p) 3 f3 (v) dv - p = 3 (d3, r2 0 id3 To show that d < -T + X*, we substitute d2 by (T + X*) in (21). Doing this we get J3(d3d ld2=+X2 = C (T + X2) - E' [J* (di - T - 2)] > 0 3d2 Proposition 5 d* < dt < 2+ + X* Proof: To show that d >~ d*, we substitute dl by d* in (20), d2 by d* in (21) and substitute C' (d)) in (20) from (21). Doing this we get (J3 (d3, d2, dl)d - C, * E' (ddld=dd = C(d2) + [J1 (X2 - )]j f3 (v) dv + 5d)l 12 12

fd2 Xi rd2-v fd2-u-v h dX* fd*-V r d*-u-v _h /2 1 ] 2 fi (t) f2 (u) f (v) dtdudv, d2-X2 d2-X-v o pj*x dI - d(* -f (v d - d2 -X1 2 fi (t) f2 (u) f3 (v) dtdudv - 2 1 roo fd*-X fd-v /d- v h d;; JO d-2-v fi (t) f2 (u) f3 (v) dtdudv - Jd-X; JO 1 P fd*-x; ~-* f2 (u) f3 (v) dudv - 2d-X2~d-v j- o Jd-X2 Jd-X-v d-u-v fd;-Xr [00 Id [J; X2I 2_f(-( uf3(v)dtdvP /2 d-v j2) f3 (t) f2 (u) f3 () dtdudv - 2 -X Jd-v P f )f (t) f2 (u) f3 (v)dtdudv - Jd2-X Jd — v Jd P 2 0f (u) f (v) fdudv - f ( v) dddv rd*-X* rd*-v d-u- v Ph f i (t) f2 (U) f3 ) dtdudv + d~ —X; Jd -X,-v o d*drd rd*-v d *-u-v h 1 J j 2f2 (u) fi ( t) f ) fd () dtdudv - 2 1 d*-X' o-v1 P 2 X d2 - t f2 ( u) f3 (v ) dudv - h~ J~-X2 J O d-X2 Jfd-vj2-v P 2 2 f i (t ) f2 (U) f3 (v) d tdudvv JJ-x;' J o- JJO — d2-v Jd2 1-v J Jd X2 JO 22 r 2 u f(f (v)Ududv) f3(v) dudv <3 ~rd -X* rd-v d-u 1 // fi2t) f2 (u) f3 (v) dtdudv + Jd^-X'2 Jd^ ^ - X2 \ 2 f2 (t ) f3 (v) dtdudv pd2 13

d2 -X do Jdo-u-v jd-x 2d;-v d;- fi (t) f2 (u) f3 (v) dtdudv + Jd; Jd-Ov d- u fi (t) f2 (u) f3 (v) dtdudv = rd2 rd -v rd2-u-v *-x;/ Jo o J2 x2- f f, (t) f2 (u) f3 (v)dtdudv < Jd-2 Jo Comparing the shortage cost coefficients in (23), the terms with single and double integrals cancel and only the non-positive triple integrals terms remain, resulting in dt > d*. To show d; < 2y + X1, we substitute d1 by (27 + Xf) in (19). Doing this we get &J3 (d3, d2, d1) -3 (- d21 dl=2+ = C'(2 + X) + E' [J1 (X2 + 27 + X* - d2 - T)] j ff3 (v) dv + roo J-X E' [J1 (2T + X; - - v)] f3 () dv Jdz2-X2 C'(2T + X)>O since E' [Jl (d1 - T2)] = 0 for di > T + X* from proposition 2 and d* <~ + X2 from proposition 4. Before leaving 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. Proposition 6 Adding a third job results in quoting earlier (or the same) due dates to the two preexisting jobs in the set. Proof: In a two-jobs problems, dt is given by (8) rewritten as C' (d1) = -E' [J1 (dl - r2)] (24) 14

where PE [.Jl (di - Tr2) ] i E d -= (h + p) Jx fl (dl - u) f2 (u)du > (25) as was shown in proposition 2. In a three jobs problem, d* satisfies equation (21) rewritten as yd2 d2 -v' (d2) -h f (u) f3 (v)dudv+ Jd2 -X2d JP f2 (u) f 3 (v)dudv + p f3 (v) d + J2 -X2 2-v 2J E' [J; (X2 + d -d -2 - 2)] 2 f3 (v)dv (26) Differentiating the right-hand side of (26) with respect to d2 we get d2 X2 -h f2 (d2 -v) f3 (v) dv + h f3 (d2 - X) f2 (u)du - Jd2-X2 d2 0oo P J f2 (d2- v) f3 (v) dv+p f3 (d2 - X2) f2(u)duro00 P /xf3(d2 - X2) f2 (u)du - pf3 (d2 - X2) + X2 f3 (d2 - X2) E [J1 (X2 + d1 - d - 2)] d2 -(h+p) f2(d2-v)f3(v)dv+ Jd2-X2 f3 d2 - X2) h f2 (u) du-p f (u) du - E' [J (X2 + d - d2 - T2)] - (h +p)2 Xf2 (d - v) f3 (v)dv < 0 (27) J2-X2 The right-hand sides of (24) and (26) are equal at d1 = 0 and d2 = 0 respectively. Furthermore, the derivative of the right-hand side of equation (26) given by (27), is steeper than the derivative of the right-hand side of equation (24) given by the negative of (25), that is [d Xf2 (d2 - v) f3 (v) dv> dl fi (d, -u) f2 (u) du J2d -X 2 J15 -X 15

since Xl < X2. As a result, the right-hand side of (26) intersects C' (d2) at a smaller value than the one at which the right-hand side of (24) intersects C' (dl), i.e. d* <K d 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. 4 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 been quoted and processing has started, then the starting time of the next job in the sequence must be determined given the quoted optimal due dates and the optimal planned lead times of the jobs remaining to be processed. In this section we shall provide an economic interpretation to the first-order conditions that give rise to the optimal due dates (equations (21), (20) and (8)) and the optimal planned lead times (equation (14)), in the two-jobs and three-jobs problems analyzed in the previous sections. 4.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 coimpletely by the solution of the classical Newsvendor problem which balances the tardiness cost p and the earliness cost h to find the optimal starting time Xl. 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 (15), determined completely by the solution to (14). 16

Equation (14) has a very appealing economic interpretation. It can be rewritten as h[Pr {.2 < X2} + Pr7 {T2 > X2 - X + r,T - + T X2+ r }1 - [Pr {T2 > X2} + Pr {r2 > X2- X1 + rl, T2 > X2 + rl}] =0 (28) where r1 is defined as in figure 2. Equation (28) illustrates the combined impact of the marginal holding and shortage costs associated with each of the two jobs, on the optimal planned lead time decision X2, i.e. the time window comprising the next job (job 2 in our case). The effect of job 2 is the one of the Newsvendor problem, indicated by the first probability term inside the marginal holding and shortages cost brackets in the left-hand side of (28). 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 achieved only if the processing time of job 2 continues past the predetermined starting time of the next job and job 1 processing time does not end past its due date. While the second condition is a reminder of the savings achieved in the Newsvendor problem, the first condition stresses 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 achieved 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. In other words, if X2 <I X1 - rl, 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 17

2. In that case Pr {fy < 0} = Pr {Tr2 X2 - (X1 - r)} = 1 For a three jobs problem, we have shown that X. >_ Xl > X> - r hence we never decide a priori to rush the next job and X* is indeed determined by (28). This property can be generalized for larger number of jobs. We prove it for any number of jobs in the next section. There exist scenarios in production where the manager must plan for the processing of two jobs in series and must decide a priori to rush immediately the second job independently of the realization of the first job. 4.1.1 A Serial Production System Revisited Consider for example a serial production line consisitng of two stages, where the processing time at stage 2 and 1 (stage 2 is the upstream stage), r2 and Tr are random with distribution F2 and Fl. Suppose that an order has been placed and a due date has been set at some point in the future. Assume that the order consists of a project and that once production is started at a stage, it must be completed. Assume also that raw material is available at no additional cost, there is a cost h2 and h1 for holding an extra unit of time the semi-finished product at stage 2 and the finished product at stage 1 respectively, there is a penalty p for finishing production one unit of time beyond the quoted due date d and naturally h2 < hi < p. Yano [11] considers this problem and solves the two-stage problem. However, the mathematical approach that Yano adopted renders the analysis of three-stage problem and larger extremely difficult. By formulating the problem using backwards dynamic programming we are able to provide additional insight into the optimal solution of larger problems. What is required to be determined in this problem is Y2 (12) and y* (li), the optimal starting time at stage 2 and 1 with the due date being 12 and 11 units of time away respectively. To determine y4 (11) we solve Jd (li) = Mins>0o h2 (l - -y)+ hl [(l - Yyl) - t] fi (t) dt + 18

P/ [t - ( y1 - Yi)] fi (t) dt (29) The objective function is clearly convex in yi and therefore yl (1i) is given by (2) where X1 = F-1 [(h2 + p) / (hl + p)] is the optimal planned lead time for job 1. To determine Y2 (12) we solve J2 (12) = Min.2>0E [J' (12 - Y2 - T2)] (30).J1 (1i) is convex in 11 using the same arguments as in (4), hence J2 (12) is convex in Y2. We substitute (12 - Y2) by X21, differentiate with respect to X21 and set to zero (note that convexity in X21 is conserved). The result is that y* (12) is given by (15), where X21, the optimal cumulative planned lead time for jobs 2 and 1, satisfies dJ2 (X2) h i r -x dJ2 (X2) hi, 2 fI (t) f2 (u) dtdu + h2 f2 (u) du dX2 J2-X Jo Jo X21 00o oo \ -P ( 1 -X 1 fi (t) f2 (u) dtdu + 1 f2 () u= 0 (31).21- X1 JX 21 JX2 1 which may be interpreted as dJ2(X21) - hlPr {r2 > X21 - X,r2 + < X21 + h3Pr {T2 > X21 X} dX21l -pPr {r2 > X21 - X, r2 + r7 > X21} = 0 (32) The obective of this paper is not to analyze the single period serial production system, but we have carried this analysis of the serial production system to illustrate a situation when it is decided a priori to rush the processing at stage 1 immedialtely after processing is done at stage 2, i.e. when no slack is allowed between two successive jobs independently of the processing time realization of the first job to have been processed. In this serial production system, the slack time between job 2 and job 1 is Yi and no slack is achieved 19

with certainty by having Pr {y <~ 0} = 1. Equivalently Pr { < 0} = Pr 72 > X; - Xl} = 1 which does occur, but only whenever X21 < X1. This result is counter intuitive since it means that the presence of job 2 has resulted in the allocation of a smaller safety time for both jobs 2 and 1 than the safety time that was originally allocated to job 1 alone. Mathematically, evaluating the first-order derivative at X21 = X1 gives dJ2 (x21<) dX 21 x21=x = (hl + p) Pr {T2 + r1 < X } - p (33) dX21 which may be either positive or negative. Hence there may be instances when h2, the holding cost at stage 2, is so high (with respect to the holding cost of raw materials assumed zero here) that it becomes more economical to wait long enough before releasing job 2 so as to ensure with certainty that when the processing at stage 2 is completed, the semi-finished product is not held at stage 2 but rather rushed immediately because the time remaining till the due date is less than its allocated planned lead time. It turns out that to ensure no waiting at stage 2, we must not release job 2 before we are X1 units of time away from the due date, hence the cumulative planned lead time of job 2 and 1 being smaller than the planned lead time that was originally allocated to job 1 alone. In this case, X1 < X1 is determined by solving d=(X21) (hi + p) Pr {r2 + r < X21 -p = 0 dX21 since (33) is non-negative and J2 (X2) is convex. Here X21 is simply F,21 [pl (hl + p)] and the two stages are pooled into a single stage whose processing time distribution is the convolution of the individual processing time distributions at stage 2 and 1, as Yano indicated in [11]. The problem becomes significantly more complicated for serial production systems with more than two stages. Consider for instance a three stage problem with 20

h3 < h2. Using the same arguments as in a two-stage problem, the first order condition in a 3-stage problem can take one of the two forms, depending on whether or not stages 2 and 1 were pooled. If they were not pooled and X1 is indeed determined by (32), i.e. X2 > X*, then the first order condition is given by dJ3 (1X31) = hlPr {r3 > X31 - X21*, 3 + T2 > X31 - X, T3 + r2 + 71 < X31} + dX31 h2Pr {73 > X31 -X2, T3 + T2 < X31- Xl } + h3Pr {3 < X31 -X21} - pPr {r3 > X31 - X21, T3 + T2 > X31 - X;, T3 + T2 + T1 > X31} (34) If they were pooled, then the 3-stage problem is treated as a 2-stage problem where lead time T21 at the new stage 21 has a distribution F21, the convolution of F1 and F2, and lead time r3 at stage 3 has a distribution F3. We also have if stages 2 and 1 are pooled that X = F [(p + 3) / (p + hi)] < - [(p + h2) / (p + h)] = X1 and in (34), 73 > X31 - X21 = T3 + T2 > X31 - X. Thus the first-order condition becomes d(31) = hiPr {T3 > X31 - X21, 3 + 721 X31} + dX31 h3Pr{ 73 < X -X1 }pPr {r3 > X31 - X2, T3 + r21 > X31} (35) In this latter case, it should be clear by now that due to convexity, stage 3 is pooled with the new stage 21 if and only if (35) is nonnegative at X31 = X21. If this is the case, we pool stages 1,2,3 and set X*1 = F31l [p/ (p + h1)] < X1 < X. Otherwise, X1 > X1 and X* is the unique solution to (35) set to zero. The case when stage 1 and 2 are not pooled is more complicated. Here, one of the three things can happen: a) Pool 3, 2 and 1, b) Pool 3 and 2, c) do not pool. We present the algorithm that determines the optimal configuration and hence X3. The algorithm is based on the convexity of J3 (X31) in X31, and the fact that stage 1 and 2 are not pooled i.e. X1 > X1 where X21 solves (32) and 21

-~ = F —l [(p+h2) /(p + hi)] Algorithm 1) If (34) is nonnegative at X31 = X1, then a) is optimal and X31= F,[1 [p/ (p + h1)] < X*. 2) Otherwise, if (34) is negative at X31 = X2, then b) is optimal, X1 < X <1 < X21 and we set X3 at the unique root of dJ3 (X31) = hPr {T3 + T2 > X31 - X,T3 + T2 + 1 < X31} + dX31 - h2Pr {T3+T2 X31 - X1 } + pPr {73 + 2 > X31 - Xl, T3 + T2 + rT > X31} = 3) Otherwise, c) is optimal, X1 < X1 <~ X1 and X1 is the unique solution to (34) set to zero. In contrast, the solution to the problem considered in this paper is never such that we decide a priori to rush the second job immediately after the completion of the first job and independently of the realization of the processing time. However, X* >~ X1 - r and X1 satisfies (28) indeed. The reason why it is never economical to pool the two jobs into a single job whose processing time distribution is the convolution of the individual processing time distributions is the following. Assume that the same due date has been quoted for both jobs, i.e. r; = 0. Then (28) becomes h [Pr {r2 < X2} + Pr {72 > X2 - X r,71 + 72 X2}] -p [Pr {r2 X2} +Pr{rT2 > X2 - X*, r+ r2 > X2}] = 0 (36) and X2 can be seen now as the cumulative planned lead time for both jobs. Comparing (36) with (32), one can see from the joint events terms that the impact of job 1 on 22

the starting time of job 2 is the same. However, while in (36) h2 may be so high that it becomes more economical to start the processing of job 2 together with having less than X1 remaining till the due date, it is never the case in (32) since no matter how high is h. the holding cost of job 2, the shortage cost guarantees that safety time must be increased when a second job is added. It is the shortage cost that forces us to have safety time in the Newsvendor problem, and it is the shortage cost that guarantees that safety time must be increased when a second job with the same cost structure is added at the same due date. As a result, X2 > Xl - r, Xi satisfies (28) indeed and hence computations of optimal planned lead times when the due dates have been set in advance for problems with more than two jobs are significantly simplified, knowing that X* > X' for j > i. 4.2 Optimal Due Dates Equations (21), (20) and (8) also have an appealing economic interpretation. They can be rewritten respectively as C' (d*) = -hPrT {3 > d*-, T32 < d} + pPr {73 > d2- X2,T32 > d]} (37) C' (d7) = -hPr {r3 > d-X2, T32 - < dt-X, T31 < dt} + pPr {3 > d2 - X2, 32 > d* - X, T31 > d;} (38) C'(d;) = -hPr {r2 d -X1, rT21 d} + pPr {r2 > d;- X1, r21 > dt} (39) The marginal costs associated with the first job to be processed are obvious as illustrated in (9) and (22) 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 (37). For a three jobs problem, the marginal increases in holding cost associated with job 2 23

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 (37) and (38) indicate. In other words, the tardiness argument is stronger than the earliness argument for job 2 and 1. Consider job 2 and equation (37). 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. Equation (37) and (38) 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 T + X2 for job 2 and 2T + X' for job 1. However if that cost exists and A > 2T + X, then T + X2 < d < A and T + X1 - X + d d < A as shown by the shaded area in figure 3a. In figure 3a, the shaded area represents the set of multiple optima (dt, d*) when the first order conditions of the unrealistic problem corresponding to the case of A -- oo are set to zero. This area of multiple optimal due date values represents the set of slacks s2 = d - (T + X) < A - (T + X) and s = d - (T + X - X + d*) < A - ( + X1 - X* + d*) that the manager will have with probability 1 after the completion of job 3 and after the completion of job 2 respectively under the optimal starting policy. Figures 3b, c and d show how the feasible region varies 24

with A. Note that we cannot have d~ > d + T+ X -X2 and d* < + X2 in figure 3b, i.e. when T-+X2 <.4 < 2-~+X*. If dl > d*+ X+X'-X*, then E' [J, (X2 + d - - - r2)] = 0 in (21) and hence d* = {x,x E [Tf + X2, A]}. As a result, we have that if A < 2T + X1. then Max{A, d)} < d* < 2T + X1 and d* < d* < T + X2. Otherwise, the darkened area in figure 3a represents the set of multiple optima (dT, d*) where there exists an optimal solution d~ < d* = A. Therefore there exists an optimal solution where d~ > A. For all due dates to be less than A, we must have that dt < A, hence 2T + Xi < A. For all due dates to be more than A we must have d~ > A, hence Xl > A. Xl < A < 27 + X1 implies merely that d <K A and dt > A and does not provide additional information about d*. T + X* < A < 2T + X* implies naturally that d* < A since we have shown that d < ~T + X*, but A < T + X* can result in d~ < A as well as d* > A as can be seen in figure 3c and d. 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 for the last job to be processed when c is high. Several additional observations can be made from equations (37) and (38). 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 increases 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 rt > 0, 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. 25

5 Managerial Insights In this section, we discuss the managerial insights provided by the two main practical results obtained in sections 2 and 3, namely a) the optimal planned lead times are nonincreasing 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 and b) adding a job to a preexisting set of jobs results in quoting earlier (or the same) due dates to the jobs in the former set. 5.1 Effect of Additional Job on Optimal Planned Lead Times 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. This agrees with the intuition that jobs are processed earlier as their number increase. For instance, the second job is processed earlier if it is not the last one in line. This increase in planned lead time represents the added protection required due to the presence of a third job down the line, and the uncertainty induced with it. The planned lead times of the first and the last job would be the same if we would know the starting time of the last job with certainty. Intuititvely the first job to be processed has the smallest planned lead time because the starting time of the last job to be processed is uncertain whereas the starting time of the first job to be processed is immediate. 5.2 Effect of Additional Job on Optimal Due Dates Adding a job to a preexisting set of jobs results in quoting earlier (or the same) due dates to the jobs in the former set. For instance, the due date of the second job to be processed was shown to decrease when a third job is added. This agrees with the intuition that due dates need to be quoted the earliest possible to avoid the due date cost. Hence if 26

a job is added at the last minute, the manager ought to revise the quoted due dates for the preexisting jobs and reduce them since more jobs now are sharing time, the single resource in this problem. 6 Extension to N-Jobs Extending the problem to N > 3 jobs, the problem becomes for 1 < i < N - 1: li-Yt 00 Ji (li, ri_,, rl) = Miny>o h [(li - yi) - t] fi (t) dt + p j [t - (i - yi)] fi (t) dt + E [Ji1l (i - yi + r-i1 - 7i, r7i2,..., ri)] (40) and for i = N: Min JN (dN, rN-1,..., r) = C (dN) + C (dN + rN-1) +... + C (dN+ rN-l +... + ri) + r^{d~ ~ ~ ~ ~~(N f00 ) { )-) h (dN -t) fN (t)dt+p (t-dN)fN(t)dt+ E [JN- (dN + rN-1 - TN, rN-2,.., r)] (41) s.t. dN,rN-1,...,rl > 0 where ri = d+l - di, i = 1,..., N- 1. Proposition 7 y (l,d_...,.dl) - y (i, r_,..., 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 di_,..., d, is expressed by Y (l Xi if li > X* y;(lir,) zri,.., 1- r (42) 0 otherwise where XZ, the optimal planned lead time of job i, solves dJi (4I, r_l,..., rl) /dXi = O (after subtituting li - yi by Xi). 27

It is true for i = 1 and 2. To prove this for 3 < i < N, we assume that J*1 (l_-I, r_2,.. r1 ) is convex in 1i_-, hence (42) is true for job i, and show that this implies J* (l., r_l,...., ri) is convex in l, hence (42) is true for job i + 1. In fact, substituting y* (,l.,... r1) in ~Ji (li, ri-1,..., rl), we get h fox (X? - t) f, (t) dt + p fx* (t - X*) fi (t) dt+ E [Ji1 (XZ + r+ i - rI rT-2, r1i)] 4. > Xt Ji (li, r._,..., rl)= - J (Xi + yi, ri_,..., r1) {y,=o,x=}=1 - (43) h ol' (I - t) fi (t) dt + p fo (t - t,) fi (t) dt+ E [J:- (i + r.1 - -i, ri-2,..., ri)] X It is clearly convex in li for li < X* since the first 2 terms are convex in i and we assumed that Ji*_ (li-l,ri-2,...,rl) is convex in li-1, hence convex in li. Furthermore dJi (I,ri_,...,rl) /dl4 = 0 at li = Xi* since we assumed that X* solves the equation dJi (-, ri_1,...r) /dXi = 0 (after subtituting 4I - yi by Xi), hence solves the equation dJi (Xi + y i, r i_,..., r) {yi=o,xi=li}/dli = 0. Proposition 8 X*, 1 < i < N - 1 solves the following equation (after subtituting li- yi by Xi): i I) i i-i i i-i dX= h h Pr E k < E rk + XI, k > E rk + Xi-X;, dX; j=l [k=j k=j k=j+l k=j E Tk E rk +Xi-Xj,..... k=j+2 k=j+l pE Pr ETrk > E rk + Xi, Tk > Erk + -X j=l k=j k=j k=j+l k=j 1 i E T > E rk+Xi-X j+l,..... = (44) k= j+2 k=j+1 It is true for i = 1 and 2. To prove this for 3 < i < N - 1, assume that it is true for i. Jr (l r+i,..., r) is given by (43) and..., rr) is given by (43)and... isgiven (40). Substituting 28

li by 1i+ - yi+i + r, - r+l in (40), letting /+1 - yi+i = Xi+1, differentiating (40) with respect to X;,1 setting it to zero, and after doing further manipulations we get d'Ji+l (/+j, ~,..., ) dJ+1 (i r.) = hPr {ri+l < Xi+ } - pPr {Ti+1 > Xi+l } + [ dXi+l ] but from (43), we have that dJ+ (Xi+l + ri - Ti+1, ri -,.. rl) i dXi+l dJ,(I,.rI-l'''.I) I.. =X.+ I _ + d41 Il X +r*s-ri+^- i otherwise (46) For T.+1 > Xi+1 + ri - X, it is given by the middle side of (44) evaluated at X, = Xi+1 + ri - Ti+l. Substituting this latter in (45) gives the following first order condition: i + l + l i 1 2, z Tk~Zrk+N+l-NP, Z Tk~ S rkI + +lN -+l.. + k= +j=.+i+-X kk=j k= i+ i i+1 2 rE Tk rk+ i+lX-XN, Tk> S rk+X+l -X,* + l (fu)du )k=j+l k=j k==j+2 k=j+l i i+l i 00 i 1 p Pr{r + Tk rXi}+ Pr Xi+rk> rk+X+l.-, k=^1j= l k=j=++ri- k=j k=j dJ^{l^ r ) ^ /Pr{T,}- pPr{T X}+ k=+l k= j k=+=j2 k=j+l ~i+1 i h Pr E k z Ek + Xi+l, E rk> ~ JJr + x,+, -x S Tk > )I3 + X3+l-X+l.. c =j+2 kc=j+l2 29

hEPr Tk >ZE rk +l, L Tk >E rk + XAI~1-.X. j='l k=j k=j k=j+l k=j i+l i' E Tk> + Xi +l -+.... - o k=j+2 k=j+l and finally to dJ+l (i+1i,ri,...,ri) r+1 1 = )h h Pr Tk rk + Xi+l, Tk > E rk + Xi+l -Xf j=l k=j k=j k=j+l k=j i+l 2+1 E Tk E 5k i+l -Xj+....k=j+2 k=j+l and we are done. Proposition 9 X* > X_1, i = 2,..., N -1 Proposition 10 r, i = 1,..,N - 1 satisfy the following set of first-order conditions: ( N N-1 n NC' (d + r(N-) +.. + ri) = -hPr < E rk + dN, E T > E k + X dN - Xi k =i k =i k=i+l k=i i+1 2 TE T E + N - i+l1-0 (47) k =i+2 k= i+l and we are done. Proposition 9 X* > Xi*, i 2...,N- 1 Proposition 10 r*, i = 1,.., N - 1 satisfy the following set of first-order conditions: N N- N-1 N+pdPr 1Tk E rk + dN, E Tk > E rk + dN - x k=i k=i k=i+l k=i N N-1 E Tk > E5 rk+dN-Xi+l,. = (48) k=i+2 k=i++l N N-i rl5 in (44), for i = 1,...,N (1. k=i+2 30 The proof is by differentiating (41) with respect to r, and noting that the expression

Proposition 11 d* is given by: C' (di) = -hPr {TN < dN} + pPr {rv > dN} (49) The proof is by differentiating (41) with respect to dN and noting that the expression NJv (dv, rN-1,..., r1) /6dN is nothing but the due date cost terms plus the terms containing XN in (44). Proposition 12 Let dN* be the quoted due date for job i in an N jobs problem. (N+I)* d*N di+), i- 1...,N. (50) 7 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 and optimal planned lead times can be obtained analytically by balancing the marginal effects of holding cost, shortage cost and cost of quoting an uncompetitive due date for each job, due to quoting a due date one unit of time longer. We have also shown that once the optimal due dates have been quoted and the optimal planned lead times have been determined, the optimal starting time for each job is described by a simple wait-until policy. Finally we have shown that the effect of an additional job is to increase the planned lead times and decrease the quoted due dates of the preexisting jobs, except for the first job to be proceesed. The first job to be processed, which is to be started immediately, is not affected by the addition of job to the set, and hence its quoted due date remains the same. 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 31

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. 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. De, 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 32

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. Emmons, 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. 33

ir"- - - - 12 - - - - 4.' I I t- - - -- - I'- - - -- - -I { { I I Figure 2 -- 2 - - -1 - - - X2- - II -I 3 -I- Y2-I- T2 -1+1 Y1 -I-I I I 4I- -d3- _1 -' - Y- -- -- - - - - - - FIl I ^ _ _ _ _ _ _- - d2 --- - _ _ I Figure 2!~~~~~~Fgr I1

di A.1 A ___ —-------- - - - - - X/ I 1I 2/ * 7 / I I /, I I /0/ I -X2/, I / I / / d/ /, I I // I I I I I I d3dF X+X2 A3

d, A..... / /y / > I.~~/~ I I I / / I I / /I I / I I dX3 +X IA Figure 3b Figure 3b

d, 2Z+X1 / / /T / 2 -- _ / I,- X I/ +AX- -I I I / /)I I /I I 0d A Figure 3c

d, T + x;- - / /I / / / / / T+X O - - I I Ii; - ~~~~~~~~I A* / I / I I / I i I // I I d0 A + X2 Figure 3d

UNIVERSITY OF MICHIGAN 901111 11111111111047353340 3 9015 04735 3340