Consider the following job scheduling problem. We are given all at once n jobs with positive lengths t1,t2,,tn and positive weights w1,,wn. We can schedule only one job at a time and once we start a job we must run it to completion. A schedule for a set of jobs is then the starting time for each job s1,s2,,sn. Find an efficient algorithm to schedule the jobs to minimize the total weighted turnaround time, where the turnaround time for a job is the difference between the time the job arrived and when it finished. Since all jobs arrive at the same time t=0, the turnaround time for job i simplifies to and so the problem is to schedule the jobs to minimize . Prove that your algorithm is correct (if you use a greedy algorithm you need only prove that the solution resulting from your greedy choice is always optimal, not that your algorithm correctly finds that greedy solution).

Transcribed image text