ASTEC 2009 Workshop/Summer school on Algorithms and Techniques for Scheduling on Clusters and Grids

Co-authorDenis Trystram, Johanne Cohen and Frederic Wagner

Game Theoretic Analysis of the Multi-Organization Scheduling Problem

Current grid computing systems allow several users and/or organizations to combine their computation resources in order to produce a powerful distributed supercomputer infrastructure. Nevertheless, combining different performance goals of users with potentially different profiles is a challenging task. In this talk we will present our attempts to model this problem as a multi-objective scheduling problem. We will present some centralized algorithms with guaranteed performance bounds and our current work-in-progress to describe this problem as a game theoretic problem. We will show that in our current model this NP-Complete problem doesn't admit Nash Equilibriums when each organization is interested in minimizing its own maximum completion time or its own average completion time.