טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentNir Solomon
SubjectOptimal Scheduling for Multi-class Customers in the
Non-degenerate Slowdown Diffusion Regime
DepartmentDepartment of Electrical Engineering
Supervisor Full Professor Atar Rami
Full Thesis textFull thesis text - English Version


Abstract

Asymptotic optimality of scheduling policies is the theme of many studies in the field of queueing networks, and has a variety of applicative implementations. This thesis deals with a stochastic queueing network, which consists of a single pool of identical parallel servers that serve multi-class customers. Every customer experiences a single service and leaves the network. Every class has its own queue, arrival rate and service rate.

The network operates under the Non-Degenerate Slowdown (NDS) heavy traffic regime. This regime has been considered more recently than the conventional and Halfin-Whitt (HW) heavy traffic regimes. A unique property of the NDS regime is that the delay and the service time experienced by a customer are of the same order of magnitude. Thus, the sojourn time is asymptotically distinct from the either the delay or the service time in this regime.

The main contribution of this research is described in two parts of this thesis. In the first part, two cost functions are presented. The first is a cost function of the total number of customers in the network. The second is a cost function of the number of customers in the queues. Both cost functions are asymptotically lower bounded. Next, a candidate for a scheduling policy in a feedback function form is proposed, and shown to be asymptotically optimal in the sense that it attains the lower bound for both cost functions. The attainability is due to the feedback function being related to the minimizing curve of the cost functions. This is the first result on asymptotic optimality in the NDS regime in the literature.

In the second part, a Diffusion Control Problem (DCP) that arises from the queueing model and the scheduling policy is formulated. This DCP has a cost function of the sojourn time. Such a cost function has a significant meaning, distinct from delay or service time, only under NDS regime. Next, the obtained DCP is reduced into equivalent deterministic optimization problem. The main result here is that the minimizing curve corresponding to the cost function can be evaluated by solving the DCP. An analysis of the deterministic optimization problem is performed for two specific cost functions of sojourn time, and explicit expressions for the corresponding minimizing curve are obtained.