Four solution techniques for a general one machine scheduling problem: A comparative study

Gelders and Kleindorfer suggested a generalized detailed scheduling cost structure, based on the sum of weighted tardiness and weighted flowtime. They solved the single-machine scheduling problem using a transportation scheme to obtain lower bounds in their branch and bound approach. Recently, Fisher, Baker, Rinnooy Kan and Srinivasan reported attractive computation times with general algorithms adapted to the total tardiness problem for the single-machine case. In this paper four algorithms are adapted to the generalized cost structure mentioned above and extensive computational results are presented.This investigation shows that much is to be expected from the dual approach for more complex scheduling problems while dynamic programming deserves a new research effort because of its efficiency in special structured problems and/or problems where a posteriori precedence relations (dominance criteria) can be developed.