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



Peng-Yeng Yin*, Benjamin B.M. Shao , Yung-Pin Cheng , Chung-Chao Yeh
Department of Information Management, National Chi Nan University, 303 University Rd., Puli, Nan- tou 545, Taiwan


Article Metrics

CrossRef Citations:
0
Total Statistics:

Full-Text HTML Views: 138
Abstract HTML Views: 103
PDF Downloads: 74
Total Views/Downloads: 315
Unique Statistics:

Full-Text HTML Views: 91
Abstract HTML Views: 73
PDF Downloads: 63
Total Views/Downloads: 227



© 2017 Yin et al.;

open-access license: This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International Public License (CC-BY 4.0), a copy of which is available at: (https://creativecommons.org/licenses/by/4.0/legalcode). This license permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

* Address correspondence to this author at the Department of Information Management, National Chi Nan University, 303 University Rd., Puli, Nantou 545, Taiwan; Tel: +886-49-2910960; Fax: +886-49-2915205; E-mail:pyyin@ncnu.edu.tw


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.