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

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.

PDF file of full paper

Mauricio G.C. Resende's Home Page