Efficient Operation of Optional-Priority Queuing Systems

This paper studies an M/G/1 queuing system with two classes of customers. The cost per unit time of holding a customer differs for the two classes. The server has the option of serving the first customer in line at no extra charge or paving a fee to earn the right to serve any higher-class customer further back in the queue. The paper finds an optimal policy for the simple case where this fee is independent of the position in the queue of the promoted customer. For the case where the server is restricted to serving either the first customer or the first higher-class customer further back in the queue, an appealing conjectured form of an optimal policy is shown to be invalid.