A Game-Theoretic and Hybrid Genetic Meta-Heuristics Model for Security-Assured Scheduling of Independent Jobs in Computational Grids

Scheduling independent tasks in Computational Grids commonly arises in many Grid-enabled large scale applications. Much of current research in this domain is focused on the improvement of the efficiency of the Grid schedulers, both at global and local levels, which is the basis for Grid systems to leverage large computing capacities. However, unlike traditional scheduling, in Grid systems security requirements are very important to scheduling tasks/applications to Grid resources. The objective is thus to achieve efficient and secure allocation of tasks to machines. In this paper we propose a new model for secure scheduling at the Grid sites by combining game-theoretic and genetic-based meta-heuristic approaches. The game-theoretic model takes into account the realistic feature that Grid users usually perform independently of each other. The scheduling problem is then formalized as a noncooperative non-zero sum game with Nash equilibria as the solutions. The game cost function is minimized, at global and user levels, by using four genetic-based hybrid meta-heuristics. We have evaluated the proposed model through a static benchmark of instances, for which we have measured two basic metrics, namely the makespan and flowtime. The obtained results suggest that it is more resilient for the Grid users (and local schedulers) to tolerate some job delays defined as additional scheduling cost due to security requirements instead of taking a risk of allocating at unreliable resources.