Efficient Algorithms for Selecting Advanced Reservations

Grid computing leverages and generalizes distributed computing by focusing on large scale resource sharing for high performance and innovative applications. Those applications require the simultaneous or successive use of various grid resources. An important problem that faces Grid computing is then to ensure the timed access to various resources. One possible way to achieve this is to negotiate some service level agreement between the application and the infrastructure. This is called Advanced Reservations (AR). This paper focuses on this important problem. We take the rationale of a Grid resource broker which maximizes its utility with respect to incoming demands for resource access. We define two new algorithms for this. The first one computes optimal solutions through a problem decomposition strategy while the second one uses greedy exploration to quickly find a solution.