Individual, Class-Based, and Social Optimal Admission Policies in Two-Priority Queues

Abstract

This paper considers the admission control problem for an M/M/1 queueing system serving two classes of customers. Class 1 customers have preemptive resume priority over class 2 customers. Within each class, the service is provided on a first-come, first-served basis. The system is controlled by accepting or rejecting arriving customers. There is a class-dependent reward and holding cost associated with each accepted customer. The goal is to minimize the expected total discounted net cost. We analyze and compare the optimal control policies under three criteria: individual optimization, class optimization, and social optimization. We show (i) the optimal policy is of either critical-number or switching-curve form under each optimization criterion, (ii) the class-optimal policy accepts more class 1 customers but less class 2 customers than the socially optimal policy, which has interesting socioeconomic implication, (iii) the individually optimal policy accepts more class 1 customers than the class-optimal policy, while it can accept either more or less class 2 customers than either of the other two optimal policies.

Keywords:

• M/M/1 queue
• Optimal admission control
• Switching curve
• Two-priority
• Value iteration

Mathematics Subject Classification:

• Primary 60K25
• Secondary 90B22

ACKNOWLEDGMENTS

We would like to thank Professor Eylem Tekin for her helpful comments and suggestions.

This reasearch was partially supported by NSF Grant DMII-0223117.