Metaheuristic Algorithms for Task Assignment in Distributed Computing Systems: A Comparative and Integrative Approach

ABSTRACT

We consider the assignment of program tasks to processors in distributed computing systems such that system cost is minimized and resource constraints are satisfied. Several formulations for this task assignment problem (TAP) have been proposed in the literature. Most of these TAP formulations, however, are NP-complete and thus finding exact solutions is computationally intractable. Recently, some approximation methods like simulated annealing have been proposed, and simulation results exhibited the potential to solve the TAP using metaheuristics. In order to better understand the strengths and weaknesses of various metaheuristics applied to the TAP, we first propose two alternative metaheuristics— one using genetic algorithm and the other reinforcement learning algorithm—as well as their implementation details. Extensive computational evidences of the two heuristic algorithms against that of simulated annealing are presented, compared and discussed. Based on these experimental results, a hybrid strategy employing both metaheuristics is then proposed in order to solve the TAP more effectively and efficiently.

Keywords:

heuristic algorithms, Task assignment problem, distributed systems, genetic algorithms, reinforcement learning, simulated annealing.