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.     

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.     

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.     

A survey of the perturbation analysis of discrete event dynamic systems

This paper introduces an analysis and optimization technique for discrete event dynamic systems, such as flexible manufacturing systems (FMSs), and other discrete part production processes. It can also be used for enhancement of the simulation results of, or the monitoring of the operations of such systems in real time. Extensive references are given where readers may pursue futher details.     

Stochastic petri net analysis of finite-population vacation queueing systems

We consider queueing systems in which the server occasionally takes a vacation of random duration. The vacation can be used to do additional work; it can also be a rest period. Several models of this problem have been analyzed in the past assuming that the population of the system is infinite. Similarly, it is generally assumed that the capacity of the system is infinite. In this paper we show how the finite-population system can be modeled by the stochastic Petri net. We also extend the model to the finite-capacity system. This research was sponsored by the SDIO Innovative Science and Technology Office and was managed by the Office of Naval Research under grant N3014-88-K-0623.     

Smoothed perturbation analysis algorithms for estimating the derivatives of occupancy-related functions in serial queueing networks

We present unbiased Smoothed Perturbation Analysis (SPA) estimators for the derivatives of occupancy-related performance functions in serial networks ofG/G/1 queues with respect to parameters of the distributions of service times at the queues. The sample functions for these performance measures are piecewise constant, and established Infinitesimal Perturbation Analysis (IPA) methods typically fail to provide unbiased estimators in this case. The performance measures considered in this paper are: the average network occupancy as seen by an arrival, the average occupancy of a specific queue as seen by an arrival to it, the probability that a customer is blocked at a specific queue, and the probability that a customer leaves a queue idle. The SPA estimators derived are quite simple and flexible, and they lend themselves to straightforward analysis. Unlike most of the established SPA algorithms, ours are not based on the comparison of hazard rates, and the proofs of their unbiasedness do not require the boundedness of such hazard rates.Supported in part by the National Science Foundation under Grant ECS-8801912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

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.     

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.     

Stability criteria for controlled queueing systems

We give an almost complete classification of ergodicity and transience conditions for a general multi-queue system with the following features: arrivals form Poisson streams and there are various routing schemes for allocating arrivals to queues; the servers can be configured in a variety of ways; completed jobs can feed back into the system; the exponential service times and feedback probabilities depend upon the configuration of the servers (this model includes some types of multi-class queueing system); switching between service regimes is instantaneous. Several different levels of control of the service regimes are considered. Our results for the N-queue system require randomisation of service configurations but we have studied the two queue system in situations where there is less control. We use the semi-martingale methods described in Fayolle, Malyshev and Menshikov [3] and our results generalise Kurkova [8] and complement Foley and McDonald [4] and [5]. AMS 2000 subject classification: Primary: 90B22; Secondary: 60J10 90B15     

Asymptotic analysis for closed multiclass queueing networks in critical usage

We consider a class of closed multiclass queueing networks containing First-Come-First-Serve (FCFS) and Infinite Server (IS) stations. These networks have a productform solution for their equilibrium probabilities. We study these networks in an asymptotic regime for which the number of customers and the service rates at the FCFS stations go to infinity with the same order. We assume that the regime is in critical usage, whereby the utilizations of the FCFS servers slowly approach one. The asymptotic distribution of the normalized queue lengths is shown to be in many cases a truncated multivariate normal distribution. Traffic conditions for which the normalized queue lengths arealmost asymptotically independent are determined. Asymptotic expansions of utilizations and expected queue lengths are presented. We show through an example how to obtain asymptotic expansions of performance measures when the networks are in mixed usage and how to apply the results to networks with finite data.Supported partially by NSF grant NCR93-04601.     

A technique for on-line sensitivity analysis of flexible manufacturing systems

The recent perturbation analysis approach to discrete event systems is applied to flexible manufacturing systems (FMS). While analytic (queueing) models are useful in preliminary design of such systems, they are not accurate enough at the detailed design/operation stage. Thus, experimentation on detailed simulations or on the actual system has been the way to optimize system performance. Perturbation analysis allows us to derive the sensitivity of system performance, with respect to several design/operating parameters, by observing a single experiment (and without having to actually alter the parameters — often a costly operation). Thus, observation of one experiment can give accurate directions for the improvement of several parameter values. Here we give a simulation example illustrating how perturbation analysis could be used on-line on an FMS to improve its performance, including reducing its operating cost. Experimental results are also presented validating the estimates obtained from this technique.Work supported by U.S. Office of Naval Research Contracts N00014-75-C-0648 and N00014-79-C-0776, and NSF Grant ENG78-15231, at Harvard University.A preliminary version of this paper appeared in the Proc. 1st ORSA/TIMS Conf. on Flexible Manufacturing Systems, August 1984. This version includes two appendices, which relate to implementation of the technique described in the main body of the paper.     

Estimating the sojourn time sensitivity in queueing networks using perturbation analysis

The sample path perturbation analysis technique developed earlier for the analysis of throughput sensitivities (Refs. 1–3) is extended to the performance measures involving mean sojourn times of customers. The major features of the sojourn time sensitivity problem are twofold. Firstly, it is a performance associated with servers, and not with customers. Secondly, the average sojourn time in any finite observation period can be a discontinuous function of mean service times when blocking is involved in a system. This discontinuity causes errors which must be accounted for in the estimation of sensitivities. Numerical experiments and analysis validate this method of computation of the sensitivities.This work was supported by the US Office of Naval Research, Contracts N00014-84-K-0465 and N00014-79-C-0776, and by the National Science Foundation, Grant No. ENG-78-15231.     

Statistical analysis of queueing systems

This paper provides an overview of the literature on statistical analysis of queueing systems. Topics discussed include: model identification, estimation, hypothesis testing and other related aspects. Not all of these statistical problems are covered in books on queueing theory or stochastic processes. The bibliography is not exhaustive, but comprehensive enough to provide sources from the literature.     

Robustness bounds of Hurwitz and Schur polynomials

In this paper, the problem of robustness bounds of Hurwitz and Schur polynomials is addressed. For weightedL ₂-norm perturbations of a Hurwitz polynomialp(s) or a Schur polynomialp(z), a new method is developed for calculating the maximal perturbation bound under which stability is preserved. We show that such a robustness bound is related to the minimum of a rational function. The new method is superior to the previous one developed by Soh, Berger, and Dabke in Ref. 1. Our approach also provides solutions for the perturbation polynomial p(s) or p(z) with minimal coefficient norm which causep(s)+p(s) orp(z)+p(z) to be unstable.     

Infinitesimal perturbation analysis for second derivative estimation and design of manufacturing flow controllers

A simulation-based numerical technique for the design of near-optimal manufacturing flow controllers for unreliable flexible manufacturing systems uses quadratic approximations of the value functions that characterize the optimal policy and employs stochastic optimization to design the key coefficients of the quadratic approximations. First and second derivative estimates that drive the optimization algorithm are obtained from a single sample path of the system via infinitesimal perturbation analysis (IPA). Extensive computational experience is reported for one, two, and three-part-type production systems. The relative performance of first-order and second-order stochastic optimization algorithms is investigated. The computational efficiency of these algorithms is finally compared to conventional controller design algorithms based on state-space discretization and successive approximation.This research was supported by the National Science Foundation, Grant No. DDM-89-14277 and DDM-9215368.     

Relative priority policies for minimizing the cost of queueing systems with service discrimination

This paper considers several single-server two-class queueing systems with different cost functions. Customers in the two classes are discriminated by service rates and relative priorities. Most attention is focused on the ones with general quadratic bivariable and exponential cost functions that are usually applied in the relatively complicated systems. To the best of the authors’ knowledge, there is no literature analyzing these two kinds of cost functions on the subject of relative priority. We explicitly present the conditions under which relative priority outperforms absolute priority for reducing system cost and further provide the method to find the optimal DPS policy. Moreover, we also discuss variations where service rates of the two classes are decision variables under service equalization and service discrimination disciplines, respectively.     

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.     

On the perturbation analysis of discrete-event dynamic systems

The paper describes a new approach to the analysis and optimization of discrete-event dynamic systems, such as queueing networks.Dedicated to G. LeitmannThe work reported in this paper was supported in part by ONR Contracts Nos. N00014-75-C-0648 and N00014-79-C-0776 and in part by NSF Grant No. NSF-ECS-82-13680.     

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.     

Variance comparison between infinitesimal perturbation analysis and likelihood ratio estimators to stochastic gradient

We theoretically compare variances between the Infinitesimal Perturbation Analysis (IPA) estimator and the Likelihood Ratio (LR) estimator to Monte Carlo gradient for stochastic systems. The results presented in Cui et al. (2020) [2] on variance comparison between these two estimators are substantially improved. We also prove a practically interesting result that the IPA estimators to European vanilla and arithmetic Asian options' Delta, respectively, have smaller variance when the underlying asset's return process is independent with the initial price and square integrable.