Reference no: EM13812168

Question 1: Describe a simple greedy algorithm that computes a 2-approximation of the optimal schedule. In other words, if T* is the smallest possible makespan achievable for the given set of jobs using k processors, then the schedule produced by your algorithm should have a makespan of at most 2T*. Your algorithm should run in O(kn) time. Prove that the schedule produced by your algorithm has makespan at most 2T*. To do so, you will probably want to use two properties the minimum makespan T* must obviously satisfy:

• T* ≥ 1/k Σ P^k_i=1 t_i. (The processor doing the most amount of work must do at least a 1/k fraction of the total amount of work.)
• T* ≥ max{t₁, t₂,..., t_n}. (The longest job needs to run on some processor P_j, so this processor finishes no earlier than the time it takes to complete this job.)

You should then prove that the schedule produced by your algorithm has makespan at most 1/k Σ^k_i=1 t_i +max{t₁, t₂, ..., t_n}.

Question 2:  Describe a modification of the above greedy algorithm that computes an optimal schedule, that is, one with the smallest possible makespan, provided the given set of jobs satisfies the following condition: Let t₁, t₂,..., t_n once again be the predicted amounts of time it takes to run jobs J₁, J₂,..., J_n, and let t* = min{t₁, t₂, ..., t_n}. You may assume that t* = 1. Then, for all 1 ≤ i ≤ n, t_i is a power of 2. Your algorithm should run in O(n lg n + kn) time. Prove that it produces an optimal schedule.