Scheduling independent tasks in heterogeneous environments under communication constraints

Abstract

With the advent of the Grid, task scheduling in heterogeneous environments becomes more and more important. Of particular interest is the fact that especially in scientific experiments a non negligible amount of data must be transferred to the processing node before a task can commence execution. Given bandwidth constraints, scheduling both computations and data transfers is required. In this paper we first develop a suitable model that captures heterogeneity in the processing nodes while imposing communication constraints. We proceed by proposing scheduling heuristics with the aim of minimizing the total makespan of a set of independent tasks. Through a series of experiments we illustrate the potential of a particular heuristic that is based on backfilling. © 2006 IEEE.