Suggest a Book

# Minimum makespan problem

Level: unknown

posted Jul 03 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

Minimum makespan scheduling problem : You are given $n$ jobs and $m$ identical machines. You are given processing times (say $t_i$) for the $n$ jobs. Your goal is to find an assignment of the $n$ jobs on these $m$ machines so as to minimize the completion time.

Algorithm : Sort the $n$ jobs by decreasing times. Schedule jobs in this order i.e., assign the next job to the machine that has least total work assigned to it.

• (Easy) Prove that the above algorithm achieves a factor of $(2−1/m)$ approximation.
• (Medium) Prove that the above algorithm achieves a factor of $3/2$ approximation.
• (Not so easy) Show that the above algorithm achieves a factor of $4/3$ approximation.
Source: folklore
delete retag edit

First, prove that it is a $(2-1/m)$-approximation and then that it is a $3/2$-approximation. Proving that it is a $4/3$-approximation is not so easy.

(Jul 28 '12)edit