A comparison of static QoS-based scheduling heuristics for a meta-task with multiple QoS dimensions in heterogeneous computing

Abstract

The problem of scheduling a set of independent tasks (a meta-task) with multiple QoS needs, such as Timeliness, Reliability, Versions, Security and Priority, in a Heterogeneous Computing (HC) environment is referred to as the QoS-based scheduling problem. Several heuristics have been proposed in the literature to solve the QoS-based scheduling problem, which is proven to be NP-hard. Selecting the best heuristic to use in a given HC environment is not trivial, since each heuristic makes different assumptions about the underlying QoS model. This paper performs a comparative study of five such heuristics, namely QSMTS-IP, Min-min, Genetic Algorithm, Least Slack First and Sufferage. The heuristics have been modified from their original implementations to incorporate additional QoS attributes, the notion of service-types and to enable them to be simulated using a common set of assumptions. The study provides a fair basis for comparison of these heuristics, for tasks with varied service-types (Hard, Soft or Best-effort) for each QoS dimension and varied degrees of tightness of task deadlines. The heuristics are outlined, the QoS-model is defined and the simulation environment is described. The simulation study shows how each heuristic performs in terms of number of satisfied users, makespan and total utility. The results provide suggestions on which heuristic is best suited for conditions prevailing in a particular HC environment.