Consider the following scheduling problem: we have two machines, and a set of jobs j1, j2,...

   

Transcribed Image Text:

Consider the following scheduling problem: we have two machines, and a set of jobs j1, j2, j3,. jn that we have to process one at a time. To process a job, we place it on a machine. Each job j; has an associated running time r;. The load on the machine is the sum of the running times of the jobs placed on it. The goal is to minimize the completion time, which is the maximum load over all machines. Suppose we adopt a greedy algorithm: each job j; is put on the machine with the minimum load after the first i- 1 jobs. (Ties can be broken arbitrarily.) Show that this strategy yields a completion time within a factor of 3/2 of the best possible placement of jobs. (Hint: Think of the best possible placement of jobs. Even for the best placement, the completion time is at least as big as the biggest job, and at least as big as half the sum of the jobs. You may want to use both of these facts.) Give an example where a factor of 3/2 is achieved. Suppose now instead of 2 machines we have m machines. What is the performance of the greedy solution, compared to the optimal, as a function of m? Give a family of examples (that is, one for each m if they are very similar, it will be easier to write down!) where the factor separating the optimal and the greedy solutions is as large as you can make it. Consider the following scheduling problem: we have two machines, and a set of jobs j1, j2, j3,. jn that we have to process one at a time. To process a job, we place it on a machine. Each job j; has an associated running time r;. The load on the machine is the sum of the running times of the jobs placed on it. The goal is to minimize the completion time, which is the maximum load over all machines. Suppose we adopt a greedy algorithm: each job j; is put on the machine with the minimum load after the first i- 1 jobs. (Ties can be broken arbitrarily.) Show that this strategy yields a completion time within a factor of 3/2 of the best possible placement of jobs. (Hint: Think of the best possible placement of jobs. Even for the best placement, the completion time is at least as big as the biggest job, and at least as big as half the sum of the jobs. You may want to use both of these facts.) Give an example where a factor of 3/2 is achieved. Suppose now instead of 2 machines we have m machines. What is the performance of the greedy solution, compared to the optimal, as a function of m? Give a family of examples (that is, one for each m if they are very similar, it will be easier to write down!) where the factor separating the optimal and the greedy solutions is as large as you can make it.

Answer rating: 100% (QA)

Step 1 of 7 a In the best case each job has its own machine ... View the full answer