Balanceamento de Carga: Jogo, Análise e Teorema de PoA
Informações do documento
| Idioma | Portuguese |
| Número de páginas | 103 |
| Formato | |
| Tamanho | 287.92 KB |
Resumo
I.Proposição
Dado um valor q e um conjunto de máquinas {G0, ..., Gq}, onde Gi possui k! q! máquinas com velocidade 2k e k tarefas com peso 2k, existe uma atribuição A que atribui as tarefas às máquinas de forma que as máquinas em Gi sejam socialmente ótimas.
II.Equilíbrio de Custo Social e LPT
A atribuição A é um equilíbrio de custo social q e tem custo menor ou igual a 2 vezes o custo ótimo. O algoritmo LPT (Largest Processing Time), que atribui tarefas em ordem decrescente de peso às máquinas que minimizam o custo, calcula um equilíbrio de custo social.
III.Jogo de Balanceamento de Carga
No jogo de balanceamento de carga, cada tarefa escolhe uma máquina com base em uma distribuição de probabilidade e são considerados dois tipos de equilíbrio: equilíbrio de Nash puro e equilíbrio de Nash misto.
IV.Delimitação Superior no PoA
Para qualquer instância do jogo de balanceamento de carga com m máquinas idênticas e n tarefas, existe um equilíbrio de Nash P tal que o seu custo é menor ou igual a O(ln ln ln m / m) vezes o custo ótimo.
1. Delimitação Superior do PoA
Teorema: Considere uma instância J do jogo de balanceamento de carga com m máquinas idênticas e seja P um equilíbrio de Nash do jogo. Vale que:
V.Tempo de Convergência
Não há um resultado conhecido para o tempo de convergência do jogo de balanceamento de carga com máquinas relacionadas, mas é possível calcular um equilíbrio eficientemente.
1. Equilíbrio de Custos Sociais
No caso de máquinas não idênticas, não há um resultado conhecido como para máquinas idênticas, mas é possível calcular um equilíbrio de forma eficiente usando o Algoritmo LPT.
2. Algoritmo LPT
O algoritmo LPT (largest processing time) atribui as tarefas em ordem decrescente de peso, colocando-as nas máquinas que minimizam o seu custo. Este algoritmo retorna um equilíbrio, conforme demonstrado por indução no número de tarefas atribuídas.
3. Jogo com Estratégias Mistas
O problema de balanceamento de carga pode ser modelado como um jogo com estratégias mistas, onde cada tarefa escolhe uma máquina com base em uma distribuição de probabilidade. Um equilíbrio de Nash do jogo é uma estratégia mista onde nenhuma tarefa tem incentivo para mudar de máquina.
4. Delimitação Superior no PoA
Para um jogo de balanceamento de carga com m máquinas idênticas e n tarefas, existe um equilíbrio de Nash P com custo(P) = Ω ln ln ln m m.