Analysis and Adaptive Control of a Discrete-Time Single-Server Network with Random Routing
Abstract
This paper considers a discret time system composed of k infinite capacity queues that compete for the use of a single server. Customers arrive in i.i.d batches and are served according to a server allocation policy. Upon completing service, customers either leave the system or are routed instantaneously to another queue according to some random mechnism. As an alternative to simply randomized strategies, a policy based on a Stochastic Approximation aigonthm is proposed to drive a long-run average cost to a given value. The motivation can be traced to implementation issues associated with constrained optimal strategies. A version of the ODE method as given by Metivier and Priouret is developed for proving a.s. convergence of this algorithm. This is done by exploiting the recurrence structure of the system under non-idling policies. A probabilistic representation the solutions to an associated Poisson equation is found most useful for proving their requisite Lipschitz continuity. The conditions which guarantee convergence are given directly in terms of the model data. The approach is of independent interest, as it is not limited to this particular queueing application and suggests a way of attacking other similar problems. Keywords: Stochastic Approximations, stochastic adaptive control, queueing network.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1989
- Accession Number
- ADA454733
Entities
People
- Adam Shwartz
- Armand M. Makowski
Organizations
- University of Maryland