Algorithmen zur Polynomialzeitnäherung für die Maschinenplanung: Wie viele offene Probleme sind noch zu lösen?

22

1999 veröffentlichten Petra Schuurman und Gerhard J. Woeginger die Arbeit "Polynomial Time Approximation Algorithms for Machine Scheduling: Ten Open Problems" . Seitdem sind meines Wissens nach keine Bewertungen erschienen, die genau dieselbe Liste von Problemen betreffen würden. Daher wäre es großartig und nützlich, wenn jeder von uns eine solche Zusammenfassung zu einigen der zehn offenen Probleme erstellen und hier beitragen könnte.

Dai Le
quelle
Ich glaube nicht, dass dies CW gemacht werden musste ...
Suresh Venkat
@Suresh Venkat: CW entfernen
Oleksandr Bondarenko
Leider gibt es keine Möglichkeit, eine Community-Wiki-Frage in eine Nicht-CW-Frage umzuwandeln. Das Hinzufügen dieser Funktion zur Stack Exchange-Engine ist erforderlich unter
Tsuyoshi Ito
Lesen Sie
Suresh Venkat

Antworten:

16

Makespan-Minimierung auf identischen Maschinen unter Vorrangbedingungen

Offenes Problem 1. Geben Sie ein 4/3 Unannäherungsergebnis für .4/3+δP|prec|Cmax

Hier ist zunächst das diesjährige Papier von Ola Svensson "Bedingte Härte der Präzedenzbedingten Zeitplanung auf identischen Maschinen" zu nennen. In seiner Arbeit beweist Ola das

"Wenn das Einzelmaschinenproblem innerhalb eines Faktors von schwer zu approximieren ist, dann ist das betrachtete Parallelmaschinenproblem, selbst im Fall von Verarbeitungszeiten in Einheiten, innerhalb eines Faktors von schwer zu approximieren , wobei tendiert zu 0, da zu 0 tendiert. "2ϵ2ζζϵ

Im Jahr 2008 wurde die Arbeit "Precedence Constrained Scheduling in · optimal" veröffentlicht, die einen Algorithmus für mit dem Leistungsverhältnis beschreibt. im Titel erwähnt. Dies verbessert den Coffman-Graham-Algorithmus mit gebundenem , wobei die Anzahl der Maschinen ist.(273p+1)P|prec,pj=1|Cmax22pp

Die Arbeit "Approximationsalgorithmen für die Planung von Jobs mit Kettenprioritätsbeschränkungen" von Jansen und Solis-Oba enthält PTAS für und folglich für als Sonderfall des früheren Problems.Qm|chains|CmaxPm|chains|Cmax

In diesem Jahr erschien der Artikel "Approximationsschemata zum Planen von Jobs mit Kettenprioritätsbeschränkungen" von Jansen und Solis-Oba (Journalversion der vorherigen), der PTAS für ketten mit einer festen Anzahl von Jobs in jeder Kette und mit einer konstanten Anzahl von Jobs in der verbundenen Komponente jedes Auftrags.P|chains|CmaxP|prec|Cmax

Makespan-Minimierung auf einheitlichen Maschinen unter Vorrangbedingungen

Die 2003 erschienene Arbeit "Approximationsalgorithmen zur Planung von Jobs mit Kettenprioritätsbeschränkungen" von Jansen und Solis-Oba enthält PTAS für .Qm|chains|Cmax

Makespan-Minimierung unter Prioritätseinschränkungen mit Kommunikationsverzögerungen

Makespan-Minimierung auf unabhängigen Maschinen

Makespan-Minimierung in offenen Läden

Makespan-Minimierung in Flow-Shops

In der Veröffentlichung von Nagarajan und Sviridenko aus dem Jahr 2008 "Enge Grenzen für die Planung von Permutationsabläufen" können wir die Obergrenze für das Verhältnis zwischen optimaler Makespan und der Makespan des besten Permutationsplans finden. Diese Grenze ist das Näherungsverhältnis eines vorgeschlagenen Algorithmus, und es ist das bestmögliche unter den Algorithmen, die auf den trivialen unteren Grenzen basieren, bis zu Faktor. Übrigens sind die vorgeschlagenen Algorithmen derzeit diejenigen mit den besten Approximationsverhältnissen.22

Makespan-Minimierung in Job-Shops

Offenes Problem 7. Entscheide, ob es für einen Algorithmus zur Polynomzeitnäherung gibt, dessen Leistung im ungünstigsten Fall unabhängig von der Anzahl der Maschinen und / oder der maximalen Anzahl der Operationen ist. Geben Sie für 5/4 Unannäherungsergebnis an . Geben Sie ein Unangemessenheitsergebnis für dessen Wert mit der Anzahl der Maschinen bis zur Unendlichkeit wächst.J||Cmaxmμ5/4+δJ||CmaxJ||Cmaxm

Entwerfen Sie einen PTAS für für den Fall, dass Teil der Eingabe ist. oder die Existenz eines solchen PTAS unter P NP widerlegen .J2||Cmaxμ

Die Dissertation von Svensson "Approximierbarkeit einiger klassischer Graph- und Scheduling-Probleme" enthält Ergebnisse, die zeigen, dass nicht innerhalb von vorausgesetzt, und dass kein PTAS hat, außer .J||CmaxO((loglb)1ϵ)NPZTIME(2lognO(1/ϵ))J2||CmaxNPDTIME(nO(logn))

Gesamtdauer der Auftragserfüllung ohne Vorrang

Gesamtdauer der Auftragserfüllung unter Vorrangbedingungen

Offenes Problem 9. Man beweise, dass und keine polynomiellen mit Leistungsgarantie sei denn, P = NP.1|prec|Cj1|prec|wjCj2ϵ

Im "Optimal Long Code Test mit einem freien Bit" haben Bansal und Khot dies bewiesen, unter der Annahme einer neuen Variante der einzigartigen Spielehypothese.

Durchlaufzeitkriterien

Offenes Problem 10. Entwerfen Sie polynomiale mit konstanten Leistungsgarantien für und für .1|pmtn;rj|wjFjP|pmtn;rj|Fj

In "Weighted Flow Time lässt keine -kompetitiven Algorithmen zu" haben Bansal und Chan bewiesen, dass "keine -kompetitiven Algorithmen zulässt". Interessanterweise zitieren die Autoren das Papier von Schuurman und Woeginger nicht.O(1)1|pmtn;rj|wjFjO(1)

In "Minimierung der durchschnittlichen Fließzeit: Ober- und Untergrenze" haben Garg und Kumar eine Untergrenze von für das Näherungsverhältnis für . Später wurde diese Bindung von Garg, Kumar und Muralidhara in in "Minimizing Total Flow-Time: The Unrelated Case" verbessert.P| pmtn; rj| FjΩ(logPΩ(logPloglogP)P|pmtn;rj|FjΩ(logPloglogP)

Oleksandr Bondarenko
quelle