Optimal Priority Assignment with Heterogeneous Waiting Costs

For an M/G/1 queuing system, this paper assumes (l) that the discipline is administratively constrained to a “head-of-the-line” rule with n classes, and (2) that priorities are centrally assigned to customers according to their individual cost per unit time spent in the system, or their individual service-time requirements, or both (as the available information may be), but independently of the state of the queue. Then optimal priority-assignment rules for the various information structures are characterized. When n = 2, the higher priority may always be optimally assigned to all customers who are “no worse than average” and with sufficiently high load to “practically all” customers.