Online Reusable Resource Allocations with Multi-class Arrivals

In this paper, we study an adversarial online reusable resource allocation problem with multi-class arrivals, where each class is associated with its price per unit time and usage duration. Each unit of resource will be returned after the usage duration of the class of customer that the unit has been allocated to. We propose a simple online algorithm which achieve the best possible competitive ratio among all online policies when the usage durations of any two classes are divisible. Its competitive ratio is proved using a novel Auxiliary Algorithm that constructs a feasible solution to a linear program that upper bounds the optimum. We show that our policy can be extended to the case of general durations and the advance booking problem where each usage duration only starts after an arbitrary period. We show that our policy achieves at least half of the optimal when the durations are general, and for advance booking with equal usage durations.