Author Topic: Balanced Ant Colony Algorithm for Scheduling DAG to Grid Heterogeneous System  (Read 1878 times)

0 Members and 1 Guest are viewing this topic.

IJSER Content Writer

  • Sr. Member
  • ****
  • Posts: 327
  • Karma: +0/-1
    • View Profile
Quote
Author : Mrs. Smitha Jha,Dr. D. K. Mallik,Dr. R.K. Suri
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011
ISSN 2229-5518
Download Full Paper : PDF

Abstract- Ant Colony Optimization can be used for scheduling tasks on resources in Grid. In earlier work this technique has been applied for independent task scheduling. This paper applies the above technique for dependent task scheduling. Here a hybrid algorithm by Sakellariou can be applied, where tasks in DAG (Directed acyclic graph) are upward ranked and sorted decreasingly. Then the sorted tasks are grouped along the sorted sequences and in every group, tasks are independent. Then independent task groups can be scheduled to resources using algorithm specified by author Chang.
Index Terms – Grid System, Directed Acyclic graph(DAG),Independent, Dependent task scheduling, Ant Colony Optimization, Grouping, Ranking.
 
1 INTRODUCTION
Current scientific problems are very complex and need huge computing power and storage space. The past technologies such as distributed or parallel computing are unsuitable for current scientific problems with large amounts of data. Processing and storing massive volumes of data may take a very long time. Grid computing [3] is a new paradigm for solving those complex problems. In grids, we need to consider the conditions such as network status and resources status. If the network or resources are unstable, jobs would be failed or the total computation time would be very large. So we need an efficient job scheduling algorithm for these problems in the grid environment. Because the environment status may change frequently, traditional job scheduling algorithm such as ‘‘First Come First Serve’’ (FCFS), ‘‘Shortest Job First’’ (SJF), etc., may not be suitable for the dynamic environment in grids.

In grids, users may face hundreds of thousands of computers to utilize. It is impossible for anyone to manually assign jobs to computing resources in grids. Therefore, grid job scheduling is a very important issue in grid computing.
Please refer to a survey [3], which also poses some open issues. A good schedule would adjust its scheduling strategy according to the changing status of the entire environment and the types of jobs. Therefore, a dynamic algorithm in job scheduling such as Ant Colony Optimization (ACO) [4,5] is appropriate for grids. ACO is a heuristic algorithm with efficient local search for combinatorial problems. ACO imitates the behavior of real ant colonies in nature to search for food and to connect to each other by pheromone laid on paths traveled. Many researches use ACO to solve NP-hard problems such as traveling salesman problem [6],graph coloring problem [7], vehicle routing problem [8], andso on. In [1]  this technique has been applied for independent task scheduling. This paper apply the above technique for dependent task scheduling. Here a hybrid algorithm by Sakellariou[2] can be applied,where tasks in DAG(Directed acyclic graph) are upward ranked and sorted decreasingly. Then the sorted tasks are grouped along the sorted sequences and in every group,tasks are independent. We assume each job is an ant and the algorithm  sends the ants to search for resources. We also modify the global and local pheromone update functions in ACO algorithm in order to balance the load for each grid resource.
The rest of the paper is organized as follows. Section 2 introduces the related work about many kinds of ACO algorithm and job scheduling in grids. Section 3 details the proposed ACO optimization algorithm, its pseudocode and algorithm analysis in job scheduling for dependent task scheduling. Section 4 gives the comparison of proposed algorithm with other existing methods in terms of time complexity. Section 5 concludes paper and Section 6 lists references.

2.RELATED WORK:

2.1. Ant algorithms
There are many different kinds of ACO algorithm, i.e., AntColony System (ACS) [6], Max-Min Ant System (MMAS) [9],Rank-based Ant System (RAS) [10], Fast Ant System (FANT) [11] and Elitist Ant System (EAS) [12]. ACS uses the pseudo-randomproportional rule to replace state transition rule for decreasing computation time of selecting paths and update the pheromone on the optimal path only. It is proved that it helps ants search the optimal path.MMAS is based on the basic ACO algorithm but limiting the pheromone range to be greater than or equal to the low bound value (Min) and smaller than or equal to the upper bound value(Max). The low bound and upper bound are defined by the user.According to the low bound and upper bound values, MMAS could avoid ants to converge too soon in some ranges.
In the design of RAS, it sorts the ants by ant’s tour length in ascending order after all ants completed their tours. It means that the first ant finds the shortest path to complete the tour and the last ant takes the longest tour. They give each ant a different density of pheromone to update their path by the ascending order: the higher the position of the ant, the more pheromone it could update; the lower the position of the ant, the less pheromone it has. By the idea of RAS, the shortest length gets more pheromone to attract more ants to follow and the system could get the optimal solution very soon, and it updates pheromone after each iteration. In order to avoid the sub-optimal solution, it applies a reset pheromone function.EAS update more pheromone on the best-so-far tour found inorder to attract more ants to follow the best-so-far tour.

Read More: Click here...