An Object-Adjustable Heuristic Scheduling Strategy in Grid Environments

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.