Analysis and Optimization of Queueing Models
with Markov Modulated Poisson Input
Ph D Dissertation
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.