Complexity Analysis of VMs Auction-Based Scheduling in Cloud Datacenters for Grid Balancing

Auction-based mechanisms are widely used tools for price discovery and optimizing the allocation of resources under competition. However, the computational complexity of auctions is always a main factor to consider when determining the applicability of the different auction mechanisms for particular settings. In this work, we consider the complexity of our auction-based scheduling system used for providing grid balancing by scheduling the consumption of excess energy on cloud datacen-terse. We implemented our system using the IBM ILOG CPLEX optimization solver and evaluated its solution-quality vs. time-complexity under three different settings used to manage the solve-time required by the solver. Our results show that the solve-time of the proposed system increases quickly for larger problem sizes and therefore, the development of heuristic algorithms would be more practical for a wider range of scenarios.