Division of Research Graduate School of Business Administration The University of Michigan April 1985 SOME PROPERTIES OF WEIGHTED TARDINESS PROBLEMS Working Paper No. 426 Ram Mohan V. Rachamadugu FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the expressed permission of the Division of Research., ^

I I i i I i I I i i I I I I

Some Properties of Weighted Tardiness Problems Ram Mohan V. Rachamadugu The University of Michigan, Ann Arbor, Michigan Abstract We consider scheduling of n jobs available simultaneously to be scheduled on a single machine. The criterion is to minimize total weighted tardiness. We identify a necessary condition for adjacent jobs in optimal sequences. Further it is shown that the well known Modified Due Date Rule is a special case of the necessary condition identified by us. Lastly, we identify circumstances under which first job in an optimal sequence can be determined without fully solving the problem.

I

-2 - Consider the following single machine weighted tardiness problem —we have a set of n jobs to be scheduled simultaneously on a single machine. Each job has associated with it a triple —(wi, Pi, di) representing the weight, processing time and due date of Ji (job i). Let ci represent the completion time of job i for a particular sequence. We wish to schedule the jobs such that the sum of weighted tardiness is minimized —i.e., i =n ii wi max (o, ci - di) is minimized. It has been shown by Lenstra [1977] that the above problem is NP-Complete. In the past, various researchers developed enumerative methods for solving this problem. Noteworthy among these methods are the approaches developed by Rinnooy Kan et al [1975], Picard and Queyranne [1978] and Schrage and Baker [1978]. These procedures make use of the dominance tests developed by Emmons [1969] for average tardiness problems and extended for the weighted tardiness problem by Rinnooy Kan et al [1975] in structuring the problem as a global precedence network. The purpose of this note is to develop an additional local precedence relationship among adjacent jobs in optimal sequences. Proposition 1: Consider any two adjacent jobs in an optimal sequence for the single machine weighted tardiness problem. Either the following condition holds good or an alternate optimal sequence can be constructed by interchanging the adjacent jobs which satisfies the following condition. w -(d -t-p iL )Q wi+i] ( d i+t] -p + W[i] 1(3 tPi) fil > [i+l] [i+l] t [i+l] P[i1]Pi P[i+] P[i] where [i] denotes the index of the job in ith position, x+ denotes max (O,x) and t is the start time for J[i]'

-3 - Proof: In the optimal sequence under consideration, jobs are either early (being on time is considered as early case) or tardy. We show through pairwise interchange arguments that either our condition is satisfied or an alternate optimal sequence is constructed in which that condition is satisfied. We have 16 cases to consider (E is early and T is tardy). Without loss of generality, assume that i is the index of job occupying ith position and j be the index of jobs occupying i+lth position. Case # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Before interchange Job i E E E E E E E E T T T T T T T T Job j E E E E T T T T E E E E T T T T After interchange Job i E E T T E E T T E E T T E E T T Job j E T E T E T E T E T E T E T E E Note that cases 2, 4, 9, 10, 12, 13 and 14 are logically inconsistent. In case 1, if the condition is not satisfied, we merely interchange jobs i and j without losing optimality. In all other cases, the condition can be shown to be necessary through pairwise interchange arguments. Details are omitted here for the sake.of brevity. Further, it is interesting to note that the Corollary 2 developed by Picard and Queyranne [3] is a special case of Proposition 1. Also, we further show that a very effective dispatch rule developed by Baker and Bertrand [6] for the average tardiness problem (wi=l,i=l,....n) is a special case of Proposition 1. The details are given below.

-4 -Baker and Bertrand [1982] had developed a very effective dispatch type heuristic rule for the average tardiness problem —i.e., wi = 1 for all jobs. The rule is as follows —for all jobs yet to be scheduled, determine modified due date (d' ) as follows: d; = max(d.,t+P ). Schedule next the jobs that has earliest modified due date. Proposition 2: MDD is a necessary condition for any optimal sequence for the static average tardiness problems. Proof: We establish the claim by showing that the Modified Due Date Rule can be derived from Proposition 1. Since wi = 1 for all jobs in the unweighted case, Proposition 1 can be rewritten as 1 ( di-t-Pi ) 1 (d -t-p + Pi Pi PI Pi p( - (di -t-pi)i ) p (d j - t- pQ) Pj >- p Pi. - p i Pi d t-P ~ >i -Pi (d j-t-p j) + -P i- (d.-t-p.) > -pj - (dj —pj Pi + (di-t-Pi) -< P - (dj-t-pj) Pi+ max(O, d -t-p.) < p + max(O, d -t-p.) -(t+Pi)+Pi+max(t+pidi) < -(t+p )+p+mnax(t+p.,d) max(di t+pi) < max(d.,t+p.) Proposition 1 is easy to implement in any search procedure for weighted tardiness problem. It can be applied at any point in an enumerative procedure to ensure local optimality, thus reducing the search for optimal solution.

-5 - Further, it may be noted that Proposition 1 can easily be used irrespective of whether the enumerative method generates the schedule in forward direction or backward direction. Further, Proposition 1 can be used as a stopping rule in some situations in identifying optimal first job. In most practical situations, we are concerned with identifying next job to be scheduled on the machine and not necessarily develop the full schedule. Proposition 3: If the job with the highest w ratio is tardy even if scheduled P first, then there exists at least one optimal sequence in which it should be scheduled first. Proof: The proof is by contradiction. Let k be the index of the job with the w highest - ratio. Suppose that there exists an optimal sequence p such that Ji immediately precedes Jk and let t be the start time for Ji. By Proposition 1, /1 (di-t-pi Wk (dk-t-P k)+ >.... Pi Pj - Pk Pj Wk Note that since d < Pk, right hand side is always - and LHS is Pk w wk wi never more than -. Since >- (by definition), this condradicts Pi Pk Pi the supposition that the original sequence was optimal. Thus there can be no optimal sequence in which Jk is preceded by another job. This implies that Jk should be scheduled first irrespective of the rest of the schedule.

-6 - Ackn owl edgement We wish to thank an anonymous referee for pointing out the current version of Proposition 1 which is actually a stronger version of the result than claimed by Morton and Rachamadugu [1982] and also for pointing out the validity of their result aft for a case4analyzed in their earlier work. REFERENCES Baker, K., and Bertrand, J. 1982. A dynamic priority rule for scheduling against due-dates. Journal of Operations Management. 3, 37-42. Emmons, H. 1969. One machine sequencing to minimize certain functions of job tardiness. Operations Research. 17, 701-715. Lenstra, J. K. 1977. Sequencing by Enumerative Methods. Mathematisch Centrum, Amsterdam. Morton, T. E., and Rachamadugu, R. V. 1982. Myopic Heuristics for the single machine weighted tardiness problem. GSIA Working Paper, Carnegie Mellon University, Pittsburgh, PA. Picard, J. D., and Queyranne, M. 1978. The time dependent traveling salesman problem and its applications to the tardiness problem in one machine scheduling. Operations Research. 26, 86-110. Rinnooy Kan, A. H. G., Lagweg, B. J., and Lenstra, J. K. 1975. Minimizing total costs in one machine scheduling. Operations Research. 23, 908-927. Schrage, L. and Baker, K. R. 1978. Dynamic Programming Solution of sequencing problems with precedence constraints. Operations Research. 26, 444-449.