Delay analysis of discrete-time priority queue with structured inputs

This paper investigates a discrete-time priority queue with multi-class customers. Applying a delay-cycle analysis, we explicitly derive the probability generating function of the waiting time for an individual class in a geometric batch input queue under preemptive-resume and head-of-the-line priority rules. The conservation law and waiting time characterization for a general class of discrete-time queues are also presented. The results in this paper cover several previous results as special cases.     

A single-server discrete-time queue with correlated positive and negative customer arrivals

An MMBP/Geo/1 queue with correlated positive and negative customer arrivals is studied. In the infinite-capacity queueing system, positive customers and negative customers are generated by a Bernoulli bursty source with two correlated geometrically distributed periods. I.e., positive and negative customers arrive to the system according to two different geometrical arrival processes. Under the late arrival scheme (LAS), two removal disciplines caused by negative customers are investigated in the paper. In individual removal scheme, a negative customer removes a positive customer in service if any, while in disaster model, a negative customer removes all positive customers in the system if any. The negative customer arrival has no effect on the system if it finds the system empty. We analyze the Markov chains underlying the queueing systems and evaluate the performance of two systems based on generating functions technique. Some explicit solutions of the system, such as the average buffer content and the stationary probabilities are obtained. Finally, the effect of several parameters on the system performance is shown numerically.     

Regularly varying tails in a queue with discrete autoregressive arrivals of order p

We consider a discrete time single server queueing system where the service time of a customer is one slot, and the arrival process is governed by a discrete autoregressive process of order p (DAR(p)). For this queueing system, we investigate the tail behavior of the queue size and the waiting time distributions. Specifically, we show that if the stationary distribution of DAR(p) input has a tail of regular variation with index −β−1, then the stationary distributions of the queue size and the waiting time have tails of regular variation with index −β. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

A discrete-time Geo/G/1 retrial queue with preemptive resume and collisions

We consider a discrete-time Geo/G/1 retrial queue with preemptive resume, collisions of customers and general retrial times. We analyze the Markov chain underlying the considered queueing system and derive its ergodicity condition. Using generating function technique, the system state distribution as well as the orbit size and the system size distributions are studied. Some interesting and important performance measures are obtained. Besides, the stochastic decomposition property is investigated. Finally, some numerical examples are provided.     

A discrete-time Geo/G/1 retrial queue with preferred and impatient customers

This paper is concerned with a discrete-time Geo/G/1 retrial queue with preferred, impatient customers and general retrial times. We analyze the Markov chain underlying the considered queueing system and derive its ergodicity condition. The system state distribution as well as the orbit size and the system size distributions are obtained in terms of their generating functions. These generating functions yield exact expressions for different performance measures. Besides, the stochastic decomposition property and the corresponding continuous-time queueing system are investigated. Finally, some numerical examples are provided to illustrate the effect of priority and impatience on several performance characteristics of the system.     

A complete and simple solution for a discrete-time multi-server queue with bulk arrivals and deterministic service times

A complete distribution for the system content of a discrete-time multi-server queue with an infinite buffer is presented, where each customer arriving in a group requires a deterministic service time that could be greater than one slot. In addition, when the service time equals one slot, a complete distribution for the delay is also presented.     

Two competing discrete-time queues with priority

This paper considers a class of two discrete-time queues with infinite buffers that compete for a single server. Tasks requiring a deterministic amount of service time, arrive randomly to the queues and have to be served by the server. One of the queues has priority over the other in the sense that it always attempts to get the server, while the other queue attempts only randomly according to a rule that depends on how long the task at the head of the queue has been waiting in that position. The class considered is characterized by the fact that if both queues compete and attempt to get the server simultaneously, then they both fail and the server remains idle for a deterministic amount of time. For this class we derive the steady-state joint generating function of the state probabilities. The queueing system considered exhibits interesting behavior, as we demonstrate by an example.     

The discrete-time preemptive repeat identical priority queue

Priority queueing systems come natural when customers with diversified delay requirements have to wait to get service. The customers that cannot tolerate but small delays get service priority over customers which are less delay-sensitive. In this contribution, we analyze a discrete-time two-class preemptive repeat identical priority queue with infinite buffer space and generally distributed service times. Newly arriving high-priority customers interrupt the on-going service of a low-priority customer. After all high-priority customers have left the system, the interrupted service of the low-priority customer has to be repeated completely. By means of a probability generating functions approach, we analyze the system content and the delay of both types of customers. Performance measures (such as means and variances) are calculated and the impact of the priority scheduling is discussed by means of some numerical examples.     

Mean queue size in a queue with discrete autoregressive arrivals of order <Emphasis Type="Italic">p</Emphasis>

We consider a discrete time single server queueing system where the arrival process is governed by a discrete autoregressive process of order p (DAR(p)), and the service time of a customer is one slot. For this queueing system, we give an expression for the mean queue size, which yields upper and lower bounds for the mean queue size. Further we propose two approximation methods for the mean queue size. One is based on the matrix analytic method and the other is based on simulation. We show, by illustrations, that the proposed approximations are very accurate and computationally efficient.     

On the steady-state queue size distribution of the discrete-timeGeo/G/1 queue with repeated customers

In this paper, we study the steady-state queue size distribution of the discrete-timeGeo/G/1 retrial queue. We derive analytic formulas for the probability generating function of the number of customers in the system in steady-state. It is shown that the stochastic decomposition law holds for theGeo/G/1 retrial queue. Recursive formulas for the steady-state probabilities are developed. Computations based on these recursive formulas are numerically stable because the recursions involve only nonnegative terms. Since the regularGeo/G/1 queue is a special case of theGeo/G/1 retrial queue, the recursive formulas can also be used to compute the steady-state queue size distribution of the regularGeo/G/1 queue. Furthermore, it is shown that a continuous-timeM/G/1 retrial queue can be approximated by a discrete-timeGeo/G/1 retrial queue by dividing the time into small intervals of equal length and the approximation approaches the exact when the length of the interval tends to zero. This relationship allows us to apply the recursive formulas derived in this paper to compute the approximate steady-state queue size distribution of the continuous-timeM/G/1 retrial queue and the regularM/G/1 queue.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0046415.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0105828.     

Time-dependent analysis of a queue with batch arrivals andn levels of nonpreemptive priority

A queueing system with batch arrivals andn classes of customers with nonpreemptive priorities between them is considered. Each batch arrives according to the Poisson distribution and contains customers of all classes while the service times follow arbitrary distributions with different probability density functions for each class. For such a model the system states probabilities both in the transient and in the steady state are analysed and also expressions for the Laplace transforms of the busy period densities for each class and for the general busy period are obtained.     

The discrete-time single-server queue

In this paper we consider the discrete-time single server queueing model with exceptional first service. For this model we cannot define the steady-state waiting-time distribution simply as the limiting distribution of the waiting times, since this limit does not always exist. Instead, we use the Cesaro limit to define the limiting waiting-time distribution. We give an exact relation between the generating functions of the steady-state waiting-time distribution and of the idle-time distribution in the case of general interarrival-time and service-time distributions. Once we have this relation, we can give more explicit results when the generating function of either the interarrival-time distribution or the service-time distribution is rational. We also derive some results on the asymptotic behaviour of the waiting-time distribution.     

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.     

Discrete-time queue with Bernoulli bursty source arrival and generally distributed service times

In this contribution, a discrete-time single-server infinite-capacity queue with correlated arrivals and general service times is investigated. Arrivals of cells are modelled as an on/off source process with geometrically distributed on-periods and off-periods, which is called Bernoulli bursty source. Based on the probability generating function technique, closed-form expression of some performance measures of system, such as average buffer content, unfinished work, cell delay and so on, are obtained. Finally, the effects of system parameters on performance measures are illustrated by some numerical examples.     

The discrete-time MAP/PH/1 queue with multiple working vacations

We consider a discrete-time single-server queueing model where arrivals are governed by a discrete Markovian arrival process (DMAP), which captures both burstiness and correlation in the interarrival times, and the service times and the vacation duration times are assumed to have a general phase-type distributions. The vacation policy is that of a working vacation policy where the server serves the customers at a lower rate during the vacation period as compared to the rate during the normal busy period. Various performance measures of this queueing system like the stationary queue length distribution, waiting time distribution and the distribution of regular busy period are derived. Through numerical experiments, certain insights are presented based on a comparison of the considered model with an equivalent model with independent arrivals, and the effect of the parameters on the performance measures of this model are analyzed.     

A discrete-time priority queue with two-class customers and bulk services

This paper studies the behavior of a discrete queueing system which accepts synchronized arrivals and provides synchronized services. The number of arrivals occurring at an arriving point may follow any arbitrary discrete distribution possessing finite first moment and convergent probability generating function in ¦ z ¦ 1 + with > 0. The system is equipped with an infinite buffer and one or more servers operating in synchronous mode. Service discipline may or may not be prioritized. Results such as the probability generating function of queue occupancy, average queue length, system throughput, and delay are derived in this paper. The validity of the results is also verified by computer simulations.The work reported in this paper was supported by the National Science Council of the Republic of China under Grant NSC1981-0404-E002-04.     

A discrete-time single-server queue with set-up time

This paper studies a generalization of the GI/G/1 queueing system in which there is a random ‘set-up’ time for customers who arrive when the server is idle. Mathematical methods are given for finding various transient characteristics of the system.     

A Discrete-Time Geo/G/1 retrial queue with the server subject to starting failures

This paper studies a discrete-time Geo/G/1 retrial queue where the server is subject to starting failures. We analyse the Markov chain underlying the regarded queueing system and present some performance measures of the system in steady-state. Then, we give two stochastic decomposition laws and find a measure of the proximity between the system size distributions of our model and the corresponding model without retrials. We also develop a procedure for calculating the distributions of the orbit and system size as well as the marginal distributions of the orbit size when the server is idle, busy or down. Besides, we prove that the M/G/1 retrial queue with starting failures can be approximated by its discrete-time counterpart. Finally, some numerical examples show the influence of the parameters on several performance characteristics. This work is supported by the DGINV through the project BFM2002-02189.     

The randomized threshold for the discrete-time Geo/G/1 queue

This paper discusses a discrete-time Geo/G/1 queue, in which the server operates a random threshold policy, namely 〈p, N〉 policy, at the end of each service period. After all the messages are served in the queue exhaustively, the server is immediately deactivated until N messages are accumulated in the queue. If the number of messages in the queue is accumulated to N, the server is activated for services with probability p and deactivated with probability (1 − p). Using the generating functions technique, the system state evolution is analyzed. The generating functions of the system size distributions in various states are obtained. Some system characteristics of interest are derived. The long-run average cost function per unit time is analytically developed to determine the joint optimal values of p and N at a minimum cost.     

Performance analysis of discrete-time queue GI/G/1 with negative arrivals

In this paper, we consider a discrete-time GI/G/1 queueing model with negative arrivals. By deriving the probability generating function of actual service time of ordinary customers, we reduced the analysis to an equivalent discrete-time GI/G/1 queueing model without negative arrival, and obtained the probability generating function of buffer contents and random customer delay.