Consider the following scheduling problem. We are given a set of n tasks; task i has...

Transcribed Image Text:

Consider the following scheduling problem. We are given a set of n tasks; task i has a processing time pi representing the number of units of time it takes to complete. There is one resource, which can process only one task at a time; tasks cannot be interrupted once they begin. Let c; be the completion time of task i, the time when task i completes processing. Your goal is to schedule the tasks (i.e., determine what order to process them) so as to minimize the average completion time, 1 Ci. 1 n = (a) Suppose there are two tasks, with pi 5 and p2 = 9. There are two possible schedules: (i) the schedule that completes task 1 first, followed by task 2; and (ii) the schedule that completes task 2 first, followed by task 1. For each of these two schedules, compute the average completion time of tasks. (b) Describe a greedy algorithm that schedules the tasks so as to minimize the average completion time. Consider the following scheduling problem. We are given a set of n tasks; task i has a processing time pi representing the number of units of time it takes to complete. There is one resource, which can process only one task at a time; tasks cannot be interrupted once they begin. Let c; be the completion time of task i, the time when task i completes processing. Your goal is to schedule the tasks (i.e., determine what order to process them) so as to minimize the average completion time, 1 Ci. 1 n = (a) Suppose there are two tasks, with pi 5 and p2 = 9. There are two possible schedules: (i) the schedule that completes task 1 first, followed by task 2; and (ii) the schedule that completes task 2 first, followed by task 1. For each of these two schedules, compute the average completion time of tasks. (b) Describe a greedy algorithm that schedules the tasks so as to minimize the average completion time.

Answer rating: 100% (QA)

a Schedule 1 Task 1 first followed by Task 2 C1 P1 P2 5 9 14 Schedule 2 Task 2 first followed by Tas... View the full answer