A dynamic programming method for single machine scheduling

This paper treats the single machine scheduling problem that minimizes the sum of general cost functions defined for jobs, e.g., weighted sums of earliness and tardiness. Since the straightforward dynamic programming recursion requires 2’n states, where n is the number of jobs, an SSDP (successive sublimation dynamic programming) method is developed to keep the number of generated states within manageable level, by utilizing several types of dynamic programming recursions representing varied degrees of state-space relaxations. Computational results on problem instances of up to n=35 exhibit a clear superiority of this SSDP approach over the original dynamic programming recursion.