A tandem queueing model with coupled processors

We consider a tandem queue with coupled processors and analyze the two-dimensional Markov process representing the numbers of jobs in the two stations. A functional equation for the generating function of the stationary distribution of this two-dimensional process is derived and solved through the theory of Riemann-Hilbert boundary value problems.     

A decomposition-related throughput property of tandem queueing networks with blocking

A general throughput property of tandem queueing networks with blocking that relates existing decomposition methods to throughput bounds is discussed using the sample path approach.     

Optimal server assignment in a two-stage tandem queueing system

We study Markovian queueing systems consisting of two stations in tandem. There is a dedicated server in each station and an additional server that can be assigned to any station. Assuming that linear holding costs are incurred by jobs in the system and two servers can collaborate to work on the same job, we determine structural properties of optimal server assignment policies under the discounted and the average cost criteria.     

On product form tandem structures

This paper is written in honour to A. Hordijk. It establishes product form results for a generic and instructive multi-class tandem queue with blocking, to which A. Hordijk has directly and indirectly contributed. First, a sufficient and necessary product form characterization is provided. Next, three special cases are briefly presented. These illustrate the possibility of product forms despite finite capacity constraints (blocking), unproportional processor sharing mechanisms and resource contentions (such as for access control). The results are partially new and of interest for present-day applications. In essence these rely upon the pioneering work by A. Hordijk     

On the order of tandem queues

We consider the optimal order of servers in a tandem queueing system withm stages, an unlimited supply of customers in front of the first stage, and a service buffer of size 1 but no intermediate storage buffers between the first and second stages. Service times depend on the servers but not the customers, and the blocking mechanism at the first two stages is manufacturing blocking. Using a new characterization of reversed hazard rate order, we show that if the service times for two servers are comparable in the reversed hazard rate sense, then the departure process is stochastically earlier if the slower server is first and the faster server is second than if the reverse is true. This strengthens earlier results that considered individual departure times marginally. We show similar results for the last two stages and for other blocking mechanisms. We also show that although individual departure times for a system with servers in a given order are stochastically identical to those when the order of servers is reversed, this reversibility property does not hold for the entire departure process.     

Symmetry property of the throughput in closed tandem queueing networks with finite buffers

In this paper we consider closed tandem queueing networks with finite buffers and blocking before service. With this type of blocking, a server is allowed to start processing a job only if there is an empty space in the next buffer. It was recently conjectured that the throughput of such networks is symmetrical with respect to the population of the network. That is, the throughput of the network with population N is the same as that with population C − N, where C is the total number of buffer spaces in the network. The main purpose of this paper is to prove this result in the case where the service time distributions are of phase type (PH-distribution). The proof is based on the comparison of the sample paths of the network with populations N and C − N. Finally, we also show that this symmetry property is related to a reversibility property of this class of networks.     

Optimal prices for finite capacity queueing systems

We prove a lower bound on the optimal price for a fairly large class of blocking systems with general arrival and service processes, determine optimal price expressions for M/M/1/m and M/GI/s/s systems, and investigate how optimal prices change with changes in the size of the waiting room and service capacity.     

On stationary tandem queueing networks with job feedback

The class of tandem queueing networks with job feedback is studied under stationarity conditions on the arrival and service times sequences. Each job, after completing service in the last queue, is fed back (rerouted) to the first one, a random number of times, before leaving the system. The average execution time per job is exactly computed, as the number of jobs becomes large, and is minimized under mild conditions. The degree of parallelism achieved in the processing is also computed. The issue of rate-stability of the system is then considered. The network is defined to be rate-stable iff the job departure rate is equal to the job arrival rate; that depends heavily on the dynamic feedback policy we employ to place rerouted jobs in specific places of the front queue buffer of the network. The condition under which the network is rate-stable is specified, and a dynamic feedback policy is constructed, which rate-stabilizes the system under the maximum possible job arrival rate; thus, it maximizes the dynamic throughput of the network. Other related results concerning the performance of tandem networks with feedback are obtained.Research supported in part by grants NSF-DDM-RIA-9010778, NSF-NCR-9116268, NSF-NCR-NYI-9258 507, by an AT&T Foundation grant and a GTE Fellowship.     

A tandem Jackson network with feedback to the first node

AnN-node tandem queueing network with Bernoulli feedback to the end of the queue of thefirst node is considered. We first revisit the single-nodeM/G/1 queue with Bernoulli feedback, and derive a formula forEL(n), the expected queue length seen by a customer at his nth feedback. We show that, asn becomes large,EL(n) tends to /(l ), being the effective traffic intensity. We then treat the entire queueing network and calculate the mean value ofS, the total sojourn time of a customer in theN-node system. Based on these results we study the problem ofoptimally ordering the nodes so as to minimize ES. We show that this is a special case of a general sequencing problem and derive sufficient conditions for an optimal ordering. A few extensions of the serial queueing model are also analyzed. We conclude with an appendix in which we derive an explicit formula for the correlation coefficient between the number of customers seen by an arbitrary arrival to anM/G/1 queue, and the number of customers he leaves behind him upon departure. For theM/M/1 queue this coefficient simply equals the traffic intensity .     

Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution

A tandem queueing system with infinite and finite intermediate buffers, heterogeneous customers and generalized phase-type service time distribution at the second stage is investigated. The first stage of the tandem has a finite number of servers without buffer. The second stage consists of an infinite and a finite buffers and a finite number of servers. The arrival flow of customers is described by a Marked Markovian arrival process. Type 1 customers arrive to the first stage while type 2 customers arrive to the second stage directly. The service time at the first stage has an exponential distribution. The service times of type 1 and type 2 customers at the second stage have a phase-type distribution with different parameters. During a waiting period in the intermediate buffer, type 1 customers can be impatient and leave the system. The ergodicity condition and the steady-state distribution of the system states are analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transform of the sojourn time distribution of type 2 customers is derived. Numerical examples are presented.     

Smoothed perturbation analysis for queues with finite buffers

Applying the technique of smoothed perturbation analysis (SPA) to theGI/G/1/K queue, we derive gradient estimators for two performance measures: the mean steady-state system time of a served customer and the probability that an arriving customer is rejected. Unbiasedness of the estimators follows from results of a previous general framework on SPA estimators. However, in that framework, the estimators often require the simulation of numerous additional sample subpaths, possibly making the technique practically infeasible in applications. We exploit some of the special structure of theGI/G/1/K queue to come up with an estimator which requires at most the simulation of a single additional sample subpath. By establishing certain regenerative properties, we provide a strong consistency proof for the estimator.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

On the equivalence of three types of blocking in non-Markovian tandem queues

Definitions of blocking types for tandem queueing systems are given where each stage consists of multiple servers. Some of them are shown to be identical with respect to service initiation epochs at each stage. Such identical relationships are proved using sample path correspondence, and are therefore valid irrespective of the arrival process and the service time distributions.     

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.     

On the optimal design of plates for a given deflection

The optimum design problem of an elastic plate for a given deflection is considered. The design variable is chosen to be the thickness of the plate. Using the principle of stationary mutual potential energy first introduced by Shield and Prager, a sufficient optimality condition (which makes the volume stationary) is derived for plates under bending caused by general loading conditions. As an example, the optimum profile of a simply supported circular plate under a given rotationally symmetric loading is obtained.     

On the optimal control of a single-server queueing system: Comment

In a recent paper by Scott and Jefferson, the optimal control of the service rate for a single-server queue with limited waiting space is treated by the maximum principle. We show that their control policies are necessarily suboptimal. Characterizations for optimal control are derived and used to obtain corresponding optimal trajectories in both nonsingular and singular regions.     

A tandem of discrete-time queues with arrivals and departures at each stage

A discrete-time system of a tandem of queues with exogenous arrivals and departures at each stage is considered. A customer leaving queuek–1 departs the system with probability 1– ^[k] and continues to queuek with probability ^[k] . Exogenous arrivals to each stage are i.i.d. at each time slot. An approximate analysis of the occupancy and busy-period distributions of each stage based on a General Busy-period with batches and Memoryless (geometric) Idle period renewal Process (GBMIP) provides improved performance over two-state Markov approximations and gives exact results when there are no interstage departures.This research was supported in part by NSF grant NCR-8708282.     

Approximate analysis of single-server tandem queues with finite buffers

In this paper, we study single-server tandem queues with general service times and finite buffers. Jobs are served according to the Blocking-After-Service protocol. To approximately determine the throughput and mean sojourn time, we decompose the tandem queue into single-buffer subsystems, the service times of which include starvation and blocking, and then we iteratively estimate the unknown parameters of the service times of each subsystem. The crucial feature of this approach is that in each subsystem successive service times are no longer assumed to be independent, but a successful attempt is made to include dependencies due to blocking by employing the concept of Markovian Arrival Processes. An extensive numerical study shows that this approach produces very accurate estimates for the throughput and mean sojourn time, outperforming existing methods, especially for longer tandem queues and for tandem queues with service times with a high variability.     

A heuristic technique for the transient behavior of Markovian queueing systems

Through an examination of numerical solutions to Markovian queueing systems, it has been shown that the expected queue length eventually approaches its equilibrium value in an approximately exponential manner. Based on this observation a heuristic is proposed for approximating the transient expected queue length for Markovian systems by scaling the numerical solution of an M/M/1 system.