On-Line Optimization of Queues Using Infinitesimal Perturbation Analysis

Infinitesimal perturbation analysis (IPA) is a method for estimating the gradient of a performance measure in a discrete event system by observing a single sample path of the system. The method lends itself naturally to recursive optimization using gradient-based algorithms. Such algorithms can be used in on-line optimization applications, or in single-run optimization of simulation models. We describe the use of such algorithms for optimization of single server queues. We give sufficient conditions that guarantee convergence of the algorithm to the optimizing point. The convergence proof is simple, and provides insight into how the algorithm behaves under different update times.