Pianificazione di attività sequenziali / paralleli avida

Question

Abbiamo attività N che devono essere pianificate per l'elaborazione. Ogni attività è composta da due parti che devono essere eseguite in ordine. Il primo è custodito da un mutex e quindi solo un compito può eseguire questa parte alla volta. La seconda parte non ha tale vincolo e qualsiasi numero di compiti può eseguirlo allo stesso tempo. Per Task i Sappiamo quanto tempo deve spendere in ogni parte, vale a dire m _{i per la parte custodita e un i per la parte che può essere eseguita in parallelo .}

Il problema è trovare una permutazione dei compiti in modo tale che il tempo necessario per eseguirlo tutti sia ridotto al minimo.

La mia intuizione dice che questo può essere risolto con un avido algoritmo, programmando le attività in ordine decrescente a _{I .}

ad esempio dato le attività con:
m _{1 = 3, a 1 = 9 m 2 = 2, a 2 = 7
M 3 = 6, A 3 = 10}

La soluzione ottimale è la permutazione 3, 1, 2.

Tuttavia, ho difficoltà a dimostrare che la soluzione avida è ottimale. Qualche idea su come farlo?

Answer 1

Ho una prova piuttosto disordinata. Sono sicuro che questo può essere ripulito con un po 'di lavoro. Fammi sapere se hai bisogno di me per semplificare la prova.

Per motivi della prova, consente di riorganizzare tutti i termini tali $ A_1 \ GEQ A_2 \ GEQ A_3 \ LDOT $ . Let $ f (1), f (2), \ ldots, f (n) $ Sii qualche programma. Il tempo totale trascorso per qualsiasi programma $ f $ è dato dal seguente. $$ 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)}} $$ . Per il bene della contraddizione, supponiamo che il tuo metodo avido non sia la soluzione ottimale. Esiste alcuni programmi $ \ phi $ tale che $ t (id)> t (\ phi) $ (qui $ ID $ è l'identità). Scegli $ K $ In tal modo $ \ sum_ {i= 1} ^ k m_ {i} + a_k= t (id ) $ . Let $ H $ Sii il numero più piccolo in modo tale da $ \ {1, \ Ldots, K \} \ sottoinsieme \ {\ \} \ PHI (1), \ LDOTS, \ PHI (h) \} $ . Si noti che $ \ PHI (h) \ leq k $ . Perché $ \ {1, \ LDOTS, K \} \ Subset \ {\ PHI (1), \ LDOTS, \ PHI (h) \} $ , < class="container math"> $ \ sum_ {i= 1} ^ h m _ {\ phi (i)} \ geq \ sum_ {i= 1} ^ k m_i $ . Perché $ a_1 \ geq a_2 \ geq \ ldots $ , sappiamo che $ a _ {\ phi (h)} \ \ Geq A_K $ . Ciò significa che $$ \ sum_ {i= 1} ^ k m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ {\ phi (i)} + a _ {\ phi (h )} $$ Ma $ T (ID)=sum_ {i= 1} ^ k m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ {\ phi (i)} + a_ {\ phi (h)} \ leq t (\ phi) $ . Questa è una contraddizione.