Ph.D Student | Giat Chanit |
---|---|

Subject | Asymptotic Optimality of Priority Control Rules in Queueing Systems with Abandonment |

Department | Department of Electrical Engineering |

Supervisors | Professor Rami Atar |

Professor Nahum Shimkin | |

Full Thesis text |

We consider an overloaded multi-class,
many server queueing system with homogeneous servers and customer abandonment.
Motivated by call centers, we are interested in minimizing a weighted average
holding cost. It is well known that the *cµ *priority rule minimizes
average linear holding costs in a variety of settings that do not support
abandonment. Thus, we seek simple control policies that perform optimally, at
least in an asymptotic sense.

The system consists of a fixed number
of customer classes and a server pool with *n *homogeneous servers.
Arrivals are according to independent Poisson processes, services are
exponential and so are the abandonment times. The arrival, service and
abandonment rates are class-dependent. Because of the abandonments, this
overloaded system is stable. For class *i*, we denote by *c _{i }*the
individual holding cost per unit time, by

We study the system under a many-server
fluid scale. Under the large time average cost criterion, the formal scaling
limit leads to a simple deterministic ordinary differential equation. We show
that the solution of the corresponding deterministic control problem is a lower
bound on the limiting cost of the stochastic queueing problem, under any
policy. The solution to the deterministic problem turns out to be particularly
simple and explicitly solvable. When translated back to the queueing model,
this solution formally corresponds to assigning priority, either preemptive or
non-preemptive, to the classes in agreement with the order of the quantities *c _{i}µ_{i}/θ_{i}*.
We prove that this priority rule is indeed asymptotically optimal for the
queueing system, using tightness of Poisson processes and detailed analysis.

Proving that the *c _{i}µ_{i}/θ_{i
}*priority rule is asymptotically optimal under the fluid limited
ergodic cost criterion, requires a different approach. The aforementioned
deterministic problem is shown to be the lower bound using the ergodic
characteristic of the system. Martingale representation and Lyapunov function
type argument are used to show the asymptotic optimality of the preemptive
priority rule.

Finally, we measure the effectiveness of our approximation, for practical use, via simulations. The simulations show that our results are effective even for small systems when the traffic intensity is significant, and for moderate and large systems when the system is lightly or critically loaded. Moreover, the simulations imply that our results may hold for different arrival and service distributions, as long as the abandonment distribution is kept exponential.