A Cooperative Game Theoretical Technique for Joint Optimization of Energy Consumption and Response Time in Computational Grids

With the explosive growth in computers and the growing scarcity in electric supply, reduction of energy consumption in large-scale computing systems has become paramount research issue. In this paper, we study the problem of allocation of tasks onto a computational grid, with the aim to simultaneously minimize the energy consumption and the makespan subject to the constraints of deadlines and tasks' architectural requirements. We propose a solution from cooperative game theory based on the concept of Nash Bargaining Solution (NBS). In this cooperative game, machines collectively arrive at a decision that describes the task allocation that is collectively best for the system, ensuring that the allocations are both energy and makespan optimized. Through rigorous mathematical proofs we,show that the proposed cooperative game in mere O(nmlog(m)) time (where n is the number of tasks, and m is the number of machines in the system) produces a NBS that guarantees Pareto optimally. The simulation results show that the proposed technique achieves superior performance compared to the Greedy and Linear Relaxation (LR) heuristics and with competitive performance relative to the optimal solution implemented in UNDO for small-scale problems.