<p>This web page may have some information of use:</p>

<p><a href="http://www.mathematik.uni-osnabrueck.de/research/OR/class/" rel="nofollow">http://www.mathematik.uni-osnabrueck.de/research/OR/class/</a></p>

CC BY-SA 2.5
2010-09-15T02:05:38.173Z
2010-09-15T02:05:38.173Z
Joseph Malkevitch
<h2>Makespan minimization on identical machines under precedence constraints</h2>

<blockquote>
  <p>Open problem 1. Provide a $4/3+\delta$ inapproximability result for $P|prec|C_{max}$.</p>
</blockquote>

<p>Here what comes first to mind is the paper of this year by Ola Svensson "Conditional Hardness of Precedence Constrained Scheduling on Identical Machines". In his paper Ola proves that </p>

<blockquote>
  <p>"if the single machine problem is hard to approximate within a factor of $2-\epsilon$ then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of $2-\zeta$, where $\zeta$ tends to 0 as $\epsilon$ tends to 0."</p>
</blockquote>

<p>In 2008 there was published the paper "Precedence constrained scheduling in $(2−\frac{7}{3p+1})$ · optimal" describing an algorithm for $P|prec,p_j=1|C_{max}$ with the performance ratio, mentioned in its title. This improves upon Coffman-Graham algorithm with bound $2-\frac{2}{p}$, where $p$ is the number of machines.</p>

<p>The paper "Approximation algorithms for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba contains PTAS for $Qm|chains|C_{max}$, and, as a consequence, for $Pm|chains|C_{max}$ as a special case of the former problem.</p>

<p>This year there was appeared the article "Approximation schemes for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba (journal version of the previous one), which concerns PTAS for $P|chains|C_{max}$ with a fixed number of jobs in every chain and $P|prec|C_{max}$ with a constant number of jobs in every order's connected component.</p>

<h2>Makespan minimization on uniform machines under precedence constraints</h2>

<p>The 2003 year's paper "Approximation algorithms for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba contains PTAS for $Qm|chains|C_{max}$.</p>

<h2>Makespan minimization under precedence constraints with communication delays</h2>

<h2>Makespan minimization on unrelated machines</h2>

<h2>Makespan minimization in open shops</h2>

<h2>Makespan minimization in flow shops</h2>

<p>In the paper of Nagarajan and Sviridenko from 2008 "Tight Bounds for Permutation Flow Shop Scheduling" we can find the upper bound on the ratio between optimal makespan and the makespan of the best permutation schedule. This bound is the approximation ratio of an algorithm proposed, and it is the best possible among algorithms based on the trivial lower bounds, up to $2\sqrt{2}$ factor. Incidentally, the algorithms proposed are currently the ones with the best approximation ratios.</p>

<h2>Makespan minimization in job shops</h2>

<blockquote>
  <p>Open problem 7. Decide whether there exists a polynomial time approximation algorithm
  for $J||C_{max}$ whose worst-case performance is independent of the number $m$ of machines and/or independent of the maximum number $\mu$ of operations. Provide a $5/4+\delta$ inapproximability result for $J||C_{max}$. Provide an inapproximability result for $J||C_{max}$ whose value grows with the number $m$ of machines to infity.</p>
  
  <p>Design a PTAS for $J2||C_{max}$ for the case where $\mu$ is part of the input; or disprove the existence of such a PTAS under P$\ne$NP.</p>
</blockquote>

<p>Dissertation by Svensson "Approximability of Some Classical Graph and Scheduling Problems" contains results showing that $J||C_{max}$ cannot be approximated within $O((\log lb)^{1-\epsilon})$ assuming $NP\subseteq ZTIME(2^{\log n^{O(1/\epsilon)}})$ and that $J2||C_{max}$ has no PTAS unless $NP\subseteq DTIME(n^{O(\log n)})$.</p>

<h2>Total job completion time without precedence constraints</h2>

<h2>Total job completion time under precedence constraints</h2>

<blockquote>
  <p>Open problem 9. Prove that $1|prec|\sum C_j$ and $1|prec|\sum w_jC_j$ do not have polynomial time approximation algorithms with performance guarantee $2−\epsilon$ unless P=NP.</p>
</blockquote>

<p>In "Optimal long code test with one free bit" Bansal and Khot proved that it is so, but assuming a new variant of the unique games conjecture.</p>

<h2>Flow time criteria</h2>

<blockquote>
  <p>Open problem 10. Design polynomial time approximation algorithms with constant performance guarantees for $1|pmtn;r_j|\sum w_jF_j$ and for $P|pmtn;r_j|\sum F_j$.</p>
</blockquote>

<p>In "Weighted ﬂow time does not admit $O(1)$-competitive algorithms" Bansal and Chan proved that $1|pmtn;r_j|\sum w_jF_j$ "does not admit $O(1)$-competitive algorithms". Interestingly, the authors don't cite the paper of Schuurman and Woeginger.</p>

<p>In "Minimizing Average Flow-time: Upper and Lower Bounds" Garg and Kumar proved a lower bound $\Omega(\sqrt{\frac{\log P}{\log\log P}})$ on the approximation ratio for $P|pmtn;r_j|\sum F_j$. Later this bound was improved to $\Omega(\frac{\log P}{\log\log P})$ in "Minimizing Total Flow-Time: The Unrelated Case" by Garg, Kumar and Muralidhara.</p>

CC BY-SA 2.5
2010-09-13T22:44:37.733Z
2011-01-20T13:54:52.763Z
2011-01-20T13:54:52.763Z
Oleksandr Bondarenko
<p>In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper <a href="http://www.win.tue.nl/~gwoegi/papers/ten.pdf">"Polynomial time approximation algorithms for machine scheduling: Ten open problems"</a>. Since then, to the best of my knowledge, reviews which would concern very the same list of problems haven't appeared. Thus it would be great and useful if each of us could make such summary on some of the ten open problems and contribute it here.</p>

CC BY-SA 2.5
2010-09-13T18:33:18.973Z
PDF: [Polynomial time approximation algorithms for machine scheduling: Ten open problems](http://www.win.tue.nl/~gwoegi/papers/ten.pdf)
Daniel Apon
CC BY-SA 2.5
2010-09-14T00:01:46.063Z
I don't think this needed to be made CW...
Suresh Venkat
CC BY-SA 2.5
2010-09-14T00:49:26.847Z
@Suresh Venkat:How to remove CW?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-09-14T01:06:57.677Z
Unfortunately, there is no way to turn a community wiki question into a non-CW question.  Adding this feature to the Stack Exchange engine is requested at: http://meta.stackexchange.com/questions/6821/ability-to-undo-the-community-wiki
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-14T01:21:31.453Z
Also see the FAQ on when to use the CW tag: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/239#239
Suresh Venkat
<ds.algorithms><approximation-algorithms><open-problem><approximation-hardness><scheduling>
Polynomial time approximation algorithms for machine scheduling: how many open problems are left?
Oleksandr Bondarenko
# Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

(Asked by: username_0 on 2010-09-13)

In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper ["Polynomial time approximation algorithms for machine scheduling: Ten open problems"](http://www.win.tue.nl/~gwoegi/papers/ten.pdf). Since then, to the best of my knowledge, reviews which would concern very the same list of problems haven't appeared. Thus it would be great and useful if each of us could make such summary on some of the ten open problems and contribute it here.

**Tags:** ds.algorithms, approximation-algorithms, open-problem, approximation-hardness, scheduling

> **Comments:**
> **username_1**: PDF: [Polynomial time approximation algorithms for machine scheduling: Ten open problems](http://www.win.tue.nl/~gwoegi/papers/ten.pdf)  
> **username_2**: I don't think this needed to be made CW...  
> **username_0**: @username_2:How to remove CW?  
> **username_3**: Unfortunately, there is no way to turn a community wiki question into a non-CW question.  Adding this feature to the Stack Exchange engine is requested at: http://meta.stackexchange.com/questions/6821/ability-to-undo-the-community-wiki  
> **username_2**: Also see the FAQ on when to use the CW tag: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/239#239  

---

## 2 answers

### Answer by username_0 on 2010-09-13. Score: 17 | Accepted answer

## Makespan minimization on identical machines under precedence constraints

> Open problem 1. Provide a $4/3+\delta$ inapproximability result for $P|prec|C\_{max}$.

Here what comes first to mind is the paper of this year by Ola Svensson "Conditional Hardness of Precedence Constrained Scheduling on Identical Machines". In his paper Ola proves that

> "if the single machine problem is hard to approximate within a factor of $2-\epsilon$ then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of $2-\zeta$, where $\zeta$ tends to 0 as $\epsilon$ tends to 0."

In 2008 there was published the paper "Precedence constrained scheduling in $(2−\frac{7}{3p+1})$ · optimal" describing an algorithm for $P|prec,p\_j=1|C\_{max}$ with the performance ratio, mentioned in its title. This improves upon Coffman-Graham algorithm with bound $2-\frac{2}{p}$, where $p$ is the number of machines.

The paper "Approximation algorithms for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba contains PTAS for $Qm|chains|C\_{max}$, and, as a consequence, for $Pm|chains|C\_{max}$ as a special case of the former problem.

This year there was appeared the article "Approximation schemes for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba (journal version of the previous one), which concerns PTAS for $P|chains|C\_{max}$ with a fixed number of jobs in every chain and $P|prec|C\_{max}$ with a constant number of jobs in every order's connected component.

## Makespan minimization on uniform machines under precedence constraints

The 2003 year's paper "Approximation algorithms for scheduling jobs with chain precedence constraints" by Jansen and Solis-Oba contains PTAS for $Qm|chains|C\_{max}$.

## Makespan minimization under precedence constraints with communication delays

## Makespan minimization on unrelated machines

## Makespan minimization in open shops

## Makespan minimization in flow shops

In the paper of Nagarajan and Sviridenko from 2008 "Tight Bounds for Permutation Flow Shop Scheduling" we can find the upper bound on the ratio between optimal makespan and the makespan of the best permutation schedule. This bound is the approximation ratio of an algorithm proposed, and it is the best possible among algorithms based on the trivial lower bounds, up to $2\sqrt{2}$ factor. Incidentally, the algorithms proposed are currently the ones with the best approximation ratios.

## Makespan minimization in job shops

> Open problem 7. Decide whether there exists a polynomial time approximation algorithm
> for $J||C\_{max}$ whose worst-case performance is independent of the number $m$ of machines and/or independent of the maximum number $\mu$ of operations. Provide a $5/4+\delta$ inapproximability result for $J||C\_{max}$. Provide an inapproximability result for $J||C\_{max}$ whose value grows with the number $m$ of machines to infity.
>
> Design a PTAS for $J2||C\_{max}$ for the case where $\mu$ is part of the input; or disprove the existence of such a PTAS under P$\ne$NP.

Dissertation by Svensson "Approximability of Some Classical Graph and Scheduling Problems" contains results showing that $J||C\_{max}$ cannot be approximated within $O((\log lb)^{1-\epsilon})$ assuming $NP\subseteq ZTIME(2^{\log n^{O(1/\epsilon)}})$ and that $J2||C\_{max}$ has no PTAS unless $NP\subseteq DTIME(n^{O(\log n)})$.

## Total job completion time without precedence constraints

## Total job completion time under precedence constraints

> Open problem 9. Prove that $1|prec|\sum C\_j$ and $1|prec|\sum w\_jC\_j$ do not have polynomial time approximation algorithms with performance guarantee $2−\epsilon$ unless P=NP.

In "Optimal long code test with one free bit" Bansal and Khot proved that it is so, but assuming a new variant of the unique games conjecture.

## Flow time criteria

> Open problem 10. Design polynomial time approximation algorithms with constant performance guarantees for $1|pmtn;r\_j|\sum w\_jF\_j$ and for $P|pmtn;r\_j|\sum F\_j$.

In "Weighted ﬂow time does not admit $O(1)$-competitive algorithms" Bansal and Chan proved that $1|pmtn;r\_j|\sum w\_jF\_j$ "does not admit $O(1)$-competitive algorithms". Interestingly, the authors don't cite the paper of Schuurman and Woeginger.

In "Minimizing Average Flow-time: Upper and Lower Bounds" Garg and Kumar proved a lower bound $\Omega(\sqrt{\frac{\log P}{\log\log P}})$ on the approximation ratio for $P|pmtn;r\_j|\sum F\_j$. Later this bound was improved to $\Omega(\frac{\log P}{\log\log P})$ in "Minimizing Total Flow-Time: The Unrelated Case" by Garg, Kumar and Muralidhara.


---

### Answer by username_4 on 2010-09-15. Score: 1

This web page may have some information of use:

<http://www.mathematik.uni-osnabrueck.de/research/OR/class/>


---

