A Heuristic Approach to the Allocation of Different Workloads in Computational Grid Environments

Self-scheduling algorithms can achieve a good balance between workload and communication overhead in compu-tational systems. In particular, Quadratic Self-Scheduling (QSS) and Exponential Self-Scheduling (ESS) are flexible enough to adapt to distributed systems. Thus, they are of interest for application in Internet-based Grids of comput-ers. We have tackled the problem of scheduling a set of independent tasks in a computational Grid using a simula-tor and a heuristic approach based in simulated annealing. To test this approach, we have considered different work-load distributions. We find that the optimal Simulated An-nealing (SA) results permit to reduce the overall computing time of a set of tasks up to a 16%, with respect to results obtained with previous values of the parameters experimen-tally determined. In addition, the time to obtain the SA opti-mized parameters by simulation is negligible compared with that needed using experimental measures. Moreover, after the optimization, the heuristic approach provides equiva-lent performance for different workloads (random, increas-ing, decreasing) and different number of tasks. These re-sults show the high adaptability of the QSS and ESS self-scheduling algorithms, which can be fully exploited thanks to the heuristic approach here presented