Ordinal optimization based approach to the optimal resource allocation of grid computing system

In this paper, we have formulated the resource allocation optimization problem for expanding service and increasing reliability of a grid computing system. The formulated problem is a combinational optimization as well as an NP-hard problem. We firstly decompose this problem into a minimizing budget problem and a maximizing reliability problem. An approximate model is proposed to estimate the service reliability of a resource allocation design within a tolerable computation time. Secondly, we employ an ordinal optimization (OO) based approach to solve the maximizing reliability problem and a bisection method to solve the minimizing budget problem. The proposed OO based approach consists of two stages. A binary particle swarm optimization (BPSO) algorithm is employed in the first stage using the approximate model for fitness evaluation and selects a subset of good enough solutions. Then we proceed with the goal softening searching procedure in the second stage using more refined approximate models to search for a good enough solution from the subset obtained in the first stage. We have demonstrated the test results by the simulation on a 16-node and 25-link large grid computing system including two resource-managing nodes. We used 8 bisection iterations that consumed 20 minutes to obtain a good enough resource allocation design and the corresponding minimum budget. To test the optimality of the solutions obtained by our approach, we also solved the maximizing reliability problem using two competing methods, the GA and classical BPSO algorithm. The good enough solution obtained by the proposed approach is promising in the aspects of solution quality and computational efficiency.