Provably Near-Optimal LP-Based Policies for Revenue Management in Systems with Reusable Resources

Motivated by emerging applications in workforce management, we consider a class of revenue management problems in systems with reusable resources. The corresponding applications are modeled using the well-studied loss network systems. We use an extremely simple linear program (LP) that provides an upper bound on the best achievable expected long-run revenue rate. The optimal solution of the LP is used to devise a conceptually simple control policy that we call the class selection policy (CSP). Moreover, the LP is used to analyze the performance of the CSP and show that it admits uniform performance guarantees. In particular, for the model with a single resource and uniform resource requirements, we prove that the CSP is guaranteed to have an expected long-run revenue rate that is at least half of the best achievable. Furthermore, as the capacity of the system grows to infinity, the CSP is asymptotically optimal, regardless of any other parameter of the problem. Finally, our techniques can be used to analyze the performance of the well-known class of trunk-reservation policies.