A FAST ACCURATE HEURISTIC FOR THE TOTAL TARDINESS PROBLEM Technical Report 84-21 James C. Bean Daniel N. Hall Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan, 48109 September 1984 Working paper, results not to be used or quoted without permission of author

A FAST, ACCURATE HEURISTIC FOR THE TOTAL TARDINESS PROBLEM James C. Bean Daniel N. Hall Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 ABSTRACT This paper presents a sorting type heuristic for the single machine total (or average) tardiness sequencing problem. The algorithm has one to two per cent errors, on average, for 46 test problems. The algorithm logic is designed to fit as a module in a hierarchical system for larger, more complicated, due date driven scheduling systems. A variation is presented with errors less than one percent at the expense of the sorting structure. KEYWORDS: Scheduling, Total Tardiness 1. Introduction The single machine sequencing problem to minimize total tardiness (or equivalently, average tardiness) involves a set of tasks each having a known processing time, pj, and due date, dj. The tardiness of job j is defined as Tj = max(0, Cj - dj), where Cj is the completion time assigned to job j. This problem is important in some large scheduling problems (Bean, Birge, Mittenthal and Noon [1984]). Though actual objectives in such problems are much more complicated, total tardiness is sometimes used as a surrogate. It is not known whether or not the single machine problem to minimize total tardiness is NPcomplete. A pseudo-polynomial algorithm has been presented in Lawler [1977]. Other effective approaches to optimally solving this problem include Schrage and Baker [1978], and Fisher [1976]. Heuristic approaches to the total tardiness problem include Wilkerson-Irwin [19711 and Montagne [1969]. The potential impact of the single machine total tardiness problem lies in its use as a module within large hierarchical systems. To be useful in such a hierarchical system, it is desirable for the single machine logic to schedule jobs singty and forward in time. For efficiency it is desirable to schedule in a greedy manner, using only local information. These so called dispatching rules are discussed in Baker and Kanet 19831 and Baker [19841. 1

This paper presents heuristics for the single machine total tardiness problem designed for this use. The logic of the Basic Algorithm is equivalent to that in Baker and Bertrand [1982]. This paper goes beyond that by testing the algorithm against optimal solutions, presenting a modification with better accuracy, and giving theoretical justification for the performance. Section 2 presents the Basic Algorithm and the Augmented Algorithm. Section 3 presents justification and motivation for the algorithms. Section 4 contains computational results. 2. The Algorithms These algorithms contain much of the intelligence of both Emmons [1969] global dominance criteria and the local interchange from Wilkerson-Irwin [1971]. It is this combination that results in the efficiency and efficacy described in Section 4. Following is a statement of the algorithms. Basic Algorithm Step 0: Set r = 0. Go to Step 1. Step 1: For each unscheduled job calculate xj = max(pj, dj - r). Let j' = arg mini xj. Go to Step 2. Step 2: Put j' next in the sequence. Update r to r + pj-. If jobs remain unscheduled, then go to Step 1. Otherwise, stop. This is a sorting type algorithm which places individual jobs by minimizing the simple statistic xj. It is not a true sorting algorithm since the comparison of two jobs requires knowledge of the current time, r. This algorithm does, however, meet the desired characteristics of scheduling forward in time with local information. As discussed in Section 4. this algorithm performs surprisingly well on a large set of test problems taken from the literature. However, a slight modification improves its accuracy with little cost in computation. The algorithm with this modification is: Augmented Algorithm Step 0: and Step 1: are the same as in the Basic Algorithm. Step 2: Put j* next in the sequence. Update, to - pj-. Go to Step 3. Step S: For each job currently scheduled, construct a trial schedule with that job removed from its current position and placed last. If the best of such trial schedules has lower total tardiness than the current schedule, consider it the current schedule. If jobs remain unscheduled, then go to Step 1. Otherwise, stop. The augmentation of this algorithm with Step 3 allows an incorrectly placed job to be freed to a later position in the schedule. This algorithm is still very fast. but it loses the forward, 2 A,

local information characteristics of the Basic Algorithm. The accuracy of this algorithm could be improved further by checking the local optimality from Lemma 1 after Step 3. 3. Justification of the Algorithms As seen in Section 4, these algorithms deliver nearly optimal solutions on the problems tested. There is theoretical justification for this high degree of accuracy. The Basic Algorithm contains the local intelligence used by the Wilkerson-Irwin Algorithm. We know that, for two adjacent jobs j and k, we will locally lower tardiness if they are in earliest due date order unless r +max(pj, pk) > max(dy, dk), in which case they should be in shortest processing time order. This pairwise interchange argument is not guaranteed to lead to an optimal sequence because the comparison of j and k is local. Lemma 1: At any time, r > 0, max(pj, dj - r) < max(pk, dk - r) if and only if j may precede k according to this interchange rule. Proof: Omitted. (consists of several obvious cases) The Basic Algorithm goes further in that it performs global comparisons. Since the value xi contains data pertaining only to job j, all unscheduled jobs can be considered simultaneously at each placement. As a corollary of Emmons [1969] classic set of dominance properties for the total tardiness problem we can see that these global comparisons are commonly optimal. Theorem 2: (Emmons) Let 3j be the set of jobs known to precede job j in some optimal sequence. Let aj be the set of jobs known to succeed job j in some optimal sequence. Finally, let ac be the set of jobs not represented in aj. If any of the properties a), b) or c) below is satisfied for two jobs j and k, then j precedes k in some optimal sequence. a) pj < Pk, dj < max(dk, Pk + Eisk Pi) b) pj > Pk dj < dk, dk + Pk >2 Eia'. Pi C) dk >~ iEr Pi j' = arg min max(pj, dy). In choosing j' we hope that for all k = j' that j' precedes k in some optimal sequence. By construction we know that max(pj., dj-) < max(pk, dk). If this fact were sufficient to prove that j' precedes k then. by induction, we could prove that the Basic Algorithm is in fact optimal (see Emmons [1969]). This is. of course, not the case. However, it is instructive to proceed in this manner. Pointing out the valid parts of such a proof and those that break down suggests a reason for the algorithms' accuracy and potential directions for bounding its error. 3

The fact that max(pj., dj-) < max(pk, dk) leads to five possible cases. In three of them we can prove that the decision is in fact optimal. The cases are 1) dj- pij < Pk 2) dj& < pej < dk, Pk < Pj3) pw < dj- < Pk 4) pi- < dj _< dk, pj- < Pk 5) pj- < dj- < dk, Pk < PjCorollary 3: In cases 1, 3, and 4 above it is optimal to place j' before k. Proof: A corollary of Theorem 2 part a).M Equally interesting is the analysis of cases 2 and 5. In these cases we do not know that in fact the choice to place j' before k is in error. We simply do not have enough information. From Theorem 2 parts b) or c), if Z,' Pi is small enough, this choice will be optimal as well. Knowledge of this value requires knowledge of the future schedule and global information. The computational results show how frequently decisions were made in the known optimal cases and the unknown cases, 2 and 5. 4. Analysis of Computation 4.1 Complexity Since the Basic Algorithm is not a pure sorting algorithm it cannot be solved by an efficient (nln n) sorting routine. At some stage of the Basic Algorithm let there be i unscheduled jobs. Then to carry out the next placement we must make i subtractions and i comparisons to calculate the xj, then another i- 1 comparisons to determine j'. Hence the computation for the entire algorithm is (3i-1) = O(n2), i=l where n is the number of jobs in the problem. The Augmented Algorithm requires the additional Step 3. The total computation becomes 3i - 1 = O(n). i=1 4.2 Computational Results Computational experiments were carried out on the University of Michigan Amdahl 5860 computer under the MTS operating system. All CPU times are given in seconds and exclude data input. 4

Test problems were taken from Baker [1974] and Fisher [1976]. In all, 46 problems were run ranging from 8 to 50 jobs. Table 1 shows the averages of runs in four problem sets using the Basic Algorithm. The same information for the Augmented Algorithm is in Table 2. The first set of problems is comprised of the 16 problems in Baker [1974]. Sets two, three, and four are subsets of the 20, 30, and 50 job problems in Fisher [1976]. The column labeled "% 1,3,4" in Table 1 is the fraction of decisions made under the optimal cases in Corollary 3. The column labeled "MEAN ERROR" displays the arithmetic average of heuristic value - optimal value optimal value for the problems in that set. In Table 2 the column "# OPT" presents how many of the problems in that set were solved optimally. These results are the same as for the Basic Algorithm and, hence, are not included in Table 1. 6. Summary and Conclusions This paper presents low order polynomial algorithms for the basic single machine sequencing problem with objective to minimize total tardiness. The Basic Algorithm has the characteristics that jobs are scheduled forward in time using only local information. Hence, the logic of the algorithm may be useful as part of a hierarchical system to solve due date driven scheduling problems. The algorithms have negligible computation times for problems up to 50 jobs. The error is on the order of one to two per cent. Of the two algorithms presented here, the Augmented Algorithm has better accuracy for the total tardiness problem. This does not indicate, however, that it should be the algorithm of choice in an application situation. As mentioned earlier, the objective to minimize total tardiness is usually a surrogate for the actual, more complex, objective. Hence, we should look generally at the quality of solutions generated by the algorithms. In particular we will look at the distribution of tardiness in the solutions. Table 3 compares the maximum tardiness and mean tardiness over tardy jobs for the solutions from the Basic Algorithm, the Augmented Algorithm and the optimal solution. For each problem the secondary values for the Basic Algorithm were considered the reference points. The results from the Augmented Algorithm and the optimal solution were normalized by these values and the averages reported. Keeping in mind that the Basic Algorithm displays average error in total tardiness of under two per cent. it appears to have a distinct advantage in the other measures over both the Augmented Algorithm and any optimal algorithm. In many cases, going too far towards the total tardiness optimal produced schedules with particular jobs that were very tardy. Overall, our experience 5

with practitioners indicates that the Basic Algorithm delivers more usable solutions than either the Augmented Algorithm or any optimal algorithm. The structure of this algorithm is simple enough that obvious changes could be made to handle ready times and sequence dependent set-ups. Some extensions are discussed in Baker and Bertrand [1982]. Job shop adaptations are in Baker and Kanet [1983] and Baker [1984]. These and other extensions are currently being investigated. 6

REFERENCES Baker, K. [1974], Introduction to Sequencing and Scheduling, Wiley: New York. Baker, K. [1984], "Sequencing Rules and Due-Date Assignments in' a Job Shop," Management Science, Vol. 30, pp. 1093-1104. Baker, K. and J. Bertrand [1982], "A Dynamic Priority Rule for Scheduling Against Due-Dates," Journal of Operations Management, Vol. 3, pp. 37-42. Baker, K. and J. Kanet [1983], "Job Shop Scheduling with Modified Due Dates," Journal of Operations Management, Vol. 4, pp. 11-22. Bean J., J. Birge, J. Mittenthal and C. Noon [1984], "An Adaptive Approach to Real-Time Scheduling," Technical Report 84-18, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109. Emmons, H. [1969], "One-Machine Sequencing to Minimize Certain Functions of Job Tardiness," Operations Research, Vol. 17. pp. 701-715. Fisher, M. [1976], "A Dual Algorithm for the One-Machine Scheduling Problem," Mathematical Prograrmning, Vol. 11, pp. 229-251. Lawler, E. [19771, "A Pseudopolynomial Algorithm for Sequencing Jobs to Minimize, Total Tardiness," Annals of Discrete Mathematics 1, pp. 331-342. Montagne, E. [1969], "Sequencing with Time Delay Costs," Arizona State University Industrial Engineering Research Bulletin No. 5, pp. 20-31. Schrage, L. and K. Baker 1978', "Dynamic Programming Solution of Sequencing Problems with Precedence Constraints," Operations Research, Vol. 26. pp. 444-449. Wilkerson, L. and J. Irwin [1971, "An Improved Method for Scheduling Independent Tasks," AIIE Transactions, Vol. 3, pp. 239-245. This research was supported by a grant from General Motors Corporation. -W i

TABLE 1: Computational Results SOURCE Baker Fisher Fisher Fisher # JOBS 8 20 30 50 # PROBS 16 13 10 7 for the Basic Algorithm MEAN MAX CPU CPU.002.002.002.002.004.004.008.009 MEAN ERROR.004.022.012.025 MAX ERROR.053.118.060.055 MEAN ERROR.004.010.006.009 % 1,3,4 68 73 69 78 MAX ERROR.049.066.024.017 TABLE 2: Computational Results SOURCE Baker Fisher Fisher Fisher # JOBS 8 20 30 50 - PROBS 16 13 10 7 for the Augmented Algorithm MEAN MAX # OPT CPU CPU 14.002.002 7.007.008 7.016.020 1.066.072 TABLE 3: Secondary BASIC,# JOBS Tmax 8 1.000 20 1.000 30 1.000 50 1.000 Objective Considerations BASIC AUG. TTj>O Tmax 1.000 1.012 1.000 1.162 1.000 1.000 1.000 1.057 AUG. TTj>o 1.000 1.142 1.075 1.178 OPT. Tmax 1.041 1.195 1.021 1.040 OPT. TTj>O 1.058 1.140 1.065 1.204 8