A Bipartite Genetic Algorithm for Multi-processor Task Scheduling

• DOI: 10.1007/s10766-009-0107-8
• Publication Date: 2009-06-02T11:11:22Z
• Authors: Mohammad Reza Bon...; Mohsen Ebrahimi M...
• Keywords: 1712 Software; Task scheduling; Makespan; Genetic algorithm; 0202 electrical engineering, electronic engineering, information engineering; Multiprocessor; 006; 02 engineering and technology; 1710 Information Systems; 2614 Theoretical Computer Science

Until now, several methods have been presented to optimally solve the multiprocessor task scheduling problem that is an NP-hard one. In this paper, a genetic-based algorithm has been presented to solve this problem with better results in comparison with related methods. The proposed method is a bipartite algorithm in a way that each part is based on different genetic schemes, such as genome presentation and genetic operators. In the first part, it uses a genetic method to find an adequate sequence of tasks and in the second one, it finds the best match processors. To evaluate the proposed method, we applied it on several benchmarks and the results were compared with well known algorithms. The experimental results were satisfactory and in most cases the presented method had a better makespan with at least 10% less iterations compared to related works.