Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization

This paper deals with the problem of task allocation (i.e., to which processor should each task of an application be assigned) in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation is known to be NP-hard in the strong sense. We propose a new swarm intelligence technique based on the honeybee mating optimization (HBMO) algorithm for this problem. The HBMO based approach combines the power of simulated annealing, genetic algorithms with a fast problem specific local search heuristic to find the best possible solution within a reasonable computation time. We study the performance of the algorithm over a wide range of parameters such as the number of tasks, the number of processors, the ratio of average communication time to average computation time, and task interaction density of applications. The effectiveness and efficiency of our algorithm are demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature. (C) 2010 Elsevier Inc. All rights reserved.