We consider the following scheduling problem: INPUT: A collection of jobs J1, ··· , Jn. The size of job Ji is xi, which is a non-negative integer. An integer m. OUTPUT: A nonpreemptive feasible...

We consider the following scheduling problem: INPUT: A collection of jobs J1, ··· , Jn. The size of job Ji is xi, which is a non-negative integer. An integer m. OUTPUT: A nonpreemptive feasible schedule for these jobs on m processor that minimizes the total n completion time Pn i=1 Ci . A schedule specifies for each unit time interval and for each processor, the unique job that that is run during that time interval on that processor. In a feasible schedule, every job Ji has to be run for exactly xi time units after time 0. In a nonpreemptive schedule, once a job starts running on a particular processor, it has to be run to completion on that particular processor. The completion time Ci for job Ji is the earliest time when Ji has been run for xi time units. So for example if m = 2 jobs of size 1, 4, 3 are run in that order on the first processor, and jobs of size 7, 10 are run on the second processor in that order, then the total completion time would be 1 + 5 + 8 + 7 + 17 = 38. Give a greedy algorithm for this problem and prove that it is correct.