Scheduling, Greedy-Algorithmus

Question

Dies ist eine Variation des beliebten El Goog-Problems.

---

Betrachten Sie das folgende Zeitplanproblem: Es gibt n Jobs, i = 1..n. Es gibt 1 Supercomputer und unbegrenzte PCs. Jeder Auftrag muss zuerst vom Supercomputer vorverarbeitet und dann auf einem PC verarbeitet werden. Die Zeit, die für den Job i auf dem Supercomputer benötigt wird, ist si, i = 1..n. Für PCs ist es Pi, i = 1..n. Die PCs können parallel arbeiten, aber der Supercomputer kann jeweils nur einen Job bearbeiten. Ein Zeitplan S wird erstellt, gemäß dem der Supercomputer die Jobs verarbeitet. Die Beendigungszeit Ti (S) im Zeitplan S ist durch die Taktzeit gegeben, zu der der Job auf dem PC endet. Wir wollen einen Plan finden, der Maxi [Ti (s)] minimiert (zu lesen als: wir müssen einen Plan finden, der die höchste Endzeit minimiert). Der folgende Greedy-Algorithmus wird vorgeschlagen: Ordnen Sie die Jobs in absteigender Reihenfolge der Verarbeitungszeiten auf den PCs an. Die Komplexität dieses Algorithmus ist O (nlogn). Stellen Sie entweder sicher, dass dieser Algorithmus eine optimale Lösung liefert oder ein Gegenbeispiel liefert, um zu zeigen, dass dies nicht der Fall ist.

Meine Lösung (nicht sicher, ob das korrekt ist): Ich glaube nicht, dass es wichtig ist, wie wir die Aufträge bestellen. Die höchste Zielzeit ist immer noch dieselbe. Betrachten Sie dieses Beispiel der Verarbeitungszeiten auf den PCs für eine Liste von Jobs: < 5, 7, 17, 8, 10>. Dies ergibt Endzeiten wie < 5, 12, 29, 37, 47>. Gemäß dem Algorithmus werden wir die Liste als < 17, 10, 8, 7, 5> sortieren und die Endzeiten von < 17, 27, 35, 42, 47> ergeben. Während also der Greedy-Algorithmus eine optimale Reihenfolge bietet, braucht es dazu noch Zeit, während das einfache Durchlaufen der Liste der Jobs das gleiche Ergebnis liefert.

Wenn jemand denkt, dass der Greedy-Algorithmus besser funktioniert oder dass mein Ansatz fehlerhaft ist, würde ich Ihre Gedanken begrüßen. Danke!

---

aktualisieren: Ich denke, ich die Antwort haben. Die Zeit, die der Supercomputer benötigt, spielt keine Rolle. Der Schlüssel hier ist, dass die PCs in parallel laufen. Aus dem anfänglichen Beispiel von pi = < 5, 7, 17, 8, 10>, addieren wir si = < 8, 5, 1, 12, 9>. Jetzt hätten wir in der unsortierten Standardreihenfolge Bearbeitungszeiten von < 13, 20, (8 + 5 + 1 + 17 =) 31, 34, 45>. Also 45 ist die Zeit der Fertigstellung. Nehmen Sie eine sortierte Reihenfolge an, in der Pi abnimmt. Die Ausgabe ist: < 18, 20, 30, 34, 40>. [Sortierte Eingabe: pi = < 17, 10, 8, 7, 5>, si = < 1, 9, 12, 5, 8>].

Hier ist ein Beispiel, das wahrscheinlich die ganze Sache aufräumt: si = < 17, 10>, pi = < 10, 17>. Die Ausgabe im unsortierten Fall (die zufällig auch in absteigender Reihenfolge von si sortiert ist) lautet < 27, 44>. Sortiert basierend auf Pi, ist die Eingabe: si = < 10, 17>, pi = < 17, 10>. Ausgabe ist < 27, 37>. Da die PCs parallel laufen, möchten Sie zuletzt den kürzesten Job senden.

Answer 1

für eine begrenzte Anzahl von PCs:

w.l.o.g Angenommen es kein Super-Computer ist, wird Ihr Problem zu Minmum Makespan Scheduling Problem umgewandelt werden (oder ppt), die NP-Hard ist. Ihr aktueller Algorithmus funktioniert also nicht oder P = NP.

Aber gierige Algorithmen sind nützlich für Approximationen, Auch können Sie Bin Packing zu diesem Problem konvertieren und durch eine feste Menge an Fehler für die Approximation gute Ergebnisse finden, aber Laufzeit wird nicht gut sein polynomial (z. B. n^10).

P. S: Sie können einfach annehmen, dass es kein Super-Computer ist, denn dies ist die Instanz, so dass Max (s _i) < Min (P _i) annehmen.

P.S2: Ich habe anfangs keine unbegrenzte Anzahl von PCs gesehen, also schrieb ich das, ich denke über eine unbegrenzte Anzahl von PCs nach.

UnLimitiert Fall:

Ihr aktueller Algorithmus falsch ist, übernehmen diese Bedingungen:

For PCs: <5, 7, 17, 8, 10> 
For super computer: <1000,800,500,600,700). 

Ihre aktuelle Lösung wird nicht.

Answer 2

S={a1,a2,...,an} of n Einheit-Zeit-Aufgabe. Eine Einheit-Zeit-Aufgabe erfordert genau 1 Zeiteinheit zum Abschluss Deadlines d1,d2,...,dn, 1<=di<=n Strafen w1,w2,...,wn. Eine Strafe wi tritt auf, wenn die Aufgabe ai nicht durch die Zeit di abgeschlossen ist, und keine Strafe, wenn die Aufgabe zum Stichtag endet.

Das Problem ist, einen Zeitplan für S zu finden, die die Gesamt straflos für verpasste Termine

ich dies habe ein Problem in Bezug auf ein Minimum reduziert. Es ist, als

ai 1 2 3 4 5 6 7 
di 4 2 4 3 1 4 6 
wi 70 60 50 40 30 20 10 

Die Lösung dieses Problems folgt

{a2,a4,a1,a3,a7,a5,a6} 
penalty, w5+w6=50 

Answer 3

Die Jobs in absteigender Reihenfolge der PC Timing bestellt werden müssen.
Quelle - http://mypathtothe4.blogspot.in/2013/03/greedy-algorithm-example.html