A Novel ACO-Based Static Task Scheduling Approach for Multiprocessor Environments

DOI

10.1080/18756891.2016.1237181How to use a DOI?

Keywords

Ant colony optimization (ACO); metaheuristics; multiprocessor task scheduling; parallel and distributed systems

Abstract

Optimized task scheduling is one of the most important challenges in parallel and distributed systems. In such architectures during compile step, each program is decomposed into the smaller segments so-called tasks. Tasks of a program may be dependent; some tasks may need data generated by the others to start. To formulate the problem, precedence constraints, required execution times of tasks, and communication costs among them are modeled using a directed acyclic graph (DAG) named task-graph. The tasks must be assigned to a predefined number of processors in such a way that the program completion time is minimized, and the precedence constraints are preserved. It is well known to be NP-hard in general form and most restricted cases; therefore, a number of heuristic and meta-heuristic approaches have so far been proposed in the literature to find near-optimum solutions for this problem. We believe that ant colony optimization (ACO) is one of the best methods to cope with such kind of problems presented by graph. ACO is a metaheuristic approach inspired from social behavior of real ants. It is a multi-agent approach in which artificial ants (agents) try to find the shortest path to solve the given problem using an indirect local communication called stigmergy. Stigmergy lets ACO to be fast and efficient in comparison with other metaheuristics and evolutionary algorithms. In this paper, artificial ants, in a cooperative manner, try to solve static task scheduling problem in homogeneous multiprocessor environments. Set of different experiments on various task-graphs has been conducted, and the results reveal that the proposed approach outperforms the conventional methods from the performance point of view.

Copyright

© 2016. the authors. Co-published by Atlantis Press and Taylor & Francis

Open Access

This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Download article (PDF)
View full text (HTML)

TY  - JOUR
AU  - Hamid Reza Boveiri
PY  - 2016
DA  - 2016/09/01
TI  - A Novel ACO-Based Static Task Scheduling Approach for Multiprocessor Environments
JO  - International Journal of Computational Intelligence Systems
SP  - 800
EP  - 811
VL  - 9
IS  - 5
SN  - 1875-6883
UR  - https://doi.org/10.1080/18756891.2016.1237181
DO  - 10.1080/18756891.2016.1237181
ID  - Boveiri2016
ER  -