Task Matching And Scheduling In Network Computing Environments Based On Genetic Algorithms

Task matching and scheduling plays an important role in network computing and makes a notable impact on the overall performance. Scheduling problems are known to be in general NP-complete, only sub-optimal can be obtained by classical scheduling approaches in most cases. Though the conventional single-population-based genetic algorithms (CSGAs) can find solutions with better quality than classical approaches for scheduling problems, the efficacy and efficiency of CSGA decrease with the number of tasks. This paper studied task matching and scheduling algorithms using improved genetic algorithms for network computing by means of theoretical analysis and simulation experiments.We first proposed a general genetic algorithm for task matching and scheduling in homogeneous network environments. Three genetic operators, such as improved crossover, internal crossover and migration as a kind of mutation, were designed based on permutation representation. Horizontal partition for initial population construction can guarantee the feasibility and quality of initial solution. A large mount of experiments had been performed to obtain a range of main control parameters settings for proposed algorithm.CSGA for task matching and scheduling is not scalable for multiple independent decomposable tasks. The computational model of cooperative coevolution is addressed, which simulates the process of natural coevolution among species. When solving independent problems, the mathematical analysis shows that when a schema whose fitness is higher than the overall average fitness, the schema's exponential increase index of trials allocated in the next generations of coevolutionary genetic algorithm (CGA) is higher than that of CSGA. To deal with dependent problems with epistatic interactions, Experimental study of CGA for NK landscape problem is given.Following the study of the computational model of cooperative coevolution, a CGA is then designed to match and schedule multiple decomposed tasks in homogeneous network environments. The work includes the combination of sub-schedules into a whole with heuristic, and the individual's fitness computation, etc.Simplified model and general model are the two types of network heterogeneous computing discussed. In the general model there are many factors effecting the algorithm of task matching and scheduling, such as data dependencies among tasks, processor's processing speed, topology of network connectivity,communication protocol and bandwidth, volume of transferring data, etc. In each model, we proposed two genetic algorithms for task matching and scheduling, one is for single decomposed task, the other as a CGA is for multiple independent tasks. This dissertation presented serial genetic algorithms for task matching and scheduling from single decomposed task in homogeneous environments to multiple independent tasks in heterogeneous environments. Theoretical analysis and simulation experiments showed that those algorithms are more efficient and effective for task matching and scheduling than traditional List scheduling approach and the existing CSGAs.