A Genetic/Tabu Thresholding Hybrid Algorithm for the Process Allocation Problem

In this paper we describe an hybrid heuristic approach, which combines Genetic Algorithms and Tabu Thresholding, for the static allocation of interacting processes onto a parallel target system, where the number of processes is greater than the number of available processors. This problem is known to be NP-hard and finds many practical applications, given the increasing diffusion of distributed and parallel computing systems. The algorithm faces infeasibilities due to processors overload by incorporating them into the objective function and by adapting the mutation operator. Global search is performed on the set of local optima obtained by a repair search operator based on a Tabu Thresholding procedure. Extensive computational testing on randomly generated instances with up to 100 processes characterized by different target network topologies with 4 to 25 processors, shows that the algorithm favorably compares with other approaches from the literature. The proposed approach has also been extended to the allocation of parallel objects and classes, where an additional co-residence constraint between each parallel object and the associated class arises.