A two-queue model with Bernoulli service schedule and switching times

In this paper, we present a detailed analysis of a cyclic-service queueing system consisting of two parallel queues, and a single server. The server serves the two queues with a Bernoulli service schedule described as follows. At the beginning of each visit to a queue, the server always serves a customer. At each epoch of service completion in the ith queue at which the queue is not empty, the server makes a random decision: with probability p_i, it serves the next customer; with probability 1-p_i, it switches to the other queue. The server takes switching times in its transition from one queue to the other. We derive the generating functions of the joint stationary queue-length distribution at service completion instants, by using the approach of the boundary value problem for complex variables. We also determine the Laplace-Stieltjes transforms of waiting time distributions for both queues, and obtain their mean waiting times. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Dynamic server assignment in a two-queue model

We consider a polling model of two M/G/1 queues, served by a single server. The service policy for this polling model is of threshold type. Service at queue 1 is exhaustive. Service at queue 2 is exhaustive unless the size of queue 1 reaches some level T during a service at queue 2; in the latter case the server switches to queue 1 at the end of that service. Both zero- and nonzero switchover times are considered. We derive exact expressions for the joint queue length distribution at customer departure epochs, and for the steady-state queue-length and sojourn time distributions. In addition, we supply a simple and very accurate approximation for the mean queue lengths, which is suitable for optimization purposes.     

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.     

Optimal stochastic scheduling in a single server biclass retrial queueing system

The paper deals with the assignment of a single server to two retrial queues. Each customer reapplies for service after an exponentially distributed amount of time. The server operates at customer dependent exponential rates. There are holding costs and costs during service per customer and per unit of time. We provide conditions on which it is optimal to allocate the server to queue 1 or 2 in order to minimize the expected total costs until the system is cleared.     

Distributional Form of Little's Law for FIFO Queues with Multiple Markovian Arrival Streams and Its Application to Queues with Vacations

This paper considers stationary queues with multiple arrival streams governed by an irreducible Markov chain. In a very general setting, we first show an invariance relationship between the time-average joint queue length distribution and the customer-average joint queue length distribution at departures. Based on this invariance relationship, we provide a distributional form of Little's law for FIFO queues with simple arrivals (i.e., the superposed arrival process has the orderliness property). Note that this law relates the time-average joint queue length distribution with the stationary sojourn time distributions of customers from respective arrival streams. As an application of the law, we consider two variants of FIFO queues with vacations, where the service time distribution of customers from each arrival stream is assumed to be general and service time distributions of customers may be different for different arrival streams. For each queue, the stationary waiting time distribution of customers from each arrival stream is first examined, and then applying the Little's law, we obtain an equation which the probability generating function of the joint queue length distribution satisfies. Further, based on this equation, we provide a way to construct a numerically feasible recursion to compute the joint queue length distribution.     

A two-queue,one-server model with priority for the longer queue

The queueing model studied consists of one server and two queues. Each queue has its own Poisson arrival stream and service time distribution. After a service completion, the server proceeds with a customer from the longer queue, if the queues are unequal; if the queues are equal, the server chooses with some probability a customer from one of the queues. The model is of practical interest in performance analysis, but also of theoretical interest because the functional equation to be solved has not yet been studied in the queueing literature. A basic analysis of this functional equation is presented. Some numerical results are given to assess the influence of the present service discipline. Some new properties of L.S. transforms of service time distributions are discussed in the appendix.Dr. T. Katayama has formulated the present problem and brought it to the author's attention during his visit in October/November 1984 to the NTT-Electr. Comm. Lab.'s Musashino, Tokyo 180.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

Mixed gated/exhaustive service in a polling model with priorities

In this paper we consider a single-server polling system with switch-over times. We introduce a new service discipline, mixed gated/exhaustive service, that can be used for queues with two types of customers: high and low priority customers. At the beginning of a visit of the server to such a queue, a gate is set behind all customers. High priority customers receive priority in the sense that they are always served before any low priority customers. But high priority customers have a second advantage over low priority customers. Low priority customers are served according to the gated service discipline, i.e. only customers standing in front of the gate are served during this visit. In contrast, high priority customers arriving during the visit period of the queue are allowed to pass the gate and all low priority customers before the gate. We study the cycle time distribution, the waiting time distributions for each customer type, the joint queue length distribution of all priority classes at all queues at polling epochs, and the steady-state marginal queue length distributions for each customer type. Through numerical examples we illustrate that the mixed gated/exhaustive service discipline can significantly decrease waiting times of high priority jobs. In many cases there is a minimal negative impact on the waiting times of low priority customers but, remarkably, it turns out that in polling systems with larger switch-over times there can be even a positive impact on the waiting times of low priority customers.     

Waiting time analysis of the multiple priority dual queue with a preemptive priority service discipline

The dual queue consists of two queues, called the primary queue and the secondary queue. There is a single server in the primary queue but the secondary queue has no service facility and only serves as a holding queue for the overloaded primary queue. The dual queue has the additional feature of a priority scheme to help reduce congestion. Two classes of customers, class 1 and 2, arrive to the dual queue as two independent Poisson processes and the single server in the primary queue dispenses an exponentially distributed service time at the rate which is dependent on the customer’s class. The service discipline is preemptive priority with priority given to class 1 over class 2 customers. In this paper, we use matrix-analytic method to construct the infinitesimal generator of the system and also to provide a detailed analysis of the expected waiting time of each class of customers in both queues.     

Dynamic scheduling of a single-server two-class queue with constant retrial policy

We analyze the non-preemptive assignment of a single server to two infinite-capacity retrial queues. Customers arrive at both queues according to Poisson processes. They are served on first-come-first-served basis following a cost-optimal routing policy. The customer at the head of a queue generates a Poisson stream of repeated requests for service, that is, we have a constant retrial policy. All service times are exponential, with rates depending on the queues. The costs to be minimized consist of costs per unit time that a customer spends in the system. In case of a scheduling problem that arise when no new customers arrive an explicit condition for server allocation to the first or the second queue is given. The condition presented covers all possible parameter choices. For scheduling that also considers new arrivals, we present the conditions under which server assignment to either queue 1 or queue 2 is cost-optimal.     

A tandem GI/PH/1→•/PH/1/0 queue with blocking

Tandem queues are widely used in mathematical modeling of random processes describing the operation of manufacturing systems, supply chains, computer and telecommunication networks. Although there exists a lot of publications on tandem queueing systems, analytical research on tandem queues with non-Markovian input is very limited. In this paper, the results of analytical investigation of two-node tandem queue with arbitrary distribution of inter-arrival times are presented. The first station of the tandem is represented by a single-server queue with infinite waiting room. After service at the first station, a customer proceeds to the second station that is described by a single-server queue without a buffer. Service times of a customer at the first and the second server have PH (Phase-type) distributions. A customer, who completes service at the first server and meets a busy second server, is forced to wait at the first server until the second server becomes available. During the waiting period, the first server becomes blocked, i.e., not available for service of customers. We calculate the joint stationary distribution of the system states at the embedded epochs and at arbitrary time. The Laplace–Stieltjes transform of the sojourn time distribution is derived. Key performance measures are calculated and numerical results presented.     

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.     

Waiting times in queueing networks with a single shared server

We study a queueing network with a single shared server that serves the queues in a cyclic order. External customers arrive at the queues according to independent Poisson processes. After completing service, a customer either leaves the system or is routed to another queue. This model is very generic and finds many applications in computer systems, communication networks, manufacturing systems, and robotics. Special cases of the introduced network include well-known polling models, tandem queues, systems with a waiting room, multi-stage models with parallel queues, and many others. A complicating factor of this model is that the internally rerouted customers do not arrive at the various queues according to a Poisson process, causing standard techniques to find waiting-time distributions to fail. In this paper, we develop a new method to obtain exact expressions for the Laplace–Stieltjes transforms of the steady-state waiting-time distributions. This method can be applied to a wide variety of models which lacked an analysis of the waiting-time distribution until now.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

Equilibrium customers’ choice between FCFS and random servers

Consider two servers of equal service capacity, one serving in a first-come first-served order (FCFS), and the other serving its queue in random order. Customers arrive as a Poisson process and each arriving customer observes the length of the two queues and then chooses to join the queue that minimizes its expected queueing time. Assuming exponentially distributed service times, we numerically compute a Nash equilibrium in this system, and investigate the question of which server attracts the greater share of customers. If customers who arrive to find both queues empty independently choose to join each queue with probability 0.5, then we show that the server with FCFS discipline obtains a slightly greater share of the market. However, if such customers always join the same queue (say of the server with FCFS discipline) then that server attracts the greater share of customers. This research was supported by the Israel Science Foundation grant No. 526/08.     

M/M/∞ Queues in series with non-homogeneous inputs

This paper studies the transient behaviour of tandem queueing system consisting of an arbitrary number r of queues in series with infinite server service facility at each queue. Poisson arrivals with time dependent parameter and exponential service times have been assumed. Infinite server queues realistically describe those queues in which sufficient service capacity exist to prevent virtually any waiting by the customer present. The model is suitable for both phase type service as well services in series. Very elegant solutions have been obtained and it has been shown that if the queue sizes are initially independent and Poisson then they remain independent and Poisson for all t.     

Symmetric queues served in cyclic order

Consider a symmetrical system of n queues served in cyclic order by a single server. It is shown that the stationary number of customers in the system is distributed as the sum of three independent random variables, one being the stationary number of customers in a standard M/G/1 queue. This fact is used to establish an upper bound for the mean waiting time for the case where at most k customers are served at each queue per visit by the server. This approach is also used to rederive the mean waiting times for the cases of exhaustive service, gated service, and serve at most one customer at each queue per visit by the server.     

Geometric equilibrium distributions for queues with interactive batch departures

Gelenbe et al. [1, 2] consider single server Jackson networks of queues which contain both positive and negative customers. A negative customer arriving to a nonempty queue causes the number of customers in that queue to decrease by one, and has no effect on an empty queue, whereas a positive customer arriving at a queue will always increase the queue length by one. Gelenbe et al. show that a geometric product form equilibrium distribution prevails for this network. Applications for these types of networks can be found in systems incorporating resource allocations and in the modelling of decision making algorithms, neural networks and communications protocols.In this paper we extend the results of [1, 2] by allowing customer arrivals to the network, or the transfer between queues of a single positive customer in the network to trigger the creation of a batch of negative customers at the destination queue. This causes the length of the queue to decrease by the size of the created batch or the size of the queue, whichever is the smallest. The probability of creating a batch of negative customers of a particular size due to the transfer of a positive customer can depend on both the source and destination queue.We give a criterion for the validity of a geometric product form equilibrium distribution for these extended networks. When such a distribution holds it satisfies partial balance equations which are enforced by the boundaries of the state space. Furthermore it will be shown that these partial balance equations relate to traffic equations for the throughputs of the individual queues.