Research On Grid Multiple QoS Constrained Scheduling Based On Ant Colony Optimization

The scheduling problem in grid proved to be NP-hard is a hot topic. Furthermore, the grid has the characters of dynamicity, distributiveness, heterogeneity, and autonomy, which make the grid scheduling more complex. Because Ant Colony Optimization has the characters of concurrency, expansibility and so on, it is suit to solve the grid scheduling. The quality of service (QoS) is also an important measure of the grid, thus, we should consider the users' requirement of QoS in scheduling.In this thesis, we present a model of multiple QoS constrain in grid. Focusing on the meta-task with multiple QoS dimensions and combining the Ant Colony Optimization, two Ant Colony Optimization for grid task scheduling of multiple QoS constrain is proposed (QACO and QIACO). QACO apply the Ant System to the grid of multiple QoS constrained scheduling. Because the ability of Ant System is limited and the performance will decline as to some larger scale computation, many improved Ant Colony Optimization were proved. Ant Colony Systems is one of the improved Ant Colony Optimization which has good performance. Combining random change local search to improve Ant Colony Systems, a grid multiple QoS constrained scheduling based on improved Ant Colomy Systems (QIACO) has been proposed. The proposed considering five kinds of QoS dimensions: time, reliability, version, security and priority which are transformed to utility as the heuristic information of the algorithm.We have done the simulation experiments and compared QACO, QIACO, improved Min-Min and QoS-Min-Min. The results have shown that QIACO performs better than others in both Makespan and total utility. We have described the details of how put the algorithm QIACO into grid environment. Because of the limit of time there are still some problems must be solved. We will implement QIACO and apply it into the real grid environment to prove its validity in the future.