Optimization of Queues Using an Infinitesimal Perturbation Analysis-Based Stochastic Algorithm with General Update Times
Authors:
- Edwin K. P. ChongECEdwin K. P. Chong
- Peter J. RamadgePRPeter J. Ramadge
- 1 May 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 31 (3) , 698-732
Abstract
Convergence (with probability one) of a stochastic optimization algorithm for a single server queue is proved. The parameter to be optimized is updated using an infinitesimal perturbation analysis estimate of the gradient of the performance measure, and the updates are performed at general times. First, an algorithm in which the parameter is updated before each customer begins service is considered. Then it is shown how this analysis can be extended to an algorithm that updates at certain stopping times. The analysis suggests that the sample path behavior of the algorithm is similar to that of an algorithm that updates at the start of every busy period.Keywords
This publication has 11 references indexed in Scilit:
- Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation analysisJournal of Optimization Theory and Applications, 1990
- Single Run Optimization of Discrete Event Simulations—An Empirical Study Using the M/M/l QueueIIE Transactions, 1989
- Using perturbation analysis for gradient estimation, averaging and updating in a stochastic approximation algorithm1988
- Perturbation Analysis Gives Strongly Consistent Sensitivity Estimates for the M/G/1 QueueManagement Science, 1988
- Stopped Random Walks1988
- Regeneration and Networks of Queues1987
- Optimization of stochastic systems1986
- The queue GI/G/1: Finite moments of the cycle variables and uniform rates of convergenceStochastic Processes and their Applications, 1985
- Applications of a Kushner and Clark lemma to general classes of stochastic algorithmsIEEE Transactions on Information Theory, 1984
- Probability1984