Min–min GA Based Task Scheduling In Multiprocessor Systems
Medhat Awadall1, Afaq Ahmad2, Samir Al-Busaidi3
1Medhat Awadalla, Department of Electrical and Computer Engineering, Sultan Qaboos University, Oman.
2Afaq Ahmad, Department of Electrical and Computer Engineering, Sultan Qaboos University, Oman.
3Samir Al-Busaidi, Department of Electrical and Computer Engineering, Sultan Qaboos University, Oman.
Manuscript received on November 25, 2013. | Revised Manuscript received on December 15, 2013. | Manuscript published on December 30, 2013. | PP: 22-31 | Volume-3, Issue-2, December 2013. | Retrieval Number: B2337123213/2013©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: An efficient assignment and scheduling of tasks of a multiprocessor system is one of the key elements in the effective utilization of multiprocessor systems. This problem is extremely hard to solve, consequently several methods have been developed to optimally tackle it which is called NP-hard problem. This paper presents two new approaches, Modified List Scheduling Heuristic (MLSH) and enhanced genetic algorithm by constructing promising chromosomes. Furthermore, this paper proposes three different representations for the chromosomes of the genetic algorithm: Min-min task list, processor list and combination of both. Extensive simulation experiments have been conducted on different random and real-world application graphs such as Gauss-Jordan, LU decomposition, Gaussian elimination and Laplace equation solver problems. Comparisons have been performed with the most related algorithms, LSHs, Bipartite GA (BGA) and Priority based Multi-Chromosome (PMC). The achieved results show that the proposed approaches significantly surpass the other approaches in terms of task make span and processor efficiency.
Keywords: Multiprocessors, Task scheduling, Genetic algorithm, Make span, Parallel and distributed system, List Scheduling Heuristic.