A Perturbation Analysis Approach to Phantom Estimators for Waiting Times in the G/G/1 Queue

We study gradient estimation for waiting times in the G/G/1 queue. We propose a new estimator based on a synthesis of perturbation analysis and weak differentiation. More specifically, we combine the perturbation propagation rules from perturbation analysis with perturbation generation rules from weak differentiation. This leads to an on-line phantom estimator. Numerical experiments show that this estimator has smaller work normalized variance than IPA.     

A note on the relation between weak derivatives and perturbation realization

Studies the relationship between two important approaches in perturbation analysis (PA)-perturbation realization (PR) and weak derivatives (WDs). Specifically, we study the relation between PR and WDs for estimating the gradient of stationary performance measures of a finite state-space Markov chain. We show that the WDs expression for the gradient of a stationary performance measure can be interpreted as the expected PR factor where the expectation is carried out with respect to a distribution that is given through the weak derivative of the transition kernel of the Markov chain. Moreover, we present unbiased gradient estimators.     

Complexity reduction in MPC for stochastic max-plus-linear discrete event systems by variability expansion

Model predictive control (MPC) is a popular controller design technique in the process industry. Recently, MPC has been extended to a class of discrete event systems that can be described by a model that is “linear” in the max-plus algebra. In this context both the perturbations-free case and for the case with noise and/or modeling errors in a bounded or stochastic setting have been considered. In each of these cases an optimization problem has to be solved on-line at each event step in order to determine the MPC input. This paper considers a method to reduce the computational complexity of this optimization problem, based on variability expansion. In particular, it is shown that the computational load is reduced if one decreases the level of “randomness” in the system.     

Perturbation analysis of waiting times in the G/G/1 queue

This paper is devoted to perturbation analysis of the stationary distribution of waiting times in the G/G/1 queue with a parameter-dependent service time distribution. We provide sufficient conditions under which the stationary distribution is Lipschitz continuous and we explicitly compute the Lipschitz constant. Thereby, we provide bounds on the effect of a (finite) perturbation of the service time distribution on the stationary waiting time. The case of infinitesimal perturbations (read, derivatives) is treated as well.     

A Note on Gradient Estimation for Maintenance Systems

This technical note addresses gradient estimation for the cost performance of a two-component maintenance system with respect to the threshold parameter of an age replacement policy. We derive a new gradient estimator based on the measure-valued differentiation (MVD) approach. The performance of the phantom estimator is compared with that of the known smoothed perturbation analysis (SPA) estimator. We show that the phantom estimator has a lower variance, and requires less computational effort than the SPA estimator.     

Customer-Oriented Finite Perturbation Analysis for Queueing Networks

We consider queueing networks for which the performance measureJ ( ) depends on a parameter , which can be a service time parameter or a buffer size, and we are interested in sensitivity analysis of J ( ) with respect to . We introduce a new method, called customer-oriented finite perturbation analysis (CFPA), which predicts J ( + ) for an arbitrary, finite perturbation from a simulation experiment at . CFPA can estimate the entire performance function (by using a finite number of chosen points and fitting a least-squares approximating polynomial to the observation) within one simulation experiment. We obtain CFPA by reformulating finite perturbation analysis (FPA) for customers. The main difference between FPA and CFPA is that the former calculates the sensitivities of timing epochs of events, such as external arrivals or service time completions, while the latter yields sensitivities of departure epochs of customers. We give sufficient conditions for unbiasedness of CFPA. Numerical examples show the efficiency of the method. In particular, we address sensitivity analysis with respect to buffer sizes and thereby give a solution to the problem for which perturbation analysis was originally built.     

A functional approximation for the M/G/1/N queue

This paper presents a new approach to the functional approximation of the M/G/1/N built on a Taylor series approach. Specifically, we establish an approximative expression for the remainder term of the Taylor series that can be computed in an efficient manner. As we will illustrate with numerical examples, the resulting Taylor series approximation turns out to be of practical value.     

Towards a (Max,+) Control Theory for Public Transportation Networks

We consider the modelling and analysisof public transportation networks, such as railway or subwaynetworks, governed by a timetable. Specifically, we study a (max,+)-linearmodel of a generic transportation network and thereby give aself-contained introduction to the key ideas underlying the (max,+)algebra. We elaborate on the algebraic structure implied by the(max,+)-model to formulate (and solve) the control problem inthe deterministic as well as in the stochastic case. The controlproblem is here whether a train should wait on a connecting trainwhich is delayed. Our objective is then to minimise the propagationof the delay through the network while maintaining as many connectionsas possible. With respect to the deterministic control problem,we present some recent ideas concerning the use of (max,+)-techniquesfor analysing the propagation of delays. Moreover, we show howone can use the (max,+)-algebra to drastically reduce the searchspace for the deterministic control problem. For the stochasticcontrol problem, we consider a parameterised version of the controlproblem, that is, we describe the control policy by means ofa real-valued parameter, say . Finding theoptimal control is then turned into an optimisation problem withrespect to . We address the problem by incorporatingan estimator of the derivative of the expected performance withrespect to into a stochastic approximationalgorithm.