Open AccessMetaheuristic Algorithms for Task Assignment in Distributed Computing Systems: A Comparative and Integrative Approach
Author(s) -
Peng-Yeng Yin,
Benjamin B. M. Shao,
Yung-Pin Cheng,
Chung-Chao Yeh
Publication year - 2009
Publication title -
the open artificial intelligence journal
Language(s) - English
Resource type - Journals
ISSN - 1874-0618
DOI - 10.2174/18740618009030100016
Subject(s) - metaheuristic , simulated annealing , computer science , mathematical optimization , heuristic , task (project management) , reinforcement learning , assignment problem , algorithm , tabu search , parallel metaheuristic , artificial intelligence , mathematics , engineering , systems engineering , meta optimization
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.