A Dual Heuristic Scheduling Strategy Based on Task Partition in Grid Environments

Focusing on the fact that the collection of independent tasks to be scheduled onto the grid is always on a large-scale, a conception of task partition is proposed to group tasks exclusively according to the machine that gives the earliest completion time. As a result, several tasks in different task partitions can be scheduled at the same time, which reduces the range of task searching and eliminates the re-assignment of tasks completely. Furthermore, a Task Partition-Based Heuristic (TPBH) is presented with sufferage as the first heuristic and minimum completion time as the second one. Simulation results confirm that this dual heuristic scheduling strategy can reduce both makespan and the runtime; and the larger the task set is, the better performance the algorithm shows.