A comparison of utility-oriented algorithms for scheduling parallel tasks in multi-cluster grid

Scheduling parallel tasks in multi-cluster grid can be seen as two interdependent problems: cluster allocation and scheduling parallel task on the allocated cluster. In this paper both rigid and moldable parallel tasks are considered. We propose a theoretical model of utility-oriented parallel task scheduling in multi-cluster grid with advance reservations. On the basis of the model we present an approximation algorithm, a repair strategy based genetic algorithm and greedy heuristics MaxMax, T-Sufferage and R-Sufferage to solve the two interdependent problems. We compare the performance of these algorithms in aspect of utility optimality and timing results. Simulation results show on average the (1+α)-approximation algorithm achieves the best trade-off between utility optimality and timing. Genetic algorithm could achieve better utility than greedy heuristics and approximate algorithm at expensive time cost. Greedy heuristics do not perform equally well when adapted to different utility functions while the approximation algorithm shows its intrinsic stable performance.