On optimal exhaustive policies for the M/G/1-queue

Given an M/G/1 queue controlled by an exhaustive policy P, we consider a (P + tau)-policy consisting of turning the server on at a random time tau later than P. The objective is to obtain necessary and sufficient conditions such that the (P + tau)-policy are better than the P-policy. Under the infinite-horizon average-cost criterion, policies are compared when the costs assumed are linear. When the holding cost is the waiting time cost per unit time per customer, the optimality of the N-policy over, both the (N + tau)-policy and the D-policy is showed. We will also discuss on the different types of T-policies, single and multiple, establishing a relation between them, which is independent of the optimization criterion. (C) 2000 Elsevier Science B.V. All rights reserved.