<p>Any reference is appreciated.</p>

<p>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.</p>

<p>Chandra Chekuri and Michael Bender studied it under constraint: "precedence constraints between jobs are given in the form of a partial order" at <a href="http://www.cs.sunysb.edu/~bender/pub/jalg-uniformly.ps" rel="nofollow">CB</a>. </p>

<p>I am looking for reference of the problem without precedence constraints. Shmoys, Wein, and Williamson <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=185361&amp;tag=1" rel="nofollow">SWH</a> showed a 2-approximation algorithm. </p>

<p>Is there any other result? </p>

CC BY-SA 3.0
2012-03-28T12:12:17.793Z
Did you ask [Google](http://scholar.google.com/scholar?hl=en&lr=&cites=5077071937633115354&um=1&ie=UTF-8&ei=BwBzT5qLJ4bUsgbLmtjMDQ&sa=X&oi=science_links&ct=sl-citedby&resnum=1&ved=0CDQQzgIwAA)?
Jeffε
CC BY-SA 3.0
2012-03-29T18:15:34.493Z
@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
CC BY-SA 3.0
2012-03-30T14:25:27.637Z
@Peng The PTAS is due to Hochbaum and Shmoys (SICOMP, 1988).
Matthias
CC BY-SA 3.0
2012-04-05T04:43:08.037Z
@Matthias Thank you for your comment. I cannot obtain the paper. Judging from the abstraction, I cannot find the clue.
Peng Zhang
<ds.algorithms><reference-request><approximation-algorithms><scheduling>
minimizing makespan for related machines
Peng Zhang
# minimizing makespan for related machines

(Asked by: username_0 on 2012-03-28)

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](http://www.cs.sunysb.edu/~bender/pub/jalg-uniformly.ps).

I am looking for reference of the problem without precedence constraints. Shmoys, Wein, and Williamson [SWH](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=185361&tag=1) showed a 2-approximation algorithm.

Is there any other result?

**Tags:** ds.algorithms, reference-request, approximation-algorithms, scheduling

> **Comments:**
> **username_1**: Did you ask [Google](http://scholar.google.com/scholar?hl=en&lr=&cites=5077071937633115354&um=1&ie=UTF-8&ei=BwBzT5qLJ4bUsgbLmtjMDQ&sa=X&oi=science_links&ct=sl-citedby&resnum=1&ved=0CDQQzgIwAA)?  
> **username_0**: @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.  
> **username_2**: @Peng The PTAS is due to Hochbaum and Shmoys (SICOMP, 1988).  
> **username_0**: @username_2 Thank you for your comment. I cannot obtain the paper. Judging from the abstraction, I cannot find the clue.  

---

## 0 answers

