A Retrial Queue with a Constant Retrial Rate,Server Downs and Impatient Customers

ABSTRACT

In this paper, we consider a retrial queueing system consisting of a waiting line of infinite capacity in front of a single server subject to breakdowns. A customer upon arrival may join the queue (waiting line) or go to the retrial orbit (another queue) to retry for service after a random time. Only the customer at the head of the retrial orbit is allowed to retry for service. Upon retrial, the customer enters the service if the server is idle; otherwise, it may go back to the retrial orbit or leave the system (become impatient). All the interarrival times, service times, server up times, server down times and retrial times are exponential, and all the necessary independence conditions in these variables are assumed. For this system, we provide sufficient conditions under which, for any given number of customers in the orbit, the stationary probability of the number of customers in the waiting line decays geometrically. We also provide explicitly an expression for the decay parameter.     

Performance measures of M/G/1 retrial queues with recurrent customers,breakdowns, and general delays

In this paper, an M/G/1 retrial system with two classes of customers: transit and recurrent customers is studied. After service completion, recurrent customers always return to the orbit and transit customers leave the system forever. The server is subject to breakdowns and delayed repairs. The customer whose service is interrupted stays in the service, waiting for delay and repair of the server. After repair this customer completes his service. The study of the system concerns the joint generating function of the server state and the queue length in steady state. Some performance measures of the system are then derived and some numerical results are presented to illustrate the effect of the system parameters on the developed performance measures.     

Equilibrium strategies in a constant retrial queue with setup time and the N-policy

Abstract

In this article, customers’ strategic behavior and social optimation in a constant retrial queue with setup time and the N-policy are investigated. Customers who find the server isn’t idle either leave forever or enter an orbit. After a service, the server will seek a customer from the orbit at a constant rate. The server is closed whenever the system becomes empty, and is activated when the number of waitlisted customers reaches a threshold. We obtain the equilibrium arrival rates in different states. There exist both Follow-the-Crowd (FTC) and Avoid-the-Crowd (ATC) behaviors. Through the Particle Swarm Optimization (PSO) algorithm, we numerically obtain the optimal solution of the social welfare maximization problem. Finally, numerical examples are presented to illustrate the sensitivity of system performance measures.     

ANALYSIS OF A GI/G Y /1 SYSTEM IN DISCRETE-TIME

ABSTRACT

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.     

Subexponential asymptotics of the waiting time distribution in a single-server queue with multiple Markovian arrival streams

This paper considers subexponential asymptotics of the tail distributions of waiting times in stationary work-conserving single-server queues with multiple Markovian arrival streams, where all arrival streams are modulated by the underlying Markov chain with finite states and service time distributions may differ for different arrival streams. Under the assumption that the equilibrium distribution of the overall (i.e., customer-average) service time distribution is subexponential, a subexponential asymptotic formula is first shown for the virtual waiting time distribution, using a closed formula recently found by the author. Further when customers are served on a FIFO basis, the actual waiting time and sojourn time distributions of customers from respective arrival streams are shown to have the same asymptotics as the virtual waiting time distribution.     

COMPUTATION OF STEADY-STATE PROBABILITIES FOR RESOURCE-SHARING CALL-CENTER QUEUEING SYSTEMS

Two routing rules for a queueing system of two stations are considered as alternative models for modeling a call-center network. These routing rules allow customers to switch queues under certain server and other resource availability conditions, either external to the system upon arrival to the network, or internal to the system after arrival to a primary call center. Under the assumption of Poisson arrivals and exponentially distributed service times, these systems are analyzed using matrix-geometric techniques, yielding a non-trivial set of ergodicity conditions and the steady-state joint probability distribution for the number of customers at each station. An extensive numerical analysis is conducted, yielding some physical insight into these systems and related generalizations.     

Analysis of a discrete-time queue with load dependent service under discrete-time Markovian arrival process

In the study of normal queueing systems, the server’s average service times are generally assumed to be constant. However, in numerous applications this assumption may not be valid. To prevent congestion in overload control telecommunication networks, the transmission rates vary depending on the number of packets waiting in the queue. As traffics in telecommunication networks are of bursty nature and correlated, we assume that arrivals follow the discrete-time Markovian arrival process. This paper analyzes a queueing model in which the server changes its service times (rates) only at the beginning of service depending on the number of customers waiting in the queue. We obtain the steady-state probabilities at various epochs and some performance measures. In addition, varieties of numerical results are discussed to display the effect of the system parameters on the performance measures.     

Stationary analysis of a BMAP/R/1 queue with R-type multiple working vacations

We consider an infinite-buffer single server queue with batch Markovian arrival process (BMAP) and exhaustive service discipline under multiple working vacation policy. The service time during a working vacation is generally distributed random variable which is independent of the service times during a normal busy period as well as the arrival process. Duration of service times during a normal busy period and duration of working vacation times follow the class of distributions whose Laplace-Stieltjes transforms are rational functions (R-type distributions). The service time during a normal busy period, working vacation time, and the service time during a working vacation are independent of each other as well as of the arrival process. If a working vacation terminates while service is going on for a customer at head of the queue in vacation mode then, the server switches to normal mode and the customer at head of the queue is entitled to receive a full service time in the normal busy period irrespective of the amount of service received by the customer at head of the queue during the previous working vacation period. We obtain system-length distributions at various epoch, such as post-departure, pre-arrival, arbitrary, and pre-service. The proposed analysis is based on the use of matrix-analytic procedure to obtain system-length distribution at post-departure epoch. Later, we use supplementary variable technique and simple algebraic manipulations to obtain system-length distribution at arbitrary epoch using the system-length distribution at post-departure epoch. Some important performance measures, such as mean system lengths and mean waiting time have been obtained. Finally, some numerical results have been presented in the form of tables and graphs to show the applicability of the results obtained in this article. The model has potential application in areas of computer and communication networks, such as ethernet passive optical network (EPON).     

An Exact Analysis of the Multi‐class M/M/k Priority Queue with Partial Blocking

Abstract

We consider a multi‐server queuing model with two priority classes that consist of multiple customer types. The customers belonging to one priority class customers are lost if they cannot be served immediately upon arrival. Each customer type has its own Poisson arrival and exponential service rate. We derive an exact method to calculate the steady state probabilities for both preemptive and nonpreemptive priority disciplines. Based on these probabilities, we can derive exact expressions for a wide range of relevant performance characteristics for each customer type, such as the moments of the number of customers in the queue and in the system, the expected postponement time and the blocking probability. We illustrate our method with some numerical examples.     

Analysis and Computation of the Joint Queue Length Distribution in a FIFO Single-Server Queue with Multiple Batch Markovian Arrival Streams

This paper considers a work-conserving FIFO single-server queue with multiple batch Markovian arrival streams governed by a continuous-time finite-state Markov chain. A particular feature of this queue is that service time distributions of customers may be different for different arrival streams. After briefly discussing the actual waiting time distributions of customers from respective arrival streams, we derive a formula for the vector generating function of the time-average joint queue length distribution in terms of the virtual waiting time distribution. Further assuming the discrete phase-type batch size distributions, we develop a numerically feasible procedure to compute the joint queue length distribution. Some numerical examples are provided also.     

Matrix Product-Form Solutions for LCFs Preemptive Service Single-Server Queues with Batch Markovian Arrival Streams

ABSTRACT

This paper considers three variants of last-come first-served (LCFS) preemptive service single-server queues, where customers are served under the LCFS preemptive resume (LCFS-PR), preemptive repeat-different (LCFS-PD), and preemptive repeat-identical (LCFS-PI) disciplines, respectively. These LCFS queues are fed by multiple batch Markovian arrival streams. Service times of customers from each arrival stream are generally distributed and their distributions may differ among different streams. For each of LCFS-PR, LCFS-PD, and LCFS-PI queues, we show that the stationary distribution of the queue string representing enough information to keep track of queueing dynamics has a matrix product-form solution. Further, this paper discusses the stability of LCFS-PD and LCFS-PI queues based on the busy cycle. Finally, by numerical experiment, we examine the impact of the variation of the service time distribution on the mean queue lengths for the three variants of LCFS queues.     

AN INFINITE-PHASE QUASI-BIRTH-AND-DEATH MODEL FOR THE NON-PREEMPTIVE PRIORITY M/PH/1 QUEUE

This paper considers a single server queue that handles arrivals from N classes of customers on a non-preemptive priority basis. Each of the N classes of customers features arrivals from a Poisson process at rate λ _i and class-dependent phase type service. To analyze the queue length and waiting time processes of this queue, we derive a matrix geometric solution for the stationary distribution of the underlying Markov chain. A defining characteristic of the paper is the fact that the number of distinct states represented within the sub-level is countably infinite, rather than finite as is usually assumed. Among the results we obtain in the two-priority case are tractable algorithms for the computation of both the joint distribution for the number of customers present and the marginal distribution of low-priority customers, and an explicit solution for the marginal distribution of the number of high-priority customers. This explicit solution can be expressed completely in terms of the arrival rates and parameters of the two service time distributions. These results are followed by algorithms for the stationary waiting time distributions for high- and low-priority customers. We then address the case of an arbitrary number of priority classes, which we solve by relating it to an equivalent three-priority queue. Numerical examples are also presented.     

Multi-class M/PH/1 queues with deterministic impatience times

This article considers computational procedures for the waiting time and queue length distributions in stationary multi-class first-come, first-served single-server queues with deterministic impatience times. There are several classes of customers, which are distinguished by deterministic impatience times (i.e., maximum allowable waiting times). We assume that customers in each class arrive according to an independent Poisson process and a single server serves customers on a first-come, first-served basis. Service times of customers in each class are independent and identically distributed according to a phase-type distribution that may differ for different classes. We first consider the stationary distribution of the virtual waiting time and then derive numerically feasible formulas for the actual waiting time distribution and loss probability. We also analyze the joint queue length distribution and provide an algorithmic procedure for computing the probability mass function of the stationary joint queue length.     

Simultaneous arrival of customers to two different queues and modeling dependence via copula approach

ABSTRACT

In classical queueing systems, a customer is allowed to wait only in one queue to receive the service. In practice, when there exist a number of queues rendering the same service, some customers may tend to simultaneously take turn in more than one queue with the aim to receive the service sooner and thus reduce their waiting time. In this article, we introduce such a model and put forward a methodology to deal with the situation. In this regard, we consider two queues and assume that if a customer, who has turn in both queues, receives the service from one of the queues, the other turn is automatically withdrawn. This circumstance for the model brings about some abandonment in each queue as some customers receive the service from the other one. We study the customer’s waiting time in the mentioned model, which is defined as the minimum of waiting times in both queues and obtain probability density function of this random variable. Our approach to obtain probability density function of each of the waiting time random variables is to rely on the existing results for the abandonment case. We examine the situation for the cases of independence and dependence of the waiting time random variables. The latter is treated via a copula approach.     

Limit theorems for single server queues with mixed renewal and poisson inputs

The following queuing system is considered:Two independent recurrent input streams (streams 1 and 2) arrive at a server. It is assumed that stream 1 is of Poisson type. Three priority disciplines are studied in case that these customers have priority:head-of-the-line, preemptive-resume, and preemptive-repeat discipline. Formulas derived for the limiting distribution functions of the actual and the virtual waiting time of low priority customers and of the number of these customers in the system, by using of independences of certain random processes when the time tends to infinity.     

A two phases queueing system with Bernoulli vacation schedule under multiple vacation policy

This paper deals with a single server Poisson arrival queue with two phases of heterogeneous service along with a Bernoulli schedule vacation model, where after two successive phases service the server either goes for a vacation with probability p (0≤p≤1) or may continue to serve the next unit, if any, with probability q(=1−p). Further the concept of multiple vacation policy is also introduced here. We obtained the queue size distributions at a departure epoch and at a random epoch, Laplace Stieltjes Transform of the waiting time distribution and busy period distribution along with some mean performance measures. Finally we discuss some statistical inference related issues.     

POLLING SYSTEMS WITH SIMULTANEOUS BATCH ARRIVALS

We study the delay in polling systems with simultaneous batch arrivals. Arrival epochs are generated according to a Poisson process. At any arrival epoch, batches of customers may arrive simultaneously at the different queues, according to a general joint batch-size distribution. The server visits the queues in cyclic order, the service times and the switch-over times are generally distributed, and the service disciplines are general mixtures of gated and exhaustive service. We derive closed-form expressions for the expected delay at each of the queues when the load tends to unity (under proper scalings), in a general parameter setting. The results are strikingly simple and reveal explicitly how the expected delay depends on the system parameters, and in particular, on the batch-size distributions and the simultaneity of the batch arrivals. Moreover, the results suggest simple and fast-to-evaluate approximations for the expected delay in heavily loaded polling systems. Numerical experiments demonstrate that the approximations are highly accurate in medium and heavily loaded systems.     

BMAP/G/1 Queue Under D-Policy: Queue Length Analysis

ABSTRACT

We study the queue length distribution of a queueing system with BMAP arrivals under D-policy. The idle server begins to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We derive the vector generating functions of the queue lengths both at a departure and at an arbitrary point of time. Mean queue lengths are derived and a numerical example is presented.     

Queue Length Analysis of MAP/G/1 Queue Under D-Policy

Abstract

We study the queue length distribution of a queueing system with MAP arrivals under D-policy. The idle server begins to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We derive the vector generating functions of the queue lengths both at a departure and at an arbitrary point of time. Mean queue lengths will be derived from these transform results. A numerical example is provided.     

On some probability distributions associated with random walks

The probability distribution of the total number of games to ruin in a gambler's ruin random walk with initial position n, the probability distribution of the total size of an epidemic starting with n cases and the probability distribution of the number of customers served during a busy period M/M/1 when the service starts with n waiting customers are identical. All these can be easily obtained by using Lagrangian expansions instead of long combinatorial methods. The binomial, trinomial, quadrinomial and polynomial random walks of a particle have been considered with an absorbing barrier at 0 when the particle starts its walks from a point n, and the pgfs. and the probability distributions of the total number of jumps (trials) before absorption at 0 have been obtained. The values for the mean and variance of such walks have also been given.