A dynamic programming algorithm for single machine scheduling with ready times

The authors propose a dynamic programming algorithm for the single machine scheduling problem with ready times and deadlines to minimize total weighted completion time. Weights may be positive or negative and the cost function may be non-regular. This problem appears as a subproblem in the Dantzig-Wolfe decomposition of the job-shop scheduling problem. The authors show that the algorithm is polynomial if time window length is bounded by a constant and times are integer-valued. They present computational results for problems with up to 200 jobs.