*Analysis and Optimization of Queueing Models
with Markov Modulated Poisson Input
*

N. Hemachandra

**SUMMARY**

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
programming approach.

*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.