An M / M /1 Dynamic Priority Queue with Optional Promotion

Ehud Kofman and Steven A. Lippman
Additional contact information
Ehud Kofman: University of Illinois, Urbana, Illinois
Steven A. Lippman: University of California, Los Angeles, California

Operations Research, 1981, vol. 29, issue 1, 174-188

Abstract: We consider an M / M /1 queue with two types of customers: priority customers and regular customers. They arrive at the service facility according to two independent Poisson streams and form a single queue according to the order in which they arrive. The two types of customers are distinguished by the holding costs charged per unit time that each of them resides in the queue. The server can either serve customers according to the order in which they arrive or pay a fixed fee R and promote a priority customer, bypassing the customers ahead of him. The server selects the customers to be served so as to minimize the expected average cost per unit of time of operating the system. We show that whenever the number of regular customers bypassed in a promotion, times the expected holding costs per priority customer per service period, is greater than or equal to R , promotion is strictly optimal. Moreover, for each state there exists a value of R —with R exceeding the number of regular customers bypassed in a promotion, times the expected holding costs per priority customer per service period—for which promotion is optimal. This result contradicts previous work in the literature. In addition, we demonstrate that the set of states from which promotion is optimal decreases in the sense of set inclusion as R increases. This fact is the key to an efficient algorithm.

Date: 1981
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.29.1.174 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:29:y:1981:i:1:p:174-188

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().