We consider a simple Markovian queue with Poisson arrivals and exponential service times for jobs. The controller can choose service rates from a specified action space depending on number of jobs in the queue. The queue has a finite buffer and when full, new jobs get rejected. The controller’s objective is to choose optimal (state-dependent) service rates that minimize a suitable long-run average cost, subject to an upper bound on the job rejection-rate (quality-of-service constraint). We solve this problem of finding and computing the optimal control under two cases: When the action space is unbounded (i.e. [0, ∞)) and when it is bounded (i.e. [0, μ ̄], for some μ ̄ > 0). We also numerically compute and compare the solutions for different specific choices of the cost function.