Greedy algorithm for job scheduling

Question

Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime.

How to prove that this algorithm has an approximation ratio of 2?

Suppose that once the algorithm is completed, processor 1ドル$ is the busiest and assume task $l$ is the last task assigned to it. Let $s$ be the time that was used on processor 1ドル $ before adding task $i$. The algorithm has therefore found a valuable solution $u_1 = s + t_\ell$.

I'm stuck on how to show that:

• for every 1ドル \leq j \leq k$ we have $s \leq \sum_{i: \alpha(i)=j}t_i$.
• $s \leq 1/k \; \sum_i t_i \leq u^*$ and $t_\ell \leq u^*$ and use these results to limit $u_1$ ($u^*$ is the optimal value). ​

Here is the definition of the Job Scheduling problem

Input: A set of $n$ tasks of length $t_1, t_2, \ldots, t_n \in \mathbb N$ and $k$ processors.

A feasible solution is a function $\alpha\colon \{1, \ldots ,n\} \rightarrow \{1, \ldots k\}$ which assigns each task to a processor.

The usage time $u_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u_j = \sum_{i: \alpha(i)=j}t_i$.

We try to minimize $\max_j u_j$, that is to say the time of use of the most used processor.​

Answer 1

You can find this algorithm analyzed at the very beginning of these lecture notes, or in these lecture notes (which consider a better variant of the algorithm but only analyze your variant), as well as in many other resources.

These are the first two hits when searching for makespan approximation.

• Max N: where did you look? scholar.google.com has Springer.com as first!
• Yuval Filmus: I used google.com.
• Max N: sorry found the anwser, it was google Web search.
• Max N: scholar is better for Whitepapers and research work