EOMT: A Master-Slave task scheduling strategy for grid environment

Task scheduling has been a key issue to improve parallel execution in distributed systems. Master-Slave task scheduling, as a technique of mapping and scheduling loads to heterogeneous platforms, has aroused interests of many researchers. Although minimizing the Master-Slave application's makespan (the overall completion time) in general case is a NP-complete problem, it is still meaningful in some special fields. In this paper, we aim at improving the performance of the Master-Slave pattern applications in the case with a large number of equal-sized and independent tasks and propose a new strategy EOMT (Equilibrium Overhead with Multi-cycle Tasking) for task scheduling in the grid environment. The EOMT strategy is designed for the grid environment with heterogeneous resources. The main concept of EOMT is to make the workload assigned to each slave node as even as possible to reduce application's makespan. A detailed analysis for Master-Slave task scheduling is given in this paper. Experiment results show that our strategy outperforms other traditional task scheduling strategies in different computation and network resource combinations in the grid environment.