Mathematical programming-based perturbation analysis for GI/G/1 queues

ABSTRACT

This paper addresses several issues of using the mathematical programming representations of discrete-event dynamic systems in perturbation analysis. In particular, linear programming techniques are used to perform Infinitesimal Perturbation Analysis (IPA) on GI/G/1 queues. A condition for unbiasedness is derived. For finite perturbation analysis (FPA), an upper bound is given for the error term of FPA.

REFERENCES

• 1: Cao, X. R. 1985. Convergence of parameter sensitivity estimates in a stochastic experiment. IEEE Transactions on Automatic Control, 30(9):845--853.
• 2: Wai Kin Chan , Lee W. Schruben, Special topics on simulation analysis: properties of discrete event systems from their mathematical programming representations, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
• 3: Chan, W. K. V. 2005. Mathematical representation of discrete-event system dynamics. Ph.D dissertation, University of California, Berkeley.
• 4: Dudley, R. M. 2002. Real analysis and probability. 2nd ed. Cambridge, England: Cambridge University Express.
• 5: Michael Freimer , Lee Schruben, Stochastic optimization using simulation: graphical representation of IPA estimation, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
• 6: Fu, M. C. and J. Q. Hu. 1991. Consistency of infinitesimal perturbation analysis for the GI/G/m queue. European Journal of Operations Research, 34(1):39--64.
• 7: Fu, M. and J. Q. Hu. 1997. Conditional monte carlo: gradient estimation and optimization applications. Boston, Massachusetts: Kluwer Academic Publishers.
• 8: Gal, T. 1979. Postoptimal analysis, parametric programming, and related topics. 1^st Ed. New York, USA: McGraw Hill.
• 9: Gal, T. and H. J. Greenberg. 1997. Advances in sensitivity analysis and parametric programming. Boston, Massachusetts: Kluwer Academic Publishers.
• 10: Glasserman, P. and Y. C. Ho. 1991. Gradient estimation via perturbation analysis. Boston, Massachusetts: Kluwer Academic Publishers.
• 11: Philip Heidelberger , Xi-Ren Cao , Michael A. Zazanis , Rajan Suri, Convergence properties of infinitesimal perturbation analysis, Management Science, v.34 n.11, p.1281-1302, Nov. 1988 [doi>10.1287/mnsc.34.11.1281]
• 12: Ho, Y. C. and X. R. Cao. 1991. Perturbation analysis of discrete event dynamic systems. Boston, Massachusetts: Kluwer Academic Publishers.
• 13: James Renegar, Some perturbation theory for linear programming, Mathematical Programming: Series A and B, v.65 n.1, p.73-91, May 31, 1994 [doi>10.1007/BF01581690]
• 14: Rockafellar, R. T. 1970. Convex Analysis. Princeton, New Jersey: Princeton University Press.
• 15: Lee W. Schruben, Mathematical programming models of discrete event system dynamics, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 16: Rajan Suri , Michael A. Zazanis, Perturbation analysis gives strongly consistent sensitivity estimates for the M/G/1 queue, Management Science, v.34 n.1, p.39-64, Jan. 1988 [doi>10.1287/mnsc.34.1.39]
• 17: James E. Ward , Richard E. Wendell, Approaches to sensitivity analysis in linear programming, Annals of Operations Research, v.27 n.1-4, p.3-38, Dec. 1990 [doi>10.1007/BF02055188]
• 18: Zazanis, M. A. 1987. Weak convergence of sample path derivatives for the waiting time in a single-server queue. In Proceedings of the 25^th Allerton Conference on Communication, Computing and Control: 297--304.