Home > IEEE Papers > Ant Colony Algorithm for Job Scheduling in Grid Computing

Ant Colony Algorithm for Job Scheduling in Grid Computing

Ant Colony Algorithm for Job Scheduling in Grid Computing
Abstract – Scheduling jobs to resources in grid computing is complicated due to the distributed and heterogeneous nature of the resources. Stagnation in grid computing system may occur when all jobs require or are assigned to the same resources. This will lead to resources having high workload and stagnation may occur if computational times of the processed jobs are high. This paper proposed an enhanced ant colony optimization algorithm for jobs and resources scheduling in grid computing. The proposed ant colony algorithm for job scheduling in the grid environment combines the techniques from Ant Colony System and Max – Min Ant System. The algorithm focuses on local pheromone trail update and the trail limit values. A matrix is used to record the status of the available resources. The agent concept is also integrated in this algorithm for the purpose of updating the grid resource table. Experimental results obtained showed that this is a promising ant colony algorithm for job scheduling in grid environment.

Essential matter : There are two types of scheduling

(1) Static scheduling: Where jobs are assigned to suitable resources before their execution begin.

(2) Dynamic Scheduling: Reevaluation of status of the resources is allowed even if jobs have been assigned to those resources, and can trigger job migration and interruption based on the status of the system and workload.

Jobs submitted to a grid computing system need to be processed by the available resources. Best resources in term of processing speed, memory and availability status are more likely to be selected for the submitted jobs during the scheduling process. Ant Colony algorithm has been used in this paper as an effective method for solving this scheduling issue.

ACO is inspired by a colony of ants that work together to find the shortest path between their nest and food source. Every ant will deposit a chemical substance called pheromone on the ground after they move from the nest to food sources and vice versa. Therefore, they will choose the shortest or optimal path based on the pheromone value. The path with high pheromone value is shorter than the path with low pheromone value. This behavior is the basis for a cooperative communication.

Balanced job assignment based on ant algorithm for computing grids called BACO was proposed by “Balanced Job Assignment Based on Ant Algorithm for Grid Computing,”

BACO algorithm chooses optimal resources to process the submitted jobs by applying the local and global pheromone update technique to balance the system load. Local pheromone update function updates the status of the selected resource after job has been assigned and the job scheduler depends on the newest information of the selected resource for the next job submission. Global pheromone update function updates the status of each resource for all
jobs after the completion of the jobs. By using these two update techniques, the job scheduler will get the newest information of all resources for the next job submission.

An ant colony optimization for dynamic job scheduling in grid environment,” International Journal of Computer and Information Science and Engineering, vol. 1(4), pp. 207-214, 2007,  considered initial pheromone value of each resource based on expected execution time and actual execution time of each job, and process to update the pheromone value on each resource is based on local update and global update rules as in ACS. In that study, ACO algorithm performed the best when compared to First Come First Serve, Minimal Tardiness Earliest Due Date and Minimal Tardiness Earliest Release Date techniques.

“A Bio-inspired Adaptive Job Scheduling Mechanism on a Computational Grid,” International Journal of Computer Science and Network Security (IJCSNS), vol. 6(3), pp. 1-7, 2006, minimize the execution time of the computational jobs by effectively taking advantage of the large amount of distributed resource. The pheromone value of each resource depends on their execution time. Resources with higher execution value gets large number of pheromone.

“An improved ant algorithm for job scheduling in grid computing,” presented at Proceedings of the Fourth International Conference on Machine
Learning and Cybernetics, vol. 5, pp. 2957-2961, 2005, The strength of pheromone of each resource will be updated after completion of the job. The
encouragement and punishment and local balancing factor coefficient are defined by users and are used to update pheromone values of resources. If a resource completed a job successfully, more pheromone will be added by the encouragement coefficient in order to be selected for the next job execution. If a resource failed to complete a job, it will be punished by adding less pheromone value.

This paper proposes ACS is the most popular variant of ACO that has been successfully used in gridcomputing environment to solve the scheduling problems which eventually reduce the stagnation problem. This is a fertile area of research for the improvement of grid resource management with new or enhanced ACS algorithm for job scheduling. This study proposed a new pheromone initializing process which is different from [A Bio-inspired Adaptive Job Scheduling Mechanism on a Computational Grid,” International Journal of Computer Science and Network Security (IJCSNS), vol. 6(3), pp. 1-7, 2006], where the consideration was only on the condition of the resource. The scheduling process in [“An ant colony optimization for dynamic job scheduling in grid environment,” International Journal of Computer and Information Science and Engineering, vol. 1(4), pp. 207-214, 2007]   has proposed resource with the lightest load to be assigned to  new submitted job regardless of the job size. This study will consider assigning new submitted jobs to resources that are suitable based on the resource processing ability as well as the characteristics of the jobs.

Proposed ACO for Grid load balancing

1) User will send request to process a job. Details about the job such as the total number of jobs, size of each job, and CPU time needed by jobs will be included in the request.

2) Grid resource broker starts to calculate the relevant parameter to schedule the job after receiving the message from the user. The information server also provides theresource information to grid resource broker.

3) The largest entry in the pheromone value (PV) matrix will be selected by proposed technique as the resource to process the submitted job. A local pheromone update is performed after a job is assigned to a resource.

4) A global pheromone update is performed after a resource completed processing a job.

5) The execution results will be sent to the user.

In this algorithm, an ant represents a job in the grid system. The grid resource broker will find available resources from grid information server. Ant will move randomly in grid system and check the status of each resource. Pheromone value on a resource indicates the capacity of each resource in grid system. Pheromone value will be determined by two types of pheromone update technique which are local pheromone update in ACS (Ant colony system) and global pheromone update in MMAS (Max Min ant system).

Advertisements
Categories: IEEE Papers
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: