# Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". 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.

-
–  Daniel Apon Sep 13 '10 at 18:33
I don't think this needed to be made CW... –  Suresh Venkat Sep 14 '10 at 0:01
@Suresh Venkat:How to remove CW? –  Oleksandr Bondarenko Sep 14 '10 at 0:49
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: meta.stackexchange.com/questions/6821/… –  Tsuyoshi Ito Sep 14 '10 at 1:06
Also see the FAQ on when to use the CW tag: meta.cstheory.stackexchange.com/questions/225/… –  Suresh Venkat Sep 14 '10 at 1:21

## 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 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 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.

-
Thanks for finding and summarising these papers! –  András Salamon Sep 18 '10 at 18:36

This web page may have some information of use:

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

-