Division of Research Graduate School of Business Administration The University of Michigan March 1985 ON POTTS' AND VAN WASSENHOVEN'S ALGORITHM FOR SINGLE MACHINE SEQUENCING WITH DEADLINES TO MINIMIZE TOTAL WEIGHTED COMPLETION TIME Working Paper No. 418 Hans. M. Schneeberger FOR DISCUSSION PURPOSES ONLY None of this material reproduced without the of the Division is to be quoted or expressed permission of Research.

I

ABSTRACT The European Journal of Operations Research 12 (1983) reported on a branch and bound algorithm by Potts and van Wassenhoven to solve the single machine sequencing problem with deadlines to minimize total weighted completion time. One key feature of their algorithm is a multiplier adjustment method to solve the dual problem which is used as a lower bound in the branch and bound scheme. This note analyzes the lower bound procedure and provides insight with respect to the excellent computational results which have been obtained with the algorithm.

I i I iI I i

1. Introduction Using the notation of Potts and van Wassenhoven, let pi, wi, di, and Ci be the processing time, weight, due date, and completion time, respectively, for job i. The problem under consideration can then be stated as follows: N min Z w.C. (1) i=l 1 1 s.t. Ci-di 0 for i = 1, 2,..., N (2) N is the total number of jobs. The completion time Ci in a schedule is the sum of the processing times of job i and all jobs preceding job i. This problem has been studied extensively [1,2,3,4,5,6,7,8,9,10]. Of particular interest in the context of this note is the work done by Smith [10] and the work done by Potts and van Wassenhoven [8]. Smith provided optimal algorithms for the sequencing problem without deadlines as well as for the sequencing problem with deadlines but equal weights for all jobs, that is w = w =... = wN. He then combined the two algorithms and proposed a procedure for the sequencing problem with deadlines and unequal weights, that is, the problem under consideration in this paper. Counter examples provided by Emmons [4] and Heck and Roberts [5], however, show that Smith's procedure does not guarantee an optimal solution for the problem with unequal weights and deadlines. Today it is well known that this problem is NP-hard

- 2 - which implies that it is very unlikely that it can be solved using a simple polynomial time algorithm [6]. Computational results indicate that the Smith-Heuristic provides tight upper bounds [2,8]. Since it is computationally simple it can be used effectively in a branch and bound scheme. In many branch and bound algorithms, Lagrangean relaxations have been proven to provide effective lower bounds. It is well known that an optimal dual solution provides a bound which is at least as tight as an LP-relaxation. In addition the dual can always be solved using subgradient optimization. However, since subgradient optimization can become computationally burdensome, one tries to resort to some kind of a multiplier adjustment method to approximate the dual solution. In this note we will show that the multiplier adjustment method used by Potts and van Wassenhoven [8] not just approximates the dual solution but actually provides the optimal solution to the dual problem. This, together with the fact that the procedure is computationally simple, explains to a large extent the good performance of their algorithm. 2. Analyses of the Multiplier Adjustment Method Smith [10] showed that for the sequencing problem without deadlines the optimal solution is such that the pi/wi-ratios form a nondecreasing sequence. Consider now the dual of problem [(1), (2)]. This dual problem can be stated as follows.

- 3 - N max {min z [wiCi + Ui(Ci-di)]} (3) u C i=l for a fixed set of multipliers this reduces to N h(u) - min { C.(w.+u.)} (4) C i=l 1 1 We can easily obtain h(u) simply by sequencing the jobs according to nondecreasing pi/(wi+ui) - ratios to obtain Ci and then N compute Z C.(wi+ui). It should further be noted that h(u) i=l 1 11 is concave which implies that verifying local optimality is sufficient to guarantee global optimality. Consider now a sequence S, obtained by applying the Smith procedure to problem [(1), (2)] (see [3,8,10] for details of this procedure). Further let the elements of the vector u be such that ui > O, ui as small as possible, and the pi/(wi+ui) - ratios are nondecreasing in the sequence S. Note that this is the multiplier adjustment scheme used in [8]. We show that u solves max h(u), that is, u solves the dual problem (3). First consider the following Lemma. Let K(u) be the set of all sequences S which solve h(u). Lemma: If u~ solves the dual problem (3), then there exists a sequence S K(u~) which is primal feasible. Proof: Assume the preceding lemma is not true. This implies that for every sequence in K(u~) there is always at least one i

- 4 - for which Ci-di > O. The dual solution can then be improved simply by increasing ui, implying that u is not optimal which, contradicts the assumption and hence completes the proof. Theorem: u solves max h(u), that is, u solves the dual problem (3). Proof: First consider a vector A > 0 of appropriate dimension. Since the sequence used to generate u is primal feasible h(u+A) < h(u). Next consider a vector A with some elements A. < 0. It is easy to see that in this case K(u+A) does not 1 contain a primal feasible sequence. According to the preceding lemma this implies that h(u+A) < h(u). Hence h(u+A) < h(u) for any vector A. 3. Discussion and Conclusion In this note we showed that the multiplier adjustment method used by Potts and van Wassenhoven in their branch and bound algorithm provides the optimal solution to the dual problem. Since the procedure is computationally simple we expect a good performance of any algorithm exploiting such easy to solve dual problems. In the context of the result of this paper it is not surprising that the lower bounds obtained using subgradient optimization are within fractions of a percent to the solution obtained using the multiplier adjustment method. However, it is surprising that the results reported in [8] indicate that the subgradient bound is tighter than the bound obtained using the multiplier adjustment scheme, especially since we established

- 5 - that the latter is always tighter. In addition the computational results showed two instances where the bounds generated using Bansal's bounding procedure [1] were substantially tighter than the bounds obtained using the multiplier adjustment method. From a theoretical point of view this seems very unlikely since Bansal's procedure corresponds to the dual solution where all multipliers are equal to zero. Finally, I believe that this particular sequencing problem is not the only combinatorial problem where a relatively simple heuristic in conjunction with a multiplier adjustment method can provide tight lower bounds by not just approximating the dual solution but actually solving the dual problem.

- 6 REFERENCES 1. Bansal, S. P., "Single Machine Scheduling to Minimize Weighted Sum of Completion Times With Secondary Criterion - A Branch and Bound Approach," European Journal of Operations Research, No. 5 (1980), pp. 177 -181. 2. 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. 3. Chand, S. and H. Schneeberger, "A Note on Smith's Schedule to Minimize the Weighted Sum of Completion Times with Maximum Allowable Tardiness," Working Paper, Krannert Graduate School of Management, Purdue University. 4. Emmons, H., "Note on a Scheduling Problem with Dual Criteria," Naval Research Logistics Quarterly, Vol. 22, No. 4 (1975), PP. 615-616. 5. 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. 6. 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. 7. Miyazaki, Shigeji, "One Machine Scheduling Problem with Dual Criteria," Journal of the Operations Society of Japan, Vol. 24, No. 1 (1981), pp. 37-50. 8. Potts, C. N. and L. N. van Wassenhoven, "An Algorithm for Single Machine Sequencing with Deadlines to Minimize Total Weighted Completion Time," European Journal of Operations Research, No. 12 (1983), pp. 379-387. 9. Shanthikumar, J. G. and J. A. Buzacott, "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. 10. Smith, W. E., "Various Optimizers for Single Stage Production," Naval Research Logistics Quarterly, Vol. 3, No. 1 (1956), pp. 59-66.