Management Science · 1988 · 164 citations · 28 references
BusinessComputer ScienceDerivativesQueuing TheoryStochastic ProcessesDiscrete-event SimulationQueueing AnalysisQueueing NetworksQueueing ProcessesQueueing SystemsQueueing TheoryConvergenceDiscrete Event Simulation ModelsDiscrete-event System SimulationMean Response TimeQueueing Network SimulationSimulation Of Queueing SystemsSteady-state Queueing AnalysisSteady-state Throughput
Infinitesimal Perturbation Analysis (IPA) is a method for computing a sample path derivative with respect to an input parameter in a discrete event simulation. The IPA algorithm is based on the fact that for certain parameters and any realization of a simulation, the change in parameter can be made small enough so that only the times of events get shifted, but their order does not change. This paper considers the convergence properties of the IPA sample path derivatives. In particular, the question of when an IPA estimate converges to the derivative of a steady state performance measure is studied. Necessary and sufficient conditions for this convergence are derived for a class of regenerative processes. Although these conditions are not guaranteed to be satisfied in general, they are satisfied for the mean stationary response time in the M/G/1 queue. A necessary condition for multiple IPA estimates to simultaneously converge to the derivatives of steady state throughputs in a queueing network is determined. The implications of this necessary condition are that, except in special cases, the original IPA algorithm cannot be used to consistently estimate steady state throughput derivatives in queueing networks with multiple types of customers, state-dependent routing or blocking. Numerical studies on IPA convergence properties are also presented.
28
Open, Closed, and Mixed Networks of Queues with Different Classes of Customers
Forest Baskett, K. Mani Chandy, Richard R. Muntz et al. · Journal of the ACM · 1975 · 2.4K citations · Full text
Mean-Value Analysis of Closed Multichain Queuing Networks
M. Reiser, S. S. Lavenberg · Journal of the ACM · 1980 · 1.2K citations · Full text
A Retrospective and Prospective Survey of the Monte Carlo Method
John H. Halton · SIAM Review · 1970 · 347 citations · Full text