Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling

The authors present an introductory review of recent work on the control of open queueing networks. They assume that customers of different types arrive at a network and pass through the system via one of several possible routes; the set of routes available to a customer depends on its type. A route through the network is an ordered set of service stations: a customer queues for service at each station on its route and then leaves the system. The two methods of control the authors consider are the routing of customers through the network, and the sequencing of service at the stations, and the present aim is to minimize the number of customers in the system. They concentrate especially on the insights which can be obtained from heavy traffic analysis, and in particular from Harrison’s Brownian network models. The main conclusion is that in many respects dynamic routing simplifies the behaviour of networks, and that under good control policies it may well be possible to model the aggregate behaviour of a network quite straightforwardly.