Exercise 4.9. Consider the following scheduling problem. Given are 3 machines and n jobs, each of which needs to be processed on one of the three machines. Each machine can process at most one job at a time. Processing job j takes pj time units, independent of the machine on which it is processed. The goal is to assign the jobs to the three machines in such a way that the maximum load of the three machines is minimized. That is, let Si denote the set of jobs assigned to machine i(i=1,2,3), the objective is to minimize max{jS1pj,jS2pj,jS3pj}. You may assume that pj is integral (j=1,,n). For example, consider an instance with 7 jobs, p1=p2=5,p3=p4=4 and p5=p6=p7=3. Then the optimal value is 9 which is obtained by assigning jobs 1 and 3 to one machine, jobs 2 and 4 to a second machine and the final machine processes jobs 5,6 and 7 . Hint: Try to determine all possible machine loads for machines 1 and 2 for a certain set of jobs. What are the corresponding machine loads for machine 3? How do you determine the optimal solution? a. Describe a dynamic programming algorithm that finds the optimal solution value (so your algorithm does not need to give the optimal assignment of jobs to the machines). Give a good description in words of the function(s) that you want to compute. Show how to initialize them, how to recursively compute their values, and where to find the optimal solution value. b. Analyze the running time of your algorithm. Is this bounded by a polynomial in the size of the input