Late-rejection, a strategy to perform an overflow policy

Motivated by overflow policies implemented in service systems, we consider a multi-server queue with customers’ abandonment where rejection control is exercised on customers currently waiting in the queue. Our aim is to find a good balance between conflicting goals, namely, the rate of rejected customers and a cost function which may involve wait and abandonment metrics like percentiles of the waiting time or rate of abandonment. We develop a Markov decision process approach where the waiting time of the first customer in line is used in a discretized form to define the system state. We show that a time-based threshold policy is optimal, and develop a procedure to compute the optimal threshold. Our analysis explains some known behaviors in practice. For instance, if the cost function is constant in the system state like with wait percentiles, then the optimal threshold is one of the time limits defining the percentiles. Also, abandonment is shown to have beneficial or detrimental effect depending on the system manager’s objective.