Optimality of randomized trunk reservation for a problem with multiple constraints

We study the optimal admission of arriving customers to a Markovian finite-capacity queue (e.g., M/M/c/N queue) with several customer types. The system managers are paid for serving customers and penalized for rejecting them. The rewards and penalties depend on customer types. The penalties are modeled by a K-dimensional cost vector, K >= 1. The goal is to maximize the average rewards per unit time subject to the K constraints on the average costs per unit time. Let K-m denote min{K, m - 1}, where m is the number of customer types. For a feasible problem, we show the existence of a K-m-randomized trunk reservation optimal policy, where the acceptance thresholds for different customer types are ordered according to a linear combination of the service rewards and rejection costs. Additionally, we prove that any K-m-randomized stationary optimal policy has this structure.