silveira neto

carbon-based lifeform. virgo supercluster

Menu Close

Alocação de Tarefas é NP-Completo

Vamos tentar reduzir o problema da partição em um problema de alocação de tarefas em dois processadores.

O Problema da Partição:
Este problema de decisão consistem em dizer se, dado um conjunto de inteiros S e um inteiro k, é possível particiona-lo em dois outros conjuntos de inteiros S1 e S2 de maneira que a soma dos elementos de S1 menos a soma dos elementos de S2 seja igual a k.

O Problema da Alocação:
Uma tarefa possui uma duração e uma prioridade.
Dado uma lista de tarefas P1, P2…Pn com durações T1, T2…Tn e prioridades K1, K2…Kn, deseja-se alocar essas tarefas em dois processadores da seguinte forma:

  • Uma tarefa de maior prioridade tem acesso a um determinado processador antes das tarefas de menor prioridade o tenham.
  • Deve-se minimizar a soma das diferenças de prioridade entre o processador 1 e o processador 2, a todo momento. Mais formalmente, Pr1(t) é a prioridade do processador 1 no tempo t, que é dado pela prioridade do programa que está sendo executado no tempo t, neste processador. Análogamente, Pr2(t).
    Deseja-se Minimizar a expressão | Pr1(t) – Pr2(t) | para todo t.

O problema de decisão consistem em alocar as tarefas de modo que a expressão de somatório seja igual à k.

A Redução

Dado uma instância do problema da partição, para cada número i do conjunto S, criamos uma tarefa de prioridade 1 com tempo de duração i. O número k permanece o mesmo.

Instâncias positivas

Quando é possível particionar S em conjuntos S1 e S2 de maneira que | S1– S2 | =k (quando nos referimos a Si com um operador de subtração queremos dizer que Si não denota um conjunto e sim a soma dos elemento do conjunto Si).

Na solução X da instancia positiva do problema de partição reduzida ao problema da alocação, temos que o processador 1 vai assumir o papel de conjunto S1 porque a noção dos numerais que compunham S é preservada na s tarefas de tempo i e prioridade 1. O processador 2 vai assumir o papel de conjunto S2.
A função de somatório vai ser numericamente igual a | S1– S2 |.

Instâncias negativas

Da mesma maneira, nas instâncias negativas, quando não for possível particionar o conjunto da maneira desejada, não é possível alocar as tarefas da maneira desejada. Note que a noção de numeral é preservada durante a transformação.

Referências:

2 Comments

Add yours →

  1. hotomv says:

    Wow unflappable forum. Happy I took the time to sign up. I be suffering with been lurking in behalf of a while but wanted to be able to post. SO here I am :)

    If you yen to be informed how to [url=http://www.improvegolftoday.com] improve golf[/url] on scholarship a elevate surpass
    [url=http://www.improvegolftoday.com]golf swing[/url]

Leave a Reply

© 2016 silveira neto. All rights reserved.

Theme by Anders Norén.