Closed queueing networks with batch services

In this paper we study queueing networks which allow multiple changes at a given time. The model has a natural application to discrete-time queueing networks but describes also queueing networks in continuous time. It is shown that product-form results which are known to hold when there are single changes at a given instant remain valid when multiple changes are allowed.     

Product form stationary distributions for queueing networks with blocking and rerouting

In this paper we study Markovian queueing networks in which the service and the routing characteristics have a particular form which leads to a product form stationary distribution for the number of customers in the various queues of the network. We show that if certain transitions are prohibited due to blocking conditions, then the form of the stationary distribution is preserved under a certain rerouting protocol. Several examples are presented which illustrate the wide applicability of the model. This revised version was published online in June 2006 with corrections to the Cover Date.     

A general formulation for mean-value analysis in product-form batch-movement queueing networks

A number of recent papers have shown that many classes of queueing networks with batches of customers served and routed through the network have equilibrium distributions which factorise into product forms over the nodes of the network. In this paper we demonstrate how such networks are amenable to a mean-value analysis which generalises that used for single-movement networks.Since product-form stochastic Petri nets (SPNs) can be viewed as batch-movement queueing networks, our algorithm is also applicable to their analysis.     

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.     

A retrial queue with structured batch arrivals,priorities and server vacations

A retrial queue accepting two types of customers with correlated batch arrivals and preemptive resume priorities is studied. The service times are arbitrarily distributed with a different distribution for each type of customer and the server takes a single vacation each time he becomes free. For such a model the state probabilities are obtained both in a transient and in a steady state. Finally, the virtual waiting time of an arbitrary ordinary customer in a steady state is analysed.     

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.     

Transient analysis of queues with heterogeneous arrivals

In this paper we consider a discrete time queueing model where the time axis is divided into time slots of unit length. The model satisfies the following assumptions: (i) an event is either an arrival of typei of batch sizeb _i, i=1,...,r with probability _i or is a depature of a single customer with probability or zero depending on whether the queue is busy or empty; (ii) no more than one event can occur in a slot, therefore the probability that neither an arrival nor a departure occurs in a slot is 1––_{i i} or 1–_{i i} according as the queue is busy or empty; (iii) events in different slots are independent. Using a lattice path representation in higher dimensional space we will derive the time dependent joint distribution of the number of arrivals of various types and the number of completed services. The distribution for the corresponding continuous time model is found by using weak convergence.     

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.     

Batch arrival queues with vacations and server setup

We study a single server queueing system whose arrival stream is compound Poisson and service times are generally distributed. Three types of idle period are considered: threshold, multiple vacations, and single vacation. For each model, we assume after the idle period, the server needs a random amount of setup time before serving. We obtain the steady-state distributions of system size and waiting time and expected values of the cycle for each model. We also show that the distributions of system size and waiting time of each model are decomposed into two parts, whose interpretations are provided. As for the threshold model, we propose a method to find the optimal value of threshold to minimize the total expected operating cost.     

Equilibrium analysis in batch-arrival queues with complementary services

This paper studies a batch-arrival queue with two complementary services. The two services are complementary and any customer has no benefit from obtaining just one of them. To the best of the authors’ knowledge, there are no works contributed to the batch-arrival queues on analysis of the equilibrium behaviors in queueing systems by now. The properties of batch-arrival queues, which is more practical and universal in reality, induce different Nash equilibria under competition or monopoly compared with the single-arrival queues. We observe the joint effect of batch joining rate and cost structure on the behavior of customers and graphically interpret the equilibrium solutions under competition. Moreover, we discuss the model under three types of price structures and give comparisons from customer and server points.     

Threshold control by a single-server retrial queue with batch arrivals and group services

A controlled single-server retrial queueing system is investigated. Customers arrive according to batch Markovian arrival process. The system has several operation modes which are controlled by means of a threshold strategy. The stationary distribution is calculated. Optimization problem is considered and a numerical example is presented.     

Poisson flows in single class open networks of quasireversible queues

This paper analyzes open networks of quasireversible nodes with a single class of customers and in equilibrium. A simple argument shows, under a stability conditions, that a flow on a link of such a network is Poisson if and only if the link is not part of a loop. This loop criterion is shown to apply to the usual quasireversible networks with bounded service rates.     

Response time in a tandem queue with blocking, Markovian arrivals and phase-type services

A novel approach for obtaining the response time in a discrete-time tandem-queue with blocking is presented. The approach constructs a Markov chain based on the age of the leading customer in the first queue. We also provide a stability condition and carry out several numerical examples.     

On the characterization of departure rules for discrete-time queueing networks with batch movements and its applications

This paper supplements and generalizes the results of sawa [11] in this special issue from the viewpoint of discrete-time networks of queues with batch arrivals and batch departures, due to Henderson and Taylor [7]. We first note that the D-rule of sawa [11] is equivalent to the specific form for the release rate function, introduced in [7]. Such forms have widely appeared in the literature, too. sawa [11] found that the D-rule can be characterized in terms of the reversed-time process of a certain vector-valued process. He obtained this characterization for a single node model. We generalize this result for networks of queues with batch arrivals and batch departures. This reveals why the specific form of the release rate function is common in the literature. Furthermore, the characterization is useful to consider traffic flows in a discrete-time queueing network.This research is partially supported by NEC C&C Laboratories.     

Admission control and pricing in a queue with batch arrivals

We investigate a problem of admission control in a queue with batch arrivals. We consider a single server with exponential service times and a compound Poisson arrival process. Each arriving batch computes its expected benefit and decides whether or not to enter the system. The controller’s problem is to set state dependent prices for arriving batches. Once prices have been set we formulate the admission control problem, derive properties of the value function, and obtain the optimal admission policy.     

Triggered batch movement in queueing networks

A product form equilibrium distribution is derived for a class of queueing networks, in either discrete or continuous time, in which multiple customers arrive simultaneously, multiple customers complete service simultaneously, and any event occurring in the network can force/trigger the release of multiple customers to be routed through the network.