共查询到10条相似文献,搜索用时 109 毫秒
1.
Perturbation analysis of communication networks with feedback control using stochastic hybrid models
Communication networks may be abstracted through Stochastic Fluid Models (SFM) with the node dynamics described by switched flow equations as various events take place, thus giving rise to hybrid automaton models with stochastic transitions. The inclusion of feedback mechanisms complicates these dynamics. In a tandem setting, a typical feedback mechanism is the control of a node processing rate as a threshold-based function of the downstream node’s buffer level. We consider the problem of controlling the threshold parameters so as to optimize performance metrics involving average workload and packet loss and show how Infinitesimal Perturbation Analysis (IPA) can be used to analyze congestion propagation through a network and develop gradient estimators of such metrics. 相似文献
2.
M. C. Fu 《Journal of Optimization Theory and Applications》1990,65(1):149-160
Discrete-event systems to which the technique of infinitesimal perturbation analysis (IPA) is applicable are natural candidates for optimization via a Robbins-Monro type stochastic approximation algorithm. We establish a simple framework for single-run optimization of systems with regenerative structure. The main idea is to convert the original problem into one in which unbiased estimators can be derived from strongly consistent IPA gradient estimators. Standard stochastic approximation results can then be applied. In particular, we consider the GI/G/1 queue, for which IPA gives strongly consistent estimators for the derivative of the mean system time. Convergence (w.p.1) proofs for the problem of minimizing the mean system time with respect to a scalar service time parameter are presented. 相似文献
3.
We consider resource contention games in a stochastic hybrid system setting using Stochastic Flow Models (SFM) with multiple classes and class-dependent objectives. We present a general modeling framework for such games, where Infinitesimal Perturbation Analysis (IPA) estimators are derived for the derivatives of various class-dependent objectives. This allows us to study these games from the point of view of system-centric optimization of a performance metric and compare it to the user-centric approach where each user optimizes its own performance metric. We derive explicit solutions for a specific model in which the competing user classes employ threshold control policies and service is provided on a First Come First Serve (FCFS) basis. The unbiasedness of the IPA estimators is established in this case and it is shown that under certain conditions the system-centric and user-centric optimization solutions coincide. 相似文献
4.
C. G. Cassandras W. B. Gong J. I. Lee 《Journal of Optimization Theory and Applications》1991,70(3):491-519
Sample-path-based stochastic gradient estimators for performance measures of queueing systems rely on the assumption that a probability distribution of the random vector of interest (e.g., a service or interarrival time sequence) is given. In this paper, we address the issue of dealing with unknown probability distributions and investigate the robustness of such estimators with respect to possibly erroneous distribution choices. We show that infinitesimal perturbation analysis (IPA) can be robust in this sense and, in some cases, provides distribution-independent estimates. Comparisons with other gradient estimators are provided, including experimental results. We also show that finite perturbation analysis (FPA), though only providing gradient approximations, possesses some attractive robustness properties with respect to unknown distribution parameters. An application of FPA estimation is included for a queueing system performance optimization problem involving customers with real-time constraints.This work was supported in part by the National Science Foundation Grant ECS-88-01912 and by the Office of Naval Research Contract N00014-87-K-0304.The authors wish to thank Dr. Jack Holtzman for several useful comments and suggestions. 相似文献
5.
A single-stage Make-to-Stock (MTS) production-inventory system consists of a production facility coupled to an inventory facility,
and is subject to a policy that aims to maintain a prescribed inventory level (called base stock) by modulating production capacity. This paper considers a class of single-stage, single-product MTS systems with backorders,
driven by random demand and production capacity, and subject to a continuous-review base-stock policy. A model from this class
is formulated as a stochastic fluid model (SFM), where all flows are described by stochastic rate processes with piecewise
constant sample paths, subject to very mild regularity assumptions that merely preclude accumulation points of jumps with
probability 1. Other than that, the MTS model in SFM setting is nonparametric in that it assumes no specific form for the underlying probability law, and as such is quite general. The paper proceeds
to derive formulas for the (stochastic) IPA (Infinitesimal Perturbation Analysis) derivatives of the sample-path time averages
of the inventory level and backorders level with respect to the base-stock level and a parameter of the production rate. These
formulas are comprehensive in that they are exhibited for any initial condition of the system, and include right and left
derivatives (when they do not coincide). The derivatives derived are then shown to be unbiased and their formulas are seen
to be amenable to fast computation. The generality of the model and comprehensiveness of the IPA derivative formulas hold
out the promise of gradient-based applications. More specifically, since the base-stock level and production rate are the
key control parameters of MTS systems, the results provide the theoretical underpinnings for optimizing the design of MTS
systems and for devising prospective on-line adaptive control algorithms that employ IPA derivatives. The paper concludes
with a discussion of those issues. 相似文献
6.
《Operations Research Letters》2022,50(2):199-204
We theoretically compare variances between the Infinitesimal Perturbation Analysis (IPA) estimator and the Likelihood Ratio (LR) estimator to Monte Carlo gradient for stochastic systems. The results presented in Cui et al. (2020) [2] on variance comparison between these two estimators are substantially improved. We also prove a practically interesting result that the IPA estimators to European vanilla and arithmetic Asian options' Delta, respectively, have smaller variance when the underlying asset's return process is independent with the initial price and square integrable. 相似文献
7.
Y. Wardi M. H. Kallmes C. G. Cassandras W. -B. Gong 《Annals of Operations Research》1992,39(1):269-293
We present unbiased Smoothed Perturbation Analysis (SPA) estimators for the derivatives of occupancy-related performance functions in serial networks ofG/G/1 queues with respect to parameters of the distributions of service times at the queues. The sample functions for these performance measures are piecewise constant, and established Infinitesimal Perturbation Analysis (IPA) methods typically fail to provide unbiased estimators in this case. The performance measures considered in this paper are: the average network occupancy as seen by an arrival, the average occupancy of a specific queue as seen by an arrival to it, the probability that a customer is blocked at a specific queue, and the probability that a customer leaves a queue idle. The SPA estimators derived are quite simple and flexible, and they lend themselves to straightforward analysis. Unlike most of the established SPA algorithms, ours are not based on the comparison of hazard rates, and the proofs of their unbiasedness do not require the boundedness of such hazard rates.Supported in part by the National Science Foundation under Grant ECS-8801912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595. 相似文献
8.
We consider a class of single-stage, single-product Make-to-Stock production-inventory system (MTS system) with backorders. The system employs a continuous-review base-stock policy which strives to maintain a prescribed
base-stock level of inventory. In a previous paper of Zhao and Melamed (Methodology and Computing in Applied Probability 8:191–222, 2006), the Infinitesimal Perturbation Analysis (IPA) derivatives of inventory and backorders time averages with respect to the base-stock level and a parameter of the production-rate
process were computed in Stochastic Fluid Model (SFM) setting, where the demand stream at the inventory facility and its replenishment stream from the production facility are
modeled by stochastic rate processes. The advantage of the SFM abstraction is that the aforementioned IPA derivatives can
be shown to be unbiased. However, its disadvantages are twofold: (1) on the modeling side, the highly abstracted SFM formulation
does not maintain the identity of transactions (individual demands, orders and replenishments) and has no notion of lead times,
and (2) on the applications side, the aforementioned IPA derivatives are brittle in that they contain instantaneous rates
at certain hitting times which are rarely known, and consequently, need to be estimated. In this paper, we remedy both disadvantages
by using a discrete setting, where transaction identity is maintained, and order fulfillment from inventory following demand
arrivals and inventory restocking following replenishment arrivals are modeled as discrete jumps in the inventory level. We
then compute the aforementioned IPA derivatives with respect to the base-stock level and a parameter of the lead-time process
in the discrete setting under any initial system state. The formulas derived are shown to be unbiased and directly computable
from sample path observables, and their computation is both simple and computationally robust. 相似文献
9.
R. A. Bowman 《Annals of Operations Research》1994,53(1):533-551
10.
Perturbation analysis is a technique that expedites the process of performing experiments on discrete-event simulation models. This makes it possible to derive sensitivity estimates from one computer execution of a simulation model. Infinitesimal perturbation analysis (IPA) is one class of algorithms used in perturbation analysis. In this paper, the techniques and algorithms used in simulation to perform infinitesimal perturbation analysis are examined. Each algorithm is discussed in detail, with comments concerning implementation problems and examples with experimental results for serial transfer lines. The results of this paper show that for simple systems, IPA can be easily implemented in a general-purpose simulation language such as SIMAN. Unfortunately, for any given system, parameter or performance measure, the algorithm used to generate the gradient may vary. Additionally, algorithms for more complex classes of problems do not yet exist. This problem hampers the current possibility of incorporating IPA into general-purpose simulation languages. 相似文献