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

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

0.00 Avg rating0 Votes
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: , , ,
Keywords: combinatorial optimization, heuristics: genetic algorithms, heuristics, networks, networks: scheduling, production
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 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.

Reviews

Required fields are marked *. Your email address will not be published.