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 S₁ e S₂ de maneira que a soma dos elementos de S₁ menos a soma dos elementos de S₂ seja igual a k.

O Problema da Alocação:
Uma tarefa possui uma duração e uma prioridade.
Dado uma lista de tarefas P₁, P₂…P_n com durações T₁, T₂…T_n e prioridades K₁, K₂…K_n, 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, Pr₁(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, Pr₂(t).
  Deseja-se Minimizar a expressão ∑ | Pr₁(t) – Pr₂(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 S₁ e S₂ de maneira que | S₁– S₂ | =k (quando nos referimos a S_i com um operador de subtração queremos dizer que S_i não denota um conjunto e sim a soma dos elemento do conjunto S_i).

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 S₁ 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 S₂.
A função de somatório vai ser numericamente igual a | S₁– S₂ |.

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:

• Partiotion Problem. Wikipédia (inglês)