Agent-Based Routing in Queueing Systems

Waiting time in any network is often a costly and hence a bad experience. Therefore, to avoid jamming regions becomes essential in the optimization of traffic flows. In this regard, the conception and the control of complex networks supporting flows of units are key issues in various strategic engineering and service areas ranging from manufacturing systems, supply chains, retail stores, transportation and communication networks to only quote a few. Flow dynamics depend jointly on the routing rules defining the ways the units are dispatched at the network vertexes and on the behaviour of the servers which process these items. Due to stochastic customer demands, to fluctuations in the raw material of supply chains, to failures arising in production devices, to uncertainties in operator availability and to ubiquitous financial volatility steadily affecting optimization objectives, the flow dynamics are always affected by random fluctuations. The need to model, to study and to quantify the characteristics of such complex stochastic dynamics has strongly stimulated the development of the so-called queueing network (QN) theory. Under fairly general hypothesis (including the possibility to describe the underlying dynamics by general Markov processes), powerful methods are available to calculate the time-invariant probability densities ultimately describing the system state and therefore to obtain useful quantitative information on the corresponding stationary regimes. However, the Markovian character imposed to the dynamics obviously limits not only the behaviour of the servers but also lays down strong restrictions on the allowable routing rules followed by the circulating items. While the classical QN theory assumes that the circulating items composing the flows are mainly passive entities, it is however mandatory in numerous applications that each circulating item possesses its own identity as well as the ability to take individual decisions. Indeed, the inherent complexity characterizing nowadays production and/or service networks strongly favours decentralized and self-organizing mechanisms to regulate the circulating flows of humans, matter and/or information. This clearly shows the importance to study the flow dynamics of QNs visited by autonomous travelling agents which select their routing according to individual historical data collected during their past progression in the network. When such kind of history-based (HB) routing mechanisms is taken into account, the resulting flow dynamics are intrinsically non-Markovian and hence one of the fundamental assumption of classical QN theory is explicitly violated. In particular, the existence of stationary regimes can not be anymore guaranteed. As it will be unveiled in this thesis, the joint action of HB features and of feedback loop topologies in the QNs opens wide the door for the emergence of entirely new dynamical features. The decentralized autonomous dispatching rules considered in the prese