An auction based mathematical model and heuristics for resource co-allocation problem in grids and clouds

Resource co-allocation problem is one of the challenging problems in grid and cloud environments. In this paper, we propose an auction based mathematical model for providing economically efficient allocations of resources in these environments. Our model improves our earlier multi-unit nondiscriminatory combinatorial auction model by introducing a penalty cost mechanism which results in better utilization of resources and hence increasing revenue depending on the application domain. The model is formulated using integer linear programming. Five new heuristic algorithms based on the well-known meta-heuristic techniques are proposed. An intelligent neighbor selection method is also introduced. The performances of the algorithms are compared with a commercial mixed integer programming (MIP) solver on generated test cases. The solutions provided by the evolutionary algorithm are as good as the solutions provided by the MIP solver for these test cases.