Online job allocation with hard allocation ratio requirement

The problem of allocating jobs to appropriate servers in cloud computing is studied in this paper. We consider that jobs of various types arrive in some unpredictable pattern and the system is required to allocate a certain ratio of jobs. In order to meet the hard allocation ratio requirement in the presence of unknown arrival patterns, one can increase the capacity of servers by expanding the size of data centers. We then aim to find the minimum capacity needed to meet a given allocation ratio requirement. We propose two online job allocation policies with low complexity. We prove that, given a hard allocation ratio requirement, these two policies can achieve the requirement with the least capacity. We also derive a closed-from expression for the amount of capacity needed to achieve any given requirement. Two other popular policies are studied, and we demonstrate that they need at least an order higher capacity to meet the same hard allocation ratio requirement. Simulation results demonstrate that our policies remain far superior than the other two when jobs arrive according to some random process.