Task Scheduling In Network Computing Environments Based On Intelligent Algorithms

Intelligent optimization algorithms are a class of bionic algorithms and are well characterized by its self-organizing, self-learning, self-adaptive, implicit parallelism and guided search, etc. These algorithms have the preponderance over solving complex issues and have been widely used in engineering technology, nonlinear optimization, structural design, parallel computing, social science as well as many other fields. By employing intelligent optimization algorithms, this paper studies task matching and scheduling for network computing. In order to make full use of the potential power of network computing system, tasks matching and scheduling is one of the critical challenges in this filed and is also NP-hard. Solving the problem is of great significance to the development and application of high performance computing.Considering the universality of intelligent optimization algorithms against the particularity of specific issues, the proposed algorithm adjusts evolution strategies and designs special operators. Based on common characteristics of the evolutionary algorithms, scheduling techniques and strategies for the network computing are further investigated. The main contents are as follows:(1) Ant Colony Optimization (ACO) algorithm is good at solving discrete problems, but the pheromone is very difficult to select. Using static and dynamic properties of task graphs as heuristic informations, the corresponding algorithms are designed and the excellent performances of these algorithms are demonstrated by the experiment results. By analyzing the performances of the proposed algorithms, the selection strategies and the implementation principles of heuristic informations are further studied. Moreover, a parallel scheduling algorithm is designed and implemented under the MPICH supporting environment. Distinct parallel techniques are analyzed to find how the parallel performance is affected. The strategy and frequency of the information exchanges among the parallel colonies are studied to further improve the performance and speed.(2) In response to characteristics of evolutionary algorithms in solving combinatory problems, different solution encoding and decoding methods are investigate and feasible evolution operation is designed for the search process of the algorithms. Based on Differential Evolution algorithm (DE), the scheduling algorithms of the two encoding structures are designed for homogeneous system and the scheduling performances of two methods are compared. Special crossover and mutation operator are designed to fit in with the specific problem, and initial value is obtained by stochastic topological sorting for permutation-based method. In order to improve the solution quality and the global search capability, local search strategy is integrated to accelerate the convergence of the algorithms. Experiments show that the two encoding methods can effectively solve the scheduling problem, and permutation-based method is superior to priority-based method.(3) Based on permutation-based method, the particle swarm optimization (PSO) is utilized to tackle with the scheduling problem in heterogeneous environments. By designing specific-problem operators, the algorithm can be guaranteed to provide high-quality solutions in acceptable time and avoid using the mean values which led to the unreasonable schedule in other algorithms. Quantum-behaved PSO (QPSO) algorithm is a modification of the standard PSO algorithm, and it has fewer parameters to control and can be demonstrated mathematically to be a global convergent algorithm. Combining spatial information, hybrid quantum-behaved PSO algorithm for tasks scheduling is proposed based on priority-based method to improve the performance and tests verify the effectiveness of the proposed algorithm.(4) Considering the key issues of tasks matching and scheduling in dynamic heterogeneous environments, a static scheduling algorithms is proposed under the model of Grid computing; On the basis of dynamic characteristics of jobs and the autonomy of resources in grid environments, a dynamic self-adaptive tabu search algorithm for tasks scheduling is developed, which can self-adaptively adjust algorithm parameters, and make a real-time response to the dynamic changes of the grid. Finally, implementing the scheduling algorithm in GridSim simulation environment, satisfactory results are obtained.