A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

Marginal queue length approximations for a two-layered network with correlated queues

We consider an extension of the classical machine-repair model, where we assume that the machines, apart from receiving service from the repairman, also serve queues of products. The extended model can be viewed as a layered queueing network, where the first layer consists of the queues of products and the second layer is the ordinary machine-repair model. As the repair time of one machine may affect the time the other machine is not able to process products, the downtimes of the machines are correlated. This correlation leads to dependence between the queues of products in the first layer. Analysis of these queue length distributions is hard, as the exact dependence structure for the downtimes, or the queue lengths, is not known. Therefore, we obtain an approximation for the complete marginal queue length distribution of any queue in the first layer, by viewing such a queue as a single server queue with correlated server downtimes. Under an explicit assumption on the form of the downtime dependence, we obtain exact results for the queue length distribution for that single server queue. We use these exact results to approximate the machine-repair model. We do so by computing the downtime correlation for the latter model and by subsequently using this information to fine-tune the parameters we introduced to the single server queue. As a result, we immediately obtain an approximation for the queue length distributions of products in the machine-repair model, which we show to be highly accurate by extensive numerical experiments.     

Markovian queues with Poisson control

We investigate Markovian queues that are examined by a controller at random times determined by a Poisson process. Upon examination, the controller sets the service speed to be equal to the minimum of the current number of customers in the queue and a certain maximum service speed; this service speed prevails until the next examination time. We study the resulting two-dimensional Markov process of queue length and server speed, in particular two regimes with time scale separation, specifically for infinitely frequent and infinitely long examination times. In the intermediate regime the analysis proves to be extremely challenging. To gain further insight into the model dynamics we then analyse two variants of the model in which the controller is just an observer and does not change the speed of the server.     

Some limit theorems for regenerative queues

We consider a single server queue with the interarrival times and the service times forming a regenerative sequence. This traffic class includes the standard models: iid, periodic, Markov modulated (e.g., BMAP model of Lucantoni [18]) and their superpositions. This class also includes the recently proposed traffic models in high speed networks, exhibiting long range dependence. Under minimal conditions we obtain the rates of convergence to stationary distributions, finiteness of stationary moments, various functional limit theorems and the continuity of stationary distributions and moments. We use the continuity results to obtain approximations for stationary distributions and moments of an MMPP/GI/1 queue where the modulating chain has a countable state space. We extend all our results to feed-forward networks where the external arrivals to each queue can be regenerative. In the end we show that the output process of a leaky bucket is regenerative if the input process is and hence our results extend to a queue with arrivals controlled by a leaky bucket. This revised version was published online in June 2006 with corrections to the Cover Date.     

A single server queue with gated processor-sharing discipline

In this paper we consider a single server queue in which arrivals occur according to a Poisson process and each customer's service time is exponentially distributed. The server works according to the gated process-sharing discipline. In this discipline, the server provides service to a batch of at mostm customers at a time. Once a batch of customers begins service, no other waiting customer can receive service until all members of the batch have completed their service. For this queue, we derive performance characteristics, such as waiting time distribution, queue length distribution etc. For this queue, it is possible to obtain the mean conditional response time for a customer whose service time is known. This conditional response time is a nonlinear function (as opposed to the linear case for the ordinary processor-sharing queue). A special case of the queue (wherem=) has an interesting and unusual solution. For this special case, the size of the batch for service is a Markov chain whose steady state distribution can be explicitly written down. Apart from the contribution to the theory of Markov chains and queues, the model may be applicable to scheduling of computer and communication systems.     

The infinite-buffer single server queue with a variant of multiple vacation policy and batch Markovian arrival process

We consider an infinite-buffer single server queue where arrivals occur according to a batch Markovian arrival process (BMAP). The server serves until system emptied and after that server takes a vacation. The server will take a maximum number H of vacations until either he finds at least one customer in the queue or the server has exhaustively taken all the vacations. We obtain queue length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue lengths and mean waiting times, etc. have been obtained. Several other vacation queueing models like, single and multiple vacation model, queues with exceptional first vacation time, etc. can be considered as special cases of our model.     

An MAP/G/1 G-queues with preemptive resume and multiple vacations

In this paper, we consider an MAP/G/1 G-queues with possible preemptive resume service discipline and multiple vacations wherein the arrival process of negative customers is Markovian arrival process (MAP). The arrival of a negative customer may remove the customer being in service. 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 with the method of supplementary variables, combined with the matrix-analytic method and censoring technique. We also obtain the mean of the busy period based on the renewal theory. Finally we provide expressions for a special case.     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

推广的多重休假$M^X/G/1$排队系统

在平稳状态下,Baba利用补充变量方法研究了多重休假的MX/G/1排队,但作者假定了休假时间和服务时间都有概率密度函数.本文考虑推广的多重休假MX/G/1排队,在假定休假时间和服务时间都是一般概率分布函数下,我们研究了队长的瞬态和稳态性质.通过引进"服务员忙期"和使用不同于Baba文中使用的分析技术,我们导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式,以及平稳队长的随机分解.特别地,通过本文可直接获得多重休假的M/G/1与标准的MX/G/1排队系统相应的结果.     

The GI/M/1 queue with phase-type working vacations and vacation interruption

Consider a GI/M/1 queue with phase-type working vacations and vacation interruption where the vacation time follows a phase-type distribution. The server takes the original work at the lower rate during the vacation period. And, the server can come back to the normal working level at a service completion instant if there are customers at this instant, and not accomplish a complete vacation. From the PH renewal process theory, we obtain the transition probability matrix. Using the matrix-analytic method, we obtain the steady-state distributions for the queue length at arrival epochs, and waiting time of an arbitrary customer. Meanwhile, we obtain the stochastic decomposition structures of the queue length and waiting time. Two numerical examples are presented lastly.     

A factorization property for BMAP/G/1 vacation queues under variable service speed

This paper proposes a simple factorization principle that can be used efficiently and effectively to derive the vector generating function of the queue length at an arbitrary time of the BMAP/G/1/ queueing systems under variable service speed. We first prove the factorization property. Then we provide moments formula. Lastly we present some applications of the factorization principle.     

成批到达排队系统的随机比较

本文研究成批到达排队系统中队长过程的随机比较问题．利用随机比较方法我们对成批到达指数服务的多服务台排队系统进行分析,得到了该排队系统中队长过程的随机比较以及队长函数关于时间的凹性和凸性．同时我们也给出了成批到达一般服务的单服务台排队系统队长过程、稳态队长的随机比较以及队长函数关于时间的凹性和凸性．     

A simple approach for analyzing feedback vacation queues with levy input process

We introduce a simple approach for modeling and analyzing a SII/G/I queue where the server may take repeated vacations. Whenever a busy period ends the server takes a vacation of random duration. At the end of each vacation the server may either take a new vacation or resume service; if the queue is found empty the server always takes a new vacation. Furthermore, the queuing system allows Bernoulli feedback of customers. Three classes of service disciplines, random gated, 1-limited and exhaustive, are considered. The random gated service discipline generalizes several known service disciplines. The customers arrival process is assumed to be a Levy process (i.e., satisfies the stationary and independent increments (SII property). We obtain explicit expressions for several performance measures of the system. These performance measures include the mean and second moment of the cycle time, the mean queue length at the beginning of a cycle of service and the expected delay observed by a customer. Furthermore, our analysis provides a uniform method to get several results previously obtained by Baba, Chiarawongse and Sriniwasan, and Takine, Takagi and Hasegawa.     

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.     

Exact Analysis of the State-Dependent Polling Model

We consider a polling model in which a number of queues are served, in cyclic order, by a single server. Each queue has its own distinct Poisson arrival stream, service time, and switchover time (the server's travel time from that queue to the next) distribution. A setup time is incurred if the polled queue has one or more customers present. This is the polling model with State-Dependent service (the SD model). The SD model is inherently complex; hence, it has often been approximated by the much simpler model with State-Independent service (the SI model) in which the server always sets up for a service at the polled queue, regardless of whether it has customers or not. We provide an exact analysis of the SD model and obtain the probability generating function of the joint queue length distribution at a polling epoch, from which the moments of the waiting times at the various queues are obtained. A number of numerical examples are presented, to reveal conditions under which the SD model could perform worse than the corresponding SI model or, alternately, conditions under which the SD model performs better than a corresponding model in which all setup times are zero. We also present expressions for a variant of the SD model, namely, the SD model with a patient server.     

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.     

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

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

Analysis of a discrete-time queueing system with time-limited service

We analyze a discrete-time, single-server queueing system in which the length of each service period is limited. The server takes a vacation when the limit expires or the queue empties, whichever occurs first. In the former case, the preempted service is resumed after the vacation without loss or creation of any work. This system models the transmission of message frames from a station on timed-token local-area networks (for example, FDDI and IEEE 802.4 token bus). We study the process of the unfinished work and the joint process of the queue size and the remaining service time. By using the technique of discrete Fourier transforms to determine some unknown functions in the governing equations, we numerically obtain exact mean waiting times.A part of the work of H. Takagi was done while he was with IBM Research, Tokyo Research Laboratory.     

Single-Server Queue with Markov-Dependent Inter-Arrival and Service Times

In this paper we study a single-server queue where the inter-arrival times and the service times depend on a common discrete time Markov chain. This model generalizes the well-known MAP/G/1 queue by allowing dependencies between inter-arrival and service times. The waiting time process is directly analyzed by solving Lindley's equation by transform methods. The Laplace–Stieltjes transforms (LST) of the steady-state waiting time and queue length distribution are both derived, and used to obtain recursive equations for the calculation of the moments. Numerical examples are included to demonstrate the effect of the autocorrelation of and the cross-correlation between the inter-arrival and service times. An erratum to this article is available at .     

On a bulk arrival bulk service infinite service queue

This paper considers an infinite server queue in continuous time in which arrivals are in batches of variable size X and service is provided in groups of fixed size R. We obtain analytical results for the number of busy servers and waiting customers at arbitrary time points. For the number of busy servers, we obtain a recursive relation for the partial binomial moments both in transient and steady states. Special cases are also discussed