SCHEDULING TO MINIMIZE THE WEIGHTED SUM OF COMPLETION TIMES WITH SECONDARY CRITERIA.

Abstract

The problem of minimizing the sum of weighted completion times subject to a secondary constraint has long been considered to be similar to minimizing the sum of completion times subject to a constraint. W. E. Smith (Nav Res Log Quart v 3 1976 p 59-66) presented an algorithm for the n-job, l-machine case where he minimized the weighted completion times subject to the constraint that all jobs were completed by their due dates. Recently, H. Heck and S. Roberts presented an algorithm for minimizing the sum of completion times subject to not increasing the maximum tardiness calculated by the due date sequence. They claimed that their result could be extended to the problem of weighted completion times in a manner similar to Smith's algorithm. Such is not the case since Smith's algorithm did not find the optimum sequence. In this paper, a new algorithm is given that converges to a local optimum for both problems. Show more