M.Sc Student | Gal Mendelson |
---|---|

Subject | Control in the Large Deviation Regime for a Class of Queueing Models |

Department | Department of Electrical Engineering |

Supervisor | Full Professor Atar Rami |

Full Thesis text |

A Parallel Server
queuing model is considered with *I* classes of customers with general
inter-arrival time distribution, and *J* service stations operating with general service-time distributions. The problem of dynamic
resource allocation so as to minimize a risk-sensitive criterion is studied in
a law-of-large-numbers scaling. Letting *X_i(t)* denote the number of
class-*i *jobs in the system at time,
the cost is given by

*1/n*log E exp[
n*sum(c_i*X_i_n(T)) ]*

Where *T>0* is the terminal
time, *c_i*'s are non-negative constants, and *X_i_n(t))=1/n*X_i(n*t).*

It is well-understood that this type of
cost emphasizes contributions from rare events (as *n* becomes large), and
that the limit behavior, as *n **à** infinity*,
is governed by a differential game (DG), as can be seen in analogous treatments
for some other classes of stochastic networks. In this game, the state dynamics
are given by a fluid equation (i.e., an ordinary differential equation) for the
formal limit *Phi* of *X* while the cost consists of *sum(c_i*Phi_i)*
and an additional term that originates from the underlying large-deviation rate
function.

Our main result is that we prove that the limiting control problem is governed by this DG and find an asymptotically optimal control policy for the risk sensitive control problem. In this policy, each service station devotes its full effort to a single class which maximizes the index

*eta_ij*[
c_i*(k_i)'^(-1)(-c_i)_i[(k_i)'^(-1)(-c_i)] ]*

where *k_i's* are large-deviations
rate functions corresponding to the primitives of the problem and *eta_ij*
corresponds to a normalized mean service rate of class-*i* costumers in
service station *j*.

We do not expect this policy to be optimal in the pre-limit, since several classes could be neglected, but it identifies which class is the greatest contributor to the cost defined, emphasizing rare events. The general inter-arrival and service time distributions goes well beyond the existing literature on the subject, where one often assumes exponential inter-arrival and/or service times so that Markov process techniques can be used.