A bipartite genetic algorithm for multi-processor task scheduling

Bonyadi, Mohammad Reza and Moghaddam, Mohsen Ebrahimi (2009) A bipartite genetic algorithm for multi-processor task scheduling. International Journal of Parallel Programming, 37 5: 462-487. doi:10.1007/s10766-009-0107-8


Author Bonyadi, Mohammad Reza
Moghaddam, Mohsen Ebrahimi
Title A bipartite genetic algorithm for multi-processor task scheduling
Journal name International Journal of Parallel Programming   Check publisher's open access policy
ISSN 0885-7458
1573-7640
Publication date 2009-10-01
Sub-type Article (original research)
DOI 10.1007/s10766-009-0107-8
Open Access Status Not yet assessed
Volume 37
Issue 5
Start page 462
End page 487
Total pages 26
Place of publication New York, NY, United States
Publisher Springer New York LLC
Language eng
Abstract 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.
Keyword Genetic algorithm
Makespan
Multiprocessor
Task scheduling
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: Centre for Advanced Imaging Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 16 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 18 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 13 Jul 2016, 00:52:06 EST by System User on behalf of Learning and Research Services (UQ Library)