Division of Research Graduate School of Business Administration The University of Michigan A NOTE ON SMITH'S SCHEDULE TO MINIMIZE THE WEIGHTED SUM OF COMPLETION TIMES WITH MAXIMUM ALLOWABLE TARDINESS Working Paper No. 419 Suresh Chand Purdue University and Hans M. Schneeberger The University of Michigan FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the expressed permission of the Division of Research. March 1985

ABSTRACT This paper analyzes the Smith-heuristic for the single-machine scheduling problem where the objective is to minimize the total weighted completion time subject to the constraint that the tardiness for any job does not exceed a prespecified maximum allowable tardiness. We identify several cases of this problem for which the Smith-heuristic is guaranteed to lead to optimal solutions. We also provide a worst-case-analysis of the Smith-heuristic; the analysis shows that the fractional increase in the objective function value for Smith-heuristic from the optimal solution is unbounded in the worst case.

I

1. INTRODUCTION The following single machine scheduling problem is considered in this paper. Let N be the number of jobs available for scheduling and let T be the maximum allowable tardiness. Further, let pi, ai, di, and Ci denote the processing time, weight, due date and completion time, respectively, for job i. The problem can the be stated as follows: N Minimize > aiCi i=l Subject to Ci - d < T Note that the completion time Ci in a schedule is the sum of the processing time of job i and all the jobs preceding job i. We will call this problem the Constained Weighted Completion Time Problem (CWCT-Problem). The CWCT-Problem was first considered by Smith [8] with T=O. He provided a polynomial time algorithm for the case with equal weights al = a2 =... = aN. He further proposed an extension for the case with unequal weights. Heck and Roberts [4] generalized Smith's results for the case when T > 0. Smith [8] and Heck and Roberts [4] conjectured that their algorithms for the CWCT-Problem with unequal weights are optimal. Counter examples provided Emmons [3] and Burns [1], however, show that these algorithms are not guaranteed to be optimal. Lenstra et. al [5] and Chand and Schneeberger [2] show that this problem in general is NP-hard; i.e., it is unlikely that a polynomial time algorithm could be developed that would find optimal solutions to all instances of this problem. Burns [1] and Miyazaki [6] recognized that the Smith-procedure is only locally optimal in the sense that the pairwise interchange of any two adjacent jobs would not improve the objective function. They then suggested some improvements over the Smith-heuristic. Shanthikumar and Buzacott [7] proposed a Branch and Bound

2 algorithm and Chand and Schneebergur [2] developed a dynamic programming algorithm with an inbedded Branch and Bound procedure to solve this problem. In this paper, we identify several cases of the CWCT-Problem for which the algorithm of Smith (Smith-heuristic) is guaranteed to give optimal solutions (easy problems). The insights provided by these results can be very useful to researchers in developing heuristics and optimal procedures for solving the CWCT-Problem. In section 2, we briefly review and analyze the Smith-heuristic. In section 3, we prove a new result: The CWCT-Problem with weights a, a2,..., aN is equivalent to another CWCT-Problem with weights a1 + qp1, a2 + qP 22... aN + qPN' where q is any known number. In section 4, we use the results from the previous two sections in identifying the instances of the CWCT-Problem that can be solved optimally in polynomial time. In section 5, we show that the worst - case - performance of the Smith-heuristic can be made arbitrarily bad. The paper closes in section 6 by summarizing the results. Throughout the rest of the paper, we will assume T = 0. A CWCT-Problem with T > 0 can be converted into an equivalent CWCT-Problem with zero maximum allowable tardiness simply by inflating all the due dates by T. 2. REVIEW AND ANALYSIS OF THE SMITH-HEURISTIC The following algorithm provided by Smith gives pairwise local optimal schedule for the CWCT-Problem. Algorithm (Smith): (a) Arrange the jobs in the order of increasing due dates. It is assumed that all jobs are on time in this schedule; if not, then the problem does not have a feasible solution.

3 (b) Find jobs with due dates greater than or equal to the total processing time of all jobs to be scheduled; these jobs are feasible candidates for the last position in the sequence. (c) Find the job with the largest p/a-ratio from the feasible jobs and schedule it in the last position. (d) Reduce the set of jobs yet to be scheduled by one, by removing the job just scheduled in (c). Go to (b) until all jobs have been scheduled by this method. As reported in Lenstra et. al [5], the computational time for this algorithm is bounded by O(NlogN). Let [i] denote the job in position i in a given sequence. Miyazaki [6] showed that the Smith-heuristic is globally optimal if C[+] < d[i]. Using this result, he developed an improved algorithm with the computational time bounded by 0(N). Burns [1] provided an algorithm (with computational time of the order of 0(N3)) which finds a local optimum such that a pairwise interchange of any two jobs would not improve the objective function. The sufficient condition provided by Miyazaki for the optimality of the Smith-heuristic is based on the characteristics of the final sequence. Such conditions cannot be used, a priori, to find whether or not the heuristic is optimal for the given class of problems. In this paper, our interest is to find the characteristics of the problem data (due dates, weights, and processing times) for which the Smith-heuristic is guaranteed to be optimal. One such characteristic is given by the following theorem.

4 THEOREM 1: The Smith-heuristic is globally opitmal if the problem data is such that Pi > Pj - ai < aj for all jobs i and J, and ai > 0. Proof: Note that steps (a) and (b) of the Smith-heuristic are needed to achieve a feasible sequence. We only have to show that step (c) is optimal. We prove the Theorem by contradiction. Assume that an optimal sequence does not satisfy step (c) in the algorithm. This implies that there exist jobs k and t with Pk/ak > pE/ai where both jobs are feasible candidates for the last position of the sequence and job ~ is assigned to the last position. Job k will then take a position earlier in the sequence. We show that in this case, interchanging jobs k and ~ will always improve the objective function value. Due to the specifications in the theorem, Pk/ak > pj/aE implies Pk > PR and ak < at. Clearly, interchanging jobs k and t is feasible. Denote the set of jobs between jobs k and t by Sk, with Z pi = P and Z ai = A. The ieSk,t iCSk,z decrease in the objective function value realized by interchanging jobs k and L and rearranging the jobs in Sk, optimally is AV > (pk-pt)A + (P+pk) a - (P+pa) a - (Pk-P)A + P(.aQ-k) + PkaQ - ptak >0 >0 >0 >0 Hence, AV is always positive which completes the proof. Theorem 1 implies the following corollary.

5 Corollary 1: The Smith-heuristic is globally optimal when all ai's are equal, i.e;, when a - a " -. a 1 2 N Note that the result in Corollary 1 was proved by Smith also; thus, Theorem 1 can be viewed as a generalization of this result of Smith. In the next section we prove a result for finding equivalent CWCT-Problems. 3. EQUIVALENT CWCT-PROBLEMS Two scheduling problems which differ from each other only by a constant in the objective function will be considered equivalent. Clearly, any procedure that solves a problem will also solve all the corresponding equivalent problems. Let the notation (ai, Pi di)-problem denote the CWCT-Problem with weights a, a2,..., aN; processing times pi, 2' '... PN; and due dates d1, d2,...,dN. The following Theorem provides a way of finding equivalent problems to a given CWCT-Problem. THEOREM 2: The (ai, Pi' di)-problem is equivalent to the (ai+qpi, Pi' di)problem where q is any known constant. Proof: Let p[i] denote the job in position i. Then C[i] can be expressed as C[i] ZP[j] j=l The objective function for the (ai + qPi Pi' di)-problem can then be written as:

6 N V = (a + qpi)C i=l N N N = objective function for the (ai Pi, di)-problem + q ZpiC i=l Note that N N i q PiCi- q Z E P(]P[j] i-l iil j=1 N i = q SE pipj i=1 j=l = constant. Thus, the objective function value for the (a,, Pi, di)-problem differs from that for the (a + qPi, Pi, di)-problem only by a constant. This completes the proof. In.the next section, using the results in theorems 1 and 2, we identify instances of the CWCT-problem where the Smith-heuristic is guaranteed to be globally optimal. 4. SOME EASY PROBLEMS To make the presentation easier, we assume that the weight assigned to a job is a function of it's processing time; that is, ai f(pi), il,2,...,N. This assumption implies that a = a when pi = pj. The results in this section can be easily extended to the situation when this assumption does not hold.

7 With this assumption, the result in Theorem 1 can be restated as follows: the CWCT-Problem with the weight a = f(p) a non-increasing function of p and f(p ) > 0 for i1l, 2,..., N is an easy problem. Using the result in Theorem 2 we can state that any (f(pi), Pi, di)-problem for which there exists a q such that f(p) + qp is a non-increasing function of p and f(pi) + qPi > 0, for il1, 2,...,N, is also an easy problem; the following result gives a necessary and sufficient condition for the existence of such a q. THEOREM 3: Let the jobs be numbered such that p < p2 <,... PN. Consider a (f(pi), Pi' di)-problem. An equivalent (f(Pi) - qPi Pi' di)-problem with f(Pi) - qP > 0 for i=l, 2,..., N can be found if and only if f(PN/PN < f(Pi)/P for i1l, 2,..., N (1) f(p i+) - f(pi+l) and f(P > for il, 2,..., N-l. (2) Pi -Pi Proof: Let q - f(p )/PN. From (1) we have q < f(pi)/Pi for i=l, 2,...,N or f(Pi) qPi > ~ for iml, 2,..., N. From (2), we have q > (Pi+l) (i for i - 1, 2,..., N-1 Pi+l Pi or f(p ) - f(Pi+) qPi+ for i=l, 2,..., N-1. Thus, these conditions are sufficient. We now show that these conditions are necessary also. The requirement that f(pi) - qi > 0 for il, 2,...,N implies q < f(Pi)/Pi for i-l, 2,...,N (3)

8 The requirement that f(p) - qp be a non-increasing function of p implies f(i) - q f(Pi+l) -qPi+ for i=l, 2,...,N-1 f(Pi) - f(pi) or q > (4) Pi+l Pi From (3) and (4), we have f(Pi) - f(Pi) f(Pi )/Pi _ ----> for i-l, 2,..., N-1 or Pi+l f(Pi) Pi f(Pi) > Pi f(Pi+l) - Pif(pi) or f(P)/Pi > f(Pi+l)/pi+ for i=l, 2,...,N-1 or fPN)/N < f(Pi)/Pi for i=l, 2.....N. Thus, q < f(pN)/pPN From (4), we have f(Pi+l) - f(Pi) f(PN)/PN _ for i=l, 2.... N-1 i+l Pi This completes the proof. The following Corollary gives a simple procedure to determine if the given (f(Pi)' Pi, di)-problem is an easy problem. Corollary: Consider a (f(pi), Pi di)-problem. An equivalent q- f(p )/p q max /Pmax I- rmr.- 1-11 ~~

9 The results in Theorems 1 and 3 imply that the following three problems are easy problems. Easy Problem 1: The (f(pi). Pi. di)-problem with f(p) a non-increasing function of p and f(p) 0 for i=l, 2,...,N is an easy problem. f(p) p Figure 1: Easy Problem 1 Easy Problem 2: The (f(pi), Pi' di)-problem with f(p) an increasing convex function of p is an easy problem if the job with the largest processing time has the largest p/f(p)-ratio. f(p) P P Figure 2: Easy Problem 2 Easy Problem 3: The (f(p ), Ps di)-problem with f(p) an increasing concave function of p is an easy problem if Ap/Af(p) for the smallest two jobs is greater than or equal to the p/f(p)-ratio for the largest job.

10 f(p) / P Pmax It should be noted that Easy Problems 1, 2, and 3 can be solved optimally using the Smith-heuristic. 5. WORST-CASE-ANALYSIS We first give an example of a 3-job problem where the maximum fractional increase in the objective function value for the Smith-heuristic (compared to the optimal solution) can be made arbitrarily large. The data for this example is given below. In this example x is a control variable with value > 1.7 (explained later). Job 1 2 3 2 Processing Time 6x x 4 2 22 Due Date x + 6x + 4 x + 6x x+ 6x + 4 Weight 5x 14 The sequence found by the Smith-heuristic is 3-2-1 function value equal to S: S = 5 x3 + 31 x2 + 20 x + 20 with the objective The optimal sequence is 1-2-3 with the objective function value equal to V: V = 35 x2 + 30 x + 16 we have V < S for x > 1.7.

11 S-V Fractional Increase = 5x - 4 - 10/x + 4/x2 35 + 30/x + 16/x2 Clearly, the fractional increase can be made arbitrarily large by increasing the control parameter x. If we add Job 4 in the above example with processing time = p4, weight = w4 ~~~~~~~~~and the due dated ~= w4 2 and the due date d4 = d3 + P4 = x + 6x + 4 + P4' then the fraction increase is 5x - 4 - 10/x + 4/x2 35 + 30/x + 16/x2 + (x2 + 6x + 4+ p )w4/x2 which can be made arbitrarily large by increasing x for any finite p4- and w4 -values. It is now easy to see that if we add (N-3) jobs, N > 4, in the above example such that processing times and weights for these jobs are finite and di+l = di +Pi+l for i = 3,4,...,N, then the fractional increase for the Smithheuristi- can be made arbitrarily large by increasing x. This proves that the worst-case-performance of the Smith-heuristic can be made arbitrarily bad for problems of any size. 6. SUMMARY In this paper, we analyzed the Smith-heuristic for the single-machine scheduling problem where the objective is to minimize the total weighted completion subject to no tardiness. Several problems were identified which can be solved optimally by using the Smith-heuristic. It was established that the fractional increase in the objective function value for the Smith-heuristic compared to the optimal solution can be made arbitrarily large in the worst case for problems of any size.

12 REFERENCES Burns, R. N., "Scheduling to Minimize the Weighted Sum of Completion Times with Secondary Criteria," Naval Research Logistics Quarterly, Vol. 23, No. 1 (1976), pp. 125-129. Chand, S. and H. Schneeberger, "Single Machine Scheduling to Minimize Weighted Completion Time with Maximum Allowable Tardiness," Working Paper, Krannert Graduate School of Management, Purdue University. Emmons, H., "Note on a Scheduling Problem with Dual Criteria," Naval Research Logistics Quarterly, Vol. 22, No. 4 (1975), pp. 615-616. Heck, H. and S. Roberts, "A Note on the Extension of a Result on Scheduling with a Secondary Criteria," Naval Research Logistics Quarterly, Vol. 19, No. 3 (1972), pp. 403-405. Lenstra, J. K., A. H. G. Rinnooy Kan, and P. Brucker, "Complexity of Machine Scheduling Problems," Annals of Discrete Mathematics, 1, 1979, pp. 343-362. Miyazaki, Shigeji, "One Machine Scheduling Problem with Dual Criteria," Journal of the Operations Society of Japan, Vol. 24, No. 1 (1981), pp. 37-50. Shanthikumar, J. G. and Buzacott, J. A., "On The Use of Decomposition Approaches in A Single Machine Scheduling Problem," Journal of the Operations Society of Japan, Vol. 25, No. 1 (1982), pp. 29-47. Smith, W. E., "Various Optimizers for Single Stage Production," Naval Research Logistics Quarterly, Vol. 3, No. 1 (1956), pp. 59-66.