A Multi-Population Based Parallel Genetic Algorithm for Multiprocessor Task Scheduling with Communication Costs

Multiprocessor task scheduling is one of the hardest combinatorial optimization problems in parallel and distributed systems. It is known as NP-hard and therefore, scanning the whole search space using an exact algorithm to find the optimal solution is not practical. Instead, metaheuristics are mostly employed to find a near-optimal solution in a reasonable amount of time. In this paper, a multi-population based parallel genetic algorithm is presented for the optimization of multiprocessor task scheduling in the presence of communication costs. To the best of our knowledge, this parallel genetic algorithm approach is applied to the problem at hand for the first time using a benchmark set that includes well-known task graphs from different sources. Our experiments conducted on several task graphs with different sizes from the benchmark set showed the superiority of the approach over a conventional genetic algorithm and the related works in the literature in terms of two different performance metrics. Our parallel implementation not only decreased the execution time but also increased the quality of the scheduling solutions considerably.