Coordenação Multiagente

Finalidade

Alocar tarefas a agentes especializados com capacidade limitada ao menor custo total, e medir a distância de uma regra gulosa por ordem de chegada ao ótimo exato.

Variáveis

• c_ijcusto de fazer a tarefa i com o agente j
• x_ij1 se a tarefa i é atribuída ao agente j
• n, mnúmero de tarefas e de agentes
• kcapacidade de cada agente, k = ⌈n/m⌉

Premissas

• Os custos são inteiros aleatórios de 1 a 9 gerados a partir da semente.
• Cada agente pode receber no máximo k tarefas.
• Todas as tarefas são conhecidas de antemão e os custos se somam.

Modelo

Dados que exigiria na prática

• Custo real por par tarefa-agente (tempo, taxa de erro, preço) estimado do histórico.
• Capacidades e horários reais.
• Taxas de chegada das tarefas, se nem todas chegam de uma vez.

Interpretação

A diferença é o preço da regra simples. Uma diferença pequena diz que a regra basta; uma grande justifica a coordenação. Mude a semente para ver que a diferença varia de caso a caso.

Limitações

• A designação estática ignora tarefas que chegam depois.
• O resultado é ótimo apenas para estes custos sintéticos.
• Dependências entre tarefas não são modeladas.