Journal
JOURNAL OF COMPUTATIONAL SCIENCE
Volume 7, Issue -, Pages 37-47Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.jocs.2015.01.001
Keywords
Combinatorial problems; Distributed computing; Parallel processing; Scheduling
Ask authors/readers for more resources
I present an ant colony optimization (ACO) heuristic for solving the constraint task allocation problem (CTAP). Using real-world and simulated datasets, I compare the results of ACO with those of mixed integer programming (MIP) formulation, iterated greedy (IG) heuristic, and tighter of linear programming or Lagrangian relaxation based lower bounds. For datasets where optimal results could be obtained using the MIP formulation, the ACO results were either optimal or very tight with an average relative gap of less than 0.5% from the optimal value. When comparing the ACO results to the best lower bound, the ACO results had an average relative gap of approximately 3%. In all cases, the ACO algorithm found better results than the IG heuristic. The results from my experiments indicate that the proposed ACO heuristic is very promising for solving CTAPs. (C) 2015 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available