Nonstationary analysis of the loss queue and of queueing networks of loss queues

We present an iterative scheme based on the fixed-point approximation method, for the numerical calculation of the time-dependent mean number of customers and blocking probability functions in a nonstationary queueing network with multi-rate loss queues. We first show how the proposed method can be used to analyze a single-class, multi-class, and multi-rate nonstationary loss queue. Subsequently, the proposed method is extended to the analysis of a nonstationary queueing network of multi-rate loss queues. Comparisons with exact and simulation results showed that the results are consistently close to the exact results and they are always within simulation confidence intervals.     

Infinitesimal perturbation analysis for queueing networks with general service time distributions

We study infinitesimal perturbation analysis (IPA) for queueing networks with general service time distributions. By general we mean that the distributions may have discrete components. We show that in the presence of service time distributions with discrete components commuting condition (CC) is no longer sufficient for unbiasedness of IPA. To overcome this difficulty, we introduce the notion of separability of realvalued random variables, and show that separability of service times together with (CC) establishes unbiasedness of IPA for queueing systems with general service time distributions. It turns out that the piecewise analyticity of service times is a sufficient condition for separability.     

The output of loss systems with general service time distributions

This paper analyzes the output processes of loss systems with Poisson arrival and general service time distributions. Explicit formulas to determine the characteristics of these processes are derived.     

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.     

Fluid limits of many-server queues with abandonments,general service and continuous patience time distributions

This paper extends the works of Kang and Ramanan (2010) and Kaspi and Ramanan (2011), removing the hypothesis of absolute continuity of the service requirement and patience time distributions. We consider a many-server queueing system in which customers enter service in the order of arrival in a non-idling manner and where reneging is considerate. Similarly to Kang and Ramanan (2010), the dynamics of the system are represented in terms of a process that describes the total number of customers in the system as well as two measure-valued processes that record the age in service of each of the customers being served and the “potential” waiting times. When the number of servers goes to infinity, fluid limit is established for this triple of processes. The convergence is in the sense of probability and the limit is characterized by an integral equation.     

A hybrid analysis approach for finite-capacity queues with general inputs and phase type service

A new analysis method for queueing systems with general input stream and phase type service time distributions is introduced. The approach combines discrete event simulation and numerical analysis of continuous time Markov chains. Simulation is used to represent the arrival process, whereas the service process is analyzed with numerical techniques. In this way the state of the system is characterized by a probability vector rather than by a single state. The use of a distribution vector reduces the variance of result estimators such that the width of confidence intervals is often reduced compared to discrete event simulation. This, in particular, holds for measures based on rare events or states with a small probability. The analysis approach can be applied for a wide variety of result measures including stationary, transient and accumulated measures. This revised version was published online in June 2006 with corrections to the Cover Date.     

Capacity planning in networks of queues with manufacturing applications

This paper addresses capacity planning in systems that can be modeled as a network of queues. More specifically, we present an optimization model and solution methods for the minimum cost selection of capacity at each node in the network such that a set of system performance constraints is satisfied. Capacity is controlled through the mean service rate at each node. To illustrate the approach and how queueing theory can be used to measure system performance, we discuss a manufacturing model that includes upper limits on product throughput times and work-in-process in the system. Methods for solving capacity planning problems with continuous and discrete capacity options are discussed. We focus primarily on the discrete case with a concave cost function, allowing fixed charges and costs exhibiting economies of scale with respect to capacity to be handled.     

Sojourn time distributions in the queue defined by a general QBD process

We consider a general QBD process as defining a FIFO queue and obtain the stationary distribution of the sojourn time of a customer in that queue as a matrix exponential distribution, which is identical to a phase-type distribution under a certain condition. Since QBD processes include many queueing models where the arrival and service process are dependent, these results form a substantial generalization of analogous results reported in the literature for queues such as the PH/PH/c queue. We also discuss asymptotic properties of the sojourn time distribution through its matrix exponential form.     

Time-dependent analysis of virtual waiting time behaviour in discrete time queues

Discrete time queueing models have been shown previously to be of practical use for modelling the approximate time-dependent behaviour of queue length in systems of the form M(t)/G/c. In this paper we extend these models to include the time-dependent behaviour of virtual waiting time.     

Approximate analysis of arbitrary configurations of open queueing networks with blocking

An algorithm for analyzing approximately open exponential queueing networks with blocking is presented. The algorithm decomposes a queueing network with blocking into individual queues with revised capacity, and revised arrival and service processes. These individual queues are then analyzed in isolation. Numerical experience with this algorithm is reported for three-node and four-node queueing networks. The approximate results obtained were compared against exact numerical data, and they seem to have an acceptable error level.Supported in part by a grant from CAIP Center, Rutgers University.Supported in part by the National Science Foundation under Grant DCR-85-02540.     

Limit non-stationary behavior of large closed queueing networks with bottlenecks

In this paper martingales methods are applied for analyzing limit non-stationary behavior of the queue length processes in closed Jackson queueing networks with a single class consisting of a large number of customers, a single infinite server queue, and a fixed number of single server queues with large state independent service rates. It is assumed that one of the single server nodes forms a bottleneck. For the non-bottleneck nodes we show that the queue length distribution at timet converges in generalized sense to the stationary distribution of the M/M/1 queue whose parameters explicitly depend ont. For the bottleneck node a diffusion approximation with reflection is proved in the moderate usage regime while fluid and Gaussian diffusion approximations are established for the heavy usage regime.     

Approximate analysis of load-dependent generally distributed queuing networks with low service time variability

In this paper, we present an approximate method for solution of load-dependent, closed queuing networks having general service time distributions with low variability. The proposed technique is an extension of Marie’s (1980) method. In the methodology, conditional throughputs are obtained by an iterative procedure. The iterations are repeated until an invalid result is detected or no improvements are found. We demonstrate the performance of the technique with 10 different examples. On average, the solutions have 5% or lower deviations when compared to simulation results.     

Transient analysis of a Markovian queue with deterministic rejection

We analyze the transient behavior of the M/M/1+D queue. Considering an Erlang distribution for customers’ waiting time, we approximate the real system by a Markov chain. We obtain the Laplace Transform of the transient probabilities in the approximated model and the Laplace transform of the main performance measures for the real system. We next analyze the busy period of this queue. One interesting insight is that the busy period of the unstable M/M/s queue has a finite coefficient of variation.     

Calculation of delay characteristics for multiserver queues with constant service times

We consider a discrete-time infinite-capacity queueing system with a general uncorrelated arrival process, constant-length service times of multiple slots, multiple servers and a first-come-first-served queueing discipline. Under the assumption that the queueing system can reach a steady state, we first establish a relationship between the steady-state probability distributions of the system content and the customer delay. Next, by means of this relationship, an explicit expression for the probability generating function of the customer delay is obtained from the known generating function of the system content, derived in previous work. In addition, several characteristics of the customer delay, namely the mean value, the variance and the tail distribution of the delay, are derived through some mathematical manipulations. The analysis is illustrated by means of some numerical examples.     

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.     

Analysis of preemptive loss priority queues with preemption distance

In a queueing system with preemptive loss priority discipline, customers disappear from the system immediately when their service is preempted by the arrival of another customer with higher priority. Such a system can model a case in which old requests of low priority are not worthy of deferred service. This paper is concerned with preemptive loss priority queues in which customers of each priority class arrive in a Poisson process and have general service time distribution. The strict preemption in the existing model is extended by allowing the preemption distance parameterd such that arriving customers of only class 1 throughp — d can preempt the service of a customer of classp. We obtain closed-form expressions for the mean waiting time, sojourn time, and queue size from their distributions for each class, together with numerical examples. We also consider similar systems with server vacations.     

Performance evaluation for general queueing networks in manufacturing systems: Characterizing the trade-off between queue time and utilization

Performance evaluation plays a key role in manufacturing system design and productivity improvement. Characterizing performance objectively is the first step. Inspired by the underlying structure of tandem queues, we have derived an approximate model to characterize the system performance. The model decomposes system queue time and variability into bottleneck and non-bottleneck parts while capturing the dependence among workstations. Compared the new model with prior approaches, the new model not only is more accurate but also requires less information. The property of manufacturing system performance is given based on the insight from the model.     

An algorithm for repairable item inventory system with depot spares and general repair time distribution

We consider the problem of determining the initial spare inventory level for a multi-echelon repairable item inventory system. We extend the previous results to the system, which has an inventory at the central depot as well as at bases and with a general repair time distribution. We propose an algorithm which finds spare inventory level to minimize the total expected cost and simultaneously to satisfy a specified minimum service rate. Extensive computational experiments show that the algorithm is accurate and efficient.