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

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

0.00 Avg rating0 Votes
Article ID: iaor20118422
Volume: 3
Issue: 2
Start Page Number: 91
End Page Number: 110
Publication Date: Nov 1997
Journal: Journal of Heuristics
Authors: ,
Keywords: heuristics: tabu search, heuristics: genetic algorithms, allocation: resources
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.