Gierige sequentielle / parallele Taskplanung
-
29-09-2020 - |
Frage
Wir verfügen über N
-Aufgaben, die zur Verarbeitung geplant werden müssen. Jede Aufgabe besteht aus zwei Teilen, die in der Reihenfolge ausgeführt werden müssen. Der erste wird von einem Mutex bewacht und kann daher nur eine Aufgabe diesen Teil gleichzeitig ausführen. Der zweite Teil hat keine solche Einschränkung, und eine beliebige Anzahl der Aufgaben kann dies gleichzeitig ausführen. Für den Task i
wissen wir, wie viel Zeit es in jedem Teil ausgeben muss, nämlich m i für das Schutzteil, und ein i für den Teil, der parallel ausgeführt werden kann .
Das Problem besteht darin, eine Permutation der Aufgaben zu finden, so dass die zur Ausführung aller benötigte Zeit minimiert wird.
Meine Intuition sagt, dass dies mit einem gierigen Algorithmus gelöst werden kann, indem er die Aufgaben in absteigender Reihenfolge i anplant.
Beispielsweise Angesichts der Aufgaben mit:
m 1 = 3, a 1 = 9
m 2 = 2, a 2 = 7
m 3 = 6, a 3 = 10
Die optimale Lösung ist die Permutation 3, 1, 2.
Ich habe jedoch Schwierigkeiten, sich zu beweisen, dass die gierige Lösung optimal ist. Irgendwelche Ideen, wie man das macht?
Lösung
Ich habe einen ziemlich unordentlichen Beweis. Ich bin sicher, dass dies mit etwas Arbeit aufgeräumt werden kann. Lassen Sie mich wissen, wenn Sie mich brauchen, um den Beweis zu vereinfachen.
lässt den Beweis dafür, dass alle Begriffe so ordnen