Single line queue with recurrent repeated demands

We analyze a model queueing system in which customers cannot be in continuous contact with the server, but must call in to request service. If the server is free, the customer enters service immediately, but if the server is occupied, the unsatisfied customer must break contact and reapply for service later. There are two types of customer present who may reapply. First transit customers who arrive from outside according to a Poisson process and if they find the server busy they join a source of unsatisfied customers, called the orbit, who according to an exponential distribution reapply for service till they find the server free and leave the system on completion of service. Secondly there are a number of recurrent customers present who reapply for service according to a different exponential distribution and immediately go back in to the orbit after each completion of service. We assume a general service time distribution and calculate several characterstic quantities of the system for both the constant rate of reapplying for service and for the case when customers are discouraged and reduce their rate of demand as more customers join the orbit.     

A recursive method to the optimal control of an M/G/1 queueing system with finite capacity and infinite capacity

We study a single removable server in an infinite and a finite queueing systems with Poisson arrivals and general distribution service times. The server may be turned on at arrival epochs or off at service completion epochs. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in a finite system. The method is illustrated analytically for three different service time distributions: exponential, 3-stage Erlang, and deterministic. Cost models for infinite and finite queueing systems are respectively developed to determine the optimal operating policy at minimum cost.     

Exact Solution to Tandem Fluid Queues with Controlled Input

We consider a tandem fluid system composed of multiple buffers connected in a series. The first buffer receives input from a number of independent homogeneous on-off sources and each buffer provides input to the next buffer. The active (on) periods and silent (off) periods follow general and exponential distribution, respectively. Furthermore, the generally distributed active periods are controlled by an exponential timer. Under this assumption, explicit expressions for the distribution of the buffer content for the first buffer fed by a single source is obtained for the fluid queue driven by discouraged arrivals queue and infinite server queue. The buffer content distribution of the subsequent buffers when the first buffer is fed by multiple sources are found in terms of confluent hypergeometric functions. Numerical results are illustrated to compare the trend of the average buffer content for the models under consideration.     

Joint Distributions for Interacting Fluid Queues

Motivated by recent traffic control models in ATM systems, we analyse three closely related systems of fluid queues, each consisting of two consecutive reservoirs, in which the first reservoir is fed by a two-state (on and off) Markov source. The first system is an ordinary two-node fluid tandem queue. Hence the output of the first reservoir forms the input to the second one. The second system is dual to the first one, in the sense that the second reservoir accumulates fluid when the first reservoir is empty, and releases fluid otherwise. In these models both reservoirs have infinite capacities. The third model is similar to the second one, however the second reservoir is now finite. Furthermore, a feedback mechanism is active, such that the rates at which the first reservoir fills or depletes depend on the state (empty or nonempty) of the second reservoir.The models are analysed by means of Markov processes and regenerative processes in combination with truncation, level crossing and other techniques. The extensive calculations were facilitated by the use of computer algebra. This approach leads to closed-form solutions to the steady-state joint distribution of the content of the two reservoirs in each of the models.     

具有位相型修理的离散时间可修排队系统

本文研究了具有一般独立输入，位相型修理的离散时间可修排队系统，假定服务台对顾客的服务时间和服务台寿命服从几何分布，运用矩阵解析方法我们给出系统嵌入在到达时刻的稳态队长分布和等待时间分布，并证明这些分布均为离散位相型分布．我们也得到在广义服务时间内服务台发生故障次数的分布，证明它服从一个修正的几何分布．我们对离散时间可修排队与连续时间可修排队进行了比较，说明这两种排队系统在一些性能指标方面的区别之处．最后我们通过一些数值例子说明在这类系统中顾客的到达过程、服务时间和服务台的故障率之间的关系．     

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.     

An MX/G/1 queueing system with a setup period and a vacation period

This paper deals with an M^X/G/1 queueing system with a vacation period which comprises an idle period and a random setup period. The server is turned off each time when the system becomes empty. At this point of time the idle period starts. As soon as a customer or a batch of customers arrive, the setup of the service facility begins which is needed before starting each busy period. In this paper we study the steady state behaviour of the queue size distributions at stationary (random) point of time and at departure point of time. One of our findings is that the departure point queue size distribution is the convolution of the distributions of three independent random variables. Also, we drive analytically explicit expressions for the system state probabilities and some performance measures of this queueing system. Finally, we derive the probability generating function of the additional queue size distribution due to the vacation period as the limiting behaviour of the M^X/M/1 type queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

Maximum entropy analysis to the N policy M/G/1 queueing system with a removable server

We study a single removable server in an M/G/1 queueing system operating under the N policy in steady-state. The server may be turned on at arrival epochs or off at departure epochs. Using the maximum entropy principle with several well-known constraints, we develop the approximate formulae for the probability distributions of the number of customers and the expected waiting time in the queue. We perform a comparative analysis between the approximate results with exact analytic results for three different service time distributions, exponential, 2-stage Erlang, and 2-stage hyper-exponential. The maximum entropy approximation approach is accurate enough for practical purposes. We demonstrate, through the maximum entropy principle results, that the N policy M/G/1 queueing system is sufficiently robust to the variations of service time distribution functions.     

On the discrete-time system with server breakdowns: Computational algorithm and optimization algorithm

This paper analyzes a discrete-time Geo/Geo/1 queueing system with the server subject to breakdowns and repairs, in which two different possible types of the server breakdowns are considered. In Type 1, the server may break down only when the system is busy, while in Type 2, the server can break down even if the system is idle. The server lifetimes are assumed to be geometrical and the server repair times are also geometric distributions. We model this system by the level-dependent quasi-birth-death (QBD) process and develop computation algorithms of the stationary distribution of the number of customers in the system using the matrix analytic method. The search algorithm for parameter optimization based on a cost model is developed and performed herein.     

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.     

Further results for the M/M(a, ∞)/N batch-service system

A multi-server Markovian queueing system is considered such that an idle server will take the entire batch of waiting customers into service as soon as their number is as large as some control limit. Some new results are derived. These include the distribution of the time interval between two consecutive commencements of service (including itsrth moment) and the actual service batch size distribution. In addition, the average customer waiting time in the queue is derived by a simple combinatorial approach. This is an expanded version of “Combinatorial analysis of batch-service queues” which was presented at the ORSA/TIMS meeting, Orlando, Florida, November 1983.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

具有两类服务中断的离散时间重试排队分析

本文考虑了具有破坏性和非破坏性服务中断的离散重试排队系统.两类中断都发生在顾客接受服务的过程中,假设服务台在工作时发生破坏性中断,则正在接受服务的顾客中断服务,进入到重试空间中去,重新尝试以接受服务;若服务台在工作时发生非破坏性中断,则正在接受服务的顾客将等待中断结束后再继续完成剩余的服务量.求出了系统存在稳态的充分必要条件.利用补充变量法,求出了系统稳态时系统和重试区域中队长分布的概率母函数,以及其他一些重要的排队指标,并且给出了对应的连续时间下具有两类服务中断的M/G/1排队的队长分布的概率母函数.最后,通过数值算例研究了各种参数对平均队长的影响.     

Stability analysis of parallel server systems under longest queue first

We consider the stability of parallel server systems under the longest queue first (LQF) rule. We show that when the underlying graph of a parallel server system is a tree, the standard nominal traffic condition is sufficient for the stability of that system under LQF when interarrival and service times have general distributions. Then we consider a special parallel server system, which is known as the X-model, whose underlying graph is not a tree. We provide additional “drift” conditions for the stability and transience of these queueing systems with exponential interarrival and service times. Drift conditions depend in general on the stationary distribution of an induced Markov chain that is derived from the underlying queueing system. We illustrate our results with examples and simulation experiments. We also demonstrate that the stability of the LQF depends on the tie-breaking rule used and that it can be unstable even under arbitrary low loads.     

Analysis of the M [X]/G/1 queues with second multi-optional service and unreliable server

A bulk-arrival single server queueing system with second multi-optional service and unreliable server is studied in this paper. Customers arrive in batches according to a homogeneous Poisson process, all customers demand the first ＂essential＂ service, whereas only some of them demand the second ＂multi-optional＂ service. The first service time and the second service all have general distribution and they are independent. We assume that the server has a service-phase dependent, exponentially distributed life time as well as a servicephase dependent, generally distributed repair time. Using a supplementary variable method, we obtain the transient and the steady-state solutions for both queueing and reliability measures of interest.     

On a generic class of two-node queueing systems

This paper analyzes a generic class of two-node queueing systems. A first queue is fed by an on–off Markov fluid source; the input of a second queue is a function of the state of the Markov fluid source as well, but now also of the first queue being empty or not. This model covers the classical two-node tandem queue and the two-class priority queue as special cases. Relying predominantly on probabilistic argumentation, the steady-state buffer content of both queues is determined (in terms of its Laplace transform). Interpreting the buffer content of the second queue in terms of busy periods of the first queue, the (exact) tail asymptotics of the distribution of the second queue are found. Two regimes can be distinguished: a first in which the state of the first queue (that is, being empty or not) hardly plays a role, and a second in which it explicitly does. This dichotomy can be understood by using large-deviations heuristics. This work has been carried out partly in the Dutch BSIK/BRICKS project.     

Structure-reversibility and departure functions of queueing networks with batch movements and state dependent routing

We consider characterizations of departure functions in Markovian queueing networks with batch movements and state-dependent routing in discrete-time and in continuous-time. For this purpose, the notion of structure-reversibility is introduced, which means that the time-reversed dynamics of a queueing network corresponds with the same type of queueing network. The notion is useful to derive a traffic equation. We also introduce a multi-source model, which means that there are different types of outside sources, to capture a wider range of applications. Characterizations of the departure functions are obtained for any routing mechanism of customers satisfying a recurrent condition. These results give a unified view to queueing network models with linear traffic equations. Furthermore, they enable us to consider new examples as well as show limited usages of this kind of queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of a Two‐Phase Queueing System with Vacations and Bernoulli Feedback

Abstract

We consider a two‐phase queueing system with server vacations and Bernoulli feedback. Customers arrive at the system according to a Poisson process and receive batch service in the first phase followed by individual services in the second phase. Each customer who completes the individual service returns to the tail of the second phase service queue with probability 1 ? σ. If the system becomes empty at the moment of the completion of the second phase services, the server takes vacations until he finds customers. This type of queueing problem can be easily found in computer and telecommunication systems. By deriving a relationship between the generating functions for the system size at various embedded epochs, we obtain the system size distribution at an arbitrary time. The exhaustive and gated cases for the batch service are considered.     

A MAP-modulated fluid flow model with multiple vacations

We consider a MAP-modulated fluid flow queueing model with multiple vacations. As soon as the fluid level reaches zero, the server leaves for repeated vacations of random length V until the server finds any fluid in the system. During the vacation period, fluid arrives from outside according to the MAP (Markovian Arrival Process) and the fluid level increases vertically at the arrival instance. We first derive the vector Laplace–Stieltjes transform (LST) of the fluid level at an arbitrary point of time in steady-state and show that the vector LST is decomposed into two parts, one of which the vector LST of the fluid level at an arbitrary point of time during the idle period. Then we present a recursive moments formula and numerical examples.