On the M/G/2 queeing model

The M/G/2 queueing model with service time distribution a mixture of m negative exponential distributions is analysed. The starting point is the functional relation for the Laplace–Stieltjes transform of the stationary joint distribution of the workloads of the two servers. By means of Wiener–Hopf decompositions the solution is constructed and reduced to the solution of m linear equations of which the coefficients depend on the zeros of a polynome. Once this set of equations has been solved the moments of the waiting time distribution can be easily obtained. The Laplace–Stieltjes transform of the stationary waiting time distribution has been derived, it is an intricate expression.     

Computing steady-state queueing-time distributions of single-server queues:GI X /M/1

This paper presents a computationally efficient method to find the steady-state distributions of actual queueing times of the first customer, as well as of a randomly selected customer, of an arrival group for the queueing systemGI ^X /M/1, and hence the queueing-time distribution of a customer for the systemGI/E _X /1. The distribution of virtual queueing time is also obtained. Approximate analysis based on one or more roots is also discussed. Though the exact detailed as well as approximate computations for a variety of interarrival-time distributions such as generalized Erlang, mixed generalized Erlang, hyperexponential, generalized hyperexponential, and deterministic have been carried out, only representative results in the form of tables have been appended. The results obtained should prove useful to queueing theorists, practitioners, and others.     

Multi-server queueing system with a generalized phase-type service time distribution as a model of call center with a call-back option

A multi-server queueing system with a Markovian arrival process and finite and infinite buffers to model a call center with a call-back option is investigated. If all servers are busy during the customer arrival epoch, the customer may leave the system forever or move to the buffer (such a customer is referred to as a real customer), or, alternatively, request for call-back (such a customer is referred to as a virtual customer). During a waiting period, a real customer can be impatient and may leave the system without service or request for call-back (becomes a virtual customer). The service time of a customer and the dial time to a virtual customer for a server have a phase-type distribution. To simplify the investigation of the system we introduce the notion of a generalized phase-type service time distribution. We determine the stationary distribution of the system states and derive the Laplace–Stieltjes transforms of the sojourn and waiting time distributions for real and virtual customers. Some key performance measures are calculated and numerical results are presented.     

Exact and approximate numerical solutions of steady-state distributions arising in the queueGI/G/1

In this paper we first obtain, in a unified way, closed-form analytic expressions in terms of roots of the so-called characteristic equation (c.e.), and then discuss the exact numerical solutions of steady-state distributions of (i) actual queueing time, (ii) virtual queueing time, (iii) actual idle time, and (iv) interdeparture time for the queueGI/R/1, whereR denotes the class of distributions whose Laplace-Stieltjes transforms (LSTs) are rational functions (ratios of a polynomial of degree at mostn to a polynomial of degreen). For the purpose of numerical discussions of idle- and interdeparture-time distributions, the interarrival-time distribution is also taken to belong to the classR. It is also shown that numerical computations of the idle-time distribution ofR/G/1 queues can be done even ifG is not taken asR. Throughout the discussions it is assumed that the queue discipline is first-come-first-served (FCFS). For the tail of the actual queueing-time distribution ofGI/R/1, approximations in terms of one or more roots of the c.e. are also discussed. If more than one root is used, they are taken in ascending order of magnitude. Numerical aspects have been tested for a variety of complex interarrival- and service-time distributions. The analysis is not restricted to generalized distributions with phases such as Coxian-n (C _n ), but also covers nonphase type distributions such as uniform (U) and deterministic (D). Some numerical results are also presented in the form of tables and figures. It is expected that the results obtained from the present study should prove to be useful not only to practitioners, but also to queueing theorists who would like to test the accuracies of inequalities, bounds or approximations.     

A G/M/1 retrial queue with constant retrial rate

In this paper, we are concerned with the analytical treatment of an GI/M/1 retrial queue with constant retrial rate. Constant retrial rate is typical for some real world systems where the intensity of individual retrials is inversely proportional to the number of customers in the orbit or only one customer from the orbit is allowed to make the retrials. In our model, a customer who finds the server busy joins the queue in the orbit in accordance with the FCFS (first-come-first-out) discipline and only the oldest customer in the queue is allowed to make the repeated attempts to reach the server. A distinguishing feature of the considered system is an arbitrary distribution of inter-arrival times, while the overwhelming majority of the papers is devoted to the retrial systems with the stationary Poisson arrival process. We carry out an extensive analytical analysis of the queue in steady state using the well-known matrix analytic technique. The ergodicity condition and simple expressions for the stationary distributions of the system states at pre-arrival, post-arrival and arbitrary times are derived. The important and difficult problem of finding the stationary distribution of the sojourn time is solved in terms of the Laplace–Stieltjes transform. Little’s formula is proved. Numerical illustrations are presented.     

Waiting times in queueing networks with a single shared server

We study a queueing network with a single shared server that serves the queues in a cyclic order. External customers arrive at the queues according to independent Poisson processes. After completing service, a customer either leaves the system or is routed to another queue. This model is very generic and finds many applications in computer systems, communication networks, manufacturing systems, and robotics. Special cases of the introduced network include well-known polling models, tandem queues, systems with a waiting room, multi-stage models with parallel queues, and many others. A complicating factor of this model is that the internally rerouted customers do not arrive at the various queues according to a Poisson process, causing standard techniques to find waiting-time distributions to fail. In this paper, we develop a new method to obtain exact expressions for the Laplace–Stieltjes transforms of the steady-state waiting-time distributions. This method can be applied to a wide variety of models which lacked an analysis of the waiting-time distribution until now.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

The effect of different arrival rates on the N-policy of M/G/1 with server setup

It is very important in many real-life systems to decide when the server should start his service because frequent setups inevitably make the operating cost too high. Furthermore, today's systems are too intelligent for the input to be assumed as a simple homogenous Poisson process. In this paper, an M/G/1 queue with general server setup time under a control policy is studied. We consider the case when the arrival rate varies according to the server's status: idle, setup and busy states. We derive the distribution function of the steady-state queue length, as well as the Laplace–Stieltjes transform of waiting time. For this model, the optimal N-value from which the server starts his setup is found by minimizing the total operation cost of the system. We finally investigate the behavior of system operation cost and the optimal N for various arrival rates by a numerical study.     

Distributional versions of littlewood’s Tauberian theorem

We provide several general versions of Littlewood’s Tauberian theorem. These versions are applicable to Laplace transforms of Schwartz distributions. We employ two types of Tauberian hypotheses; the first kind involves distributional boundedness, while the second type imposes a one-sided assumption on the Cesàro behavior of the distribution. We apply these Tauberian results to deduce a number of Tauberian theorems for power series and Stieltjes integrals where Cesàro summability follows from Abel summability. We also use our general results to give a new simple proof of the classical Littlewood one-sided Tauberian theorem for power series.     

Analysis of stationary discrete-time GI/D-MSP/1 queue with finite and infinite buffers

This paper considers a single-server queueing model with finite and infinite buffers in which customers arrive according to a discrete-time renewal process. The customers are served one at a time under discrete-time Markovian service process (D-MSP). This service process is similar to the discrete-time Markovian arrival process (D-MAP), where arrivals are replaced with service completions. Using the imbedded Markov chain technique and the matrix-geometric method, we obtain the system-length distribution at a prearrival epoch. We also provide the steady-state system-length distribution at an arbitrary epoch by using the supplementary variable technique and the classical argument based on renewal-theory. The analysis of actual-waiting-time (in the queue) distribution (measured in slots) has also been investigated. Further, we derive the coefficient of correlation of the lagged interdeparture intervals. Moreover, computational experiences with a variety of numerical results in the form of tables and graphs are discussed.     

The Busy Period and the Waiting Time Analysis of a MAP/M/c Queue with Finite Retrial Group

Abstract

We concentrate on the analysis of the busy period and the waiting time distribution of a multi-server retrial queue in which primary arrivals occur according to a Markovian arrival process (MAP). Since the study of a model with an infinite retrial group seems intractable, we deal with a system having a finite buffer for the retrial group. The system is analyzed in steady state by deriving expressions for (a) the Laplace–Stieltjes transforms of the busy period and the waiting time; (b) the probabiliy generating functions for the number of customers served during a busy period and the number of retrials made by a customer; and (c) various moments of quantites of interest. Some illustrative numerical examples are discussed.     

Analysis of BMAP/G/1 Queue with Reservation of Service

Abstract

In this article, we study BMAP/G/1 queue with service time distribution depending on number of processed items. This type of queue models the systems with the possibility of preliminary service. For the considered system, an efficient algorithm for calculating the stationary queue length distribution is proposed, and Laplace–Stieltjes transform of the sojourn time is derived. Little's law is proved. An optimization problem is considered.     

Sojourn times in a random queue with and without preemption

We consider an equilibrium M/M/1 queue in which customers arrive at a random position, both for the preemptive and non-preemptive cases. The Laplace–Stieltjes transforms of their sojourn time distributions are derived and in the latter case it is verified that the result is that of an M/M/1 queue where the server chooses the next task to serve at random.     

Solving Ck/Cm/1/N queues by using characteristic roots in matrix analytic methods

In this paper, we study a C_k/C_m/1/N open queueing system with finite capacity. We investigate the property which shows that a product of the Laplace Stieltjes Transforms of interarrival and service times distributions satisfies an equation of a simple form. According to this equation, we present that the stationary probabilities on the unboundary states can be written as a linear combination of vector product-forms. Each component of these products is expressed in terms of roots of an associated characteristic polynomial. As a result, we carry out an algorithm for solving stationary probabilities in C_k/C_m/1/N systems, which is independent of N, hence greatly reducing the computational complexity.     

On two-queue Markovian polling systems with exhaustive service

We consider a class of two-queue polling systems with exhaustive service, where the order in which the server visits the queues is governed by a discrete-time Markov chain. For this model, we derive an expression for the probability generating function of the joint queue length distribution at polling epochs. Based on these results, we obtain explicit expressions for the Laplace–Stieltjes transforms of the waiting-time distributions and the probability generating function of the joint queue length distribution at an arbitrary point in time. We also study the heavy-traffic behaviour of properly scaled versions of these distributions, which results in compact and closed-form expressions for the distribution functions themselves. The heavy-traffic behaviour turns out to be similar to that of cyclic polling models, provides insights into the main effects of the model parameters when the system is heavily loaded, and can be used to derive closed-form approximations for the waiting-time distribution or the queue length distribution.     

Stationary analysis of a discrete-time GI/D-MSP/1 queue with multiple vacations

This paper analyzes the steady-state behavior of a discrete-time single-server queueing system with correlated service times and server vacations. The vacation times of the server are independent and geometrically distributed, and their durations are integral multiples of slot duration. The customers are served one at a time under discrete-time Markovian service process. The new service process starts with the initial phase distribution independent of the path followed by the previous service process when the server returns from a vacation and finds at least one waiting customer. The matrix-geometric method is used to obtain the probability distribution of system-length at prearrival epoch. With the help of Markov renewal theory approach, we also derive the system-length distribution at an arbitrary epoch. The analysis of actual-waiting-time distribution in the queue measured in slots has also been carried out. In addition, computational experiences with a variety of numerical results are discussed to display the effect of the system parameters on the performance measures.     

The approximation of Laplace–Stieltjes transformations with finite order on the left half plane

In this paper, we study the error in approximating the analytic function defined by a Laplace–Stieltjes transformation of finite order, which converges on the left half plane, and obtain the relation theorems between the error, the coefficients, and the proximate order of the Laplace–Stieltjes transformation.     

广义Laplace-Stieltjes变换的准确零(R)级

本文对广义Ｌａｐｌａｃｅ－Ｓｔｉｅｌｔｊｅｓ变换确定的解析函数引进了准确零（Ｒ）级的概念，得到了这样的函数有准确零（Ｒ）级的两个充要条件．其结果类似于指数级数     

Derivation of the N-step interdeparture time distribution in GI/G/1 queueing systems

The departure process of a queueing system has been studied since the 1960s. Due to its inherent complexity, closed form solutions for the distribution of the departure process are nearly intractable. In this paper, we derive a closed form expression for the distribution of interdeparture time in a GI/G/1 queueing model. Without loss of generality, we consider an embedded Markov chain in a general K_M/G/1 queueing system, in which the interarrival time distribution is Coxian and service time distribution is general. Closed form solutions of the equilibrium distribution are derived for this model and the Laplace–Stieltjes transform (LST) of the distribution of interdeparture times is presented. An algorithmic computing procedure is given and numerical examples are provided to illustrate the results. With the analysis presented, we provide a novel analytic tool for studying the departure process in a general queueing model.     

Batch arrival single-server queue with variable service speed and setup time

In this paper, we consider an M\({}^X\)/M/1/SET-VARI queue which has batch arrivals, variable service speed and setup time. Our model is motivated by power-aware servers in data centers where dynamic scaling techniques are used. The service speed of the server is proportional to the number of jobs in the system. The contribution of our paper is threefold. First, we obtain the necessary and sufficient condition for the stability of the system. Second, we derive an expression for the probability generating function of the number of jobs in the system. Third, our main contribution is the derivation of the Laplace–Stieltjes transform (LST) of the sojourn time distribution, which is obtained in series form involving infinite-dimensional matrices. In this model, since the service speed varies upon arrivals and departures of jobs, the sojourn time of a tagged job is affected by the batches that arrive after it. This makes the derivation of the LST of the sojourn time complex and challenging. In addition, we present some numerical examples to show the trade-off between the mean sojourn time (response time) and the energy consumption. Using the numerical inverse Laplace–Stieltjes transform, we also obtain the sojourn time distribution, which can be used for setting the service-level agreement in data centers.