Research On Task Scheduling Algorithms For Distributed Systems Based On Computational Intelligence

Parallel and distributed process have always been the hot area of current scientific and technological research,development and application;they are an important way to solve the problems in the fields of scientific calculation and data service processing in terms of weather forecast,simulation of nuclear explosion and electron collision,calculation of Reynolds number for wind tunnels and financial services.And a key aspect of distributed computing is how to achieve resource sharing.Without the sharing of resources,distributed computing will be unfounded.And task scheduling is essential to resource sharing.Therefore,it is theoretically and practically significant to study the task scheduling algorithm for the distributed system.Scheduling is NP-hard.Many of the existing heuristic methods are unsatisfactory in term of optimization.So the parallel processing of the distributed system is underused.With the advancement in artificial intelligence,the theory of computational intelligence is widely used as a solution to many complex problems in the domains of the environment,economy,and management.This subject investigates the algorithms for computing the behaviors of the human and biological intelligence in order to provide new search and classification methods.In this paper,we overcome the disadvantages of the traditional methods in self-adaption and combinatorial optimization by introducing the classic techniques in computational intelligence to distributed computing as a solution to task scheduling.The main work and contributions are as follows.(?)For the multi-user network applications in the distributed system,we transform the dynamics of tasks and resources into random distribution,and define the scheduling problem based on the queuing theory as a nonlinear programming problem.But this method is only applicable to specific distributions and lacks in adaptability.Thus,the machine learning method is introduced to define the scheduling as a Markov decision process.And we propose a scheduling algorithm that can adapt to the dynamics of task arrival and resource performance.Compared to the first method,this approach achieves improved scheduling performance by adapting to uncertainties in the distributed system.The proposed algorithm is highly robust and adaptable,and reduces the average response time of the scheduled tasks.(?)The centralized scheduling policy above is applicable to the small-scale distributed system.But distributed scheduling is more common in the large scale environment.Thus,we devise a multi-layer multi-role framework for scheduling tasks based on resource properties.In the distributed scheduling,the scheduler has to adapt to randomness of the task arrival,variability of the system loads,and the impact of other schedulers' distribution policies.For the collaborative scheduling,we define it as a Markov decision process according to the interrelation among task flows,and propose a scheduling algorithm for intensifying learning correspondingly.The proposed algorithm enables the schedulers to learn the knowledge about task arrival and execution,and adapt to neighboring schedulers' distribution policies.For selfish scheduling,we establish a non-collaborative game model,and propose a distributed learning algorithm based on the Nash equilibrium joint scheduling policy.The proposed method achieves excellent performance in expected response time of tasks and fairness.(?)Data localization is not considered in the scheduling models of the two algorithms above.But many data-intensive applications in the grid need to access storage resources frequently in the process of computation.So how to jointly schedule the resources of computation and storage is essential.For data-intensive grid applications,we propose a scheduling model that can compute and store resources.This model divides the traditional scheduler into three layers,each of which plays a different role.The first layer collects information as the general scheduler.The second and third layers contain many small scheduling units that enable applications to be scheduled in parallel.On this basis,the parallel genetic algorithm and tabu search algorithm are proposed as an approach to the selection of task scheduling and resource storage for the distributed system.Shorter time consumption of applications in total is achieved.(?)Heterogeneity of resources is another factor that has to be considered in the scheduling model.Uncontrollable applicability is an important feature of resources in the distributed environment.How to improve the system's applicability to satisfy the requirements of more applications is a new question that scheduling should address.Thus,we formulate the optimization of both makespan(scheduling length)and applicability.First,we develop a formal model of finish time of system tasks and applicability,and define scheduling as an integer programming problem.Then,given the knowledge of computing resources and task applicability,and based on ant colony optimization,we propose a task scheduling algorithm that can minimize makespan while satisfying the applicability requirements of applications.At last,by using the scheduling schemes based on the above algorithms,we present the task immigration conditions and optimization methods that optimize both makespan and applicability.This optimization can maximize system applicability without lengthening the makespan.This proposed algorithm is effective in optimizing task finish time and system applicability for the distributed system of heterogeneous applicability.