Premium
A biased random‐key genetic algorithm for scheduling heterogeneous multi‐round systems
Author(s) -
Brandão Julliany S.,
Noronha Thiago F.,
Resende Mauricio G. C.,
Ribeiro Celso C.
Publication year - 2017
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12429
Subject(s) - computer science , load balancing (electrical power) , scheduling (production processes) , job shop scheduling , benchmark (surveying) , set (abstract data type) , heuristic , mathematical optimization , key (lock) , genetic algorithm , algorithm , transmission (telecommunications) , distributed computing , parallel computing , mathematics , schedule , artificial intelligence , geometry , geodesy , geography , programming language , grid , operating system , telecommunications , computer security , machine learning
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.