טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentLev-Ari Anat
SubjectControl and Optimization for Queuing Models: Asymptotic
Optimality and State Space Collapse Results
DepartmentDepartment of Electrical Engineering
Supervisor Professor Rami Atar
Full Thesis textFull thesis text - English Version


Abstract

This thesis is concerned with optimal control and optimization of queuing systems in heavy traffic. It has three parts. The first two parts are theoretical and the third provides a numerical study. The first part emphasizes the dynamic programming approach to treat diffusion limits and establishes a reduction of a multidimensional dynamic model to a one-dimensional Bellman equation, while the second part treats an optimization problem for a model that is two-dimensional in nature. Finally, the third part provides a numerical study of the second model in cases that cannot be approached via analytical tools.

The first system is a multiclass G/G/1 queue with reneging customers. There is a cost associated with holding and reneging. An asymptotically optimal policy in heavy traffic is identified, where classes are prioritized according to a workload-dependent dynamic index rule. Whereas the dynamics are multidimensional, we show that in the heavy traffic limit the system undergoes state space collapse to a one-dimensional diffusion control problem. We solve this problem via a Bellman equation in one variable from which one can read off the dynamic index rule. This result stands in sharp contrast to known fluid scale results where it is asymptotically optimal to prioritize by the fixed cµ/θ index.

The second model consists of a G/G/1 queue with finite buffer. Arriving customers that find the buffer full are rejected. A rejected customer may return to the queue, with some fixed probability, after waiting an exponential time in a retrial line. We have two results on this model. The first is the identification of the diffusion limit of the queue length and the number of jobs in the retrial line. This limit is given as a two-dimensional reflected diffusion with degenerate diffusion coefficient. Then, we formulate an optimization problem in which the optimal buffer size is sought so as to minimize a combined rejection and queue length cost. This is still a hard problem to solve analytically, but we are able to address it in two asymptotic sub-regimes. That is, we identify the optimal buffer size in the small and large limits of the retrial rate parameter µ.

The third part provides a numerical study of the optimization problem for generic µ, a problem that does not seem to have an analytic solution. We perform a simulation which shows a growth in the optimal buffer size b, as well as in the value function V, as µ grows. In addition, we observe the effect of the system parameters, such as the probability of a rejected customer to return, on the values of b and V. The two extreme cases µ → 0 and µ → ∞ match our theoretical results alluded to above.