טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentGiat Chanit
SubjectAsymptotic Optimality of Priority Control Rules in Queueing
Systems with Abandonment
DepartmentDepartment of Electrical Engineering
Supervisors Professor Rami Atar
Professor Nahum Shimkin
Full Thesis textFull thesis text - English Version


Abstract

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 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 ci the individual holding cost per unit time, by µi the average service rate, and by θi the average abandonment rate. We examine two criteria: large time average cost and fluid limited ergodic cost (corresponding to two different orders of limits for n → ∞ and time→ ∞). Both criteria are associated with overall holding cost and an additional penalty for customer abandonment is easily incorporated into this model.

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 ciµii. 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 ciµii 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.