The optimal routing problem in open, finite queueing networks

Queueing networks have been used as modeling tools for a variety of applications including manufacturing, telecommunications, and general service systems. Open, finite queueing networks take into account the fact that most real life systems have limited storage space. Analysis of open, finite queueing networks is extremely difficult and very few exact results are reported in the literature. The main purposes of this dissertation are: (1) To develop analytically tractable and computationally efficient bounds on the throughput of finite queueing networks. (2) To use the bounds in developing an approximation to the throughput function from such networks. (3) To study the routing optimization problem with the bounds and the approximations.;The general optimization problems that exist in queueing networks are discussed and the optimal routing problem is studied. In particular, this dissertation deals with the static routing problem, wherein customers arriving at split junctions in series-parallel queueing networks are assigned routing probabilities to be routed along different arcs and nodes so as to maximize total throughput. An approximation of throughput in split topology networks is developed and this is used to specify sub-optimal ranges of routing probabilities. This concept is then extended to larger series-parallel networks without blocking across split and merge junctions. A linear time algorithm is then developed to route customers in these series-parallel networks which is shown to be quite efficient and robust.;In the case of series-parallel networks with blocking across split junctions another approximation is developed for the throughput function to account for the interdependencies between different service streams. A non-linear programming algorithm is developed to solve the optimal routing problem based on this approximation. Several experimental situations are studied and the results of the algorithm are verified. Finally, some avenues for future research, including multiple classes of customers and their optimal routing in queueing networks, are explored along the lines developed in the dissertation.