A matheuristic approach for the minimum broadcast time problem using a biased random‐key genetic algorithm

• Published in: International transactions in operational research 2024-01, Vol.31 (1), p.246-273
• Main Authors: Lima, Alfredo, Aquino, Andre L. L., Nogueira, Bruno, Pinheiro, Rian G. S.
• Format: Article
• Language: English
• Subjects: Apexes; Broadcasting; Computer networks; Genetic algorithms; Heuristic methods; Hypercubes; Industrial applications; Industry 4.0; Operations research; Topology
• ISSN: 0969-6016; 1475-3995
• DOI: 10.1111/itor.13146

The Minimum Broadcast Time (MBT) is a well‐known data dissemination problem whose goal is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The problem has many applications in distributed systems and, in particular, the Industry 4.0 domain. Because Industry 4.0 applications rely primarily on the use of large‐scale machine to machine communications, they need data dissemination techniques that combine high reliability with low communication latency. This work proposes a Biased Random‐Key Genetic Algorithm and a matheuristic for the MBT. We carry out experiments with our algorithms on instances commonly used in the literature (hypercube, shuffle exchange, cube‐connected cycles, de Bruijn, Harary graphs), and also on massive synthetic instances (up to 1000 vertices), allowing to cover many possibilities of real industry topologies. Our proposal is also compared with state‐of‐the‐art exact methods and heuristics. Experimental results show that our algorithm is able to outperform the best‐known heuristics for the MBT, and also that it is a very good alternative for large instances that cannot be solved by current exact methods.