== Suppose that we have n tasks to schedule on a computer with a single- core...

 

Transcribed Image Text:

== Suppose that we have n tasks to schedule on a computer with a single- core processor where task i takes t; time units to finish. We would like to run all of the n tasks while minimizing the total waiting time for all tasks. Assuming that the first tasks starts at t=0, the waiting time w for task i is the total time before it is started. For example, if we have three tasks with execution times t = 5, t2 = 3, and t3 = 2 scheduled to run in the order (C1, C2, C3), the waiting times are w = 0, w = 5, W2 and w3 5+3=8. If they are scheduled in the order (C3, C2, C1), the waiting times become ws =0, w = 2, and w = 2+3 = 5. Propose a greedy algorithm that finds the optimal scheduling for the n tasks with the minimum waiting time. Prove the optimality of the algorithm and establish its running time. == Suppose that we have n tasks to schedule on a computer with a single- core processor where task i takes t; time units to finish. We would like to run all of the n tasks while minimizing the total waiting time for all tasks. Assuming that the first tasks starts at t=0, the waiting time w for task i is the total time before it is started. For example, if we have three tasks with execution times t = 5, t2 = 3, and t3 = 2 scheduled to run in the order (C1, C2, C3), the waiting times are w = 0, w = 5, W2 and w3 5+3=8. If they are scheduled in the order (C3, C2, C1), the waiting times become ws =0, w = 2, and w = 2+3 = 5. Propose a greedy algorithm that finds the optimal scheduling for the n tasks with the minimum waiting time. Prove the optimality of the algorithm and establish its running time.

Answer rating: 100% (QA)

To schedule the tasks with minimum waiting time we can use the following greedy algorithm 1 Sort the ... View the full answer