Analysis and Optimization of Queueing Models
with Markov Modulated Poisson Input
Ph D Dissertation
For quite sometime queueing theory considered models in which the inter-arrival times are independent and identically distributed i.e. renewal. These assumptions which simplify the analysis may not be easily justified in many present day application areas such as manufacturing systems and communication networks. We have common examples in manufacturing, where, machines work concurrently with the input to many machines being the semi-finished products emerging from other machines; in most situations, this input is non-renewal. Similarly, in communication networks, the traffic constituted by diverse components such as data, video, and voice is observed to be non-renewal. Such situations motivate the analysis of queueing models with correlated inter-arrival times and possibly with rates that are not constant. A popular model for such an arrival process with non-renewal arrivals is the Markov modulated Poisson process (MMPP). In MMPP, the arrivals are Poisson but the rate is modulated by a finite, ergodic continuous time Markov chain.
The focus of this work is to look into optimization and performance
aspects of some interesting and relevant queueing models with MMPP
as the source of input arrivals. Two optimization problems and two performance
problems are considered in this thesis. The first optimization problem
is about finding the optimal input MMPP under a linear reward and cost
structure and we use a linear programming framework for solving this problem.
The second optimization problem is concerned with the optimal scheduling
of a server in a multiclass environment with setups, where the arrivals
of individual classes are modulated. On the performance analysis side,
we first look at the performance of a multiclass priority queue with setup
times when the overall arrivals constitute an MMPP, using matrix-geometric
methods. Next, we consider a multiclass queueing network, re-entrant line,
with MMPP input and derive analytical performance bounds using a linear
Optimal Input Selection
We consider a model in which K Poisson streams are available
for the server to choose from at any time, with the choice done according
to a K state continuous Markov chain. Suppose the server is rewarded
units for each finished customer of the
stream but it costs
per unit time as long as this
stream is scanned. We view the system as a MMPP/G/1 queue and seek to maximize
the profits by optimally choosing the stationary probabilities of the modulating
Markov chain. We consider two formulations of the optimization problem.
The first one (which we call the PUT problem) seeks to maximize the profit
per unit time whereas the second one considers the maximization of the
profit per accepted customer (the PAC problem). In either case, we obtain
essentially linear programming formulations for the optimization problems
by bounding the server utilization or queue lengths. There is a
rich relationship between the solutions of the PUT and PAC problems.
Performance of a Priority Queue with Correlated Arrivals
Also we analyze the performance of a multiclass queue with correlated
arrivals and with non-zero switchover times, under a buffer priority scheduling
policy. The arrivals of the different classes are correlated in the sense
of being the individual Poisson streams of a Markov modulated Poisson process.
By focusing attention on a representative two class priority model, we
consider the structure of the underlying Markov chain in two cases. In
the first case, both the buffers are assumed to be finite and we show that
the resulting Markov chain has a quasi-birth-death process structure. We
calculate typical steady-state performance measures like the mean waiting
times and loss probabilities, in an algorithmic way. In the second case,
one of the buffers is assumed to be infinite and the invariant probability
vector of the Markov chain is shown to have matrix-geometric structure,
again leading to algorithmic solutions.
Scheduling of a Multiclass Queue with Correlated Arrivals
Consider a single server multiclass queueing system with K classes where the individual queues are fed by K correlated interrupted Poisson streams generated in the states of a K state stationary modulating Markov chain. The service times for all the classes are the same, but a setup time (and/or a setup cost) is incurred whenever the server switches from one queue to another. It is required to minimize the sum of discounted inventory and setup costs over an infinite horizon. We provide sufficient conditions under which exhaustive policies are optimal. We then present some simulation results for a two class queueing system to show that exhaustive, threshold policies outperform non-exhaustive policies.
Performance of Networks with Modulated Arrivals
Finally, we look at a multiclass queueing network a re-entrant line, rather than a queue. Here, we use a linear programming based approach to obtain lower and upper bounds for the mean steady-state number in the system of a re-entrant line with MMPP input. The bounds are tight when the load on the system is low; for moderate and high loads we have only finite lower bounds which are fair. The linear programs formulated have certain terms that are difficult to compute analytically or numerically. This leads us to place the concepts of reversibility and quasi-reversibility in the context of Markovian queues with MMPP input.