A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times (Q1014305)

The problem of minimizing the makespan on one machine is considered. Each job has a release date. The processing time of each job depends on the starting time linearly. For this strongly NP-hard problem an exact optimization algorithm with exponential worst-case complexity is presented. Polynomial solvable subproblems and upper and lower bounds to the makespan are described. Two different sets of experiments are performed. The first set of experiments is aimed at studying how the time consumption of the algorithm depends on the data. The second set of experiments compares different search policies.