Stability Criteria for Multi-class Queueing Networks with Re-entrant Lines

In this paper we show how the stability criteria for the model proposed in MacPhee and Müller (Queueing Syst 52(3):215–229, 2006) can be applied to queueing networks with re-entrant lines. The model considered has Poisson arrival streams, servers that can be configured in various ways, exponential service times and Markov feedback of completed jobs. The stability criteria are expressed in terms of the mean drifts of the process under the various server configurations. For models with re-entrant lines we impose here a boundary sojourn condition to ensure adequate control of the process when one or more queues are empty. We show with some examples, including the generalised Lu–Kumar network discussed in Niño-Mora and Glazebrook (J Appl Probab 37(3):890–899, 2000), how our results can be applied.     

Non-ergodicity criteria for denumerable continuous time Markov processes

We provide non-ergodicity criteria for denumerable continuous time Markov processes in terms of test functions. Two examples are given where the non-ergodicity criteria are applied.     

Approximate queueing models for capacitated multi-stage inventory systems under base-stock control

A queueing analysis is presented for base-stock controlled multi-stage production-inventory systems with capacity constraints. The exact queueing model is approximated by replacing some state-dependent conditional probabilities (that are used to express the transition rates) by constants. Two recursive algorithms (each with several variants) are developed for analysis of the steady-state performance. It is analytically shown that one of these algorithms is equivalent to the existing approximations given in the literature. The system studied here is more general than the systems studied in the literature. The numerical investigation for three-stage systems shows that the proposed approximations work well to estimate the relevant performance measures.     

Block cutpoint decomposition for markovian queueing systems

Steady-state probabilities of Markov Processes are computed by enumerating subgraphs of the transition diagram of the process. The presence of cutpoints in the transition diagram allows for decomposition of the problem into smaller components. Examples from queueing theory are presented. Matrix representations for these structures are also discussed.     

A queueing network analysis of a health center

This paper shows how a queueing network model helped to uncover the causes of delay in a health center appointment clinic. Patients, clerks, technicians, doctors and nurses agreed that the clerical registration area was the major bottleneck in the system. Our first reaction was to simulate the system with special attention on the complex registration procedure. Time constraints on data collection and program development led us to a queueing network model and QNA, a software tool for analyzing queueing networks developed by Whitt. The queueing analysis showed the registration area was not the bottleneck and we conjectured that delays were due to scheduling problems. A preliminary trial in the clinic of a modified appointment system showed promise with a 20 minute reduction in average time in the system (based on a small sample). Although there were significant differences between features of the real system and assumptions in the queueing network model, the queueing network model yielded insight into the operation of the appointment clinic.     

Stability of a priority queueing system with customer transfers

This paper is concerned with the stability of a preemptive priority queueing system with customer transfers. Conditions for the queueing system to be stable/unstable are found. An interesting result is that the stability/instability conditions are independent of the service rates of lower priority customers and the transfer rates.     

Taxonomy of batch queueing models in manufacturing systems

Batching plays an important role in performance evaluation of manufacturing systems. Three types of batching are commonly seen: transfer batches, parallel batches and serial batches. To model the batching behavior correctly, a comprehensive classification of batching is proposed. Eight types of batching behavior are classified and corresponding queueing models are given. The newly proposed models are validated by simulation.     

Robustness of perturbation analysis estimators for queueing systems with unknown distributions

Sample-path-based stochastic gradient estimators for performance measures of queueing systems rely on the assumption that a probability distribution of the random vector of interest (e.g., a service or interarrival time sequence) is given. In this paper, we address the issue of dealing with unknown probability distributions and investigate the robustness of such estimators with respect to possibly erroneous distribution choices. We show that infinitesimal perturbation analysis (IPA) can be robust in this sense and, in some cases, provides distribution-independent estimates. Comparisons with other gradient estimators are provided, including experimental results. We also show that finite perturbation analysis (FPA), though only providing gradient approximations, possesses some attractive robustness properties with respect to unknown distribution parameters. An application of FPA estimation is included for a queueing system performance optimization problem involving customers with real-time constraints.This work was supported in part by the National Science Foundation Grant ECS-88-01912 and by the Office of Naval Research Contract N00014-87-K-0304.The authors wish to thank Dr. Jack Holtzman for several useful comments and suggestions.     

Analysis of optimal and nearly optimal sequencing policies for a closed queueing network

We analyze sequencing policies designed to most effectively utilize the resources of a closed queueing network representation of a manufacturing system. A continuous time Markov decision process formulation is used to compare the performance of optimal sequencing policies and a heuristic developed by analyzing a heavy traffic approximation of the system.     

On the control of queueing systems with failures and repairs

Several classes of problems can be modelled as queueing systems with failures where preventative maintenance has to be optimized: relevant examples are computer systems, databases and production lines. This paper studies a simple case of such a situation based on the M/M/1 queue where the state of the server can take two values (on, off); the transition on–off happens either when there is a failure or when one decides to maintain. The characterization and an approximation of an optimal policy are given. Extensions to more general models, including general Markov processes, are examined.     

Heavy traffic limit theorems for a sequence of shortest queueing systems

A sequence of shortest queueing systems is considered in this paper. We give weak convergence theorems for the queue length and waiting time processes when the sequence of traffic intensities associated with the sequence of shortest queueing systems approaches the critical value (=1) at appropriate rates.Research supported by the National Natural Science Foundation of China.     

Stability analysis of queueing systems

This paper contains a survey of some results on the stability of queueing systems obtained by the authors by means of the method of trial functions (developed from Lyapunov's direct method). In addition, the paper contains a series of new results on the stability of regenerative processes. All the qualitative statements are accompanied by the construction of quantitative estimates.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 87, pp. 41–61, 1979.     

Simulation-based transfer function modeling for transient analysis of general queueing systems

This paper is concerned with characterizing the transient behavior of general queueing systems, which is widely known to be notoriously difficult. The objective is to develop a statistical methodology, integrated with extensive offline simulation and preliminary queueing analysis, for the estimation of a small number of transfer function models (TFMs) that quantify the input–output dynamics of a general queueing system. The input here is the time-varying arrival rate of jobs to the system; the time-dependent output performances include the departure rate of jobs and the mean of the work in process (i.e., number of jobs in the system). The resulting TFMs are difference equations, like the discrete approximations of the ordinary differential equations provided by an analytical approach, while possessing the high fidelity of simulation. Our method is expected to overcome the shortcomings of the existing transient analysis approaches, i.e., the computational burden of simulation and the lack of fidelity of analytical queueing models.     

Performance optimization of queueing systems with perturbation realization

After the intensive studies of queueing theory in the past decades, many excellent results in performance analysis have been obtained, and successful examples abound. However, exploring special features of queueing systems directly in performance optimization still seems to be a territory not very well cultivated. Recent progresses of perturbation analysis (PA) and sensitivity-based optimization provide a new perspective of performance optimization of queueing systems. PA utilizes the structural information of queueing systems to efficiently extract the performance sensitivity information from a sample path of system. This paper gives a brief review of PA and performance optimization of queueing systems, focusing on a fundamental concept called perturbation realization factors, which captures the special dynamic feature of a queueing system. With the perturbation realization factors as building blocks, the performance derivative formula and performance difference formula can be obtained. With performance derivatives, gradient-based optimization can be derived, while with performance difference, policy iteration and optimality equations can be derived. These two fundamental formulas provide a foundation for performance optimization of queueing systems from a sensitivity-based point of view. We hope this survey may provide some inspirations on this promising research topic.     

On the validity and utility of queueing models of human service systems

Based on observations made during an extensive study of police patrol operations in New York City, we examine the issues of the validity and utility of queueing models of service systems in which adaptive behavior by the (human) customers or servers is likely. We find that in addition to depending on the technical accuracy of its assumptions, the accuracy of such a model will also depend upon the level of managerial control of the system and adequacy of resources. We recommend that queueing models of human service systems be used in a normative fashion and incorporated in the management feedback loop.     

Analysis of a three node queueing network

The three node Jackson queueing network is the simplest acyclic network in which in equilibrium the sojourn times of a customer at each of the nodes are dependent. We show that assuming the individual sojourn times are independent provides a good approximation to the total sojourn time. This is done by simulating the network and showing that the sojourn times generally pass a Kolmogorov-Smirnov test as having come from the approximating distribution. Since the sum of dependent random variables may have the same distribution as the sum of independent random variables with the same marginal distributions, it is conceivable that our approximation is exact. However, we numerically compute upper and lower bounds for the distribution of the total sojourn time; these bounds are so close that the approximating distribution lies outside of the bounds. Thus, the bounds are accurate enough to distinguish between the two distributions even though the Kolmogorov-Smirnov test generally cannot.     

Design of manufacturing systems using queueing models

Design issues in various types of manufacturing systems such as flow lines, automatic transfer lines, job shops, flexible machining systems, flexible assembly systems and multiple cell systems are addressed in this paper. Approaches to resolving these design issues of these systems using queueing models are reviewed. In particular, we show how the structural properties that are recently derived for single and multiple stage queueing systems can be used effectively in the solution of certain design optimization problems.Supported in part by the Natural Sciences and Engineering Research Council of Canada via Operating and Strategic Grants on Modeling and Analyses of Production Systems and Modeling and Implementation of Just-in-Time Cells.Supported in part by the NSF Grants ECS-8811234 and DDM-9113008 and by Sloan Foundation Grants for the Consortium for Competitiveness and Cooperation and for the study on Competitive Semiconductor Manufacturing.     

Optimizing flow rates in a queueing network with side constraints

In this paper, modified versions of the classical deterministic maximum flow and minimum cost network flow problems are presented in a stochastic queueing environment. In the maximum flow network model, the throughput rate in the network is maximized such that for each arc of the network the resulting probability of finding congestion along that arc in excess of a desirable threshold does not exceed an acceptable value. In the minimum cost network flow model, the minimum cost routing of a flow of given magnitude is determined under the same type of constraints on the arcs. After proper transformations, these models are solved by Ford and Fulkerson's labeling algorithm and out-of-kilter algorithm, respectively.     

排队系统中的泰勒展开方法

综述了排队系统中的泰勒展开方法。它由Gong和Hu在1990s首次提出,并在最近几年里有了一些新的发展。首先,通过GI/GI/1队列的简单例子介绍其基本原理;其次,展示如何应用该方法分析相关性队列和离去过程;然后,阐述如何基于该方法发展排队网络近似的高阶矩方法;最后,讨论未来的几个可能研究方向。     

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.