Proving that the greedy algorithm for job scheduling has a 2 - (1/m) approximation ratio

Question

In the scheduling problem, the input is a sequence $T_1,T_2,...,T_n$ which are the times of $n$ jobs to be executed in m identical machines. A schedule is an assignment of the jobs to machines. The load of each machine is the sum of the times of the jobs assigned to it. The objective is to find a schedule with minimum makespan; the makespan is the maximum load among the machines.

The greedy algorithm for assigning jobs to machines assigns the jobs one-by-one; each job is assigned to a machine which currently has minimum load.

I'm trying to prove that this has a 2 - (1/m) approximation ratio.

I know that $opt(x) >= max(max(T_1,T_2,...,T_n), (1/m) \sum_{i=1}^n{T_i})$

I've proven an approximation ratio of 2, but can't seem to figure out how to prove that it's 2 - (1/m)

Answer 1

Suppose machine $A$ ends up with the maximum load $M$ . Let $i$ be the last job scheduled on machine $A$. Right before $i$ was scheduled, machine $A$ had the smallest load, which was at most the average load at that time. We have, $$\begin{aligned} M &= (M − T_i ) + T_i\\ &\le\frac 1m(\sum_{1\le k\le n}T_k\,-T_i) + T_i\\ &=\frac 1m\sum_{1\le k\le n}T_k + (1-\frac 1m)T_i\\ &\le opt + (1-\frac1m)opt\\ &=(2-\frac1m)opt \end{aligned}$$