Scheduling and Data Redistribution Strategies on Tree Platforms

Effective task scheduling holds the key to achieving high performance grid application. Aimed at the problem of scheduling and data redistribution on tree platforms, this paper assumes that all tasks are situated at the participating workers. The attempt to perform the processing of tasks in a given makespan results in the necessity of tasks redistribution. The paper proposes a linear program model and mechanism on tree platforms on which the redistribution mechanism is proved, and features two heuristic algorithms for scheduling and tasks redistribution. One is MBBSA on the tree platform (MBBSA-TP) that involves directly applying MBBSA on tree platforms. Another is partially optimal scheduling and redistributing algorithm (POSRA) that involves indirectly using MBBSA on tree platforms. The paper also analyzes the complexity of the two algorithms. A large number of simulation experiments for algorithms demonstrate that POSRA presents advantage over MBBSA-TP.