10 November 2016
We start considering an M/M/1 queue with impatient customers, where the service rate is controlled by a decision maker. The system can operate under two different service rates, namely, low and high service rates. Whenever a new customer arrives or a customer already in the system leaves the system, the decision maker chooses the service rate which will be used till the next arrival or departure. Service costs, holding costs for the waiting customers, and abandonment costs for the customers leaving the system without taking any service are included in the model. The objective is to find the optimal service rate policy minimizing the expected total discounted cost. This problem is modeled as a semi-Markov decision process (SMDP) with exponential sojourn times. Due to the impatient customers, the transition rates of the decision process are unbounded. This is why the standard assumption in the discounted SMDP literature, which guarantees that there is no accumulation point, cannot be satisfied for this problem. Moreover, the well-known technique uniformization cannot be used for this problem. We propose some conditions for such a SMDP, possibly not satisfying the standard assumption, under which the value iteration algorithm converges, and the existence of an optimal deterministic stationary policy is guaranteed. Then, it is proved that the optimal value function is increasing under some monotonicity assumptions by using a new device, called customization.