Resource contention games in multiclass stochastic flow models

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.     

Asymptotic analysis of the effect of arrival model uncertainties in some optimal routing problems

We study the effect of arrival model uncertainties on the optimal routing in a system of parallel queues. For exponential service time distributions and Bernoulli routing, the optimal mean system delay generally depends on the interarrival time distribution. Any error in modeling the arriving process will cause a model-based optimal routing algorithm to produce a mean system delay higher than the true optimum. In this paper, we present an asymptotic analysis of the behavior of this error under heavy traffic conditions for a general renewal arrival process. An asymptotic analysis of the error in optimal mean delay due to uncertainties in the service time distribution for Poisson arrivals was reported in Ref. 6, where it was shown that, when the first moment of the service time distribution is known, this error in performance vanishes asymptotically as the traffic load approaches the system capacity. In contrast, this paper establishes the somewhat surprising result that, when only the first moment of the arrival distribution is known, the error in optimal mean delay due to uncertainties in the arrival model is unbounded as the traffic approaches the system capacity. However, when both first and second moments are known, the error vanishes asymptotically. Numerical examples corroborating the theoretical results are also presented.This work was supported by the National Science Foundation under Grants ECS-88-01912 and EID-92-12122 and by NASA under Contract NAG 2-595.The authors wish to thank an anonymous referee for pointing out Ref. 20, thus avoiding the need for an explicit proof of convexity of the cost function considered in the paper.     

Online IPA Gradient Estimators in Stochastic Continuous Fluid Models

This paper applies infinitesimal perturbation analysis (IPA) to loss-related and workload-related metrics in a class of stochastic flow models (SFM). It derives closed-form formulas for the gradient estimators of these metrics with respect to various parameters of interest, such as buffer size, service rate, and inflow rate. The IPA estimators derived are simple and fast to compute, and are further shown to be unbiased and nonparametric, in the sense that they can be computed directly from the observed data without any knowledge of the underlying probability law. These properties hold out the promise of utilizing IPA gradient estimates as ingredients of online management and control of telecommunications networks. While this paper considers single-node SFMs, the analysis method developed is amenable to extensions to networks of SFM nodes with more general topologies.     

Ordinal optimisation and simulation

Simulation plays a vital role in designing and analysing stochastic systems, particularly, in comparing alternative system designs with a view to optimise system performance. Using simulation to analyse complex systems, however, can be both prohibitively expensive and time consuming. Efficiency is a key concern for the application of simulation to optimisation problems. Ordinal optimisation has emerged as an effective approach to significantly improve efficiency of simulation and optimisation. Ordinal optimisation for simulation problems achieves an exponential convergence rate. There are already several success stories of ordinal optimisation. This paper introduces the idea of ordinal optimisation, and reports some recent advances in this research. It also gives details of an extension of ordinal optimisation to a class of resource application problems.     

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.     

Dynamic material handling for a class of flexible manufacturing systems

A real-time hierarchical routing control scheme for a large class of material handling systems is presented. The higher level (coordinator) performs resource allocation tasks and supplies parameter values to the lower (local control) level. The lower level operates in an autonomous (without continuous supervision) and distributed fashion. If state information is made available to the coordinator, the routing strategy can furthermore be adaptively adjusted.     

Optimal control of polling models for transportation applications

We formulate and analyze a dynamic scheduling problem for a class of transportation systems in a Markov Decision Process (MDP) framework. A transportation system is represented by a polling model consisting of a number of stations and a server with switch-over costs and constraints on its movement (the model we have analyzed is intended to emulate key features of an elevator system). Customers request service in order to be transported by the server from various arrival stations to a common destination station. The objective is to minimize a cost criterion that incorporates waiting costs at the arrival stations. Two versions of the basic problem are considered and structural properties of the optimal policy in each case are derived. It is shown that optimal scheduling policies are characterized by switching functions dependent on state information consisting of queue lengths formed at the arrival stations.     

Scheduling policies using marked/phantom slot algorithms

We address the problem of schedulingM customer classes in a single-server system, with customers arriving in one ofN arrival streams, as it arises in scheduling transmissions in packet radio networks. In general,NM and a customer from some stream may join one of several classes. We consider a slotted time model where at each scheduling epoch the server (channel) is assigned to a particular class (transmission set) and can serve multiple customers (packets) simultaneously, one from every arrival stream (network node) that can belong to this class. The assignment is based on arandom polling policy: the current time slot is allocated to theith class with probability _i. Our objective is to determine the optimal probabilities by adjusting them on line so as to optimize some overall performance measure. We present an approach based on perturbation analysis techniques, where all customer arrival processes can be arbitrary, and no information about them is required. The basis of this approach is the development of two sensitivity estimators leading to amarked slot and aphantom slot algorithm. The algorithms determine the effect of removing/ adding service slots to an existing schedule on the mean customer waiting times by directly observing the system. The optimal slot assignment probabilities are then used to design adeterministic scheduling policy based on the Golden Ratio policy. Finally, several numerical results based on a simple optimization algorithm are included.This work was supported by the Naval Research Laboratory under contracts N000014-91-J-2025 and N000014-92-J-2017, by the National Science Foundation under grant EID-9212122, and by the Rome Laboratory under contract F30602-94-C-0109.     

Stochastic comparison algorithm for continuous optimization with estimation

The problem of stochastic optimization for arbitrary objective functions presents a dual challenge. First, one needs to repeatedly estimate the objective function; when no closed-form expression is available, this is only possible through simulation. Second, one has to face the possibility of determining local, rather than global, optima. In this paper, we show how the stochastic comparison approach recently proposed in Ref. 1 for discrete optimization can be used in continuous optimization. We prove that the continuous stochastic comparison algorithm converges to an -neighborhood of the global optimum for any >0. Several applications of this approach to problems with different features are provided and compared to simulated annealing and gradient descent algorithms.This work was supported in part by the National Science Foundation under Grants EID-92-12122 and ECS-88-01912, and by a Grant from United Technologies/Otis Elevator Company.