IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v349y2025i3d10.1007_s10479-025-06609-5.html
   My bibliography  Save this article

Biased random-key genetic algorithms for the weighted minimum broadcast time problem

Author

Listed:
  • Alfredo Lima

    (Universidade Federal Fluminense
    Universidade Federal de Alagoas)

  • Luiz Satoru Ochi

    (Universidade Federal Fluminense)

  • Bruno Nogueira

    (Universidade Federal de Alagoas
    Universidade de Pernambuco)

  • Rian G. S. Pinheiro

    (Universidade Federal de Alagoas)

Abstract

Broadcasting is an essential operation in distributed systems, with a wide range of applications. This study is focused on solving the Weighted Minimum Broadcast Time (WMBT), a problem that extends the classical Minimum Broadcast Time problem (MBT) by incorporating costs associated with each communication operation. We propose five contributions to the WMBT: (i) an integer linear programming model, (ii) two greedy algorithms, (iii) two Biased Random-Key Genetic Algorithms (BRKGAs), (iv) a lower bound algorithm, (v) a reduction rule to decrease an instance size, and (vi) a method to create instances with known optimal solutions. Our novel approaches are compared with state-of-the-art methods using large-scale synthetic instances. The experimental results demonstrate the effectiveness of our proposals. The greedy algorithms attains the best known solutions in a significant number of instances, while the two BRKGAs further enhance this performance, surpassing the greedy algorithms in many of the tested instances.

Suggested Citation

  • Alfredo Lima & Luiz Satoru Ochi & Bruno Nogueira & Rian G. S. Pinheiro, 2025. "Biased random-key genetic algorithms for the weighted minimum broadcast time problem," Annals of Operations Research, Springer, vol. 349(3), pages 1749-1783, June.
    • Handle: RePEc:spr:annopr:v:349:y:2025:i:3:d:10.1007_s10479-025-06609-5
    DOI: 10.1007/s10479-025-06609-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-025-06609-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-025-06609-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. López-Ibáñez, Manuel & Dubois-Lacoste, Jérémie & Pérez Cáceres, Leslie & Birattari, Mauro & Stützle, Thomas, 2016. "The irace package: Iterated racing for automatic algorithm configuration," Operations Research Perspectives, Elsevier, vol. 3(C), pages 43-58.
    2. André Renato Villela Silva & Luiz Satoru Ochi & Bruno José da Silva Barros & Rian Gabriel S. Pinheiro, 2020. "Efficient approaches for the Flooding Problem on graphs," Annals of Operations Research, Springer, vol. 286(1), pages 33-54, March.
    3. Thiago Noronha & Mauricio Resende & Celso Ribeiro, 2011. "A biased random-key genetic algorithm for routing and wavelength assignment," Journal of Global Optimization, Springer, vol. 50(3), pages 503-518, July.
    4. Cheng-Hsiao Tsou & Gen-Huey Chen & Hung-I Yu & Ching-Chi Lin, 2013. "The broadcast median problem in heterogeneous postal model," Journal of Combinatorial Optimization, Springer, vol. 25(4), pages 602-616, May.
    5. James C. Bean, 1994. "Genetic Algorithms and Random Keys for Sequencing and Optimization," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 154-160, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Andrade, Carlos E. & Toso, Rodrigo F. & Gonçalves, José F. & Resende, Mauricio G.C., 2021. "The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications," European Journal of Operational Research, Elsevier, vol. 289(1), pages 17-30.
    2. Soares, Leonardo Cabral R. & Carvalho, Marco Antonio M., 2020. "Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 955-964.
    3. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    4. F. Stefanello & L. S. Buriol & M. J. Hirsch & P. M. Pardalos & T. Querido & M. G. C. Resende & M. Ritt, 2017. "On the minimization of traffic congestion in road networks with tolls," Annals of Operations Research, Springer, vol. 249(1), pages 119-139, February.
    5. Ghorashi Khalilabadi, S. M. & Roy, D. & de Koster, M.B.M., 2022. "A Data-driven Approach to Enhance Worker Productivity by Optimizing Facility Layout," ERIM Report Series Research in Management ERS-2022-003-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    6. Gonçalves, José Fernando & Wäscher, Gerhard, 2020. "A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects," European Journal of Operational Research, Elsevier, vol. 286(3), pages 867-882.
    7. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    8. R. B. Damm & A. A. Chaves & J. A. Riveaux & D. P. Ronconi, 2025. "Scheduling technicians and tasks through an adaptive multi-objective biased random-key genetic algorithm," Annals of Operations Research, Springer, vol. 346(2), pages 945-980, March.
    9. Rafael A. Melo & Celso C. Ribeiro & Jose A. Riveaux, 2025. "A biased random-key genetic algorithm for the minimum quasi-clique partitioning problem," Annals of Operations Research, Springer, vol. 351(1), pages 575-607, August.
    10. Geiza Silva & André Leite & Raydonal Ospina & Víctor Leiva & Jorge Figueroa-Zúñiga & Cecilia Castro, 2023. "Biased Random-Key Genetic Algorithm with Local Search Applied to the Maximum Diversity Problem," Mathematics, MDPI, vol. 11(14), pages 1-11, July.
    11. Pinto, Bruno Q. & Ribeiro, Celso C. & Rosseti, Isabel & Plastino, Alexandre, 2018. "A biased random-key genetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 271(3), pages 849-865.
    12. Edson Ticona-Zegarra & Rafael CS Schouery & Leandro A Villas & Flávio K Miyazawa, 2018. "Improved continuous enhancement routing solution for energy-aware data aggregation in wireless sensor networks," International Journal of Distributed Sensor Networks, , vol. 14(5), pages 15501477187, May.
    13. Li, Xueping & Zhang, Kaike, 2018. "Single batch processing machine scheduling with two-dimensional bin packing constraints," International Journal of Production Economics, Elsevier, vol. 196(C), pages 113-121.
    14. Bruno Q. Pinto & Celso C. Ribeiro & Isabel Rosseti & Thiago F. Noronha, 2020. "A biased random-key genetic algorithm for routing and wavelength assignment under a sliding scheduled traffic model," Journal of Global Optimization, Springer, vol. 77(4), pages 949-973, August.
    15. Londe, Mariana A. & Pessoa, Luciana S. & Andrade, Carlos E. & Resende, Mauricio G.C., 2025. "Biased random-key genetic algorithms: A review," European Journal of Operational Research, Elsevier, vol. 321(1), pages 1-22.
    16. Caio César Freitas & Dario José Aloise & Fábio Francisco Costa Fontes & Andréa Cynthia Santos & Matheus Silva Menezes, 2023. "A biased random-key genetic algorithm for the two-level hub location routing problem with directed tours," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(3), pages 903-924, September.
    17. Paola Festa & Panos Pardalos, 2012. "Efficient solutions for the far from most string problem," Annals of Operations Research, Springer, vol. 196(1), pages 663-682, July.
    18. Ayşegül Altın & Bernard Fortz & Mikkel Thorup & Hakan Ümit, 2013. "Intra-domain traffic engineering with shortest path routing protocols," Annals of Operations Research, Springer, vol. 204(1), pages 65-95, April.
    19. Schirmer, Andreas & Riesenberg, Sven, 1997. "Parameterized heuristics for project scheduling: Biased random sampling methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 456, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    20. Qingzheng Xu & Na Wang & Lei Wang & Wei Li & Qian Sun, 2021. "Multi-Task Optimization and Multi-Task Evolutionary Computation in the Past Five Years: A Brief Review," Mathematics, MDPI, vol. 9(8), pages 1-44, April.

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:349:y:2025:i:3:d:10.1007_s10479-025-06609-5. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.