This Article Full Text (PDF) e-companion Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Levi, R. Articles by Radovanovic, A.

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

Retsef Levi, Ana Radovanovi

Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Google Inc., New York, New York 10011
retsef{at}mit.edu
anaradovanovic{at}google.com

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.

Subject classifications: revenue management; algorithms; loss networks.
History: Received May 2008; revision received December 2008; accepted March 2009.