A biased random-key genetic algorithm for scheduling heterogeneous multi-round systems

J.S. Brandão, T.F. Noronha, M.G.C. Resende, and C.C. Ribeiro

International Transactions in Operational Research, vol. 24, pp. 1061-1077, 2017


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 math formula 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 math formula at each round math formula, 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.

PDF file of full paper


Mauricio G.C. Resende's Home Page

Last modified: 24 September 2017