Perturbation analysis: the state of the art and research issues explained via the GI/G/1 queue
Proceedings of the IEEEPublished 1 January 1989Open access
R. Suri
Citations216
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Perturbation analysis of discrete event dynamic systems (DEDS) enables parameter sensitivities of DEDS to be obtained by observing a single sample path of the system by demonstrating the basic theoretical issues involved.
Abstract
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Keywords
Computer ScienceDecision SciencesBusiness, Management and Accounting
The Annals of Mathematical StatisticsA Stochastic Approximation Method
9,581 Citations1951Herbert Robbins, Sutton Monro
The Annals of Mathematical StatisticsStochastic Estimation of the Maximum of a Regression Function
2,143 Citations1952J. Kiefer, J. Wolfowitz
Optimization of stochastic systems
579 Citations1986Peter W. Glynn
This paper gives a short survey of Monte Carlo algorithms for stochastic optimization, with emphasis on the analysis of convergence rate.
Journal of Optimization Theory and ApplicationsPerturbation analysis and optimization of queueing networks
304 Citations1983Y. C. Ho, Xia Cao
Management SciencePerturbation Analysis Gives Strongly Consistent Sensitivity Estimates for the <i>M</i>/<i>G</i>/1 Queue
238 Citations1988Rajan Suri, Michael A. Zazanis
IEEE Transactions on Automatic ControlPerformance evaluation and perturbation analysis of discrete event dynamic systems
234 Citations1987Yu‐Chi Ho
This is a conceptual and speculative paper concerning the future development of system and control theory in operational and discrete event systems with particular emphasis to the techniques of perturbation analysis.
IEEE Transactions on Automatic ControlSmoothed (conditional) perturbation analysis of discrete event dynamical systems
226 Citations1987Weibo Gong, Yu‐Chi Ho
A new sample path analysis approach based on the smoothing property of conditional expectation for estimating the performance sensitivity of discrete event dynamical systems is proposed and it is pointed out that one can get more knowledge about the system performance by observing and analyzing the sample path than by using the conventional simulation approach.
AutomaticaInfinitesimal and finite perturbation analysis for queueing networks
177 Citations1983Y. C. Ho, Xi‐Ren Cao +1 more
Experiments with zeroth (infinitesmal) and first order (finite) pertrubation analysis show that significant accuracy improvement can be obtained with small increase in computational effort.
Lecture notes in control and information sciencesAn Introduction to the Regenerative Method for Simulation Analysis
168 Citations1977A. A. Crane, J. Lemoine
An introduction to the regenerative method for simulation analysis, which leads to a statistical methodology for analyzing the output of those simulations which have the property of 'starting afresh probabilistically' from time to time.
Management ScienceConvergence Properties of Infinitesimal Perturbation Analysis Estimates
164 Citations1988Philip Heidelberger, Xi‐Ren Cao +2 more
IRE Transactions on Communications SystemsThe Modeling of Adaptive Routing in Data-Communication Networks
156 Citations1977A. Segall
Basic analytical models for problems of dynamic and quasi-static routing in data-communication networks are introduced and control and estimation methods are used to construct algorithms for the solution of the routing problem.
Convergence of parameter sensitivity estimates in a stochastic experiment
137 Citations1984Xi‐Ren Cao
Journal of the ACMInfinitesimal perturbation analysis for general discrete event systems
123 Citations1987Rajan Suri
It is proved that this algorithm gives exact values for the sample gradients of performance with respect to the parameters, by observing only one sample path of the DEDS, which offers the potential for very efficient calculation of the gradients.
IEEE Transactions on Automatic ControlExtensions of infinitesimal perturbation analysis
101 Citations1988Y. C. Ho, Shu Li
Optimization in simulation
101 Citations1987Marc S. Meketon
Several developments within the past seven years that promise greater efficiency in optimizing simulations are discussed, including Karmarkar's algorithm, infinitesimal perturbation analysis and likelihood ratios to estimate derivatives of performance measures with respect to parameters, adaptive control and hybrid models.
Management ScienceA Variable Buffer-Size Model and Its Use in Analyzing Closed Queueing Networks with Blocking
100 Citations1986Rajan Suri, Gregory W. Diehl
A new model, with variable buffer-size, is introduced as a conceptual tool to model part of a tandem network with blocking, using only product-form submodels, which enables efficient analysis of certain types of closed queueing networks with blocking due to limited buffer spaces.
Mathematics and Computers in SimulationThe score function approach for sensitivity analysis of computer simulation models
95 Citations1986Reuven Y. Rubinstein
It is shown that both the sensitivities and the performance extrapolation can be derived simultaneously by simulating only a single sample path from the nominal system.
IIE TransactionsSingle Run Optimization of Discrete Event Simulations—An Empirical Study Using the M/M/l Queue
92 Citations1989Rajan Suri, Ying Tat Leung
This study proposes a stochastic optimization method to optimize a simulation model in a single simulation run, with the potential of large savings in computational effort.
IEEE Transactions on Automatic ControlOn-line sensitivity analysis of Markov chains
84 Citations1989Christos G. Cassandras, Stephen G. Strickland
Management ScienceA New Approach to Determine Parameter Sensitivities of Transfer Lines
83 Citations1983Y. C. Ho, M. A. Eyler +1 more
The method provides a useful management support system in identifying the line critical points, where local improvement due to change in a parameter can result in most significant improvement in the overall line throughput performance.
Sensitivity analysis via likelihood ratios
77 Citations1986Martin I. Reiman, Alan Weiss
It is proven that the method works for a wide class of parameters and performance measures in regenerative simulation and on the method's limitations and on some numerical experiments.
Journal of Optimization Theory and ApplicationsImplementation of sensitivity calculations on a monte carlo experiment
68 Citations1983R. Suri
Operations ResearchA Sample Performance Function of Closed Jackson Queueing Networks
51 Citations1988Xi‐Ren Cao
It is proved that the average of derivatives of this sample performance function with a given initial state does converge, with probability one, to the derivative of the conditional mean value, given the same initial state.
Single run optimization of a SIMAN model for closed loop flexible assembly systems
49 Citations1987Rajan Suri, Ying Tat Leung
The algorithm presented optimizes the system in a single simulation run and is a multi-dimensional extension of the single run optimization algorithm proposed recently, given in the SIMAN language.
IEEE Journal on Robotics and AutomationPerformance sensitivity to routing changes in queuing networks and flexible manufacturing systems using perturbation analysis
44 Citations1985Yu‐Chi Ho, Xi‐Ren Cao
Performance EvaluationFirst-order perturbation analysis of a simple multi-class finite source queue
43 Citations1987Xi‐Ren Cao
Perturbation analysis is an efficient method to compute parameter sensitivities for discrete event systems and yields an asymptotically unbiased estimate of the sensitivity for the example system based on only one sample path of the system.
Management ScienceA Renewal Theoretic Approach to Bias Reduction in Regenerative Simulations
41 Citations1982Marc S. Meketon, Philip Heidelberger
Journal of Statistical Computation and SimulationSensitivity estimates based on one realization of a stochastic system†
38 Citations1987Xi‐Ren Cao
The phantom customer and marked customer methods for optimization of closed queueing networks with blocking and general service times
36 Citations1983Rajan Suri, Xi‐Ren Cao
Two new methods, the phantom customer method and the marked customer method, are developed as extensions of the perturbation analysis approach, which enable efficient and accurate optimization of closed queueing networks with blocking and general service-time distributions.
Using perturbation analysis for gradient estimation, averaging and updating in a stochastic approximation algorithm
35 Citations1988Michael C. Fu, Yu‐Chi Ho
IEEE Transactions on Automatic ControlAn event domain formalism for sample path perturbation analysis of discrete event dynamic systems
30 Citations1985Christos G. Cassandras, Y. C. Ho
A state-space representation of a general discrete event dynamic system (DEDS) model is presented on the basis of a natural event domain, which replaces time, and a set of simple perturbation equations are derived.
Mathematics and Computers in SimulationOn the efficient generation of discrete event sample paths under different system parameter values
29 Citations1988Yu‐Chi Ho, Shu Li +1 more
The techniques of perturbation analysis are generalized from the viewpoint of efficiently generating sample paths of discrete event dynamic systems operating under different parameter values, and many new ways to perform discrete event simulation for parametric study appear possible.
Annals of Operations ResearchA technique for on-line sensitivity analysis of flexible manufacturing systems
28 Citations1985R. Suri, James M. Dille
A simulation example is given illustrating how perturbation analysis could be used on-line on an FMS to improve its performance, including reducing its operating cost.
IEEE Transactions on Automatic ControlSensitivity analysis and optimization of throughput in a production line with blocking
28 Citations1987Xi‐Ren Cao, Yu‐Chi Ho
Using this perturbation analysis estimate of gradient, the Robbins-Monro stochastic procedure can be applied in optimizing the system throughput and the results also hold for systems with general routing but in which no server can block more than one other server simultaneously.
IEEE Transactions on Automatic ControlOptimal scheduling of two competing queues with blocking
27 Citations1991Jung‐Bong Suk, Christos G. Cassandras
Operations Research LettersInfinitesimal perturbation analysis of a birth and death process
26 Citations1988Paul Glasserman
Journal of Optimization Theory and ApplicationsEstimating the sojourn time sensitivity in queueing networks using perturbation analysis
25 Citations1987Xi‐Ren Cao, Y. C. Ho
The sample path perturbation analysis technique developed earlier for the analysis of throughput sensitivities is extended to the performance measures involving mean sojourn times of customers, and numerical experiments and analysis validate this method of computation of the sensitivities.
IEEE Journal on Selected Areas in CommunicationsPerturbation analytic methodologies for design and optimization of communication networks
22 Citations1988C.G. Cassandras, Stephen G. Strickland
For a G/G/1 link model, it is shown that efficient PA algorithms can be used to estimate online the marginal delay of messages due to incoming flow perturbations, used in a minimum-delay distribution algorithm to optimize routing.
Perturbation analysis of sojourn time in queueing networks
16 Citations1983Xi‐Ren Cao, Y. C. Ho
Numerical experiments and analysis validate this method of computation of the sensitivities of the sample path perturbation analysis technique developed earlier for throughput sensitivity analysis to performance measure involving sojourn time of customers.
Applications of Perturbation Techniques to Optimal Resource Sharing in Discrete Event Systems
13 Citations1988Christos G. Cassandras, Jung Im Lee
A quasistatic distributed gradient-based algorithm is derived and an estimator based on Finite Perturbation Analysis is developed and compared to one obtained through the Likelihood Ratio method.
Infinitesimal perturbation analysis of the M/G/1/K queue
11 Citations2003Weibo Gong, Paul Glasserman
The consistency of the algorithm is proved for the case of an M/M/1/K queue and the results can be useful in decentralized optimization of computer networks.
IEEE Transactions on Automatic ControlOn-line optimization for a flow control strategy
9 Citations1987C.G. Cassandras
An "Augmented chain " approach for on-line sensitivity analysis of Markov process
7 Citations1987Christos G. Cassandras, Stephen G. Strickland
Distributed routing with on-line marginal delay estimation
6 Citations2003Christos G. Cassandras, M.V. Abidi +1 more
A procedure is presented for estimating online marginal packet delays through links with respect to link flows without making such assumptions, based on perturbation analysis, in the context of a minimum-delay distributed routing algorithm for real-time implementation.
Convergence of a Single Run Simulation Optimization Algorithm
3 Citations1988Ying Tat Leung, Rajan Suri
This study applies a single run optimization algorithm to a simple optimization problem related to an autoregressive process of order one and shows that the algorithm converges to the true optimum with probability one.
Lecture notes in control and information sciencesStochastic model for optimal gas exploitation
2 Citations2006Pranas Aleksiunas, Antanas Burkauskas +1 more