Perturbation Analysis of Discrete Event Dynamic Systems

1. Introduction to Discrete Event Dynamic Systems.- 1.1 Introduction.- 1.2 Models of DEDS.- 2. Introduction to Perturbation Analysis.- 2.1 Notations.- 2.2 A Short History of the Perturbation Analysis Development.- 3. Informal Treatment of the Infinitesimal Perturbation Analysis (IPA) 2.- 3.1 The Basic Idea.- 3.2 Single Class Queueing Networks.- 3.3 A GSMP Formalism for IPA.- 3.4 Realization Ratios.- 3.5 The GI/G/1 Queue.- 3.6 Load Dependent Server and IPA.- 3.7 Remarks about PA.- 4. Foundation of Infinitesimal Perturbation Analysis.- 4.1 Sample Derivative and Interchangeability.- 4.2 Perturbation Analysis for Closed Jackson Network.- 1. Sample Performance Functions.- 2. Sample Derivative of Performance in Transient Periods.- 3. Derivative of Steady State Performance.- 4.3 Realization and Sensitivity Analysis.- 1. Realization Probability.- 2. Realization Index and The Convergence Theorems.- 3. Sensitivity of Throughputs.- 4. Calculation of Other Sensitivities.- 4.4 Sensitivity Analysis of Networks with General Service Distributions.- 4.5 IPA Estimates of the M/G/1 and GI/G/1 Queue.- 1. M/G/1 Queue: A Direct Approach.- 2. M/G/1 Queue: The Approach Based on Stochastic Convexity.- 4.6 Some Technical Proofs.- 5. Extensions of IPA.- 5.1 System Representation and PA.- 5.2 Another Sufficient Condition for Interchangeability.- 1. The Basic Idea.- 2. A sufficient condition based on the generalized semi Markov process model.- 3 Queueing network examples.- 5.3 Routing Probability Sensitivity.- 5.4 The Multiclass M/G/1 Queue and Networks.- 1. The Two Class M/M/1 Queue.- 2. The Rescheduling Approach.- 3. Approximate MultiClass Network Analysis and IPA.- 5.5 Smoothed Perturbation Analysis (SPA).- 6. Finite Perturbation Analysis.- 6.1 The Idea of “Cut-and-Paste”.- 1. A Simple Example of “Cut-and-Paste”.- 2. State vs. Event Matching.- 6.2 The State Matching vs. Event Matching Algorithms.- 1. Analytical Comparison of State Matching Algorithms vs. Event Matching Algorithms for a Simple System.- 2. Empirical Validation.- 6.3 “Cut-and-Paste” as a Generalization of the Rejection Method.- 6.4 First Order Propagation Rules and Approximate EPA.- 7. General Sensitivity Analysis.- 7.1 Efficient Sample Path Generation.- 1. The Standard Clock and the M/M/1 Example.- 2. IPA via the Standard Clock.- 3. The Alias Method of Choosing Event Types.- 7.2 Trajectory Projection and State Augmentation.- 1. Trajectory Projection of the Automata Model.- 2. State Augmentation Method for Markov Chains.- 7.3 The Likelihood Ratio Approach.- 1. A Markov Chain Example and Variance Reduction.- 2. Basic Analysis.- 3. An Example of the Variances of PA and LR Estimates.- 4. Comparison of the PA and Likelihood Ratio Estimates.- 5. DEDS models Revisited.- 8. Aggregation, Decomposition, and Equivalence.- 8.1 Equivalent Server and Aggregation.- 1. Product-Form Networks.- 2. General Networks.- 8.2 Perturbation Analysis on Aggregated Systems and Aggregated PA.- 1. Perturbation Analysis of Aggregated Systems.- 2. Aggregated Perturbation Analysis.- 3. Aggregation of Multiclass Queueing Networks -An Example.- 8.3 Aggregation and Decomposition of Markov Chains.- 1. The Case of v’(s) = 0.- 2. The Case Where v’(s) Can Be Calculated in Closed Form.- 8.4 Decomposition via the A-Segment Algorithm for very Large Markov Chains.- Appendix A. Elements of Queueing Theory.- Appendix B. elements of Discrete Event Simulation.- Appendix C. Elements of Optimization and Control Theory 3.- Appendix D. A Simple Illustrative Example of the Different Models of DEDS.- Appendix E. A Sample Program of Perturbation Analysis.- References.