Agendamento de tarefa sequencial / paralela gananciosa

Question

Temos tarefas de N que precisam ser agendadas para processamento. Cada tarefa consiste em duas partes que precisam ser executadas em ordem. O primeiro é protegido por um mutex e, portanto, apenas uma tarefa pode estar executando essa parte de cada vez. A segunda parte não tem tal restrição e qualquer número de tarefas pode estar executando isso ao mesmo tempo. Para a tarefa i, sabemos quanto tempo precisa gastar em cada parte, ou seja, m _{i para a parte protegida, e um i para a peça que pode ser executada em paralelo .}

O problema é encontrar uma permutação das tarefas, de modo que o tempo necessário para executar todos eles seja minimizado.

Minha intuição diz que isso pode ser resolvido com um algoritmo ganancioso, agendando as tarefas em decrescendo um _{ordem .}

Por exemplo, dadas as tarefas com:
m _{1 = 3, A 1 = 9
m 2 = 2, A 2 = 7
m 3 = 6, A 3 = 10}

A solução ideal é a permutação 3, 1, 2.

No entanto, tenho dificuldade em provar que a solução gananciosa é ideal. Alguma idéia sobre como fazer isso?

Answer 1

Eu tenho uma prova muito confusa. Tenho certeza que isso pode ser limpo com um pouco de trabalho. Deixe-me saber se você precisar de mim para simplificar a prova.

Por causa da prova, permite reorganizar todos os termos que $ a_1 \ geq a_2 \ geq a_3 \ ldots $ . Deixe $ f (1), f (2), \ ldots, f (n) $ ser algum cronograma. O tempo total gasto para qualquer agenda $ F $ é dado pelo seguinte. $$ 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)}} $$ .

Por uma questão de contradição, suponha que o seu método ganancioso não seja a solução ideal. Existe alguma programação $ \ phi $ tal que $ t (ID)> t (\ phi) $ (aqui $ ID $ é a identidade). Escolha $ k $ tal que $ \ sum_ {i= 1} ^ k m_ {i} + a_k= t (id} + a_k= t ) $ . Deixe $ H $ Seja o menor número tal que $ \ {1, \ lDOTS, k \} \ subset \ {\ PHI (1), \ LDOTS, \ PHI (H) \} $ . Observe que $ \ phi (h) \ leq k $ . Porque $ \ {1, \ lDOTS, k \} \ subconjunto {\ phi (1), \ LDOTS, \ pHI (h) \} $ , $ \ sum_ {i= 1} ^ h m _ {\ phi (i)} \ geq \ sum_ {i= 1} ^ k m_i $ . Porque $ a_1 \ geq a_2 \ geq \ ldots $ , sabemos que $ a _ {\ phi (h)} \ geq A_k $ . Isso significa que $$ \ sum_ {i= 1} ^ k m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ {\ phi (i)} + a _ {\ phi (h ) $$ Mas $ t (ID)=sum_ {i= 1} ^ k m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ {\ phi (i)} + a_ {\ phi (h)} \ leq t (\ phi) $ . Esta é uma contradição.