A Hybrid Linear Programming and Evolutionary Algorithm Based Approach for On-line Resource Matching in Grid Environments

We describe a hybrid linear programming (LP) and evolutionary algorithm (EA) based resource matcher suitable for heterogeneous grid environments. The hybrid matcher adopts the iterative approach of the EA methods to perform a goal oriented search over the solution space and, within each iteration, uses the LP method to solve a partial resource matching problem. By judiciously controlling the partial problem size and its complexity, the hybrid matcher balances the accuracy of the solution and the execution time. We describe a grid management architecture that incorporates the hybrid resource matcher. Performance results indicate that the execution time of the hybrid matcher, under a variety of conditions, is at least as good and often significantly better than the execution time of LP and EA based matchers. The hybrid matcher is found to scale well with the complexity of the problem and to maintain sensitivity to the response time constraints of on-line environments.

By: Pawel Garbacki, Vijay K. Naik

Published in: RC24209 in 2007


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .