Search

This articles focuses on M t /M t /N queue with catastrophes and obtains stability bounds for the main characteristics of the respective queue-length process. [ABSTRACT FROM AUTHOR]

We examine an M/M/1 retrial queue with an unreliable server whose arrival, service, failure, repair, and retrial rates are all modulated by an exogenous random environment. Provided are conditions for stability, the (approximate) orbit size distribution, and mean queueing performance measures which are obtained via matrix-analytic methods. Additionally, we consider the problem of choosing arrival and service rates for each environment state with the objective of minimizing the steady state mean time spent in orbit by an arbitrary customer, subject to cost and revenue constraints. Two numerical examples illustrate the main results. [ABSTRACT FROM AUTHOR]

This paper considers the so-called M/G/∞ model: jobs arrive according to a Poisson process with rate λ, and each of them stays in the system during a random amount of time, distributed as a non-negative random variable B; throughout it is assumed that B is light-tailed. With N(t) denoting the number of jobs in the system, the random process A(t) records the load imposed on the system in [0, t], i.e., [image omitted]. The main result concerns the tail asymptotics of A(t)/t: we find an explicit function f(·) such that [image omitted] for t large; here ϱ: = λB. A crucial issue is that A(t) does not have i.i.d. increments, which makes direct application of the classical Bahadur-Rao result impossible; instead an adaptation of this result is required. We compare the asymptotics found with the (known) asymptotics for ϱ → ∞ (and t fixed). [ABSTRACT FROM AUTHOR]

The article deals with the queueing system of GI/G/1 type with individual service and batch arrival of customers. The method of integral equations on a half-axis [0, ∞) is applied to obtain new results for the actual waiting time wn of nth arriving customer. The transient and steady state as n tends to infinity are considered. Some simplifications and numerical results for M/M/1, M/E2/1, and M2/M/1 queueing systems are derived as well. [ABSTRACT FROM AUTHOR]

We consider the length of a busy period in the M/D/∞ queue and show that it coincides with the sojourn time of the first customer in an M/D/1 processor-sharing queue. We further show that the busy period is intimately related with the stationary waiting time in the M/D/1 first-come-first-served queue. We present three characterizations for the distribution function of the busy period and an asymptotic expression for its tail distribution. The latter involves complex-valued branches of the Lambert W function. [ABSTRACT FROM AUTHOR]

We consider a queueing system with Poisson arrivals and arbitrarily distributed service times, vacation times, and start-up and close-down times. The model accepts two types of customers—the ordinary and the retrial customers—and the server takes a single vacation each time he becomes free. For such a model the stability conditions and the system state probabilities are investigated both in a transient and in the steady state. Numerical results are finally obtained and used to observe system performance for various values of the parameters. [ABSTRACT FROM AUTHOR]

In the article we study the M/G/1 queue, and collect results on the age, residual, and length of service, conditional on the number of customers present in the system. Special attention is given to the M/M/1 queue. [ABSTRACT FROM AUTHOR]

The main purpose of this article is to use the strong stability method to approximate the characteristics of the M2/G2/1 priority system with non-preemptive priority by those of the M/G/1 queue, when the arrival intensity of the priority stream is sufficiently small. This last queue is simpler and more exploitable. For this, we clarify the stability conditions and next obtain stability quantitative estimates with an exact computation of constants. From these theoretical results, we elaborate an algorithm allowing to verify the approximation conditions and to provide the made numerical error. In order to have an idea about the efficiency of this approach, we consider a concrete example whose results are compared with those obtained by our simulator. [ABSTRACT FROM AUTHOR]

This article studies a single-server queueing system with autonomous service and ℓ priority classes. Arrival and departure processes are governed by marked point processes. There are ℓ buffers corresponding to priority classes, and upon arrival a unit of the kth priority class occupies a place in the kth buffer. Let N(k), k = 1,2,..., ℓ denote the quota for the total kth buffer content. The values N(k) are assumed to be large, and queueing systems both with finite and infinite buffers are studied. In the case of a system with finite buffers, the values N(k) characterize buffer capacities. This article discusses a circle of problems related to optimization of performance measures associated with overflowing the quota of buffer contents, particularly buffers models. Our approach to this problem is new, and the presentation of our results is simple and clear for real applications. [ABSTRACT FROM AUTHOR]

This article studies multi-class loss systems with two layers of servers, where each server at the first layer is dedicated to a certain customer class, while the servers at the second layer can handle all customer classes. The routing of customers follows an overflow scheme, where arriving customers are preferentially directed to the first layer. Stochastic comparison and coupling techniques are developed for studying how the system is affected by the packing of customers, altered service rates, and altered server configurations. This analysis leads to computationally fast upper and lower bounds for the performance of the system. [ABSTRACT FROM AUTHOR]

This article considers a batch service polling system. We first study the case in which the server visits the queues cyclically, considering three different service regimes: gated, exhaustive, and globally gated. We subsequently analyze the case (the so-called “Israeli Queue”) in which the server first visits the queue with the “oldest” customer. In both cases, queue lengths and waiting times are the main performance measures under consideration. [ABSTRACT FROM AUTHOR]

We study a single server queueing system with general service time distribution and memoryless inter-arrival times. The arrival rate is not constant but varies with the number of customers in the system. A recursive formula for the conditional distribution of the remaining service time given the queue length is derived for an arbitrary epoch. It is also shown that this conditional distribution holds for arrival epochs. The recursion for the corresponding Laplace-Stieltjes transforms and expected values is given in a simple formula. [ABSTRACT FROM AUTHOR]

We present a continuous time model of maturation and survival, obtained as the limit of a compartmental evolution model when the number of compartments tends to infinity. We establish in particular an explicit formula for the law of the system output under inhomogeneous killing and when the input follows a time-inhomogeneous Poisson process. This approach allows the discussion of identifiability issues which are of difficult access for finite compartmental models. The article ends up with an example of application for anticancer drug pharmacokinetics/pharmacodynamics. [ABSTRACT FROM AUTHOR]

We study the property of dependence in lag for Markov chains on countable partially ordered state spaces and give conditions which ensure that a process is monotone in lag. In case of linearly ordered state spaces, proofs are based on the Lorentz inequality. However, we show that on partially ordered spaces Lorentz inequality is only true under additional assumptions. By using supermodular-type stochastic orders we derive comparison inequalities that compare the internal dependence structure of processes with that of their speeding-down versions. Applications of the results are presented for degradable exponential networks in which the nodes are subject to random breakdowns and repairs. We obtain comparison results for the breakdown processes as well as for the queue length processes that are not even Markovian on their own. [ABSTRACT FROM AUTHOR]

We investigate a new class of stochastic networks that exhibit a product form steady state distribution. The stochastic networks developed here are integrated models for networks of service stations and inventories. We integrate a server with attached inventory under (r, Q)- or (r, S)-policy into Jackson or Gordon-Newell networks. Replenishment lead times are non-zero and random and depend on the load of the system. While the inventory is depleted the server with attached inventory does not accept new customers (lost sales regime), but we assume that the lost sales are not lost to the system. We pursue three different approaches to handle routing with respect to this node during the time the inventory is empty. We derive stationary distributions of joint queue lengths and inventory processes in explicit product form. The stationary distributions are then used to calculate performance measures of the respective systems. We discuss the advantages and disadvantages of product form modeling in the context of service-inventory systems. Finally, we sketch two network models where several nodes may have an attached inventory. [ABSTRACT FROM AUTHOR]

A geometric tail decay of the stationary distribution has been recently studied for the GI/G/1 type Markov chain with both countable level and background states. This method is essentially the matrix analytic approach, and simplicity is an obvious advantage of this method. However, so far it can be only applied to the α-positive case (or the jittered case, as referred to in the literature). In this paper, we specialize the GI/G/1 type to a quasi-birth-and-death process. This not only refines some expressions because of the matrix geometric form for the stationary distribution, but also allows us to extend the study, in terms of the matrix analytic method, to non-α-positive cases. We apply the result to a generalized join-the-shortest-queue model, which only requires elementary computations. The obtained results enable us to discuss when the two queues are balanced in the generalized join-the-shortest-queue model, and establish the geometric tail asymptotics along the direction of the difference between the two queues. [ABSTRACT FROM AUTHOR]

Arrival processes to queues often exhibit time dependence, but time-dependent queues are notoriously difficult to analyze. Usually one adopts some kind of steady-state approximation for time-dependent performance. We consider a range of queueing models that see wide use in practice, particularly in the modeling of service industry applications, and develop approximations for the error involved in using a steady-state approximation for time-dependent quantities. We focus on the distribution of the waiting time before reaching service, although the approach we use could be extended to many other performance measures. The results reinforce and extend what is known about such errors. For example, customer abandonment leads to dramatic reductions in the error in steady-state approximations as compared to a system without customer abandonment. [ABSTRACT FROM AUTHOR]

In this paper a detailed study is presented on the first time to reach buffer capacity in a queue with batch arrivals and general service time distribution. A flexible analytical model of the input stream, which is the Batch Markovian Arrival Process (BMAP), is assumed. The results include the explicit formula for the Laplace transform of the distribution of the first buffer overflow time and discussion of its computational aspects. In addition, the popular special case of the BMAP queue, which is the batch Poisson arrival queue, is studied. Theoretical results are illustrated via numerical calculations based on IP traffic data. [ABSTRACT FROM AUTHOR]

We consider a model describing the waiting time of a server alternating between two service points. This model is described by a Lindley-type equation. We are interested in the time-dependent behaviour of this system and derive explicit expressions for its time-dependent waiting-time distribution, the correlation between waiting times, and the distribution of the cycle length. As our model is closely related to Lindley's recursion, we compare our results to those derived for Lindley's recursion. [ABSTRACT FROM AUTHOR]

In many quasi-birth and death processes, the state descriptor entails at least two variables of infinite dimension. In such contexts, the classical QBD structure encompassing an infinite level and a finite phase is insufficient to prescribe a complete algorithmic solution. At the same time, it is the case in many queues that service resources intended for one type of customer can serve the other type when none of the former are present. We refer to these in the sequel as “QBDs with boundary assistance.” In this paper we address structural properties of such systems, and establish the key results needed to develop an algorithmic solution. We consider two examples to illustrate: a spatially distributed queueing system with two areas and two servers, and a bilingual call centre. The form of the matrix geometric solution is presented, as well as the structure of the R matrix itself. Computational aspects and potential applications are also discussed. [ABSTRACT FROM AUTHOR]

We determine the equilibrium distribution for a class of quasi-birth-and-death (QBD) processes using the matrix-geometric method, which requires the determination of the rate matrix R . In contrast to most QBD processes, the class under consideration allows for an explicit description of R , by exploiting its probabilistic interpretation. We show that the problem of finding each element of R reduces to counting lattice paths in the transition diagram. For resolving this counting problem, we present an extended version of the classical Ballot theorem. We also present various examples of queueing models that fit into the class. [ABSTRACT FROM AUTHOR]

This paper considers Gaussian flows multiplexed in a queueing network, where the underlying correlation structure is assumed to be short-range dependent. Whereas previous work mainly focused on the FIFO setting, this paper addresses overflow characteristics of more complex buffer architectures. We subsequently analyze the tandem queue, a priority system, and generalized processor sharing. In a many-sources setting, we explicitly compute the exponential decay rate of the overflow probability. Our study relies on large-deviations arguments, e.g., Schilder's theorem. [ABSTRACT FROM AUTHOR]

We consider two variants of a two-station tandem network with blocking. In both variants the first server ceases to work when the queue length at the second station hits a ‘blocking threshold.’ In addition, in variant 2 the first server decreases its service rate when the second queue exceeds a ‘slow-down threshold, ’ which is smaller than the blocking level. In both variants the arrival process is Poisson and the service times at both stations are exponentially distributed. Note, however, that in case of slow-downs, server 1 works at a high rate, a slow rate, or not at all, depending on whether the second queue is below or above the slow-down threshold or at the blocking threshold, respectively. For variant 1, i.e., only blocking, we concentrate on the geometric decay rate of the number of jobs in the first buffer and prove that for increasing blocking thresholds the sequence of decay rates decreases monotonically and at least geometrically fast to max{? 1 , ? 2 }, where ? i is the load at server i . The methods used in the proof also allow us to clarify the asymptotic queue length distribution at the second station. Then we generalize the analysis to variant 2, i.e., slow-down and blocking, and establish analogous results. [ABSTRACT FROM AUTHOR]

A stochastic online version of the classical bin packing problem, where a bin corresponds to the capacity of a resource allocated among streams of requests at discrete time units, is a fundamental problem that arises in a wide variety of application areas including bandwidth allocation in networks, memory management in computers, and message transmission in slotted network channels. We derive a mathematical analysis of the corresponding multi-dimensional stochastic process, potentially infinite in each dimension, under a general class of scheduling policies based on a combination of a Lyapunov function technique and matrix-analytic methods. Our analysis yields stability conditions and stationary distributions for this stochastic bin packing process under general probability distributions. We further provide some algorithmic techniques for the numerical computation of these measures. [ABSTRACT FROM AUTHOR]

We consider a class of single server queueing systems in which customers arrive singly and service is provided in batches, depending on the number of customers waiting when the server becomes free. Service is independent of the batch size. This system could also be considered as a batch service queue in which a server visits the queue at arbitrary times and collects a batch of waiting customers for service, or waits for a customer to arrive if there are no waiting customers. A waiting server immediately collects and processes the first arriving customer. The system is considered in discrete time. The interarrival times of customers and the inter-visit times of the server, which we call the service time, have general distributions and are represented as remaining time Markov chains. We analyze this system using the matrix-geometric method and show that the resulting R matrix can be determined explicitly in some special cases and the stationary distributions are known semi-explicitly in some other special cases. [ABSTRACT FROM AUTHOR]

We consider two identical parallel M/M/&infinite; queues. A new arrival is routed to the queue with the smaller number of customers. If both system have equal occupancy, the arrival joins either with probability 1/2. These types of models have been used to describe CDMA (Code Division Multiple Access) cellular systems. We analyze this model both numerically and asymptotically. For the latter, we consider the limit ρ = γ/µ→&infinite;, where γ (resp.,μ) is the arrival (resp., service) rate. An efficient numerical method is developed for computing the joint steady-state distribution of the number of customers in the two queues. We give several asymptotic formulas, valid for different ranges of the state variables, which show the qualitative Structure of the joint distribution. The numerical accuracy of the asymptotic, results is tested. [ABSTRACT FROM AUTHOR]

Closed networks of exponential queues are prototypes of systems which show strong negative dependence properties. We use the device of a test customer traveling in the network to evaluate the qualitative behavior of the network's correlation. The results are: negative association of successive sojourn times during a cycle; negative correlation of two successive cycle times; feedback-sojourn times are positively associated; correlation between cycles vanishes over long distances geometrically fast. Generalizations to networks with general topology are given. Additionally we prove for cyclic networks that the conditional cycle time stochastically increases when the initial joint queue length vector increases with respect to the partial sum ordering. This connects the space–time correlation with space–time monotonicity. [ABSTRACT FROM AUTHOR]

A Markov process in discrete time is perturbed by a small parameter. A perturbation theory is constructed, both for a time-dependent process, and for a stationary state. Some queueing applications are discussed. [ABSTRACT FROM AUTHOR]