网格环境下一种可调目标的启发式调度策略

An Object-Adjustable Heuristic Scheduling Strategy in Grid Environments

针对网格环境下不同类型的任务执行时间相差较大的问题,提出了基于任务平均执行时间的忍耐度的概念,重新构造了启发式规则,体现了任务QoS的要求;并将这种服务质量的需求与任务完成时间相结合,给出了一个可调节的局部目标函数,实现了一种基于任务完成时间和任务服务质量的启发式调度算法OA-Sufferage;最后,给出了服务率(service ratio)的概念和定义,定量地衡量任务得到的服务质量.实验结果表明,该策略优先调度那些等待时间相对于执行时间较大的任务,提高了任务的服务率;而且可以通过调节局部目标函数中的偏好因子(preference factor),追求任务完成时间和QoS的不同目标,更加适合开放复杂的网格环境.

Task scheduling in grid environments is much more challenging because grid is a distributed, heterogeneous and dynamic system. Focusing on the fact that the tasks involved in such grid environments may have quite different execution time depending on their types, the concept of sufferage based on mean execution time, which considers the requirement of QoS, is introduced to serves as the new heuristic of task scheduling. Besides, the notion and definition of service ratio are given to measure this kind of QoS quantitatively. Furthermore, by incorporating the QoS with the makespan of tasks, a local objective function, which can be adjusted, is proposed and a corresponding heuristic scheduling strategy based on the function is presented to satisfy the different demands of task scheduling. Simulation results confirm that this object-adjustable scheduling algorithm can improve the QoS of tasks by giving higher priority to the tasks with larger waiting time relative to execution time, and can trade off two objectives, makespan and QoS, by adjusting the preference factor in the local objective function. Therefore, it is more flexible than most of the existing task scheduling algorithms since they are always fixed-objective and more suitable for the complex grid environments.