An ant algorithm for balanced job scheduling in grids full report
#1

[attachment=13596]
[attachment=13597]
[attachment=13598]
[attachment=13599]
[attachment=13600]
[attachment=13603]
[attachment=13601]
CHAPTER 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 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.
The purpose of job scheduling is to balance the entire system load while completing all the jobs at hand as soon as possible according to the environment status. 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. For example, in BOINC, an open-source software for volunteer computing and grid computing, job scheduling is one of the most important key factors for achieving Teraflops performance . Because its importance, many job scheduling algorithms for grids have been proposed. Please refer to a survey, 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) 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, graph coloring problem, vehicle routing problem, and so on.
This paper applies the ACO algorithm to job schedule problems in Grid computing. 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. Finally, we compare the proposed BACO (Balanced ACO) algorithm with iACO (Improved ACO), FPLTF (Fastest Processor to Largest Task First), dynamic FPLTF, Sufferage, and random selection method in the experiments. According to the experimental results, we can find out that BACO is capable of achieving system load balance better than other job scheduling algorithms. 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 algorithm in job scheduling. Section 4 is the experimental results.
CHAPTER 2
RELATED WORK
2.1 Ant algorithms

There are many different kinds of ACO algorithm, i.e., Ant Colony System (ACS) , Max-Min Ant System (MMAS) , Rank-based Ant System (RAS) , Fast Ant System (FANT) and Elitist Ant System (EAS) .
ACS:
uses the pseudo-random proportional 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.
FANT:
employs one ant at each iteration and uses the solution of the ant to do a local search. FANT works without evaporation rule 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 in order to attract more ants to follow the best-so-far tour. There are many studies about job scheduling using ACO algorithm in grid environment such as [13]. It uses the basic idea of ACO, but changes the pheromone update rule by adding encouragement, punishment coefficient and load balancing factor.
In [20], Kwang Mong Sim et al. use multiple kinds of ant to find multiple optimal paths for network routing. The idea can be applied to find multiple available resources to balance resources utilization in job scheduling. The key of the idea is each different kinds of ant can only sense their own kind of pheromone so that it can find many different paths including the shortest-path by different kinds of ant. There are still some problems that if all kinds of ant find the same path, it will be the same as using one kind of ant. How to compare the performance for each kind of ant creates another problem. Furthermore, one solution from this algorithm may work efficiently in an environment, but it may work inefficiently in another one.
J. Heinonen et al. apply the hybrid ACO algorithm with different visibility to job-shop scheduling problem. The hybrid ACO algorithm consists of two ideas. One idea is the basic ACO algorithm, and the other idea uses the post-processing algorithm in the part of local search in ACO algorithm. When the ACO algorithm finished, all ants complete its own tours. A tour can be decomposed into blocks. The block for swap must contain more than two operations. Then the post-processing algorithm uses the swap operation on the blocks. If the swap refines the makespan, the new path is accepted; otherwise the swap is invalid and the swapped block reverts to previous status. The ACO algorithm has also been applied to hard combinatorial optimization problems such as traveling salesman problem (TSP) [10], flow shop problem [22], project presentation scheduling [23], graph coloring problem, vehicle routing problem, and nurse scheduling, and so on.
2.2 Job scheduling in grids
Job scheduling is well studied within the computer operating systems [25]. Most of them can be applied to the grid environment with suitable modifications. In the following we introduce several methods for grids.
The FPLTF (Fastest Processor to Largest Task First) [14] algorithm schedules tasks to resources according to the workload of tasks in the grid system. The algorithm needs two main parameters such as the CPU speed of resources and workload of tasks. The scheduler sorts the tasks and resources by their workload and CPU speed then assigns the largest task to the fastest available resource. If there are many tasks with heavy workload, its performance may be very bad. Dynamic FPLTF (DPLTF) [15] is based on the static FPLTF, it gives the highest priority to the largest task. DPLTF needs prediction information on processor speeds and task workload.
The WQR (Work Queue with Replication) is based on the work queue (WQ) algorithm [15]. The WQR sets a faster processor with more tasks than a slower processor and it applies FCFS and random transfer to assign resources. WQR replicates tasks in order to transfer to available resources. The amount of replications is defined by the user. When one of the replication tasks is finished, the scheduler will cancel the remaining replication tasks. The WQR’s shortcoming is that it takes too much time to execute and transfer replication tasks to resource for execution.
Min-min [26] set the tasks which can be completed earliest with the highest priority. The main idea of Min-min is that it assigns tasks to resources which can execute tasks the fastest. Maxmin [26] set the tasks which has the maximum earliest completion time with the highest priority. The main idea of Max-min is that it overlaps the tasks with long running time with the tasks with short running time. For instance, if there is only one long task, Min-min will execute short tasks in parallel and then execute long task. Max-min will execute short tasks and long task in parallel.
The RR (Round Robin) algorithm focuses on the fairness problem. RR uses the ring as its queue to store jobs. Each job in queue has the same execution time and it will be executed in turn. If a job can’t be completed during its turn, it will store back to the queue waiting for the next turn. The advantage of RR algorithm is that each job will be executed in turn and they don’t have to wait for the previous one to complete. But if the load is heavy, RR will take long time to complete all jobs.
Priority scheduling algorithm gives each job a priority value and uses it to dispatch jobs. The priority value of each job depends on the job status such as the requirement of memory sizes, CPU time and so on. The main problem of this algorithm is that it may cause indefinite blocking or starvation if the requirement of a job is never being satisfied.
The FCFS (First Come First Serve) algorithm is a simple job scheduling algorithm. A job which makes the first requirement will be executed first. The main problem of FCFS is its convoy effect [25]. If all jobs are waiting for a big job to finish, the convoy effect occurs. The convoy effect may lead to longer average waiting time and lower resource utilization.
CHAPTER 3
THE BALANCED ANT COLONY OPTIMIZATION (BACO) ALGORITHM

BACO inherits the basic ideas from ACO algorithm to decrease the computation time of jobs executing in Taiwan UniGrid [27] environment and it also considers about the loading of each resource. BACO changes the pheromone density according to the resources status by applying the local pheromone update and the global pheromone update functions. The purpose is to try to minimize the completion time for each job while balancing the system load.
3.1 System architecture
Fig 3.1 : system architcture[1]
The system architecture is shown in Fig. 3.1. There are four main components: Portal, Information Server, jobs Scheduler and grid resources. The Portal provides an interface to users for job execution. The Information Server collects resource information by using the NWS (Network Weather Service) [23]. The NWS demon reports system information back to Information Server periodically. The Jobs Scheduler selects the most appropriate
resources to execute the request according to the proposed BACO algorithm. Finally, the execution results would be sent back to the user.
3.2 The proposed BACO algorithm
In order to map the ant system to the grid system, we explain their relationships below:
A. An ant
An ant in the ant system is a job in the grid system.
B. Pheromone
Pheromone value on a path in the ant system is a weight for a resource in the grid system. A resource with a larger weight value means that the resource has a better computing power.
The scheduler collects data from Information Server and uses the data to calculate a weight value of a resource.
The pheromone (weight) of each resource is stored in the scheduler and the scheduler uses it as the parameters for BACO algorithm. At last, the scheduler selects a resource by a scheduling algorithm and it sends jobs to the selected resource by the APIs of the Globus Toolkit [29].
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
Popular Searches: new scheduling algorithm, under balanced drilling seminar, job scheduling in linux, ant hoc net seminar report, job scheduling in non multiprogrammed environment, ant colony algorithm job scheduling grid computing, balanced scorecard it strategy,

[-]
Quick Reply
Message
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  APRIORI Algorithm project report helper 1 10,882 07-02-2019, 10:19 AM
Last Post:
  computer networks full report seminar topics 8 42,014 06-10-2018, 12:35 PM
Last Post: jntuworldforum
  OBJECT TRACKING AND DETECTION full report project topics 9 30,650 06-10-2018, 12:20 PM
Last Post: jntuworldforum
  Vertical Handoff Decision Algorithm Providing Optimized Performance in Heterogeneous Wireless Networks computer science topics 2 30,168 07-10-2016, 09:02 AM
Last Post: ijasti
  imouse full report computer science technology 3 24,892 17-06-2016, 12:16 PM
Last Post: ashwiniashok
  Implementation of RSA Algorithm Using Client-Server full report seminar topics 6 26,606 10-05-2016, 12:21 PM
Last Post: dhanabhagya
  Optical Computer Full Seminar Report Download computer science crazy 46 66,331 29-04-2016, 09:16 AM
Last Post: dhanabhagya
  ethical hacking full report computer science technology 41 74,437 18-03-2016, 04:51 PM
Last Post: seminar report asees
  broadband mobile full report project topics 7 23,315 27-02-2016, 12:32 PM
Last Post: Prupleannuani
  steganography full report project report tiger 15 41,329 11-02-2016, 02:02 PM
Last Post: seminar report asees

Forum Jump: