Abstract:

In the generational scheduling （GS） algorithm, only the partial orders between tasks are considered during the generation division, and the effect of the task partition on the total scheduling time is entirely ignored. Besides, as the existing independent scheduling algorithms employed by the local scheduling consider the makespan of task subsets only, there may result in the absence of global optimization. In order to solve these problems, a modified algorithm named GA-DLTPF is presented based on GS. GA-DLTPF performs the generation adjustment based on the generation division of GS, and ensures the priority of the longest through path for the local scheduling according to the definition of through path. Simulated results indicate that GA-DLTPF is of better scheduling performance than the improved GS algorithm OGS, especially in the condition of deep task graph.

Key words: scheduling algorithm, dependent task, generational scheduling, grid, optimization