Greedy Algorithm

16-2 Scheduling to minimize average completion time Suppose you are given a set S {a1-a2 quires p, units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai, that is, the time at which task a, com- pletes processing. Your goal is to minimize the average completion time, that is, to minimize (1) =1 ci. For example, suppose there are two tasks, ai and a2. with P1 3 and P2 = 5, and consider the schedule in which a2 runs first, followed by al. Then c2 5, cl 8, and the average completion time is (5 8)/2 6.5 If task al runs first, however, then c1 3, c2 = 8, and the average completion time is (3 + 8)/2 = 5.5 al of tasks, where task ai re- a. Give an algorithm that schedules the tasks so as to minimize the average com pletion time. Each task must run non-preemptively, that is, once task a, starts, it must run continuously for p units of time. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm