Consider the following scheduling problem: we have two machines, and a set of jobs that we have to process one at a time. To process a job, we place it on a machine. Each job has an associated running time . 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 is put on the machine with the minimum load after the first 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 machines. What is the performance of the greedy solution, compared to the optimal, as a function of ? Give a family of examples (that is, one for each , 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.

1, 2, 3, ... ]n 1, 2, 3, ... ]n