Article ID: | iaor20171555 |
Volume: | 24 |
Issue: | 5 |
Start Page Number: | 1061 |
End Page Number: | 1077 |
Publication Date: | Sep 2017 |
Journal: | International Transactions in Operational Research |
Authors: | Resende Mauricio G C, Ribeiro Celso C, Noronha Thiago F, Brando Julliany S |
Keywords: | combinatorial optimization, heuristics: genetic algorithms, heuristics, networks, networks: scheduling, production |
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 A⊆P 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 i∈A at each round k∈{1,…,m}, 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.