The scheduling of independent but file-sharing tasks on heterogeneous master-slave platforms has recently found important applications in Grid environments. The scheduling heuristics recently proposed for this problem are all constructive in nature and based on a common greedy criterion which depends on the momentary completion time values of the tasks. We show that this greedy decision criterion has shortcomings in exploiting the file-sharing interaction among tasks since completion time values are inadequate to extract the global view of this interaction. We propose a three-phase scheduling approach which involves initial task assignment, refinement and execution ordering phases. For the refinement phase, we model the target application as a hypergraph and with an elegant hypergraph-partitioning-like formulation, we propose to use iterative-improvement based heuristics for refining the task assignments according to two novel objective functions. Unlike the actual scheduling cost, the smoothness of proposed objective functions enables the use of iterative-improvement-based heuristics successfully, since their effectiveness and efficiency depend on the smoothness of the objective function. Experimental results on a wide range of synthetically generated heterogeneous master-slave frameworks show that the proposed three-phase scheduling approach performs much better than the greedy constructive approach.

DATE: August 24, 2004, Tuesday @ 14:40
PLACE: EA-502