Jogo de balanceamento de carga

Balanceamento de Carga: Jogo, Análise e Teorema de PoA

Informações do documento

Idioma Portuguese
Número de páginas 103
Formato | PDF
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.