Hyper-heuristic method for processor allocation in parallel tasks scheduling

Abstract

Scheduling the tasks of parallel scientific applications is very important for efficient utilization of resources and reducing the overall execution time (makespan). Parallel applications typically include both data parallelism and task parallelism. It is known that the scheduling problem on multiprocessor systems problem is NP-Hard even for applications involving pure task parallelism. The problem becomes more difficult when data parallelism is also taken into consideration. These problems usually considered in two steps, processor allocation and task scheduling, and various algorithms have been proposed. In this study, we introduce a genetic algorithm based hyper-heuristic approach for the processor allocation problem. Experimental results indicate that the algorithm provides better performance compared to various greedy algorithms.