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?

  • $\begingroup$ Did you ask Google? $\endgroup$ – Jeffε Mar 28 '12 at 12:12
  • $\begingroup$ @JɛffE 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. $\endgroup$ – Peng Zhang Mar 29 '12 at 18:15
  • 1
    $\begingroup$ @Peng The PTAS is due to Hochbaum and Shmoys (SICOMP, 1988). $\endgroup$ – Matthias Mar 30 '12 at 14:25
  • $\begingroup$ @Matthias Thank you for your comment. I cannot obtain the paper. Judging from the abstraction, I cannot find the clue. $\endgroup$ – Peng Zhang Apr 5 '12 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.