Research Of Task Scheduling Based On Invasive Weed Optimization Algorithm In Heterogeneous Cluster Systems

In recent years,a large number of cluster system emerged with the rapid development of the parallel computing,and have become to be the major platform of high performance computing because of its superior performance?low cost?strong scalability and high reliability.For this reason,research on cluster performance-related issues has increasingly attracted the attention from scholars.Especially,the task scheduling problem is a hot spot for its critical impact on cluster performance.For the task scheduling problems under cluster environment,many effective scheduling strategy have been proposed,such as heuristic algorithm based on table scheduling:EFT(Earliest Time First)?CPOP(Critical Path ON a Processor),as well as intelligent optimization algorithms:GA(Genetic Algorithm)?PSO(Particle Swarm Optimization)?ACO(Ant Colony Optimization),and so on.These algorithms have their own characteristics:heuristic algorithms generally have lower time complexity and higher efficiency,but poor optimization and low robustness;while intelligent optimization algorithms usually have strong searching capability and excellent robustness,but complicated structure and high time complexity.In addition,most of these algorithms that have been proposed are based on the homogeneous computing environment,but for the heterogeneous cluster environment have less been involved.This paper introduces the concept,characteristics and objectives of task scheduling problems under heterogeneous cluster environment.Then,some research is made on the DAG(Directed Acyclic Graph)model which is proposed for dependent task scheduling problem.This paper also proposes a new task scheduling algorithm,named IWOTS(IWO Task Scheduling)for heterogeneous cluster environment based on a new type of bionic intelligent optimization algorithm,IWO(Invasive Weed Optimization).This algorithm combined IWO's advantages of optimization ability,convergence performance,robustness and HEFT's characteristics of high efficiency and low complexity.Experiments show that,IWOTS performs better than HEFT and GA on the aspects of optimal solution quality,robustness and feasibility.In the end,this paper proposes an algorithm,named IWOAP(Invasive Weed Optimization using Avoid Precocity strategy)for the premature problem of IWO algorithm.This algorithm has made optimization and improvement on IWOTS using individual aging,concentration control and herbicide strategy.Experiments show that IWOAP effectively prevent the premature phenomena in algorithm,and improves the optimization ability.IWOAP has obvious advantage in convergence performance and robustness.Experiments show that WIOAP has improved IWOTS in the convergence performance and optimization quality.