Dissertação: Biased Random-Key Genetic Algorithms for the Minimum Broadcast Time Problem

O Minimum Broadcast Time (MBT) é um conhecido problema de disseminação de dados cujo objetivo é encontrar um esquema de transmissão que minimize o número de passos necessários para executar uma operação de broadcasting.
O Weighted Minimum Broadcast Time (WMBT) é uma generalização do MBT, em que cada transmissão tem um custo associado.
Este trabalho propõe uma série de novas contribuições para o MBT e WMBT, incluindo: (i) Biased Random-Key Genetic Algorithms (BRKGAs) para ambos os problemas, (ii) uma matheuristic para o MBT, (iii) modelos de programação linear inteira para o WMBT, (iv) algoritmos para calcular um limite inferior para o MBT e WMBT, (v) uma regra de redução de instâncias para o WMBT e (vi) métodos para criar instâncias com ótimos conhecidos para o MBT e WMBT. Essas contribuições foram comparadas aos métodos do estado-da-arte, e os resultados demonstram a eficiência e aplicabilidade dos métodos propostos.