QIACO:一种多QoS约束网格任务调度算法

QIACO:An Algorithm for Grid Task Scheduling of Multiple QoS Dimensions

网格环境下的任务调度问题属于NP难解,难以得到精确的最优解,适合使用蚁群算法等智能优化算法对最优解进行逼近;同时,服务质量(QoS)也是衡量网格性能的一个重要指标,网格任务调度应该满足用户的QoS需求.为解决具有QoS保证的网格任务调度问题,本文以带有QoS约束的任务为研究对象,结合改进的蚁群算法,提出了一种基于蚁群算法的多QoS约束网格任务调度算法(QIACO).QIACO将蚁群算法用到网格任务调度问题中,具体考虑了5种QoS约束,并将QoS约束转换成效用,提出了多约束QoS任务调度模型.同时,本文改进了蚁群算法的搜索策略、决策规则和信息素更新策略,使总效用值即用户满意度达到最大.理论分析和仿真实验表明QIACO无论是在Makespan方面,还是在总效用方面都相比同类算法有较大的优势.

Task scheduling problem in grid is NP-hard,and it is difficult to attain an optimal solution,so we can use intelligent optimization algorithms to approximate the optimal solution（for example ant colony optimization）.Moreover,Quality of Service（QoS）is also an important factor in determining the performance of grid.Task scheduling needs to satisfy user′s QoS requirements.In this paper,we propose a novel Multiple QoS Dimensions（QIACO） algorithm for Grid Task Scheduling which is based on modified ant colony optimization algorithm and focuses on the task with QoS dimensions.The QIACO strategy use the ant colony algorithm to solve the task scheduling problem of grid,specifying 5 kinds of QoS dimensions and transforming the QoS to utility,and ultimately,representing the model of task scheduling with multiple QoS dimensions.At the same time,we improve many aspects of the ant colony algorithm,such as the search strategy,decision rule,pheromone update strategy of ant colony optimization,in order to maximize the user′s satisfaction.QIACO shows a significant improvement in both makespan and total utility according to the theoretical analysis and simulation.