Optimality of randomized trunk reservation for a problem with multiple constraints

We study the optimal admission of arriving customers to a Markovian finitecapacity 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.