Minimum makespan problem

posted Jul 03 '12

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

updated Jul 28 '12

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.