A biased random‐key genetic algorithm for scheduling heterogeneous multi‐round systems |
| |
| Authors: | Julliany S. Brandão Thiago F. Noronha Mauricio G. C. Resende Celso C. Ribeiro |
| |
| Affiliation: | 1. Institute of Computing, Universidade Federal Fluminense, Niterói, Brazil;2. Centro Federal de Educa??o Tecnológica Celso Suckow da Fonseca, Rio de Janeiro, Brazil;3. Department of Computer Science, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil;4. Amazon.com, Mathematical Optimization and Planning, Seattle, USA |
| |
| Abstract: | A divisible load is an amount W of computational work that can be arbitrarily divided into independent chunks of load. In many divisible load applications, the load can be parallelized in a master–worker fashion, where the master distributes the load among a set P of worker processors to be processed in parallel. The master can only send load to one worker at a time, and the transmission can be done in a single round or in multiple rounds. The multi‐round divisible load scheduling problem consists in (a) selecting the subset  of workers that will process the load, (b) defining the order in which load will be transmitted to each of them, (c) defining the number m of transmission rounds that will be used, and (d) deciding the amount of load that will be transmitted to each worker  at each round  , so as to minimize the makespan. We propose a heuristic approach that determines the transmission order, the set of the active processors and the number of rounds by a biased random‐key genetic algorithm. The amount of load transmitted to each worker is computed in polynomial time by closed‐form formulas. Computational results showed that the proposed genetic algorithm outperformed a closed‐form state‐of‐the‐art heuristic, obtaining makespans that are 11.68% smaller on average for a set of benchmark problems. |
| |
| Keywords: | divisible loads divisible load scheduling multi‐round biased random‐key genetic algorithms metaheuristics |
|
|
of workers that will process the load, (b) defining the order in which load will be transmitted to each of them, (c) defining the number m of transmission rounds that will be used, and (d) deciding the amount of load that will be transmitted to each worker 
at each round 
, so as to minimize the makespan. We propose a heuristic approach that determines the transmission order, the set of the active processors and the number of rounds by a biased random‐key genetic algorithm. The amount of load transmitted to each worker is computed in polynomial time by closed‐form formulas. Computational results showed that the proposed genetic algorithm outperformed a closed‐form state‐of‐the‐art heuristic, obtaining makespans that are 11.68% smaller on average for a set of benchmark problems.