Gierige sequentielle / parallele Taskplanung

Question

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?

Answer 1

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 $ A_1 \ GEQ A_2 \ GEQ A_3 \ LDOTS $ . Lassen Sie $ f (1), f (2), \ ldots, f (n) $ ein Zeitplan sein. Die Gesamtzeit für jeden Zeitplan $ F $ wird von den folgenden angegeben. $$ t (f)=max \ {m_ {f (1)} + A_ {f (1)}, m_ {f (1)} + m_ {f (2 )} + A_ {F (2)}, \ ldots, \ sum_ {i= 1} ^ n m_ {f (i)} + a_ {f (n)} \} $$ . . Nehmen wir an, dass Ihre gierige Methode nicht die optimale Lösung ist. Es gibt einige Zeitpläne $ \ phi $ so, dass $ T (ID)> T (\ phi) $ (Hier ist $ ID $ ist die Identität). Wählen Sie $ K $ so, dass $ \ sum_ {i= 1} ^ k m_ {i} + a_k= t (ID ) $ . Lassen Sie $ H $ die kleinste Anzahl derart sein, dass $ \ {1, \ ldots, k \} \ Subset \ \ \ phi (1), \ ldots, \ phi (h) \} $ . Beachten Sie, dass $ \ phi (h) \ leq k $ . Denn $ \ {1, \ ldots, k \ \ \ Subset \ {\ phi (1), \ ldots, \ phi (h) \} $ , $ \ Sum_ {i= 1} ^ h m _ {\ phi (i)} \ geq \ sum_ {i= 1} ^ k m_i $ . Weil $ A_1 \ GEQ A_2 \ GEQ \ LDOs $ , wissen wir, dass $ A _ {\ phi (H)} \ geq A_K $ . Dies bedeutet, dass $$ \ sum_ {i= 1} ^ k m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ {\ phi (i)} + a _ {\ phi (h )} $$ Aber $ t (ID)=sum_ {i= 1} ^ k m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ {\ phi (i)} + a_ {\ phi (h)} \ leq t (\ phi) $ . Dies ist ein Widerspruch.