Suppose you are given a set S = {a₁, a₂, . . . ,a_n} of tasks, where task a_i 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 task 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/n)Σⁿ_i=1c_i. For example, suppose there are two tasks, a₁ and a₂, with p₁ = 3 and p₂ = 5, and consider the schedule in which a₂ runs first, followed by a₁. Then c₂ = 5, c₁ = 8, and the average completion time is (5 + 8)/2 = 6.5. If task a1 runs first, however, then c₁ = 3, c₂ = 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 pi units of time. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.

b. Suppose now that the tasks are not all available at once. That is, each task cannot start until its release time r_i. Suppose also that we allow preemption, so that a task can be suspended and restarted at a later time. For example, a task a_i with processing time p_i = 6 and release time r_i = 1 might start running at time 1 and be preempted at time 4. It might then resume at time 10 but be preempted at time 11, and it might finally resume at time 13 and complete at time 15. Task a_i has run for a total of 6 time units, but its running time has been divided into three pieces. In this scenario, a_i 's completion time is 15. Give an algorithm that schedules the tasks so as to minimize the average completion time in this new scenario. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.