Suppose we have n jobs where job J; requires time t and has priority pi. Our problem is to design a schedule of jobs given by i, 12, ..., in to minimize the weighted sum of the completion times, that is, to minimize: n Pij Cij j=1 where the completion time C, of job Ji, is: tik k=1 For instance, suppose there are two jobs. The first job requires time t = 3 and has priority P = 2. The second job requires time t = 1 and has priority p2 = 10. If job 1 is done first then the weighted sum of the completion times is (2 3) + (10 4) = 46. If job 2 is done first then the weighted sum of the completion times is (10 1) + (2 4) = 18. Clearly, the second schedule (i = 2, 12 = 1) is better. 1. (2 marks) State a greedy choice to minimize the weighted sum of the completion times. 2. (5 marks) Prove that your schedule is optimal by swapping jobs which do not satisfy the greedy choice with those that do, and showing that the resultant schedule is no worse.