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

Given an M/G/1 queue controlled by an exhaustive policy 𝒫, we consider a (𝒫 + τ)-policy consisting of turning the server on at a random time τ later than 𝒫. The objective is to obtain necessary and sufficient conditions such that the (𝒫 + τ)-policy is better than the 𝒫-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 (N+τ)-policy and the D-policy is shown. We will also discuss the different types of T-policies, single and multiple, establishing a relation between them, which is independent of the optimization criterion.