More Web Proxy on the site http://driver.im/

article

Free access

Infinitesimal perturbation analysis for general discrete event systems

Author:

Rajan SuriAuthors Info & Claims

Journal of the ACM (JACM), Volume 34, Issue 3

Pages 686 - 717

https://doi.org/10.1145/28869.28879

Published: 01 July 1987 Publication History

Abstract

A rigorous extension of the recent perturbation analysis approach to more general discrete event systems is given. First, a general class of systems and performance measures is defined, and some basic reprsentational and linearity properties are derived. Next a sample gradient of performance with respect to a parameter of the system is defined. Then, for certain parameters of such systems, an infinitesimal perturbation analysis algorithm is derived. It is proved that this algorithm gives exact values for the sample gradients of performance with respect to the parameters, by observing only one sample path of the DEDS. (However, the sample gradient may or may not be a good estimate of the gradient of the performance measure; this point is elaborated in the body of the paper.) The computational complexity of this algorithm is bound to be linear in the number of events. These results offer the potential for very efficient calculation of the gradients—a fact that can be used for design/operation of computer systems, communication networks, manufacturing systems, and many other real-world systems, particularly since restrictive assumptions (e.g., exponential distributions) are not required of the system.

References

[1]

BUZAtX)TT, J.A. The production capacity of job shops with limited storage space. Int. J. Prod. Res. 14, 5 (1976), 597-605.

[2]

BUZEN, J. P. Queueing network models of multiprogramming. Ph.D. dissertation, Division of Engineering and Applied Physics, Harvard Univ., Cambridge, Mass., May 1971.

[3]

CAO, X. R. Convergence of parameter sensitivity estimates in a stochastic experiment. IEEE Trans. Autom. Control 30, 9 (Sept. 1985), 845-853.

[4]

CAO, X.R. First order perturbation analysis of multiclass queueing networks. Perform. Eval. To be published.

[5]

CAO, X. R. On the sample functions of queueing networks with applications to perturbation analysis. Oper. Res. Submitted for publication.

[6]

CASSANDRAS, C. Sample path analysis of discrete event dynamic systems. Ph.D. dissertation, Division of Applied Sciences, Harvard Univ., Cambridge, Mass., Oct. 1982.

[7]

CASSANDRAS, C., AND HO, Y. C. An event domain formalism for sample path perturbation analysis of discrete event dynamic systems. IEEE Trans. Aut. Control 30, 12 (Dec. 1985), 1217-1220.

[8]

CHANDY, K. M., AND SAUER, C.H. Approximate methods for analyzing queueing network models of computer systems. ACM Comput. Surv. 10, 3 (Sept. 1979), 281-317.

[9]

CLEMENTSON, A. T. Extended Control and Simulation Language II: User's Manual. Univ. of Birmingham, Birmingham, U.K., 1972.

[10]

CRANE, M. A., AND IGLEHART, D. I. Simulating stable stochastic systems III: Regenerative processes and discrete event simulation. Oper. Res. 23, 1 (1975), 33-45.

[11]

DENNING, P. J., AND BUZEN, J.P. The operational analysis of queueing network models. A CM Comput. Surv. 10, 3 (Sept. 1978) 225-261.

[12]

EYLER, M.A. A new approach to the productivity study of transfer lines. Ph.D. dissertation, Division of Applied Science, Harvard Univ., Cambridge, Mass., Oct. 1982.

[13]

FlSHMAN, G.S. Principles of Discrete Event Simulation. Wiley, New York, 1978.

[14]

GERSHWXN, S. B., AND SCHICK, I.C. Modeling and analysis of three-stage transfer lines with unreliable machines and finite buffers. Oper. Res. 31, 2 (Mar./Apr. 1983) 354-380.

[15]

HEIDELBERGER, P., AND LAVENBERG, S.S. Computer performance evaluation methodology. Res. Rep. RC 10493, IBM, Yorktown Heights, N.Y., 1984.

[16]

HEIDELBERGER, P., AND WELCH, P.D. A spectral method for confidence interval generation and run length control in simulations. Commun. ACM 24, 4 (Apr. 1981), 233-245.

[17]

Ho, Y. C., ED. SPEEDS: A new technique for the analysis and optimization ofqueueing networks. Tech. Rep. 675, Division of Applied Sciences, Harvard Univ., Cambridge, Mass., Feb. 1983.

[18]

Ho, Y. C., AND CAO, X. Perturbation analysis and optimization of queueing networks. J. Optim. Theory Appl. 40, 4 (Aug. 1983), 559-582.

[19]

Ho, Y. C., AND CAO, X. Perturbation analysis of sojourn time in queueing networks. In Proceedings of the 22nd IEEE Conference on Decsion and Control (Dec.). IEEE, New York, 1983.

[20]

HO, Y. C., AND CASSANDRAS, C. Computing costate variables for discrete event systems. In Proceedings of the 19th IEEE Conference on Decision and Control (Dec.). IEEE, New York, 1980.

[21]

Ho, Y. C., AND CASSANDRAS, C. A new approach to the analysis of discrete event dynamic systems. Automatica 19, 2 (1983), 149-167.

[22]

Ho, Y. C., CAO, X., AND CASSANDRAS, C. Infinitesimal and finite perturbation analysis for queueing networks. Automatica 19, 4 (1983), 439-445.

[23]

Ho, Y. C., CASSANDRAS, C., AND SURf, R. Stochastic similarity and linearity in perturbation analysis of discrete event dynamic systems. In SPEEDS: A New Technique for the Analysis and Optimization of Queueing Networks, Y. C. Ho, Ed. Tech. Rep. 675, Harvard Univ., Cambridge, Mass., Feb. 1983, pp. 175-185.

[24]

Ho, Y. C., EYLER, M. A., AND CHIEN, T.T. A gradient technique for general buffer storage design in a serial production line. Int. J. Prod. Res. 17, 6 (1979), 557-580.

[25]

HO, Y. C., EYLER, M. A., AND CHIEN, T.T. A new approach to determine parameter sensitivities of transfer lines. Manage. Sci. 29, 6 (June 1983), 700-714.

[26]

Ho, Y. C., Sual, R., CAO, X. R., DIEHL, G. W., DILLE, J. W., AND ZAZANIS, M.A. Optimization of large multiclass (non-product-form) queueing networks using perturbation analysis. Large Scale Syst. 7 (Dec. 1984), 165-180.

[27]

JACKSON, J.R. Jobshop-like queueing systems. Manage. Sci. 10, 1 (Oct. 1963), 131-142.

[28]

KLEINROCK, L. Queueing Systems I and H. Wiley, New York, 1975.

[29]

KOENIGSaERG, E. Twenty five years of cyclic queues and closed queue networks: A review. J. Opl. Res. Soc. 33 (1982), 605-619.

[30]

LAVENBERG, S. S., ED. Computer Performance Modeling Handbook. Academic Press, Orlando, Fla., 1983.

[31]

LAVENSERG, S. S., AND WELCH, P.O. A perspective on the use of control variables to increase efficiency of Monte Carlo simulations. Manage. Sci. 27 (Mar. 1981), 322-335.

[32]

LAW, A. Confidence intervals in discrete event simulation: A comparison of replication and batch means. Nay. Res. Logist. Q. 24, 4 (1977), 667-678.

[33]

LAZOWSKA, E. D., ZAHORJAN, J., GRAHAM, G. S., AND SEVCIK, K. C. Quantitative System Performance. Prentice-Hall, Englewood Cliffs, N.J., 1984.

[34]

MEKETON, M.S. Optimization in simulation: A tutorial. Presented at Winter Simulation Conference, WSC83 (Dec.). 1983.

[35]

MINSKY, M.L. Computation: Finite and Infinite State Machines. Prentice-Hall, Englewood Cliffs, N.J., 1967.

[36]

NEWELL, G.F. Traffic Flow on Transportation Networks. MIT Press, Cambridge, Mass., 1980.

[37]

PETERSON, J.L. Petri nets. ACM Comput. Surv. 9, 3 (Sept. 1977), 223-252.

[38]

REISER, M. Queueing network analysis of computer communication networks with window flow control. IEEE Trans. Commun. COM-27, 8 (Aug. 1979), 1199-1209.

[39]

SAUER, C. H., AND CHANDY, K.M. Computer Systems Performance Modeling. Prentice-Hall, Englewood Cliffs, N.J., 1981.

[40]

SOLBERC, J.J. A mathematical model of computerized manufacturing systems. In Proceedings of the 4th International Conference on Product Research (Tokyo, Japan). 1977.

[41]

STECKE, K.E. Production planning problems for flexible manufacturing systems. Ph.D. dissertation, Dept. of Industrial Engineering, Purdue Univ., West Lafayette, Ind., 1981.

[42]

Sum, R. Robustness of queuing network formulas. ~ ACM 30, 3 (July 1983), 564-594.

[43]

SURf, R. Implementation of sensitivity calculations on a Monte Carlo experiment. J. Optim. Theory. AppL 40, 4 (Aug. 1983), 625-630.

[44]

Sum, R., AND CAO, X. The phantom customer and marked customer methods for optimization of closed queueing networks with blocking and general service times. Perform. EvaL Rev. (Special Issue, Aug. 1983), 243-256.

[45]

SURI, R., AND DILLE, J.W. A technique for on-line sensitivity analysis of flexible manufacturing systems. Ann. Oper. Res. 3 (Dec. 1985), pp. 381-391.

[46]

Sum, R., AND HILDEBRANT, R.R. Modeling flexible manufacturing systems using mean value analysis. ~ Manuf. Syst. 3, I (1984), 27-38.

[47]

SuRI, R., AND ZAZANm, M.A. Perturbation analysis gives strongly consistent estimates for the M/G/1 queue. Manage. Sci. Submitted for publication.

[48]

ZAZANm, M. A., AND Sum, R. Estimating first and second derivatives of response time for G/G/I queues from a single sample path. Queueing Syst. Theory and Appl., submitted for publication.

[49]

ZAZANIS, M. A., AND SUR|, R. Comparison of perturbation analysis with conventional sensitivity estimates for stochastic systems. Oper. Res., submitted for publication.

[50]

ZmGLER, B.P. Theory of Modelling and Simulation. Wiley, New York, 1976.

Cited By

Jain PShashaani SByon E(2024)Simulation model calibration with dynamic stratification and adaptive samplingJournal of Simulation10.1080/17477778.2024.2420807(1-22)Online publication date: Nov-2024
https://doi.org/10.1080/17477778.2024.2420807
Kassoul KCheikhrouhou NZufferey N(2023)Simultaneous allocation of buffer capacities and service times in unreliable production linesInternational Journal of Production Research10.1080/00207543.2023.2168310(1-21)Online publication date: 24-Jan-2023
https://doi.org/10.1080/00207543.2023.2168310
Wang CZhou S(2021)Control of key performance indicators of manufacturing production systems through pair-copula modeling and stochastic optimizationJournal of Manufacturing Systems10.1016/j.jmsy.2020.11.00358(120-130)Online publication date: Jan-2021
https://doi.org/10.1016/j.jmsy.2020.11.003
Show More Cited By

Index Terms

Infinitesimal perturbation analysis for general discrete event systems

Recommendations

Using infinitesimal perturbation analysis of stochastic flow models to recover performance sensitivity estimates of discrete event systems

Stochastic Flow Models (SFMs) form a class of hybrid systems used as abstractions of complex Discrete Event Systems (DES) for the purpose of deriving performance sensitivity estimates through Infinitesimal Perturbation Analysis (IPA) techniques when ...
Extended perturbation analysis of discrete event dynamical systems
Perturbation analysis for the hyperbolic QR factorization

The hyperbolic QR factorization is a generalization of the classical QR factorization and can be regarded as the triangular case of the indefinite QR factorization proposed by Sanja Singer and Sasa Singer. In this paper, the perturbation analysis for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 34, Issue 3

July 1987

248 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/28869

Issue’s Table of Contents

Copyright © 1987 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1987

Published in JACM Volume 34, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

109
Total Citations
View Citations
1,418
Total Downloads

Downloads (Last 12 months)138
Downloads (Last 6 weeks)19

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jain PShashaani SByon E(2024)Simulation model calibration with dynamic stratification and adaptive samplingJournal of Simulation10.1080/17477778.2024.2420807(1-22)Online publication date: Nov-2024
https://doi.org/10.1080/17477778.2024.2420807
Kassoul KCheikhrouhou NZufferey N(2023)Simultaneous allocation of buffer capacities and service times in unreliable production linesInternational Journal of Production Research10.1080/00207543.2023.2168310(1-21)Online publication date: 24-Jan-2023
https://doi.org/10.1080/00207543.2023.2168310
Wang CZhou S(2021)Control of key performance indicators of manufacturing production systems through pair-copula modeling and stochastic optimizationJournal of Manufacturing Systems10.1016/j.jmsy.2020.11.00358(120-130)Online publication date: Jan-2021
https://doi.org/10.1016/j.jmsy.2020.11.003
Kim DYun TMoon IBae J(2021)Automatic calibration of dynamic and heterogeneous parameters in agent-based modelsAutonomous Agents and Multi-Agent Systems10.1007/s10458-021-09528-435:2Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10458-021-09528-4
Bowman ASchmee J(2018)Estimating Sensitivity of Process Capability Modeled by a Transfer FunctionJournal of Quality Technology10.1080/00224065.2004.1198026736:2(223-239)Online publication date: 16-Feb-2018
https://doi.org/10.1080/00224065.2004.11980267
Cao X(2016)Event coupling and performance sensitivity analysis of generalized semi-Markov processesAdvances in Applied Probability10.2307/142813227:03(741-769)Online publication date: 1-Jul-2016
https://doi.org/10.2307/1428132
Miyoshi NHasegawa T(2016)Smoothed Perturbation Analysis for Single-Server Queues by Some General Service DisciplinesAdvances in Applied Probability10.2307/142801629:02(545-566)Online publication date: 1-Jul-2016
https://doi.org/10.2307/1428016
Cao X(2016)Realization factors and sensitivity analysis of queueing networks with state-dependent service ratesAdvances in Applied Probability10.2307/142760422:01(178-210)Online publication date: 1-Jul-2016
https://doi.org/10.2307/1427604
Miyoshi NHasegawa T(2016)Smoothed Perturbation Analysis for Single-Server Queues by Some General Service DisciplinesAdvances in Applied Probability10.1017/S000186780002812329:02(545-566)Online publication date: 1-Jul-2016
https://doi.org/10.1017/S0001867800028123
Cao X(2016)Event coupling and performance sensitivity analysis of generalized semi-Markov processesAdvances in Applied Probability10.1017/S000186780002713027:03(741-769)Online publication date: 1-Jul-2016
https://doi.org/10.1017/S0001867800027130
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents