A GRASP-Genetic Metaheuristic Applied on Multi-Processor Task Scheduling Systems
Abla F. A. Saad, Ahmed Kafafy, osama Abd-El-Raof, Nancy El-Hefnawy · 2018
In the last decades, parallel processing systems are used in most applications. In these systems, task scheduling problems are considered as an important issue in managing multiprocessors. The challenge in task scheduling problems is to get the best schedule that achieves the best efficiency and the minimum make span. In this paper, a new hybrid metaheuristic algorithm called GRASP-GA is proposed to handle such problems. In the proposed algorithm, the greedy randomized adaptive search procedure is adopted to construct a population of high-quality solutions. Then, the genetic algorithm is applied on the constructed population to improve these solutions. Two heuristic functions are adopted to guide GRASP, bottom-level and top-level. The proposed GRASP-GA is verified against a set of the state-of-the-art algorithms using some test problems that considered as benchmarks. The experimental results indicated the superiority of the proposed GRASP-GA over all the tested algorithms. Since, it can achieve the best performance in all test problems used in this experiment. These results ensure the GRASP-GA is a good competitor and can be considered as a viable alternative.