| Heterogeneous multiprocessor system consists of a set of processors with different processing capacities. Task scheduling is a crucial factor in improving the efficiency of this system. It needs to resolve the problem of how to allocate tasks to different processors so that the system can obtain the highest performance. Traditional scheduling algorithms face new challenges because of the heterogeneousness, complexity and flexibility of the heterogeneous multiprocessor system. Therefore it is very important and realistic to put forward a better scheduling algorithm, which can make full use of all kinds of resources and improve the throughput and resource utilization of heterogeneous multiprocessor system based on analyzing the existing algorithms.Particle Swarm Optimization algorithm is a new kind of modern heuristics algorithm and it is well characterized by its self-organizing, self-learning, self-adaptive characteristics and the implicit parallelism and guided search, which is often used to solve different kinds of NP-complete problems and complex task scheduling problems. Some simulation experiments have confirmed that Particle Swarm Optimization algorithm has more advantages compared with traditional scheduling algorithms in dealing with task scheduling problem.This paper has made a thorough research on the task schedule policy and algorithm of the heterogeneous multiprocessor system, and made some exploration and innovation based on the previous studies. Some new results are established and developed. The innovative points have been illustrated in the following part.( 1 ) Considering the issues of independent tasks matching and scheduling of the heterogeneous multiprocessor system, an improved Particle Swarm Optimization (IPSO) algorithm is presented to enhance the ability of searching optimal solution. When calculating the fitness function, the paper makes rounded operation of the value of particle location to make PSO algorithm better apply to discrete areas. A performance index is established by analyzing the computation ability of each processor. Adjusting method on inertia weight is presented to improve the global convergence and overcome the defect that the searching ability of particle is decreasing during the later stage of iteration. The results show that our improved algorithm is able to find better schedule quality in a shorter time than other PSO algorithms.(2)Considering the issues of directed acyclic graph tasks matching and scheduling in heterogeneous multiprocessor system, a hybrid particle swarm optimization (HPSO) algorithm is presented to enhance the ability of searching optimal solution. An optimization mathematical model of multiprocessor scheduling problem is established in this paper. The concept of Swap Operator is introduced to construct a kind of special particle swarm optimization algorithm, which makes PSO algorithm apply to discrete areas. Then Hill-climbing algorithm is presented to overcome the defect of its precocious convergence and bad local optimization ability, which can improve the solution quality and accelerate the convergence of the algorithms. Compared with TPSO and Genetic Algorithm, our improved algorithm is able to find better schedule quality in a short time and is especially useful in solving the heterogeneous multiprocessor scheduling problem with a number of tasks and processors.The task scheduling problem is NP-complete problem. It can shorten the completion time and improve the efficiency of the heterogeneous multiprocessor system with the characteristics of parallelism and global solution space when using the particle swarm optimization algorithm to solve the task scheduling problem. The research result of this thesis is valuable for spreading the application of particle swarm optimization algorithm. |
PDF Full Text Request