Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-23T02:15:24.409Z Has data issue: false hasContentIssue false
  • English
  • Français

Smoothed Perturbation Analysis for Single-Server Queues by Some General Service Disciplines

Part of: Special processes Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Naoto Miyoshi  and
Toshiharu Hasegawa
Naoto Miyoshi*
Affiliation:
Kyoto University
Toshiharu Hasegawa*
Affiliation:
Kyoto University
*
∗ Address for both authors: Division of Applied Systems Science, Faculty of Engineering, Kyoto University, Kyoto 606-01, Japan.
∗ Address for both authors: Division of Applied Systems Science, Faculty of Engineering, Kyoto University, Kyoto 606-01, Japan.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider some single-server queues with general service disciplines, where the family of the queueing processes are parameterized by the service time distributions. Through the smoothed perturbation analysis (SPA) technique, we present under some mild conditions a unified approach to give the strongly consistent estimator for the gradient of the steady-state mean sojourn time with respect to the parameter of service time distributions, provided that it exists. Although the implementation of the SPA requires the additional sub-paths in general, the derived estimator is given as suitable for single-run computation. Simulation results are presented for queues with non-preemptive and preemptive-resume priority disciplines which demonstrate the performance of our estimators.

Keywords

SENSITIVITY ANALYSISSMOOTHED PERTURBATION ANALYSISSTRONG CONSISTENCYSINGLE-RUN ESTIMATIONFCFSLCFSPREEMPTIVE LIFONON-PREEMPTIVE PRIORITY QUEUEPREEMPTIVE-RESUME PRIORITY QUEUE

MSC classification

Primary: 60K25: Queueing theory
Secondary: 90B22: Queues and service
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 29 , Issue 2 , June 1997 , pp. 545 - 566
Copyright
Copyright © Applied Probability Trust 1997 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Baccelli, F. and Bremaud, P. (1994) Elements of Queueing Theory: Palm-Martingale Calculus and Stochastic Recurrences. Springer, Berlin.Google Scholar
[2] Bremaud, P. and Lasgouttes, J. M. (1993) Stationary IPA estimates for nonsmooth G/G/1/8 functionals via Palm inversion and level-crossing analysis. Discrete Event Dyn. Sys.: Theory Appl. 3, 347–374.CrossRefGoogle Scholar
[3] Cao, X.-R. (1985) Convergence of parameter sensitivity estimates in a stochastic experiment. IEEE Trans. Autom. Control 30, 845–853.Google Scholar
[4] Franken, P., König, D., Arndt, U. and Schmidt, V. (1982) Queues and Point Processes. Wiley, Chichester.Google Scholar
[5] Fu, M. C. and Hu, J.-Q. (1992) Extensions and generalizations of smoothed perturbation analysis in a generalized semi-Markov process framework. IEEE Trans. Autom. Control 37, 1483–1500.CrossRefGoogle Scholar
[6] Fu, M. C. and Hu, J.-Q. (1993) Smoothed perturbation analysis for queues with finite buffers. Queueing Systems: Theory Appl. 14, 249–269.Google Scholar
[7] Fu, M. C. and Hu, J.-Q. (1994) Smoothed perturbation analysis derivative estimation for Markov chains. Operat. Res. Lett. 15, 241–251.Google Scholar
[8] Fu, M. C. and Hu, J.-Q. (1994) (s, S) inventory systems with random lead times: Harris recurrence and its implications in sensitivity analysis. Prob. Eng. Inf. Sci. 8, 355–376.CrossRefGoogle Scholar
[9] Fu, M. C. and Hu, J.-Q. (1995) Addendum to ‘Extensions and generalizations of smoothed perturbation analysis in a generalized semi-Markov process framework’. IEEE Trans. Autom. Control 40, 1286–1287.CrossRefGoogle Scholar
[10] Fu, M. C. and Hu, J.-Q. (1995) On unbounded hazard rates for smoothed perturbation analysis. J. Appl. Prob. 32, 659–667.Google Scholar
[11] Glasserman, P. (1991) Gradient Estimation via Perturbation Analysis. Kluwer, Boston.Google Scholar
[12] Glasserman, P. (1991) Structural conditions for perturbation analysis derivative estimation: finite-time performance indices. Operat. Res. 39, 724–738.CrossRefGoogle Scholar
[13] Glasserman, P. (1992) Stationary waiting time derivatives. Queueing Systems: Theory Appl. 12, 369–390.Google Scholar
[14] Glasserman, P. (1993) Regenerative derivatives of regenerative sequences. Adv. Appl. Prob. 25, 116–139.CrossRefGoogle Scholar
[15] Glasserman, P., Hu, J.-Q. and Strickland, S. G. (1991) Strongly consistent steady-state derivarive estimates. Prob. Eng. Inf. Sci. 5, 391–413.Google Scholar
[16] Gong, W.-B. and Ho, Y.-C. (1987) Smoothed (conditional) perturbation analysis of discrete-event dynamic systems. IEEE Trans. Autom. Control 32, 858–867.CrossRefGoogle Scholar
[17] Gut, A. (1988) Stopped Random Walks: Limit Theorems and Applications. Springer, New York.CrossRefGoogle Scholar
[18] Heidelberger, P., Cao, X.-R., Zazanis, M. A. and Suri, R. (1988) Convergence properties of infinitesimal perturbation analysis estimates. Management Sci. 34, 1281–1302.CrossRefGoogle Scholar
[19] Ho, Y.-C. and Cao, X.-R. (1991) Discrete Event Dynamic Systems and Perturbation Analysis. Kluwer, Boston.Google Scholar
[20] Hu, J.-Q. (1982) Convexity of sample path performance and strong consistency of infinitesimal perturbation analysis estimates. IEEE Trans. Autom. Control 37, 258–262.Google Scholar
[21] Hu, J.-Q. (1993) Strong consistency of sample path derivatives. In Proc. First Chinese World Congress on Intelligent Control and Intelligent Automation. pp. 1668–1682.Google Scholar
[22] Hu, J.-Q. and Strickland, S. G. (1990) Strong consistency of sample path derivative estimates, Appl. Math. Lett. 3, 55–58.Google Scholar
[23] Jaiswal, N. K. (1968) Priority Queues. Academic Press, New York.Google Scholar
[24] Konstantopoulos, P. and Zazanis, M. A. (1992) Sensitivity analysis for stationary and ergodic queues. Adv. Appl. Prob. 24, 738–750.Google Scholar
[25] Konstantopoulous, P. and Zazanis, M. A. (1994) Sensitivity analysis for stationary and ergodic queues: additional results. Adv. Appl. Prob. 26, 556–560.CrossRefGoogle Scholar
[26] Miyoshi, N. (1995) Smoothed perturbation analysis estimates for stationary multiclass queues. In Proc. 34th IEEE CDC. pp. 2612–2617.Google Scholar
[27] Miyoshi, N. and Hasegawa, T. (1996) On-line gradient estimation for the multiclass GI/G/1 priority queue using perturbation analysis. IEEE Trans. Autom. Control 41, 300–305.Google Scholar
[28] Suri, R. (1987) Infinitesimal perturbation analysis for general discrete event systems. J. Assoc. Computing Machinery 34, 686–717.CrossRefGoogle Scholar
[29] Suri, R. (1989) Perturbation analysis: the state of the art and research issues explained via the GI/G/1 queue. Proc. IEEE 77, 114–137.Google Scholar
[30] Suri, R. and Zazanis, M. A. (1988) Perturbation analysis gives strongly consistent sensitivity estimates for the M/G/1 queue. Management Sci. 34, 39–64.CrossRefGoogle Scholar
[31] Takagi, H. (1988) Analysis of Polling Systems. MIT Press, Cambridge, MA.Google Scholar
[32] Takagi, H. (1991) Queueing Analysis: A Foundation of Performance Evaluation. Volume 1: Vacation and Priority Systems. Part 1. North-Holland, Amsterdam.Google Scholar
[33] Wardi, Y. and Hu, J.-Q. (1991) Strong consistency of infinitesimal perturbation analysis for tandem queueing networks. Discrete Event Dynamic Systems: Theory Appl. 1, 37–59.Google Scholar
[34] Zazanis, M. A. and Suri, R. (1994) Perturbation analysis of the GI/G//1 queue. Queueing Systems: Theory Appl. 18, 199–248.Google Scholar