Consider the problem 1 | prec | max(h1(S1),...,hn(Sn)), where Sj denotes the starting time of job j. The cost function hj , j = 1,...,n is decreasing. Unforced idleness of the machine is not allowed. Describe a dynamic programming type algorithm for this problem similar to the one in Section 3.2. Why does one have to use here forward dynamic programming instead of backward dynamic programming?

Algorithm 3.2.1 (Minimizing Maximum Cost) Step 1. Set J = , Jc = {1, ,n) and J' the set of all jobs with no successors. Step 2 Let j be such that JE.J ke.Je ke.Jc Add j* to J Delete j" from J Modify J' to represent the new set of schedulable jobs. Step 3. If J STOP, otherwise go to Step 2. Algorithm 3.2.1 (Minimizing Maximum Cost) Step 1. Set J = , Jc = {1, ,n) and J' the set of all jobs with no successors. Step 2 Let j be such that JE.J ke.Je ke.Jc Add j* to J Delete j" from J Modify J' to represent the new set of schedulable jobs. Step 3. If J STOP, otherwise go to Step 2