Optimal Operating Policies for M/G/1 Queuing Systems

We consider the economic behavior of a M/G/1 queuing system operating with the following cost structure: a server start-up cost, a server shut-down cost, a cost per unit time when the server is turned on, and a holding cost per unit time spent in the system for each customer. We prove that for the single server queue there is a stationary optimal policy of the form: Turn the server on when n customers are present, and turn it off when the system is empty. For the undiscounted, infinite horizon problem, an exact expression for the cost rate as a function of n and a closed form expression for the optimal value of n are derived. When future costs are discounted, we obtain an equation for the expected discounted cost as a function of n and the interest rate, and prove that for small interest rates the optimal discounted policy is approximately the optimal undiscounted policy. We conclude by establishing the recursion relation to find the optimal (nonstationary) policy for finite horizon problems.