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

Question

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.

Answer 1

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 flow 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 2

This web page may have some information of use:

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