Abstract:This paper suggests that the periodic scheduling of identical independent tasks on a single-level tree grid and identical independent tasks are independent tasks in the same size in computation. First, an integer linear programming model for scheduling identical independent tasks is presented. By analyzing the procedure of solving the linear programming model, and obtaining the optimal number of tasks assigned to each computing node, the study finds that a single-level tree grid composed of different nodes will be in one of three states, respectively: unsaturated, critical, and redundant states. Furthermore, the optimal number of tasks assigned to each node increases linearly as the number of tasks arriving to the master grows, and the periodic feature appears in the task scheduling. Next, some features and theories that determine the states of grid systems among unsaturated, critical, and redundant states are obtained, periodic scheduling of identical independent tasks on single-level grid is proposed, the length of period is derived. Their computational complexity is also analyzed, and a periodic scheduling algorithm, Periodic-Sched, is given. Both the theory and experiments have proved that the periodic scheduling is feasible. In this way, the problem of large-scale independent task scheduling is simplified and resolved in one period, which reduces the computational complexity dramatically. The periodic scheduling of independent tasks is suitable for Map tasks scheduling on Hadoop platform.