A job scheduling game based on a folk algorithm

In the modern distributed systems, one of the most important targets is to resolve the job scheduling problem, optimizing the solution. In fact, in a concurrent environment such as distributed systems, jobs synchronization access to shared resources allows CPU time optimization. So, in order to solve this problem, we modeled a new scheduler based on a job scheduling game, in which multiple jobs concur to use multiple CPUs as players of this game model. Every single job payoff is related to total job completion time minimization, allowing system throughput maximization. The implemented model provides integration of Nash Equilibrium to MiniMax solution inspired by the "folk theorem" of Game Theory. This new algorithm has been tested, and results validate decrease of Nash Equilibrium inefficiency for the proposed distributed model. © 2012 Springer-Verlag.