Competitiveness Of Dynamic Bin Packing For Online Cloud Server Allocation

Cloud-based systems often face the problem of transmits a stream of jobs to run on cloud servers in an online manner. Each job is assigned to run on a cloud server upon its arrival and departs after it completes. Dynamic Bin Packing (DBP) is a transformation of classical bin packing, which assumes that items may arrive and depart at arbitrary times. Existing works on DBP commonly aim to minimum the maximum number of bins ever used in the packing. In this paper, consider a new version of the DBP problem, namely, the Min Total DBP problem which targets at decreasing the total cost of the bins used over time. It motivated by the request dispatching problem arising from cloud gaming systems. To analyze and modified versions of the commonly used First Fit, Best Fit, and Any Fit. It’s show that the competitive ratio of Any Fit packing cannot be better than ratio of the greatest item duration to the lowest item duration.