Stability Conditions of the MMAP [ K ]/ G [ K ]/1/ LCFS Preemptive Repeat Queue

In this paper, we study the stability conditions of the MMAP[K]/G[K]/1/LCFS preemptive repeat queue. We introduce an embedded Markov chain of matrix M/G/1 type with a tree structure and identify conditions for the Markov chain to be ergodic. First, we present three conventional methods for the stability problem of the queueing system of interest. These methods are either computationally demanding or do not provide accurate information for system stability. Then we introduce a novel approach that develops two linear programs whose solutions provide sufficient conditions for stability or instability of the queueing system. The new approach is numerically efficient. The advantages and disadvantages of the methods introduced in this paper are analyzed both theoretically and numerically.     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

The Versatility of MMAP[K] and the MMAP[K]/G[K]/1 Queue

This paper studies a single server queueing system with multiple types of customers. The first part of the paper discusses some modeling issues associated with the Markov arrival processes with marked arrivals (MMAP[K], where K is an integer representing the number of types of customers). The usefulness of MMAP[K] in modeling point processes is shown by a number of interesting examples. The second part of the paper studies a single server queueing system with an MMAP[K] as its input process. The busy period, virtual waiting time, and actual waiting times are studied. The focus is on the actual waiting times of individual types of customers. Explicit formulas are obtained for the Laplace–Stieltjes transforms of these actual waiting times.     

A modified vacation model M[x]/G/1 system

This paper studies the operating characteristics of an M^[x]/G/1 queueing system under a modified vacation policy, where the server leaves for a vacation as soon as the system is empty. The server takes at most J vacations repeatedly until at least one customer is found waiting in the queue when the server returns from a vacation. We derive the system size distribution at different points in time, as well as the waiting time distribution in the queue. Further, we derive some important characteristics including the expected length of the busy period and idle period. This shows that the results generalize those of the multiple vacation policy and the single vacation policy M^[x]/G/1 queueing system. Finally, a cost model is developed to determine the optimum of J at a minimum cost. Copyright © 2006 John Wiley & Sons, Ltd.     

Markov-modulatedPH/G/1 queueing systems

We study a PH/G/1 queue in which the arrival process and the service times depend on the state of an underlying Markov chain J(t) on a countable state spaceE. We derive the busy period process, waiting time and idle time of this queueing system. We also study the Markov modulated E_K/G/1 queueing system as a special case.     

Analysis of the adaptive MMAP[K]/PH[K]/1 queue: A multi-type queue with adaptive arrivals and general impatience

In this paper we introduce the adaptive MMAP[K] arrival process and analyze the adaptive MMAP[K]/PH[K]/1 queue. In such a queueing system, customers of K different types with Markovian inter-arrival times and possibly correlated customer types, are fed to a single server queue that makes use of r thresholds. Service times are phase-type and depend on the type of customer in service. Type k customers are accepted with some probability a_i,k if the current workload is between threshold i − 1 and i. The manner in which the arrival process changes its state after generating a type k customer also depends on whether the customer is accepted or rejected.     

Combined Elapsed Time and Matrix-Analytic Method for the Discrete Time GI/G/1 and GI X /G/1 Systems

In this paper, we show that the discrete GI/G/1 system can be easily analysed as a QBD process with infinite blocks by using the elapsed time approach in conjunction with the Matrix-geometric approach. The positive recurrence of the resulting Markov chain is more easily established when compared with the remaining time approach. The G-measure associated with this Markov chain has a special structure which is usefully exploited. Most importantly, we show that this approach can be extended to the analysis of the GI ^X /G/1 system. We also obtain the distributions of the queue length, busy period and waiting times under the FIFO rule. Exact results, based on computational approach, are obtained for the cases of input parameters with finite support – these situations are more commonly encountered in practical problems.     

The $$MMAP\left[ K \right]/PH\left[ K \right]/1$$ queues with a last-come-first-served preemptive service discipline

This paper studies two queueing systems with a Markov arrival process with marked arrivals and PH-distribution service times for each type of customer. Customers (regardless of their types) are served on a last-come-first-served preemptive resume and repeat basis, respectively. The focus is on the stationary distribution of queue strings in the system and busy periods. Efficient algorithms are developed for computing the stationary distribution of queue strings, the mean numbers of customers served in a busy period, and the mean length of a busy period. Comparison is conducted numerically between performance measures of queueing systems with preemptive resume and preemptive repeat service disciplines. A counter-intuitive observation is that for a class of service time distributions, the repeat discipline performs better than the resume one. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of a time-limited service priority queueing system with exponential timer and server vacations

We consider a multi-class priority queueing system with a non-preemptive time-limited service controlled by an exponential timer and multiple (or single) vacations. By reducing the service discipline to the Bernoulli schedule, we obtain an expression for the Laplace-Stieltjes transform (LST) of the waiting time distribution via an iteration procedure, and a recursive scheme to calculate the first two moments. It is noted that we have to select embedded Markov points based on the service beginning epochs instead of the service completion epochs adopted for most of M/G/1 queueing analyses. Through the queue-length analysis, we obtain a decomposition form for the LST of the waiting time in each queue having the exhaustive service.      

Batch arrival queue with N-policy and at most J vacations

This paper studies the operating characteristics of an M^[x]/G/1 queueing system with N-policy and at most J vacations. The server takes at most J vacations repeatedly until at least N customers returning from a vacation are waiting in the queue. If no customer arrives by the end of the Jth vacation, the server becomes idle in the system until the number of arrivals in the queue reaches N. We derive the system size distribution at a random epoch and departure epoch, as well as various system characteristics.     

Sojourn time distributions in the queue defined by a general QBD process

We consider a general QBD process as defining a FIFO queue and obtain the stationary distribution of the sojourn time of a customer in that queue as a matrix exponential distribution, which is identical to a phase-type distribution under a certain condition. Since QBD processes include many queueing models where the arrival and service process are dependent, these results form a substantial generalization of analogous results reported in the literature for queues such as the PH/PH/c queue. We also discuss asymptotic properties of the sojourn time distribution through its matrix exponential form.     

The Periodic BMAP/PH/c Queue

In queueing theory, most models are based on time-homogeneous arrival processes and service time distributions. However, in communication networks arrival rates and/or the service capacity usually vary periodically in time. In order to reflect this property accurately, one needs to examine periodic rather than homogeneous queues. In the present paper, the periodic BMAP/PH/c queue is analyzed. This queue has a periodic BMAP arrival process, which is defined in this paper, and phase-type service time distributions. As a Markovian queue, it can be analysed like an (inhomogeneous) Markov jump process. The transient distribution is derived by solving the Kolmogorov forward equations. Furthermore, a stability condition in terms of arrival and service rates is proven and for the case of stability, the asymptotic distribution is given explicitly. This turns out to be a periodic family of probability distributions. It is sketched how to analyze the periodic BMAP/M _t /c queue with periodically varying service rates by the same method.     

Multiplicative Semiprimeness of Skew Lie Algebras

Abstract

Let A be a semiprime associative algebra with an involution over a field of characteristic not 2, let K be the Lie algebra of all skew elements of A, and let Z _{[K, K]} denote the annihilator of the Lie algebra [K, K]. We will prove that the multiplication algebra of the semiprime Lie algebra [K, K]/Z _{[K, K]} is also semiprime. As a consequence, the multiplication algebra of [K, K]/Z _{[K, K]} is prime, whenever [K, K]/Z _{[K, K]} is prime. We will obtain similar results for the Lie algebra K/Z _K whenever the base field has characteristic zero.     

On performance comparison of MR/GI/1 queues

In this paper we are interested in the effect that dependencies in the arrival process to a queue have on queueing properties such as mean queue length and mean waiting time. We start with a review of the well known relations used to compare random variables and random vectors, e.g., stochastic orderings, stochastic increasing convexity, and strong stochastic increasing concavity. These relations and others are used to compare interarrival times in Markov renewal processes first in the case where the interarrival time distributions depend only on the current state in the underlying Markov chain and then in the general case where these interarrivai times depend on both the current state and the next state in that chain. These results are used to study a problem previously considered by Patuwo et al. [14].Then, in order to keep the marginal distributions of the interarrivai times constant, we build a particular transition matrix for the underlying Markov chain depending on a single parameter,p. This Markov renewal process is used in the Patuwo et al. [14] problem so as to investigate the behavior of the mean queue length and mean waiting time on a correlation measure depending only onp. As constructed, the interarrival time distributions do not depend onp so that the effects we find depend only on correlation in the arrival process.As a result of this latter construction, we find that the mean queue length is always larger in the case where correlations are non-zero than they are in the more usual case of renewal arrivals (i.e., where the correlations are zero). The implications of our results are clear.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

Convexity of single stage queueing systems with bulk arrival

In this paper we study the convexity of the waiting time, workload and the number of jobs in single stage queueing systems with respect to the bulk size of the arrival process. In particular we show that the number of jobs in a single server queueing systemG ^[x ]/GI/1 and in a multiple server queueing systemG ^[x]/M/c with bulk sizesx=(x ₁ ,x ₂ ,x ₃ ,...) is componentwise convex inx. This is in the sense of the sample path convexity introduced in Shaked and Shanthikumar [11]. These results have applications in the stochastic comparison of bulk arrival queueing systems.Research supported in part by NSF grant DDM-9113008.     

Bayesian analysis of M/Er/1 and M/H_k/1 queues

This paper describes Bayesian inference and prediction for some M/G/1 queueing models. Cases when the service distribution is Erlang, hyperexponential and hyperexponential with a random number of components are considered. Monte Carlo and Markov chain Monte Carlo methods are used for estimation of quantities of interest assuming the queue is in equilibrium. This revised version was published online in June 2006 with corrections to the Cover Date.     

M/G/1 retrial queueing systems with two types of calls and finite capacity

We consider anM/G/1 priority retrial queueing system with two types of calls which models a telephone switching system and a cellular mobile communication system. In the case that arriving calls are blocked due to the server being busy, type I calls are queued in a priority queue of finite capacityK whereas type II calls enter the retrial group in order to try service again after a random amount of time. In this paper we find the joint generating function of the numbers of calls in the priority queue and the retrial group in closed form. When ₁=0, it is shown that our results are consistent with the known results for a classical retrial queueing system.     

Submonoids of Polycyclic-by-Finite Groups and their Algebras

We describe Noetherian semigroup algebras K[S] of submonoids S of polycyclic-by-finite groups over a field K. As an application, we show that these algebras are finitely presented and also that they are Jacobson rings. Next we show that every prime ideal P of K[S] is strongly related to a prime ideal of the group algebra of a subgroup of the quotient group of S via a generalised matrix ring structure on K[S]/P. Applications to the classical Krull dimension, prime spectrum, and irreducible K[S]-modules are given.