Abstract
Effective task scheduling, which is essential for achieving high performance of parallel processing, remains challenging despite of extensive studies. In this paper, a heuristic-based hybrid Genetic Algorithm (GA) is proposed for solving the heterogeneous multiprocessor scheduling problem. The proposed algorithm extends traditional GA-based approaches in three aspects. First, it incorporates GA with Variable Neighborhood Search (VNS), a local search metaheuristic, to enhance the balance between global exploration and local exploitation of search space. Second, two novel neighborhood structures, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized, are proposed to improve both the search quality and efficiency of VNS. Third, the use of GA is restricted to map tasks to processors while an upward-ranking heuristic is introduced to determine the task sequence assignment in each processor. Simulation results indicate that our proposed algorithm consistently outperforms several state-of-art scheduling algorithms in terms of the schedule quality while maintaining high performance within a wide range of parameter settings. Further experiments are carried out to validate the effectiveness of the hybridized VNS.
