# minimizing makespan for related machines

Any reference is appreciated.

There are $n$ jobs and $m$ machines, machines has speeds and jobs have processing times. It takes $p_j/s_i$ units of time for machine $i$ with speed $s_i$ to process job $j$ with processing requirement $p_j$. The objective is to find a non-preemptive schedule to minimize the makespan of the schedule.

Chandra Chekuri and Michael Bender studied it under constraint: "precedence constraints between jobs are given in the form of a partial order" at CB.

I am looking for reference of the problem without precedence constraints. Shmoys, Wein, and Williamson SWH showed a 2-approximation algorithm.

Is there any other result?

• Did you ask Google? – Jeffε Mar 28 '12 at 12:12
• @JɛﬀE Yes, and the two links in the question are the answers I got. One of my friends told me there is a PTAS. However, he forgot the name of that paper. I am sorry for late response, because the web connection is not good. I cannot visit stackexchange during the day. Weird. – Peng Zhang Mar 29 '12 at 18:15
• @Peng The PTAS is due to Hochbaum and Shmoys (SICOMP, 1988). – Matthias Mar 30 '12 at 14:25
• @Matthias Thank you for your comment. I cannot obtain the paper. Judging from the abstraction, I cannot find the clue. – Peng Zhang Apr 5 '12 at 4:43