Font Size: a A A

The Research Of Ant Colony Optimization In Task Scheduling Problems

Posted on:2008-08-17Degree:MasterType:Thesis
Country:ChinaCandidate:G J YuFull Text:PDF
GTID:2178360215974793Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
In recent time, parallel and distributed computation is one of the main challenging areas in the development of computer technology. It is also a focus of the research in computer science. The scheduling problem is a bottleneck in the parallel and distributed computation. This problem greatly affects the parallel computing capability and the performance of the parallel system. A good scheduling algorithm can take full advantage of the computing capability of each processor in the system, and can improve the efficiency of the parallel and distributed computation. The efficiency of the parallel and distributed system will be decreased if the tasks in the system could not be scheduled properly.Since the mid-1950's, when Bionics was advanced, many new evolutional algorithms and heuristic random-search algorithms have been presented. Among these optimization algorithms, Ant Colony Optimization (ACO) algorithm is an optimization method inspired from the mechanism of bionics. ACO algorithm is stable, distributed and can easily be combined with other heuristic optimization methods. The ACO has been applied in many combination optimization problems. It has demonstrates its strong capacity in combination optimization and discrete optimization etc.Scheduling is essentially a problem of combination optimization and discrete optimization. The strong optimization capacity of ACO algorithm on solving the discrete optimization suggests the feasibility to solve the scheduling problem using the ACO algorithm.This paper focuses on the research of applying ant colony optimization in task scheduling problems. We first illustrate the definition, model and existing research results of scheduling problem and the ACO algorithm. Then we discuses and analysis some recently presented algorithms for solving scheduling problems so as to set up a theoretical foundation for applying the ACO algorithm to solve scheduling problems.In this paper three algorithms for solving scheduling problem are presented: the ACO algorithm for solving the scheduling problem, the hybrid ACO algorithm to solve the problem and the ACO algorithm for solving the time-restrict scheduling problem in the real-time system. The main contributions and innovations of this paper are as follows.1. This paper presents an ACO algorithm for solving the scheduling problem. The algorithm uses an AOE (Active on Edge) graph on the basic of the DAG to express the topological order of these tasks. In this graph, each edge presents a task, the weight of the edge expresses the computation time of this task. The AOE can demonstrate the relation ship of these tasks better than DAG. It is also suitable for using the artificial ants to travel and search the optimal solution. When the ants select the paths, the algorithm provides the probability function which takes many of factors into a count, such as the length of critical path, the earliest start time and latest start time of tasks. It can extend the search space for the ants and prevent the local optimization of results. Finally the paper defined the pheromones as the"cooperative degree"of tasks to accelerate the convergence of the algorithm2. The article presents a Task-Allocation Model (TAM) which adapt to the ACO algorithm. This model is suitable for the characters of scheduling problems, and has good extensibility and agility. Based on the TAM, the paper presents a job scheduling algorithm (JSA) to solve the scheduling problem. To overcome the drawbacks of ACO such as low constringency, local optimization, the paper presents a hybrid ACO algorithm named as Improved Job-Scheduling Algorithm by using genetic operators. This algorithm can sufficiently exert the excellences of the ACO and the genetic algorithm. It not only has better search efficiency, but also ensures the global optimization of results. To make a foundation for further research, the paper also discusses the possibility of applying design TAM on dynamic task scheduling problems.3. The paper presents a new ACO algorithm for Deadline Scheduling Problem (ADSD). First, the algorithm extends the DAG and generates an extensible DAG. The ants travel in the graph so to generate a topological order of all tasks. The algorithm consists of two type optimizations including the optimization of tasks order and the optimization of the strategy of assigning the processors. Therefore the algorithm provides two probability formulas and two types of pheromones. This algorithm can not only ensure the tasks which have the earliest deadline to have the highest priority of scheduling, but can avoid the local optimization by using choosing probability.The experiment results of the three algorithms above illuminate that our algorithms can get better scheduling strategy than other algorithms in shorter time. Furthermore, our algorithms also have better robustness and flexibility.
Keywords/Search Tags:ACO, Scheduling, Task-Allocation Model, DAG, deadline-restriction
PDF Full Text Request
Related items