Research On Grid Workflow Scheduling Based On GAPSO Algorithm

Grid computing has been recognized as the next major computing platform for wide-area parallel and distributed computing since the mid nineties of the last century, you can achieve full share for computing, information, data, storage, knowledge and other resources. The combination of grid computing and workflow management has led to the powerful concept of grid workflow, which is now becoming the driving force for the solutions of the next generation of distributed and collaborative workflow system. In the last few years, the service-oriented technology research has became the trend in grid technology. The introduction of QoS into grid workflow allows the grid resources to be organized and distributed according to the user's requirements. During the execution of the workflow, the scheduler chooses member services based on Qos. Concerned about the large-scale resources and tasks, grid workflow scheduling is one of the most complex and challenging issues, which directly affects the success and efficiency of grid workflow execution. This thesis considers improving the grid workflow performance by two aspects:modeling of grid workflow and the improving of the algorithm of the grid job scheduling.Multiple situations like selection route and parallel route exist in the practical workflow. In the thesis, DAG modeling was used to indicate the job scheduling process of grid workflow based on simple, intuitive trait of DAG. In the workflow based on DAG, node indicated the activity or status, directed arc indicated the timing dependence relationship between nodes, the weight of arc indicated attributes and parameter. In order to resolve the multiple optimization problem in the job scheduling process of grid workflow, a kind of architecture based on multiple QoS standard was proposed, the parameter of QoS was re-defined and an analysis of QoS measurement with different restraint relationship structure was focused on. Besides that, a GAPSO hybrid algorithm was proposed based on the Genetic Algorithms (GA) and Particle Swarm Optimization (PSO). Within the hybrid algorithm, a special fitness function is quoted, crossover and mutation probability in the part of GA are set dynamically, methods of dynamically switching between algorithms and termination of the whole algorithm are proposed, as well as the setting of inertial weight was improved and a way of particle dispersion was proposed in the PSO part. Combining the advantages of the two algorithms, the hybrid algorithm uses the global search ability of GA to optimize the search in the beginning, and uses the fast-speed convergence ability of PSO to speed up the convergence rate in the latter part.In this thesis, MATLAB was used to simulate, and three experiments were designed. First of all, in order to reduce the error resulted from parameter value, based on the same initial generation population, different hybrid algorithm switch coefficients were tried to evaluate the average fitness value of last generation population, then choose the optimal value. Secondly, a specific grid workflow case was hypothesized and the solving of the optimal solution was proof of the algorithm, which was better to fit the complexity of the grid environment and could meet the different needs from customers. At the last, compared to other algorithms applied in the grid workflow scheduling, with the situation of different services, the GAPSO has the advantage on time execution. The experiment results indicated the hybrid algorithm has the ability to address grid workflow scheduling problem more effectively and efficiently.