Das notas às decisões: prioridade e capacidade

Duas perguntas diferentes

Uma nota de prioridade responde qual item é mais urgente. Uma decisão de capacidade responde quantos deles a equipe consegue de fato tratar nas horas que tem. Misturar as duas esconde a segunda pergunta.

Uma nota de prioridade

R é o risco normalizado, A o valor normalizado, P um termo de pagamento e T o tempo decorrido normalizado; α, β, γ e δ são pesos. O sinal do termo de pagamento é uma decisão de política: uma alta probabilidade de pagamento pode reduzir a urgência, então no laboratório usamos 1 − P. Os pesos precisam de calibração contra resultados; até lá, a nota é só um instrumento de ordenação.

Capacidade como mochila

Aqui x_i vale 1 se a ação i é executada, v_i é o seu valor (por exemplo, a nota de prioridade), a_i o esforço em horas e b as horas disponíveis.

A regra da razão e o seu limite

Ordene as ações por v_i / a_i e tome-as enquanto couberem. Na versão fracionária, em que uma ação pode ser dividida, essa regra é ótima, então o seu valor é um limite superior para o problema 0/1. Na versão 0/1 a regra pode ser melhorada: a programação dinâmica encontra o ótimo exato para tamanhos moderados. A diferença entre a regra, o ótimo e o limite mostra quanto um método melhor ainda poderia ganhar.

Limites

• Os valores dependem de previsões que podem estar erradas.
• Interações entre ações são ignoradas.
• Limites de política (o que nunca deve ser feito) pertencem às restrições, e não aos pesos.

Leitura de fundamentação

Obras de outros autores sobre os métodos de base. Não são publicações da Menlo Tech.

• Martello, S. & Toth, P. Knapsack Problems: Algorithms and Computer Implementations. Wiley, 1990.
• Bertsimas, D. & Tsitsiklis, J. Introduction to Linear Optimization. Athena Scientific, 1997.

Relacionados

Otimização e Pesquisa Operacional