Algorithmes d'approximation polynomiale du temps pour la planification des machines: combien de problèmes ouverts subsistent-ils?

En 1999, Petra Schuurman et Gerhard J. Woeginger ont publié l'article "Algorithmes d'approximation du temps polynomiaux pour la planification des machines: dix problèmes ouverts" . Depuis lors, à ma connaissance, des critiques qui concerneraient très exactement la même liste de problèmes ne sont pas apparues. Il serait donc formidable et utile que chacun de nous puisse faire un tel résumé sur certains des dix problèmes ouverts et y contribuer ici.

Minimisation de la durée de vie sur des machines identiques sous contraintes de priorité

Problème ouvert 1. Fournir un résultat inapproximabilité pour P | p r e c | C m a x .$4/3+\delta$$P|prec|C_{max}$

Ici, ce qui me vient à l'esprit est le papier de cette année par Ola Svensson "La dureté conditionnelle de la planification ordonnée contrainte sur les machines identiques". Dans son article, Ola prouve que

"si le problème d'une seule machine est difficile à estimer dans un facteur de alors le problème de machine parallèle considéré, même dans le cas des temps de traitement unitaires, est difficile à estimer dans un facteur de 2 - $2-\epsilon$$2-\zeta$ , où tend vers 0 car ϵ tend vers 0. "$\zeta$$\epsilon$

En 2008, il a été publié le document "Ordonnancement contraint par priorité dans · optimal "décrivant un algorithme pourP|prec,pj=1|Cma$(2−\frac{7}{3p+1})$$P|prec,p_j=1|C_{max}$ . Avec le rapport de performance, mentionné dans le titre Ce améliore algorithme Coffman-Graham avec borne $2-\frac{2}{p}$ , où $p$ est le nombre de machines.

L'article «Algorithmes d'approximation pour la planification des travaux avec des contraintes de priorité de chaîne» par Jansen et Solis-Oba contient PTAS pour et, par conséquent, pour P m | c h a i n s | C m a $Qm|chains|C_{max}$$Pm|chains|C_{max}$ comme cas particulier de l'ancien problème.

Cette année est apparu l'article "Schémas d'approximation pour la planification des travaux avec des contraintes de priorité de chaîne" par Jansen et Solis-Oba (version journal de la précédente), qui concerne PTAS pour avec un nombre fixe d'emplois dans chaque chaîne et P | p r e c | C m a x avec un nombre constant de tâches dans le composant connecté de chaque commande.$P|chains|C_{max}$$P|prec|C_{max}$

Minimisation de la durée de vie sur des machines uniformes soumises à des contraintes de priorité

L'article de 2003 de l'année «Algorithmes d'approximation pour la planification des travaux avec des contraintes de précédence de chaîne» par Jansen et Solis-Oba contient PTAS pour $Qm|chains|C_{max}$ .

Minimisation du Makespan sous contraintes de priorité avec retards de communication

Minimisation de la durée de vie sur des machines indépendantes

Minimisation du Makespan dans les magasins ouverts

Minimisation de la durée de vie dans les magasins de flux

Dans l'article de Nagarajan et Sviridenko de 2008 "Limites serrées pour la planification des ateliers de flux de permutation", nous pouvons trouver la limite supérieure du rapport entre la durée optimale et la durée du meilleur calendrier de permutation. Cette borne est le rapport d'approximation d'un algorithme proposé, et c'est le meilleur possible parmi les algorithmes basés sur les bornes inférieures triviales, jusqu'à$2\sqrt{2}$Facteur . Soit dit en passant, les algorithmes proposés sont actuellement ceux qui présentent les meilleurs rapports d'approximation.

Minimisation du Makespan dans les ateliers d'emploi

$J||C_{max}$$m$$\mu$$5/4+\delta$$J||C_{max}$$J||C_{max}$$m$ de machines à infity.

$J2||C_{max}$$\mu$$\ne$ NP.

$J||C_{max}$$O((\log lb)^{1-\epsilon})$$NP\subseteq ZTIME(2^{\log n^{O(1/\epsilon)}})$$J2||C_{max}$$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.

This web page may have some information of use:

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