Scheduling to minimize average completion time.

Suppose you are given a set S = {a_1, a_2, ..., a_n} of tasks, where task a_1 requires p_i 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 at a time. Let c_i be the completion time of task a_i, that is, the time at which task a_i completes processing. Your goal is to minimize the average completion time, that is, to minimize (1) sigma^n_i = 1 c_i. For example, suppose there are two tasks, a_1 and a_2, with p_1 = 3 and p_2 = 5, and consider the schedule in which a_2 runs first, followed by a_1. Then c_2 = 5, c_1 = 8, and the average completion time is (5 + 8)/2 = 6.5. If task a_1 runs first, however, then c_1 = 3, c_2 = 8, and the average completion time is (3 + 8)/2 = 5.5. a. Give an algorithm that schedules the tasks so as to minimize the average completion time. Each task must run non-preemptively, that is, once task a_i starts, it must run continuously for p_i units of time. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm