Scheduling to minimize average completion time. Suppose you are given a set S =

Question

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/n) 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.

Explanation / Answer

Algorithm:

Run tasks in shortest possible order of their processing time

Let's suppose {p1, p2, p3, p4, ..,pn} is the processing time. so if we run the task in this order only then

Average completion time would be (p1 + (p1 + p2) + (p1 + p2 + p3).....)

so p1 would be part of each task completion time. similarly p2 would be part of each tasks completion time except first task. so in order to minimize this summation we need to minimize p1, p2, p3 ...pn.

Therefore if we sort the task in increasing order of their procession time we would get minimum average completion time.

Steps:

1> Sort the tasks based on processing time in increasing order

2> Pick each task from sorted array and execute that task

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.