Division of Research School of Business Administration December 1989 DCMINANT SOUIPTIONS FR THIE EARLY/TARDY PROBLEM Working Paper #625 Ram Rachamadugu The University of Michigan

I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ABSTRACT In this note, we derive an optimality condition and use it to find dominant solutions for the early/tardy problem when inserted idle times are permitted. These dominance conditions are less restrictive than those established by earlier researchers. Further, we develop a stopping rule, and identify optimal sequences for various cases. We also show that if due dates are set using equal slack rule or total work content rule, shortest processing time rule yields optimal sequence in proportionate penalty environment. Extension to a completion time related cost is also discussed.

I

DOMINANT SOLUTIONS FOR THE EARLY/TARDY PROBLEM Recent efforts to reform job shops (Ashton and Cook [1989]) and the increasing acceptance of Just-in-Time manufacturing advocate starting jobs only when necessary. Under these circumstances, both early and tardy jobs are penalized (early/tardy problem). Performance measures which take both these costs into account can be nonregular in the sense that delaying the start of a job may in fact yield less costly solutions. Recently, Fry [1984] and Fry et al. [1987] addressed a general version of this problem. Their formulation permits job dependent earliness and tardiness penalties. Also, they permit inserted idle time between jobs. Garey, Johnson, and Wilfong [1988] have shown this problem to be NP-complete. Garey et al. [1988], Ow and Morton [1989], and Yano and Kim [1989] addressed various special cases of this problem. Also, significant amount of research exists for the special situation where all jobs have the same due date. The reader is directed to a recent paper by Baker and Scudder [1989] for a comprehensive survey and taxonomy of these problems. In this note, we investigate properties of optimal solutions for the early/tardy problem when idle times are permitted to be inserted between jobs and also at the start of the sequence. These properties are used to establish dominant solutions for various special cases. These dominant solutions are less restrictive than the results derived by earlier researchers. We establish the usefulness of our results by deriving a stopping rule and showing optimality of some dispatching rules for various cases. We also show how a completion time related criterion can be reduced to the early/tardy problem. Thus, such problems can be solved using currently available analytical tools for the early/tardy problem.

-2 - Notation J. job index, i = 1,2.....n h. earliness cost rate for job i w: tardiness cost rate for job i Pi: processing time for job i di due date for job i (if all jobs have the same due date, the subscript will be omitted) Ci Completion time of job i si di - Pi MDDt = Modified Due Date for job i at time t max (t + Pi, di) MSj = + Pi + Pj MStji [k] index of the job occupying kth position in the sequence under consideration WSPT Sequence resulting from the use of the weighted shortest processing time rule, i.e., w[l]/P[l] > [2]/P[2] WLPT Sequence resulting from the use of the weighted longest processing time rule, i.e., h[l]/P[1] < h[2]/P[2] EDD Sequence resulting from the use of earliest due date rule - i.e., d[]< d[2]' ESK Equal slack due date assignment, di = K + Pi, where K is a constant TWK Due date assignment based on work content of the job, i.e., di = KPi, where K is a constant. F Mean flowtime

-3 - Qi.: min (pj, max (0, di - t - i)). Ji and Jj are adjacent jobs in the sequence under consideration with Ji immediately preceding J.. t is the start time of job i. t. Priority value for J. in comparison with J. when t is the start time for 1J ~ J the next job on the machine. Pit Pj i X+ = max (0,X) Conditions for Optimalitv Throughout this communication, sequence refers to a specific permutation of jobs. Schedule refers not only to a sequence, but also specified start times of the jobs. Our objective is to find a schedule such that Zh[i] Max (0, d[] - C[i]) + W[i] Max (0, C[i] - d[]) is minimized. Henceforth, we call this as early/tardy problem. Note that we permit insertion of idle times in the sequence. Remark 1: An optimal schedule consists of 'blocks' of jobs separated by inserted idle times. If the optimal schedule consists of more than one block, then the last job in a block is tardy (or on time) and the first job in a block is early (or on time) (Figure 1). A new 'block' is formed whenever a job completes exactly on time and/or there is idle time between two consecutive jobs. TARDY EARLY JBLOCK BLOCKME BLOCK BLOCK Figure 1

-4 - Proof: Proof is by contradiction. U Proposition 1: For every optimal sequence the following condition holds: i.e., eb{ Proof: First consider the case where J. is the last job in a block and J. is the first job ( 6 jl either tardy or on time. has to be early or on time. In this case, the left 1- I! 1 + - > __1 1- 1 + (1 Pi 6P i. P j Pi W. JJ is reduced to a negative quantity. Hence it is clearly satisfied. Now consider any two adjacent jobs within a 'block.' Ow and Morton [1989] considexred a) special cas e problem here in which jobs are processed o timmediate a e ly or one i after the er with no idle time inserted at e start of the sequence or in between the jobs. Above proposition is equivalent to their Theorem 1 (p. 179) for any two adjacent jobs within a 'block' of jobs. Hence (1) is also valid for any two adjacent jobs within a block. This completes athe proof. In the next three sections, we derive dominance conditions, stopping rule, and optimal sequences for various special cases. Unsymmetric Penalties In this case, all jobs have equal earliness penalties (hi = h) and the same tardiness penalties (wi = w). Garey, Johnson and Wilfong [1988] studied the case where jobs have

-5 - symmetric penalties, i.e., w = h. We derive dominance condition for optimal sequences under unsymmetric penalties. We use the result to establish optimal sequence when the jobs have identical processing times. Reconsider Proposition 1. With a little algebraic manipulation, it can be rewritten for the unsymmetric penalties case as follows - min (t + i + Pj max (t + d) (p- ) h + min (t + pi + pj, max (t + p, d)) min (MStij, MDDt) < (Pi pj) h )+min(MSti, MD) (2) Note the similarity of (2) to the Modified Due Date rule. Prior computational experiments (Baker and Bertrand [1982]) showed that MDD is a very effective heuristic rule for the average tardiness problem (h = 0, wi = w). Further, Rachamadugu (1987) showed that MDD rule is a dominance condition for the average tardiness problem - i.e., there exists an optimal sequence for the average tardiness problem which satisfies MDD rule. (2) is generalization of the MDD rule. It can easily be verified that any sequence satisfying MDD rule also satisfies (2) (set h = 0 in (2)). Next, we establish a sufficiency condition under which an optimal sequence can be obtained for the unsymmetric penalties problem. Remark 2: If jobs have identical processing times, then EDD rule yields optimal sequence. Proof: Follows immediately from Proposition 1. Figure 2 shows the priority values for various jobs. 0. is independent of j and t. t. >. for all values ofj and t ij ii sd if d. <d.. I j

-6 - Priority Values di - 2p / / / / i / di-p / dj-p/ / "I~~~~~~ ~~~t h P Figure 2 This completes the proof. U Note that the above result finds only an optimal sequence. Optimal start times can be found by using any of the polynomial procedures on the above sequence developed by earlier researchers. Note that similar result was derived by Garey, Johnson and Wilfong (1988) for the symmetric penalties situation (w = h). Our analysis extends it to unsymmetric case as well. Job Dependent Penalties In this case, jobs have arbitrary earliness and tardiness penalties. Firstly, we derive a stopping rule for determining first job in an optimal sequence. Remark 3: If the job with the highest wi/Pi ratio is tardy in the first position, then it is scheduled first in an optimal sequence. Proof: Proof is by contradiction. Direct application of Proposition 1 yields the result. U Above result is useful in two ways: firstly, it curtails enumeration for the first position in optimum seeking procedures. Secondly, in rolling horizon environments,

-7 - computations can be terminated after determining the job to be scheduled next on the machine. Next, we derive a dominance condition for optimality in the case of arbitrary early and tardy penalties. w. w. Lemma 1: In an optimal sequence job Ji precedes J.if (1) -1 -, (2) J Pi Pi (3) h. + w. < h. + w., and (4) s. s. + (wip. - w.p.)/(h. + w.). 1 1 j J' 1 JJi 1 h. h. - < -1 Pi Pj' Proof: U Priority 4 Values sing Proposition 1, priorities for J. and J. are sketched below in Figure 3. 1 J hi + Wi slope = PiPj dipi-P h ) / di -PiPj hi — wi 0' t li Pi t 0!* ji wj Pj I hi Pi hj Pj:I/ I I/ I:/ / slope=. _ _ _ _ _ _ _J-i h.+w. i i PiPj Figure 3 It is clear from the above figure that if priority for Ji at d. - pj exceeds w./p., then J. will precede J. for all values of t. di-Pi + wi (hi + Pi)/PiPj 1 Jh + w) iL(hi+ Pi)PiPjJJ- -Pj

-8 - wiPj - W;Pi) di-pi < wp - wh. +p. si-<, sj ++ h hi-+ This completes the proof. U The reader may note that the above is less restrictive than a set of dominance conditions derived by Yano and Kim [1989]. Next, we investigate optimality of WLPT sequence. Ow and Morton (1989) showed that, if the WLPT sequence yields no tardy job, then the sequence is optimal for the early/tardy criterion with no inserted times. However, this is not necessarily true when inserted idle times are permitted between the jobs and/or at the start of the sequence. Consider the example shown in Table 1. WLPT sequence (J1 - J2) yields a penalty of 6. However J2 - J1 sequence, with the jobs started at times 3 and 6 respectively, yields optimal solution with a value zero (Figures 4 and 5). Table 1 Job# Pi di hi w 1 3 9 1 10 2 2 5 4 10

-9 - Ih FII I 3 5 9 WLPT sequence J1 - J2 Figure 4 3 56 Sequence J2 - J1 with inserted idle times Figure 5 9 Proportionate Penalties Next, we consider the case where earliness and tardiness penalties are proportionate to the processing times of the jobs. In practice, it is reasonable to expect penalties to be correlated to the processing time of the job. Yano and Kim [1989] studied the situation where earliness and tardiness penalties are proportionate to the processing times, i.e., hi = api and wi = PPi. Next, we derive a dominance condition for a pair of jobs where one of them precedes the other in an optimal sequence. Remark 4: If Ji and J. are adjacent jobs in an optimal sequence, then Ji precedes J. if J J S < sj, <sj Pi and si/pj Sj/Pi. Proposition 1 reduces to the following condition - min (pj, (di-t-Pi)) min (Pi (dj-t-pj) ) n- ~ ~ ~ v ij Fi Clearly, as shown in Figure 6 (RHS and LHS are right hand side and left hand sides of the expression (3)), the condition is satisfied if si < sj, sj < Pi and s./p. < sj/pi. This completes the proof. i i i i ij

-10 - (dj- Pj)/Pi LHS (di - Pi)/Pj / RHS di-Pi dj-pj t Figure 6 Above result supplements a set of dominant conditions derived by Yano and Kim [1989] for the proportionate penalty case. Next, we investigate the impact of due date setting procedures. Two commonly suggested due date setting procedures are equal slack rule (ESK) and total work content rule (TWK) (Baker and Scudder [1989]). ESK provides same amount of slack for each job, irrespective of the processing time. TWK provides slack proportionate to the processing time (i.e., total work content) of the job. If any of these two rules are used for due date setting, then SPT yields optimal sequence for the proportionate penalties case. Remark 5: If due dates are set using equal slack rule or total work content rule, then SPT yields optimal sequence for the proportionate penalties case. Proof: Recall that conditions (1) and (2) from Lemma 1 are satisfied by any feasible sequence for the proportionate penalties case. Condition (4) from Lemma 1 is satisfied if the due dates are set using ESK or TWK rules and SPT is used for sequencing. Condition (3) is satisfied by the SPT sequence. Hence the proof. U

-11 - Note that, here again, we determine an optimal sequence. Optimal start (or completion times) of the jobs can be easily found by inserting idle times optimally in the sequence generated by using any one of the algorithms developed by earlier researchers (Fry et al. [1987], Yano and Kim [1989]). We would like to place in proper perspective the significance of Remark 5 from practitioner's point of view. We normally expect penalties to be proportionate to the processing time. Also, ESK and TWK are among the pragmatic approaches to quoting due dates. In such an environment, SPT yields optimal sequence. Use of SPT is usually recommended for reducing F and also to reduce inventories. Our analysis here shows that even in the environments driven by J-I-T considerations, SPT can be a preferred choice. Extension to Complex Criteria Consider the following objective function which takes into account earliness, tardiness and flow time costs (Baker and Scudder [1989]). min Z = wi (Ci - d) + hi (di Ci) + fC (4) Above function takes into account not only earliness and tardiness costs, but also flowtime related costs such as WIP. Clearly, above function is also a non-regular measure of performance. However, as shown below, it can easily be transformed to early/tardy problem. Ci { (Ci - di)+ - (di- Ci)+ } + di (5) Substituting (5) in (4), n + + 2 (w. + f) (Ci.- di) + (hi- fi) (di- Ci) + fd. (6) i= ~ 1 1 1 1 1 1 1 11 i=l1

-12 - Since fidi is a constant, it can be deleted from the optimization problem. Note that h. is generally no less than f. since the former relates to finished goods inventories while f. relates to WIP inventory costs. Hence h. - f. is likely to be non-negative in practice. Thus the extension can easily be solved using methods developed for solving the early/tardy problem. References Ashton, J. E., and F. X. Cook, Jr. (1989), "Time to Reform Job Shop Manufacturing," Harvard Business Review, March-April 1989, p. 106-111. Baker, K. R., and J. Bertrand (1982), "A Dynamic Priority Rule for Scheduling Against Due Dates," Journal of Operations Management, Vol. 3, p. 37-42. Baker, K. R. and G. D. Scudder (1989), "Sequencing with Earliness and Tardiness Penalties: A Review," Working Paper No. 226, The Amos Tuck School of Business Administration, Dartmouth College, Hanover, NH 03755. Fry, T. D., (1984), "Scheduling to Minimize Weighted Absolute Deviation," Ph.D. Dissertation, University of Georgia, Athens, Georgia. Fry, T., R. Armstrong, and J. Blackstone (1987), "Minimizing Weighted Absolute Deviation in Single Machine Scheduling," IE Transactions, Vol. 19, p. 445-450. Garey, M. R., R. E. Tarjan, and G. T. Wilfong (1988), "One Processor Scheduling with Symmetric Earliness and Tardiness Penalties," Mathematics of Operations Research, Vol. 13, No. 2, p. 330-348. Ow, P. S. and T. E. Morton (1989), "The Single Machine Early/Tardy Problem," Management Science, Vol. 35, No. 2, p. 177-191. Rachamadugu, R. (1987), "A Note on Weighted Tardiness Problem," Operations Research, Vol. 35, No. 3, p. 450452. Yano, C. A. and Y. D. 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 (to appear in the European Journal of Operations Research).