טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMendelson Gal
SubjectControl in the Large Deviation Regime for a Class of
Queueing Models
DepartmentDepartment of Electrical Engineering
Supervisor Professor Rami Atar
Full Thesis textFull thesis text - English Version


Abstract

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.