Sojourn Times in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">PH</Emphasis>/1 Processor Sharing Queue

We give in this paper an algorithm to compute the sojourn time distribution in the processor sharing, single server queue with Poisson arrivals and phase type distributed service times. In a first step, we establish the differential system governing the conditional sojourn times probability distributions in this queue, given the number of customers in the different phases of the PH distribution at the arrival instant of a customer. This differential system is then solved by using a uniformization procedure and an exponential of matrix. The proposed algorithm precisely consists of computing this exponential with a controlled accuracy. This algorithm is then used in practical cases to investigate the impact of the variability of service times on sojourn times and the validity of the so-called reduced service rate (RSR) approximation, when service times in the different phases are highly dissymmetrical. For two-stage PH distributions, we give conjectures on the limiting behavior in terms of an M/M/1 PS queue and provide numerical illustrative examples.This revised version was published online in June 2005 with corrected coverdate     

Transient analysis of a queue with system disasters and customer impatience

A single server queue with Poisson arrivals and exponential service times is studied. The system suffers disastrous breakdowns at an exponential rate, resulting in the loss of all running and waiting customers. When the system is down, it undergoes a repair mechanism where the repair time follows an exponential distribution. During the repair time any new arrival is allowed to join the system, but the customers become impatient when the server is not available for a long time. In essence, each customer, upon arrival, activates an individual timer, which again follows an exponential distribution with parameter ξ. If the system is not repaired before the customer’s timer expires, the customer abandons the queue and never returns. The time-dependent system size probabilities are presented using generating functions and continued fractions.     

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.     

带有N策略,启动时间和服务台故障的M/M/1排队的均衡策略

本文考虑带有N策略,启动时间和服务台故障的M/M/1排队的顾客的策略行为.当系统为空时服务台关闭,并且只有当系统中的顾客数达到一个给定的阈值时才会被激活,启动时间服从指数分布.服务台在工作时可能会故障,一旦发生故障,它立即被维修,维修的时间服从指数分布.我们得到了不同状态的均衡到达率并且给出了均衡社会收益函数.最后对均衡到达率和均衡社会收益进行了数值研究.     

Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service

A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either queue 1 becomes empty, or the number of messages decreases to k less than that found upon the server's last arrival at queue 1, whichever occurs first, where 1 ≤ k ≤ ∞. After service completion in queue 1, the server switches over to queue 2 in the second stage and serves all messages in queue 2 until it becomes empty. It is assumed that an arrival stream is Poissonian, message service times at each stage are generally distributed and switch-over times are zero. This paper analyzes joint queue-length distributions and message sojourn time distributions.     

The queue length distributions in the finite buffer bulk-service MAP/G/1 queue with multiple vacations

We consider a finite buffer batch service queueing system with multiple vacations wherein the input process is Markovian arrival process (MAP). The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service- and vacation- times are arbitrarily distributed. We obtain the queue length distributions at service completion, vacation termination, departure, arbitrary and pre-arrival epochs. Finally, some performance measures such as loss probability, average queue lengths are discussed. Computational procedure has been given when the service- and vacation- time distributions are of phase type (PH-distribution).     

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     

Discrete time queues with delayed information

We study the behavior of a single-server discrete-time queue with batch arrivals, where the information on the queue length and possibly on service completions is delayed. Such a model describes situations arising in high speed telecommunication systems, where information arrives in messages, each comprising a variable number of fixed-length packets, and it takes one unit of time (a slot) to transmit a packet. Since it is not desirable to attempt service when the system may be empty, we study a model where we assume that service is attempted only if, given the information available to the server, it is certain that there are messages in the queue. We characterize the probability distribution of the number of messages in the queue under some general stationarity assumptions on the arrival process, when information on the queue size is delayedK slots, and derive explicit expressions of the PGF of the queue length for the case of i.i.d. batch arrivals and general independent service times. We further derive the PGF of the queue size when information onboth the queue length and service completion is delayedK=1 units of time. Finally, we extend the results to priority queues and show that when all messages are of unit length, thec rule remains optimal even in the case of delayed information.     

Discrete time analysis of MAP/PH/1 vacation queue with gated time‐limited service

We analyse a single‐server queue in which the server goes through alternating periods of vacation and work. In each work period, the server attends to the queue for no more than a fixed length of time, T. The system is a gated one in which the server, during any visit, does not attend to customers which were not in the system before its visit. As soon as all the customers within the gate have been served or the time limit has been reached (whichever occurs first) the server goes on a vacation. The server does not wait in the queue if the system is empty at its arrival for a visit. For this system the resulting Markov chain, of the queue length and some auxiliary variables, is level‐dependent. We use special techniques to carry out the steady state analysis of the system and show that when the information regarding the number of customers in the gate is not critical we are able to reduce this problem to a level‐independent Markov chain problem with large number of boundary states. For this modified system we use a hybrid method which combines matrix‐geometric method for the level‐independent part of the system with special solution method for the large complex boundary which is level‐dependent. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Conditional and unconditional distributions forM/G/1 type queues with server vacations

M/G/1 queues with server vacations have been studied extensively over the last two decades. Recent surveys by Boxma [3], Doshi [5] and Teghem [14] provide extensive summary of literature on this subject. More recently, Shanthikumar [11] has generalized some of the results toM/G/1 type queues in which the arrival pattern during the vacations may be different from that during the time the server is actually working. In particular, the queue length at the departure epoch is shown to decompose into two independent random variables, one of which is the queue length at the departure epoch (arrival epoch, steady state) in the correspondingM/G/1 queue without vacations. Such generalizations are important in the analysis of situations involving reneging, balking and finite buffer cyclic server queues. In this paper we consider models similar to the one in Shanthikumar [11] but use the work in the system as the starting point of our investigation. We analyze the busy and idle periods separately and get conditional distributions of work in the system, queue length and, in some cases, waiting time. We then remove the conditioning to get the steady state distributions. Besides deriving the new steady state results and conditional waiting time and queue length distributions, we demonstrate that the results of Boxma and Groenendijk [2] follow as special cases. We also provide an alternative approach to deriving Shanthikumar's [11] results for queue length at departure epochs.     

Strategic behavior and social optimization in Markovian vacation queues: The case of heterogeneous customers

We consider a single server queueing system in which service shuts down when no customers are present, and is resumed when the queue length reaches a given critical length. We assume customers are heterogeneous on delay sensitivity and analyze customers’ strategic response to this mechanism and compare it to the overall optimal behavior. We provide algorithms to compute the equilibrium arrival rates and also derive the monotonicity of equilibrium and optimal arrival rates. We show that there may exist multiple equilibria in such a system and the optimal arrival rate may be larger or smaller than the decentralized equilibrium one.     

Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

N-策略休假排队系统中异质信息顾客策略分析

本文研究N-策略休假M/M/1排队系统中的异质信息顾客策略和社会最优收益。来到系统的顾客分为两类,第一类顾客有系统信息,加入系统前知道服务员的状态和系统中顾客数;第二类顾客没有系统信息,加入系统前既不知道服务员的状态,也不知道系统中顾客数。利用粒子群优化算法,分析了两类顾客的最优策略行为和最优社会收益。结果表明,最优社会收益随着转换门限N的增大而减小,随着v和系统负载p的增大而增大。并且,第一类顾客的比例越大,社会收益越大。     

Decay rate for a PH/M/2 queue with shortest queue discipline

In this paper, we consider a PH/M/2 queue in which each server has its own queue and arriving customers join the shortest queue. For this model, it has been conjectured that the decay rate of the tail probabilities for the shortest queue length in the steady state is equal to the square of the decay rate for the queue length in the corresponding PH/M/2 model with a single queue. We prove this fact in the sense that the tail probabilities are asymptotically geometric when the difference of the queue sizes and the arrival phase are fixed. Our proof is based on the matrix analytic approach pioneered by Neuts and recent results on the decay rates. AMS subject classifications: 60K25 · 60K20 · 60F10 · 90B22     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

A single-server discrete-time retrial <Emphasis Type="Italic">G</Emphasis>-queue with server breakdowns and repairs

This paper concerns a discrete-time Geo/Geo/1 retrial queue with both positive and negative customers where the server is subject to breakdowns and repairs due to negative arrivals. The arrival of a negative customer causes one positive customer to be killed if any is present, and simultaneously breaks the server down. The server is sent to repair immediately and after repair it is as good as new. The negative customer also causes the server breakdown if the server is found idle, but has no effect on the system if the server is under repair. We analyze the Markov chain underlying the queueing system and obtain its ergodicity condition. The generating function of the number of customers in the orbit and in the system are also obtained, along with the marginal distributions of the orbit size when the server is idle, busy or down. Finally, we present some numerical examples to illustrate the influence of the parameters on several performance characteristics of the system.     

A Communication Multiplexer Problem: Two Alternating Queues with Dependent Randomly-Timed Gated Regime

Two random traffic streams are competing for the service time of a single server (multiplexer). The streams form two queues, primary (queue 1) and secondary (queue 0). The primary queue is served exhaustively, after which the server switches over to queue 0. The duration of time the server resides in the secondary queue is determined by the dynamic evolution in queue 1. If there is an arrival to queue 1 while the server is still working in queue 0, the latter is immediately gated, and the server completes service there only to the gated jobs, upon which it switches back to the primary queue. We formulate this system as a two-queue polling model with a single alternating server and with randomly-timed gated (RTG) service discipline in queue 0, where the timer there depends on the arrival stream to the primary queue. We derive Laplace–Stieltjes transforms and generating functions for various key variables and calculate numerous performance measures such as mean queue sizes at polling instants and at an arbitrary moment, mean busy period duration and mean cycle time length, expected number of messages transmitted during a busy period and mean waiting times. Finally, we present graphs of numerical results comparing the mean waiting times in the two queues as functions of the relative loads, showing the effect of the RTG regime.     

Large sample inference from single server queues

Problems of large sample estimation and tests for the parameters in a single server queue are discussed. The service time and the interarrivai time densities are assumed to belong to (positive) exponential families. The queueing system is observed over a continuous time interval (0,T] whereT is determined by a suitable stopping rule. The limit distributions of the estimates are obtained in a unified setting, and without imposing the ergodicity condition on the queue length process. Generalized linear models, in particular, log-linear models are considered when several independent queues are observed. The mean service times and the mean interarrival times after appropriate transformations are assumed to satisfy a linear model involving unknown parameters of interest, and known covariates. These models enhance the scope and the usefulness of the standard queueing systems.Partially supported by the U. S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

The acquisition queue

We propose a new queueing model named the acquisition queue. It differs from conventional queueing models in that the server not only serves customers, but also performs acquisition of new customers. The server has to divide its energy between both activities. The number of newly acquired customers is uncertain, and the effect of the server’s acquisition efforts can only be seen after some fixed time period δ (delay). The acquisition queue constitutes a (δ+1)-dimensional Markov chain. The limiting queue length distribution is derived in terms of its probability generating function, and an exact expression for the mean queue length is given. For large values of δ the numerical procedures needed for calculating the mean queue length become computationally cumbersome. We therefore complement the exact expression with a fluid approximation. One of the key features of the acquisition queue is that the server performs more acquisition when the queue is small. Together with the delay, this causes the queue length process to show a strongly cyclic behavior. We propose and investigate several ways of planning the acquisition efforts. In particular, we propose an acquisition scheme that is designed specifically to reduce the cyclic behavior of the queue length process. This research was financially supported by the European Network of Excellence Euro-NGI. The work of the second author was supported in part by a TALENT grant from the Netherlands Organisation for Scientific Research (NWO).