The Two-Class Two-Server Queueing Model with Nonpreemptive Heterogeneous Priority Structures

Priorities arise very naturally in many real-life queueing applications. In many of these applications, the system consists of more than one server. Often, units belong to a specific class and observe the same priority structure on all servers: a unit of class P1 has priority over a unit of class P2 on all servers. However, it also happens that the priority structure differs amongst the servers of the same system. We call such models multiserver queues with heterogeneous priority structures so as to distinguish them from the systems with homogeneous priority structures. Our aim is to gain insight in the behavior of nonpreemptive multiserver queues with heterogeneous priority structures. Since real-life examples with many servers and many classes are quite complex to analyze, we limit the scope of our investigation to a study of the Markovian two-class two-server case, the basic model, which---despite the simplicity of its description---already turns out to be surprisingly involved. Traditional means for solving queueing systems, based on transform methods, soon become very complicated when multiple priority servers are involved. The complexity largely arises from the multidimensional character of the state space and the non-existence of a product form solution. Such systems, however, if their state space is highly structured, may be efficiently solved using the matrix-geometric method, as developed by Neuts. This method has a clear advantage over purely numerical methods in that it provides qualitative insight in the behavior of the system. We apply matrix-geometric analysis to derive the stationary queue length distribution of the queues in the basic model. We investigate two different modeling alternatives, which are obtained by structuring the state space of the basic model in different ways. Each of these alternatives only yields numerical results if the state space is truncated, which influences the results of the analysis. It turns out that we obtain approximations for the average queue lengths, which converge to stable or 'exact' values if the value of the truncation parameter is sufficiently high. We derive both optimistic and pessimistic bounds for the average queue lengths by slightly changing the dynamics of the models and we prove these bounds in a formal way for the special case where the classes have equal mean service times. We also provide an efficient algorithm to derive the waiting time distributions for the classes in the basic model. We then extensively use these techniques to provide insight in the actual behavior of the system. The characteristics of the basic model are highlighted by comparing them with those of the two-class FCFS M/M/2 queue and the simple single class M/M/1. Some of our observations seem to be---at first sight---rather counterintuitive. We try to find a plausible explanation for these observations by thinking about the dynamics of the queues.Chapter 1 - Heterogeneous Priority Structures in Multiserver Systems 1.1 Initiators in MVS 1.2 Call Centers 1.3 Definition of the Basic Model 1.4 Preliminary Analysis 1.5 Equilibrium Equations Chapter 2 - Methods for Multiserver Systems with Homogeneous Priority Structures 2.1 Preliminaries 2.2 The Single Server Priority Queue 2.3 Transform Methods 2.4 Boundary Value Problems 2.5 Approximations 2.6 Matrix-Geometric Methods Chapter 3 - The Stationary Queue Lengths 3.1 Matrix-Geometric Models 3.2 The Class Bounded Model (CBM) 3.3 Stability Condition for CBM 3.4 Distribution and Moments for CBM 3.5 Effect of Truncation with CBM 3.6 The Difference Bounded Model (DBM) 3.7 Stability Condition for DBM 3.8 Distribution and Moments for DBM 3.9 Effect of Truncation with DBM 3.10 A note on Convergence Chapter 4 - Optimistic and Pessimistic Bounds 4.1 Motivation 4.2 Principles 4.3 Bounds with CBM 4.4 Bounds with DBM 4.5 Conclusions Chapter 5 - The Stationary Waiting Times 5.1 Waiting Time Distribution in QBDs 5.2 Service Process in the Basic Model 5.3 Algorithm for the Basic Model 5.4 Moments of the Waiting Time Distribution 5.5 Influence of State Space Truncation Chapter 6 - Analysis of the Basic Model 6.1 Queue Length Distribution 6.2 Correlations 6.3 Distribution of Jobs amongst Servers 6.4 The Caudal Characteristic 6.5 Waiting Times Appendix Chapter 7 - Conclusions and Extensions 7.1 Conclusions 7.2 Multiple Classes and Servers 7.3 Non-Exponential Service Time Distributions 7.4 Queueing Networks 7.5 Further Approximations Bibliographynrpages: 211status: publishe