A hybrid evolutionary approach for heterogeneous multiprocessor scheduling

Abstract

This article investigates the assignment of tasks with interdependencies in a heterogeneous multiprocessor environment; specific to this problem, task execution time varies depending on the nature of the tasks as well as with the processing element assigned. The solution to this heterogeneous multiprocessor scheduling problem involves the optimization of complete task assignments and processing order between the assigned processors to arrive at a minimum makespan, subject to a precedence constraint. To solve an NP-hard combinatorial optimization problem, as is typified by this problem, this paper presents a hybrid evolutionary algorithm that incorporates two local search heuristics, which exploit the intrinsic structure of the solution, as well as through the use of specialized genetic operators to promote exploration of the search space. The effectiveness and contribution of the proposed features are subsequently validated on a set of benchmark problems characterized by different degrees of communication times, task, and processor heterogeneities. Preliminary results from simulations demonstrate the effectiveness of the proposed algorithm in finding useful schedule sets based on the set of new benchmark problems. © Springer-Verlag 2008.