Division of Research' School of Business Administration January 1990 SCIHEULING JOBS AGAINST A COM( N DUE DATE WITH PROPCRTIONATE PENALTIES Working Paper #631 Ram Rachamadugu The University of Michigan

ABSTRACT We analyze the problem of scheduling jobs against a common due date. Both early and tardy jobs are penalized. Earliness and tardiness penalties are different and proportionate to the processing times of the jobs. Firstly, we provide a dominance condition for optimality when jobs have different due dates. This result is then used to find an optimal sequence for the common due date problem. We show that the Longest Processing Time (LPT) rule yields an optimal sequence. Also, optimal sequence is independent of the due date. Further, optimal start time of the sequence can easily be determined (newsvendor approach). Thus, this is one of the very few instances when optimal solution can be found in polynomial time even when the common due date is restrictive. Extensions to the problem of setting a common due date are also discussed. We illustrate the procedures with numerical examples. We also provide future research directions.

SCHEDULING JOBS AGAINST A COMMON DUE DATE WITH PROPORTIONATE PENALTIES Introduction Increasing emphasis on J-I-T has led the researchers to focus their attention on scheduling jobs as close to due dates as possible. Under this environment, jobs are not necessarily started early even if the machine is available (Ashton and Cook 1989). Thus inserted idle time may exist between the jobs and also at the start of the sequence. Jobs are penalized for both earliness and tardiness. Such a measure of performance is not regular in the sense that delaying the start of a job may yield better solutions. For definition of regular measure of performance, see Baker (1984). For a good survey of earlier studies on due date related problems, see the review paper by Baker and Scudder (1989a). Among these problems, a special class of problems has attracted considerable attention. These are known as Common Due Date (CDD) problems. Jobs have a common due date in this environment. For example, shipping schedules may warrant having a common due date (Chaircraft Corporation —HBS case study). Baker and Scudder (1989a) provide a helpful taxonomy of the CDD problems. In this paper, we study CDD problems in which earliness and tardiness penalties are proportionate to the processing times of the jobs. However, the constants of proportionality can be different. We generally expect the tardiness to be penalized more heavily than earliness penalty. However, our analysis and results remain valid even if this condition is not satisfied. In the next section, we provide a brief review of prior research on related problems. Subsequently, we provide a formal definition of the problem and derive characteristics of dominant solutions for a general version of the problem when the jobs have different due dates. We then make use of this property to characterize optimal solutions for the common due date problem. Next, we exploit the convexity property of the criterion to determine optimal start times of the jobs in the sequence. We show that the LPT rule yields an optimal sequence. It is noteworthy that the sequence is independent of the due date. We illustrate the concepts using a numerical example. Next, we provide

-2 - extensions to the situation where decision maker has control over the due date setting. Lastly, future research directions are provided. Prior Research Kanet (1981) initiated the early study on scheduling jobs with a common due date. He assumed that the due date was "unrestrictively" late and all jobs had the same earliness and tardiness penalty. Subsequently, other researchers analyzed various versions of this problem such as restrictive due dates, multiple processors, different or identical penalties for earliness and tardiness and restrictions on start times of optimal sequence (Sundararaghavan and Ahmed (1984), Bagchi, Chang and Sullivan (1987), Bagchi, Sullivan and Chang (1986), Hall (1986), Emmons (1987), Raghavachari (1986), Szwarc (1989), Yano and Kim (1989), Hall and Posner (1989), and Hall, Kubiak and Sethi (1990), among others). Though the measure of performance is not regular, optimal solutions to these problems have the property that there is no inserted idle time between the jobs in an optimal sequence. Idle time, if any, appears at the start of the sequence in an optimal solution. For a comprehensive review of these problems, the reader is directed to the survey paper by Baker and Scudder (1989a). Another parallel stream of work, relaxing the commonality of due dates, was studied by Fry (1984) and Fry et al. (1987). They used arbitrary penalties and job dependent due dates. Under these circumstances, jobs may have idle times inserted between them and/or at the start of the sequence. Abdul-Razaq and Potts (1988) and Ow and Morton (1989) studied the special case where no inserted idle time was permitted. Garey, Tarjan and Wilfong (1988) studied the case in which each job has "symmetric" penalty —i.e., earliness penalty equals tardiness penalty. They also showed that the problem is NP-complete. Yano and Kim (1989) studied the case where earliness and tardiness penalties are proportionate to the processing times of the jobs. Arkin and Roundy (1988) analyzed proportionate weighted tardiness case. In their analysis, earliness was not

-3 - penalized. However, due dates could be different. Reader is directed to the survey article by Baker and Scudder (1989a) for a review of these prior studies. Problem Statement In the situation studied here, jobs have a common due date. Since the value added to a job is generally proportionate to the processing time of the job, we set earliness and tardiness penalties as proportionate to the processing times of the jobs. Thus the penalties for the jobs could be different since jobs may have different processing times. The constants of proportionality for earliness and tardiness need not be equal. Thus, in our case, each job can have a distinct earliness and tardiness penalty. However, jobs have a common due date. Further, we impose no restrictions on the common due date. Next, we define the notation used in the paper. Ji: Job index, i = 1, 2,..., n (without loss of generality, assume that the jobs are index as per longest processing time rule, p1 > p2 > p3 ~ p4 ".. n) di: Due date for Ji (when jobs have identical due date, subscript will be omitted) Pi: Processing time for J P: makespan n = _ Pi i= 1 Wi: Tardiness penalty for Ji = api, a hi Earliness penalty for Ji = PpiI>o [k] Index of the job occupying kth position in a sequence Ci: Completion time of Ji x+ max(0,x) T.: Tardiness of J. = (Ci- di)+

-4-.: Earliness of J. = (di - Ci)+ Si: Slack for Ji di-Pi t: Start time of a job on the machine.lj: min(pj, (d -t- Pj) ) (reverse the notation for fi) t wi ( ij J f Wi 11 + hi t ij' p - _11 (C + (reverse the notation for O i) Pi' 1- P w i (This is priority value for Ji in comparison with J. if the start time for the next 1 J job on the machine is t) r.: Start time of job J. in a schedule gi(t): Penalty incurred by Ji if its start time is t i ( - 1 G.(t): t + PK if k > fi~l \ k=1 gl(t) ifk=1. Our problem can be stated as follows: n (PR) min k=l ([k] T[k] + h[k] E[k]) s.t. C 2 C-1l] + P] = 2,..., n C[1] P[l] C[] + E[] - T[] = d = 1,..., n. Consider optimal solutions to (PR). For any positive values of W[k] and h[k], it can easily be shown that the following remark is valid. Remark 1: In an optimal solution to the problem (PR), there is no inserted idle time between jobs. Idle time, if any, appears at the start of the sequence.

-5 - In the next section, we characterize a set of dominant solutions for the general version of PR where each job may have a different due date and no idle time is permitted to be inserted between two consecutive jobs. Call this problem as GPR. Clearly, PR a GPR. We then derive optimal solutions for PR using the characterization developed for GPR. Dominant Solutions Let J. and J. be adjacent jobs in an optimal solution to GPR. 1 ~J Proposition 1: In an optimal solution to GPR, job Ji precedes J. if the following conditions hold good w. w. h. h. (i) 2 i (ii) pl p, (iii)di dj and (iv) s Sj + (wjpj - w jpi)/(h + i) Pi Pi Pj P j Proof: Ow and Morton (1989) developed an adjacency condition for optimality when no inserted idle times are permitted between two consecutive jobs. The condition identified by them is wiPj - Qij (Wih)w - ( + hj) Above condition can be rewritten as Wi Q. h. 0.0 h1+J t Pi - Pj ( Pj Pi PjI t 8jt i.e., e 2e J ji t t O i and Oji for various values of t are shown in Figure 1. t t Ji will precede Jj in an optimal solution if.ij > Oi for all values of t. From Figure 1, it is clear that this will be the case if the priority value for Ji at d. - p. exceeds wPij —

-6 - hi + Wi ij Pi di- pi +Pj wi pi wi h.~ wj Priority t j +w i) Pj Values | 0j- i-PJ __i _j, --- di-Pi-P gue 1 ie, d.- Jh(hi+wi)/ j-pji-piP J This completes the proo/. penalty environment. hi I slopFigur e 1J i.e., d- Pi-Pj i + wi (hi + wi)/PiPjJ pj / wi )+ [ w./pj ]< wi 'wiPi si: S+ hi + w J This completes the proof. Next, we apply Proposition 1 to PR by setting di = d for all i in proportionate penalty environment. Lemma 2: LPT rule yields an optimal sequence for problem PR.

-7 - Proof: Set w[k] = PP[k]'h[k] = [fP[k] and di = d for all k in Proposition 1. Note that any pair of jobs satisfies (i), (ii) and (iii). If pi > pj, then (iv) is automatically satisfied. Further note that the relationship is transitive —i.e., 0ij > 6jk => ik > 9ki. Hence LPT rule yields an optimal sequence. This completes the proof. Note that in the above proof, we have made no reference to or put restrictions on the common due date. Thus, LPT yields optimal sequence for any common due date problem when earliness and tardiness penalties are set proportionate to the processing times of the jobs. A graphical explanation for the optimality of LPT sequence is provided in Figure 2. Priority values e.i and 0ji are shown in Figure 2 for J. and Jj. 1j Ji J a+B slope = Pj a+B Pi a d -Pi d-pj d -Pi -p Figure 2 From Figure 2, it is clear that at t < d - Pi - pj, either job can precede the other. Similarly, at t > d - pj, either job can precede the other. In the range d - pi - pj < t < d - pj, Ji (longer job) precedes the Jj (shorter job). This analysis implies that there is an optimal

-8 - sequence in which Ji precedes Jj, irrespective of the start times. Thus LPT sequence is optimal for any proportionate penalty CDD problem. This result generalizes and extends similar result derived by Hall and Posner (1989). It may be noted that there are multiple optimal sequences for this problem. It can easily be verified that in a given sequence, all jobs which are early or on time can be sequenced in any order without violating optimality. Similarly, all jobs with start times greater than or equal to the due date in an optimal sequence can be executed in any order. Let n2 denote the cardinality of the latter set of jobs. We can construct at least n2! (n - 1 - n2)! alternate optimal sequences. Though LPT rule yields an optimal sequence, it is not V-shaped. (Weakly) Vshaped property implies that all jobs which are strictly early or on time are in LPT sequence and all jobs starting after the due date are in SPT sequence. It can easily be seen by the reader that we can indeed construct an alternate optimal sequence which is weakly Vshaped. Details are omitted for the sake of brevity. However, for our subsequent analysis, it is assumed that the LPT sequence is used as the optimal sequence. Next, we discuss the issue of optimal start times of the jobs in the optimal sequence under consideration. Invoking Remark 1 and Lemma 2, it is clear that once we define the start time of the longest job in the sequence, optimal solution has been obtained. In the next section, we develop a procedure for determining the optimal start time. Optimal Start Time Let gi(t) be the penalty incurred by Ji if its start time is t. Clearly, for any given due date gi(t) is a convex function of t. Since we know that (i) there is no inserted time between the jobs, (ii) LPT is an optimal sequence, and (iii) jobs have been indexed in LPT sequence, total penalty for starting the optimal sequence at time t is given by k-1 n-1 Gn(t) = gl(t) + g2(t + p) + g3(t + p + 2)."' + gkt +. gt + = zgt +;pP 1\1 k=l

-9 - Note that each of the above terms is convex. Since the sum of convex functions is convex, Gn(t) is also convex. This simplifies our analysis. Since we are minimizing a convex function, ensuring local optimality guarantees global optimality. Let t* be the earliest optimal start time for the first job in the sequence. Then, local optimality requires that Gn(t* + At*) - Gn(t) > 0 Left hand side (LHS) of the above expression is the increase in cost due to marginal right shift of the sequence by At* time units. Let K be the first tardy or on time job in an optimal schedule (either Figure 3 or Figure 4) JK JK+1 JK+2 JK J] d d Figure 3 Figure 4 In either case, increase in cost due to the right shift of the sequence by one time unit is equal to n K-1 n K-1 q=K q q=l q=K q=- q n n QK q P - q-KKP q n - 3P + (a + p) qKpq Hence

-10 - At*{- P + (a +) pX p, _ ' > P q=K q q= K y +J Let K* be the shortest job satisfying the above condition. Optimal start time t* is given by K* d- p. j=1 J If the above quantity is negative, clearly optimal start time is 0. (This can be established rigorously by defining gi(t) to be arbitrarily large for all i for t < 0. Details are omitted here for the sake of brevity.) Hence t*=max(0, d -,Pi Next, we illustrate our results using a numerical example. Numerical Illustration Consider a four job problem p1 = 9, P2 = 7, P3 =4, and4 = 2. Leta = 6, = 1 and d = 21. Using LPT, optimal sequence is given by J1 - J2 - J3 - J4. Choose K* such that n 1 X p > 1 + 6 (9+7+4+2) q=K q 1+6 > 22/7 K*= 3. Hence optimal start time is given by max(0, 21 - (9 + 7 + 4)) = 1. Details are shown in Figure 5.

-11 - Consider the same problem with d = 11. Optimal sequence is invariant with respect to the due date. Hence optimal sequence still remains the same —J1 - J2 J3 - J4. Optimal start time is given by max(0, 11 - 16)= 0. I J1 I J2 J3 J4 Penalty = 150 0 1 10 17 21 23 I I I d Figure 5 Optimal Due Date Setting Next, we extend our analysis to the situation where the decision maker has control over due date setting. Obviously, setting a large due date puts the manufacturer at a competitive disadvantage. Hence a reasonable composite measure for due date setting and measuring penalties for deviating from that due date can be stated as follows — n (PR') min Z(d) = d + kzl(w [k] T[k]+h[k] E[k]) k — k =] h k (5) s.t. c;? p s.t. C C[gi-1] + P[i] C[1] P[l] C[] + E] - T[] = d = 2,..., n P = 1,..., n. It is clear that in an optimal solution to (5), there will be no inserted idle time at the start of the sequence. This is true for any arbitrary positive values of w., h. and y. Proof is by contradiction and omitted here for the sake of brevity. For arbitrary values wi, hi and y,

-12 - there are no known polynomial procedures for solving this problem. In such a case, optimal sequence itself will be dependent on the due date. However, in our case (proportionate penalties), LPT yields an optimal sequence and it is independent of the due date. Also, it can easily be verified that in our case Z(d) is a convex function of d. Hence local optimality of LPT sequence with respect to d will ensure global optimality of Z(d). Further, since penalties are piecewise linear with slopes changing at completion times, optimal due date will be either at zero or coincide with the completion time of a job (for other approaches to due date setting for a given sequence, see the papers by Quaddus (1987) and Baker and Scudder (1989b)). Let d* be the earliest optimal due date and k** be the job which completes at d*. For d* to be optimal, Z(d* + Ad*) - Z(d*) > 0 (pq) + ( ) \ q=k**+l k q=l X- J +P + p I+ y0 K q=l q - 1 q (k** -aP+(a+ ) PJ+yO k** Set d* such that Z p > a q=l q a + (fa+ p -( +pJ If the above quantity is negative, d* =0. As an illustration, consider the numerical example cited before. Suppose that y = 64. In this case, we choose longest job k** such that

-13 - K** a Y Ipq> oP-_ q=l q + a+ + > 6 22 -64 7 7 > 9.7 Set due date as 16. Conclusions In this paper, we have analyzed the problem of scheduling jobs against a common due date in proportionate penalty environment. We have shown that LPT yields an optimal sequence for this problem. Further, this is true irrespective of whether the due date is restrictive or unrestrictive. This is the one of the very few known instances where polynomial time solution can be found for the CDD problems when the due date is restrictive. Further we extended our analysis to the situation where the decision-maker has control over due date setting. We are currently exploring extensions of our procedures to multiple processors situation. References Abdul-Razaq, T. and C. Potts (1988), "Dynamic Programming State-space Relaxation for Single-machine Scheduling," Journal of the Operational Research Society, Vol. 39, pp. 141-152. Arkin, E. M. and R. O. Roundy (1988), "A Pseudo-polynomial Time Algorithm for Weighted-Tardiness Scheduling with Proportional Weights," Technical Report #812, School of Operations Research and Industrial Engineering, College of Engineering, Comell University, Ithaca, New York 14853-7501. Bagchi, U., R. Sullivan and Y. Chang (1986), "Minimizing Mean Absolute Deviation of Completion Times About a Common Due Date," Naval Research Logistics Quarterly, Vol. 33, pp. 227-240. Bagchi, U., Y. Chang and R. Sullivan (1987), "Minimizing Absolute and Squared Deviations of Completion Times with Different Earliness and Tardiness Penalties and a Common Due Date," Naval Research Logistics, Vol. 34, pp. 739-751. Baker, K. R. (1984), Introduction to Sequencing and Scheduling, John Wiley and Sons, Inc., New York.

-14 - Baker, K. R. and G. D. Scudder (1989a), "Sequencing with Earliness and Tardiness Penalties: A Review," Working Paper No. 226, The Amos Tuck School of Business Administration, Dartmouth College, Hanover, NH 03755 (to appear in Operations Research). Baker, K. R. and G. D. Scudder (1989b), "On the Assignment of Optimal Due Dates," Journal of the Operational Research Society, Vol. 40, No. 1, pp. 93-95. Emmons, H. (1987), "Scheduling to a Common Due Date on Parallel Common Processors," Naval Research Logistics, Vol. 34, pp. 803-810. Fry, T. D. (1984), "Scheduling to Minimize Weighted Absolute Deviations," Ph.D. Dissertation, University of Georgia, Athens, Georgia. Fry, T. D., R. Armstrong and J. Blackstone (1987), "Minimizing Weighted Absolute Deviation in Single Machine Scheduling," IIE Transactions, Vol. 19, pp. 445-450. Garey, M., R. Tarjan and G. Wilfong (1988), "One-processor Scheduling with Symmetric Earliness and Tardiness Penalties," Mathematics of Operations Research, Vol. 13, pp. 330-348. Hall, N. G. (1986), "Single and Multiple Processor Models for Minimizing Completion Time Variance," Naval Research Logistics Quarterly, Vol. 33, pp. 49-54. Hall, N. G., and M. E. Posner (1989), "Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date," Working Paper, College of Business, Ohio State University, Columbus, Ohio (to appear in Operations Research). Hall, N. G., W. Kubiak and S. P. Sethi (1990), "Earliness-Tardiness Scheduling Problems, II: Deviation of Completion Time About a Restrictive Common Due Date," Working Paper, College of Business, Ohio State University, Columbus, Ohio (to appear in Operations Research). Kanet, J. (1981), "Minimizing the Average Deviation of Job Completion Times About a Common Due Date," Naval Research Logistics Quarterly, Vol. 28, pp. 643-651. Ow. P. and T. Morton (1989), "The Single Machine Early/ardy Problem," Management Science, Vol. 35, pp. 177-191. Quaddus, M. (1987), "A Generalized Model of Optimal Due Date Assignment by Linear Programming," Journal of the Operational Research Society, Vol. 38, No. 4, pp. 353-359. Raghavachari, M. (1986), "A V-shape Property of Optimal Schedule of Jobs About a Common Due Date," European Journal of Operational Research, Vol. 23, pp. 401 -402. Sundararaghavan, P. and M. Ahmed (1984), "Minimizing the Sum of Absolute Lateness in Single-machine and Multimachine Scheduling," Naval Research Logistics Quarterly, Vol. 31, pp. 325-333.

-15 -Szwarc, W. (1989), "Single Machine Scheduling to Minimize Absolute Deviation of Completion Times from a Common Due Date," Naval Research Logistics, Vol. 26, No. 5, Sept.-Oct. 1989, pp. 663-673. Yano, C. and Y. Kim (1989), "Algorithms for a Class of Single Machine Weighted Tardiness and Earliness Problems," Working Paper, College of Engineering, The University of Michigan, Ann Arbor, Michigan.