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 mm{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.