An analysis of parallel heuristics for task allocation in multicomputers

In literature there exist many heuristic optimisation techniques which have been proposed as general-purpose methods for solving difficult problems. Of course, the question which of them is more powerful is in general meaningless, however, their application and comparison on real, well-limited problems is quite interesting and intriguing. Furthermore, parallel versions for such techniques are welcome, allowing to reduce the search times or to find new innovative solutions unreachable in a sequential environment. Within this paper we describe two such techniques, the Genetic Algorithms and the Simulated Annealing, and provide a general parallelisation framework for heuristic methods which is based on a locally linked search strategy. A comparative analysis of the parallel versions of these techniques is performed on the solution of a set of different-sized Task Allocation Problems in terms of better absolute solution quality, of lower convergence time to a same solution and of robustness expressed as lower variance around the mean value.