Transient distributions of level dependent quasi-birth-death processes with linear transition rates

Many queueing systems such asM/M/s/K retrial queue with impatient customers, MAP/PH/1 retrial queue, retrial queue with two types of customers andMAP/M/∞ queue can be modeled by a level dependent quasi-birth-death (LDQBD) process with linear transition rates of the form λ_k = α+ βk at each levelk. The purpose of this paper is to propose an algorithm to find transient distributions for LDQBD processes with linear transition rates based on the adaptive uniformizaton technique introduced by van Moorsel and Sanders [11]. We apply the algorithm to some retrial queues and present numerical results.     

Exact Asymptotics for k i -limited Exponential Polling Models

In this paper we find exact asymptotic expressions for the event that the total queue length is large for a k _i -limited exponential polling model with equal service rates and two classes of customer. It is found that this behaviour divides into two very different regimes, depending on the arrival rates to the system. Using these exact asymptotic expressions, we provide heuristics for choosing the k _i values to provide a given level of quality of service to one class while giving best effort to the other class.     

Scheduling strategies and long-range dependence

Consider a single server queue with unit service rate fed by an arrival process of the following form: sessions arrive at the times of a Poisson process of rate λ, with each session lasting for an independent integer time τ ⩾ 1, where P(τ = k) = p _k with p _k ~ αk ^−(1+α) L(k), where 1 < α < 2 and L(·) is a slowly varying function. Each session brings in work at unit rate while it is active. Thus the work brought in by each arrival is regularly varying, and, because 1 < α < 2, the arrival process of work is long-range dependent. Assume that the stability condition λE[τ] < 1 holds. By simple arguments we show that for any stationary nonpreemptive service policy at the queue, the stationary sojourn time of a typical session must stochastically dominate a regularly varying random variable having infinite mean; this is true even if the duration of a session is known at the time it arrives. On the other hand, we show that there exist causal stationary preemptive policies, which do not need knowledge of the session durations at the time of arrival, for which the stationary sojourn time of a typical session is stochastically dominated by a regularly varying random variable having finite mean. These results indicate that scheduling policies can have a significant influence on the extent to which long-range dependence in the arrivals influences the performance of communication networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Factorization and Stochastic Decomposition Properties in Bulk Queues with Generalized Vacations

This paper considers a class of stationary batch-arrival, bulk-service queues with generalized vacations. The system consists of a single server and a waiting room of infinite capacity. Arrivals of customers follow a batch Markovian arrival process. The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in groups of fixed size B. For this class of queues, we show that the vector probability generating function of the stationary queue length distribution is factored into two terms, one of which is the vector probability generating function of the conditional queue length distribution given that the server is on vacation. The special case of batch Poisson arrivals is carefully examined, and a new stochastic decomposition formula is derived for the stationary queue length distribution.AMS subject classification: 60K25, 90B22, 60K37     

Asymptotic analysis for multi-objective sequential stochastic assignment problems

ABSTRACT

We provide an asymptotic analysis of multi-objective sequential stochastic assignment problems (MOSSAP). In MOSSAP, a fixed number of tasks arrive sequentially, with an n-dimensional value vector revealed upon arrival. Each task is assigned to one of a group of known workers immediately upon arrival, with the reward given by an n-dimensional product-form vector. The objective is to maximize each component of the expected reward vector. We provide expressions for the asymptotic expected reward per task for each component of the reward vector and compare the convergence rates for three classes of Pareto optimal policies.     

The Vector Space Kinna‐Wagner Principle is Equivalent to the Axiom of Choice

We show that the axiom of choice AC is equivalent to the Vector Space Kinna‐Wagner Principle, i.e., the assertion: “For every family 𝒱= {V_i : i ∈ k} of non trivial vector spaces there is a family ℱ = {F_i : i ∈ k} such that for each i ∈ k, F_i is a non empty independent subset of V_i”. We also show that the statement “every vector space over ℚ has a basis” implies that every infinite well ordered set of pairs has an infinite subset with a choice set, a fact which is known not to be a consequence of the axiom of multiple choice MC.     

A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

Queue length distributions in a markov model of a multistage clocked queueing network

In [4], we treated the problem of passage through a discrete-time clock-regulated multistage queueing network by modeling the input time series {a_n} to each queue as a Markov chain. We showed how to transform probability transition information from the input of one queue to the input of the next in order to predict mean queue length at each stage. The Markov approximation is very good for p = E(a_n) ≦ ½, which is in fact the range of practical utility. Here we carry out a Markov time series input analysis to predict the stage to stage change in the probability distribution of queue length. The main reason for estimating the queue length distribution at each stage is to locate “hot spots”, loci where unrestricted queue length would exceed queue capacity, and a quite simple expression is obtained for this purpose.     

Approximate Queueing Formulae Based on Consideration of the Busy Period

An approximation formula to one in M/M/1 queueing theory for hours in a queue is examined. Then it is extended to models M/D/1 and M/E _k /1 whereby wasted time or queue length is found to lie between two extremes. An empirical approximation to traffic intensity called utilization rate is used.     

Traffic processes in a class of finite Markovian queues

This paper exposes the stochastic structure of traffic processes in a class of finite state queueing systems which are modeled in continuous time as Markov processes. The theory is presented for theM/E _k /φ/L class under a wide range of queue disciplines. Particular traffic processes of interest include the arrival, input, output, departure and overflow processes. Several examples are given which demonstrate that the theory unifies many earlier works, as well as providing some new results. Several extensions to the model are discussed.     

Solving convex optimization with side constraints in a multi-class queue by adaptive c\mu rule

We study convex optimization problems with side constraints in a multi-class \(M/G/1\) queue with controllable service rates. In the simplest problem of optimizing linear costs with fixed service rate, the \(c\mu \) rule is known to be optimal. A natural question to ask is whether such simple policies exist for more complex control objectives. In this paper, combining the achievable region approach in queueing systems and the Lyapunov drift theory suitable to optimize renewal systems with time-average constraints, we show that convex optimization problems can be solved by variants of adaptive \(c\mu \) rules. These policies greedily re-prioritize job classes at the end of busy periods in response to past observed delays in each job class. Our method transforms the original problems into a new set of queue stability problems, and the adaptive \(c\mu \) rules are queue stable policies. An attractive feature of the adaptive \(c\mu \) rules is that they use limited statistics of the queue, where no statistics are required for the problem of satisfying average queueing delay in each job class.     

Iterative approximation of <Emphasis Type="Italic">k</Emphasis>-limited polling systems

The present paper deals with the problem of calculating queue length distributions in a polling model with (exhaustive) k-limited service under the assumption of general arrival, service and setup distributions. The interest for this model is fueled by an application in the field of logistics. Knowledge of the queue length distributions is needed to operate the system properly. The multi-queue polling system is decomposed into single-queue vacation systems with k-limited service and state-dependent vacations, for which the vacation distributions are computed in an iterative approximate manner. These vacation models are analyzed via matrix-analytic techniques. The accuracy of the approximation scheme is verified by means of an extensive simulation study. The developed approximation turns out to be accurate, robust and computationally efficient. This research is supported by the Technology Foundation STW, applied science division of NWO and the technology programme of the Dutch Ministry of Economic Affairs.     

On the multi-phase M/G/1 queueing system with random feedback

In this paper we consider an M/G/1 queue with k phases of heterogeneous services and random feedback, where the arrival is Poisson and service times has general distribution. After the completion of the i-th phase, with probability θ _i the (i + 1)-th phase starts, with probability p _i the customer feedback to the tail of the queue and with probability 1 − θ _i − p _i  = q _i departs the system if service be successful, for i = 1, 2 , . . . , k. Finally in kth phase with probability p _k feedback to the tail of the queue and with probability 1 − p _k departs the system. We derive the steady-state equations, and PGF’s of the system is obtained. By using them the mean queue size at departure epoch is obtained.     

Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing Systems

We study a processing system comprised of parallel queues, whose individual service rates are specified by a global service mode (configuration). The issue is how to switch the system between various possible service modes, so as to maximize its throughput and maintain stability under the most workload-intensive input traffic traces (arrival processes). Stability preserves the job inflow–outflow balance at each queue on the traffic traces. Two key families of service policies are shown to maximize throughput, under the mild condition that traffic traces have long-term average workload rates. In the first family of cone policies, the service mode is chosen based on the system backlog state belonging to a corresponding cone. Two distinct policy classes of that nature are investigated, MaxProduct and FastEmpty. In the second family of batch policies (BatchAdapt), jobs are collectively scheduled over adaptively chosen horizons, according to an asymptotically optimal, robust schedule. The issues of nonpreemptive job processing and non-negligible switching times between service modes are addressed. The analysis is extended to cover feed-forward networks of such processing systems/nodes. The approach taken unifies and generalizes prior studies, by developing a general trace-based modeling framework (sample-path approach) for addressing the queueing stability problem. It treats the queueing structure as a deterministic dynamical system and analyzes directly its evolution trajectories. It does not require any probabilistic superstructure, which is typically used in previous approaches. Probability can be superposed later to address finer performance questions (e.g., delay). The throughput maximization problem is seen to be primarily of structural nature. The developed methodology appears to have broader applicability to other queueing systems.     

Classification of matrix subalgebras of length 1

We define the length of a finite system of generators of a given algebra $ \mathcal{A} $ as the smallest number k such that words of length not greater than k generate $ \mathcal{A} $ as a vector space, and the length of the algebra is the maximum of the lengths of its systems of generators. In this paper, we obtain a classification of matrix subalgebras of length 1 up to conjugation. In particular, we describe arbitrary commutative matrix subalgebras of length 1, as well as those that are maximal with respect to inclusion.     

A nested family of $$\varvec{}$$-total effective rewards for positional games

We consider Gillette’s two-person zero-sum stochastic games with perfect information. For each \(k \in \mathbb {N}=\{0,1,\ldots \}\) we introduce an effective reward function, called k-total. For \(k = 0\) and 1 this function is known as mean payoff and total reward, respectively. We restrict our attention to the deterministic case. For all k, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that k-total reward games can be embedded into \((k+1)\)-total reward games.     

An explicit solution to a tandem queueing model

We consider two queues in tandem, each with an exponential server, and with deterministic arrivals to the first queue. We obtain an explicit solution for the steady state distribution of the process (N₁(t), N₂(t), Y(t)), where N_j(t) is the queue length in the jth queue and Y(t) measures the time elapsed since the last arrival. Then we obtain the marginal distributions of (N₁(t), N₂(t)) and of N₂(t). We also evaluate the solution in various limiting cases, such as heavy traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

2-affine complete algebras need not be affine complete

For each we exhibit a finite algebra R _k such that R _k is k-affine complete, but not (k+1)-affine complete; this means that every k-ary congruence preserving function on R _k lies in , but there is a (k +1)-ary congruence preserving function of R _k that does not lie in . Received September 27, 2001; accepted in final form February 9, 2002.     

Diffusion Approximations for Queues with Markovian Bases

Consider a base family of state-dependent queues whose queue-length process can be formulated by a continuous-time Markov process. In this paper, we develop a piecewise-constant diffusion model for an enlarged family of queues, each of whose members has arrival and service distributions generalized from those of the associated queue in the base. The enlarged family covers many standard queueing systems with finite waiting spaces, finite sources and so on. We provide a unifying explicit expression for the steady-state distribution, which is consistent with the exact result when the arrival and service distributions are those of the base. The model is an extension as well as a refinement of the M/M/s-consistent diffusion model for the GI/G/s queue developed by Kimura [13] where the base was a birth-and-death process. As a typical base, we still focus on birth-and-death processes, but we also consider a class of continuous-time Markov processes with lower-triangular infinitesimal generators.