We present an algorithm for computing a near-optimal service policy for a single-server queueing system when the service cost is a convex function of the service time. The policy has state-dependent service times, and it includes the options to remove jobs from the system and to let the server be off. The systems' semi-Markov decision model has infinite action sets for the positive states. We design a new tailor-made policy-iteration algorithm for computing a policy for which the long-run average cost is at most a positive tolerance above the minimum average cost. For any positive tolerance our algorithm computes the desired policy in a finite (and small) number of iterations. The number is five for the numerical example used in the paper to illustrate results obtained by the algorithm.
European Journal of Operational Research, 2001, Vol 134, Issue 3, p. 648-663