MINIMIZATION OF TIME-VARYING COSTS IN SINGLE-MACHINE SCHEDULING

Assume n jobs are to processed consecutively by a single machine, without interruption and without idle time. Each job j has a known processing time p//j and has associated with it a time-varying cost density function c//j. It is shown that if the cost density functions of the jobs satisfy certain simple conditions, a sequence minimizing total cost is easily obtained. This result generalizes the well-known ″ratio rule″ of W. E. Smith for minimizing total weighted completion time and is applicable to problems involving discounted linear delay cost, discounted linear processing costs, discounted resetting and processing costs, and linear combinations of these cost. Moreover, it is shown that for such costs, sequences that are optimal subject to series parallel precedence constraints can be found in o(n log n) time.