×

Heavy traffic analysis of controlled queueing and communicating networks. (English) Zbl 0988.90004

Applications of Mathematics. 47. New York, NY: Springer. xix, 513 p. DM 160.00; sFr 138.00; £55.50; $ 74.95 (2001).
This volume is a treatise on the topic described by the title. It arose from a graduate course given by the author in the Applied Mathematics Department at Brown University.
Chapter one presents simplified models and concrete examples. One deals first with the one-dimensional queue and the modelling is extended to a network of queues. Here the state is the queue size and one considers a sequence of processes parametrized by the differences between mean input and output rates. When these numbers are large one gets the heavy traffic approximation. On the other hand, if the queue is empty a reflection process has to model the behaviour. So the fundamental object one deals with is the reflected diffusion. The other sections examine situations in a control context such that the heavy traffic approximation leads to simplifications. Polling, statistical multiplexing and assignment constitute the examples from communications.
Chapters two to four develop mathematical tools which are used afterwards. In chapter two one defines martingales and Wiener processes, one considers weak convergence to such processes. Chapter three provides several definitions and discussions on possibly controlled stochastic differential equations; singular and impulsive controls are also mentioned and a section is devoted to relaxed controls. Then the focus is on reflected Brownian motion and on generalizations. Chapter four is more technical and deals with convergence of the transition function of a Markov process to a stationary measure and methods from optimal control under an ergodic cost. A maximum principle is established.
Chapters five to eight treat the heavy traffic analysis in various situations. Many convergence results are established. Chapter five examines first the simplified situation of a single server and then in chapter six and seven one extends the results to the network case. Chapter six develops also situations where there is blocking by a full buffer so that the reflection procedure is more complicated and there is a pendant to a section of the previous chapter about modelling the system with the workload when there are several types of jobs being processed; this is performed via scaling. Chapter seven deals with more intricate situations where the reflection procedure has to be modified. This happens for instance in scheduling and inventory management in manufacturing where inventory shortages affect the processor idle time. Failures of processors may happen or a single processor may handle the same job in a distributed way (so that a correlation analysis leads to a more precise description). Chapter eight handles the case of state dependence. The actions depend on the level of the queues. This leads to a technical complication in the sense that the limiting processes may not be Wiener processes anymore. Some previous configurations are reexamined in this context (workload formulations, multiplexer system).
The remaining chapters are devoted to control aspects. For an optimal control problem, the goal is to show that the control obtained from the converging processes tend to the one obtained from the limiting process. In chapter nine, the discounted cost and ergodic cost problem are studied when the controls are bounded. The multiplexer problem provides an illustration. Chapter ten is a pendant to the previous one. Now one examines the case of singular controls. A first section describes a basic model allowing state dependence; section two studies what happens when one can control during vacations; section three examines controlled admission for the ISDN system; section four takes a closer look at rerouting under various constraints. Chapter eleven is on polling and its control. Here, the workload analysis is used. Chapter twelve addresses some fundamental aspects of optimal assignment and scheduling for multiclass problems. A new workload adapted to the problem at hand is used.
Throughout the book the first come first serve law is treated. Issues of stability are not considered. There are 257 references, a symbol index and an index.
This book will be a standard reference in heavy traffic analysis for controlled queues and networks.

MSC:

90B20 Traffic problems in operations research
93-02 Research exposition (monographs, survey articles) pertaining to systems and control theory
90B22 Queues and service in operations research
90B36 Stochastic scheduling theory in operations research
PDFBibTeX XMLCite