OPTIMAL-CONTROL OF THE M G/1 QUEUE WITH REPEATED VACATIONS OF THE SERVER/

We consider a M / G / 1 queue where the server may take repeated vacat ions. Whenever a busy period terminates the server takes a vacation of random duration. At the end of each vacation the server may either ta ke a new vacation or resume service; if the queue is found empty the s erver always takes a new vacation. The cost structure includes a holdi ng cost per unit of time and per customer in the system and a cost eac h time the server is turned on. One discounted cost criterion and two average cost criteria are investigated. We show that the vacation poli cy that minimizes the discounted cost criterion over all policies (ran domized, history dependent, etc.) converges to a threshold policy as t he discount factor goes to zero. This result relies on a nonstandard u se of the value iteration algorithm of dynamic programming and is used to prove that both average cost problems are minimized by a threshold policy.