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 present work require the capability for each circulating entity to monitor, to memorize and to process data. As a consequence, we actually consider agents that autonomously adapt to environmental changes and that interact to produce intelligent global behaviours. As it is typical for self-organized systems, the numerous stigmergic interactions between the agents and their environment open possibilities for the emergence of various collective structures. In this context, we show in the present thesis how QNs in which agents are allowed to modify autonomously their routing strategies according to measures of (i) their personal waiting times and/or (ii) real-time observations of the queue contents might give rise to the creation of dissipative collective spatio-temporal patterns. By restricting our analysis to simple network topologies and despite the intrinsically non-Markovian character of the dynamics, we are able to explicitly provide analytical results characterizing the macroscopic structures that might appear in such stylized multi-agent QNs. Since the different emerging collective patterns that will be described in this work are solely induced by the agents' local actions and interactions, our particular QNs reveal themselves to be specific instances of complex adaptive systems (CAS). For the purpose of modelling recurrent services, we first consider the dynamics of a single server feedback queueing system where the agents' autonomous decision to take the feedback loop depends on their individual experimented waiting time. This is an idealization of the dynamics induced by a collection of customers who remain loyal to a server provided their service time stays below a critical threshold. The emerging self-organized behaviour takes the form of a cyclo-stationary regime which exhibits a periodical purging of the queue content. This ensures a bounded queue length as well as a maximum server utilization. Further, we increase the complexity of the network and consider a topology with two parallel feedback queues in which the agents, besides their ability to monitor waiting times, also possess a vision capability (hence, the agents "intelligence" is enhanced). Concerning the agents' initial choice between the two service providers, we introduce several different routing policies. These autonomous rules, which are wholly based on specific agent capabilities, differ in their level of complexity and with respect to the available amount of information about the current system state. In this context, we are able to analytically characterize nonlinear collective behaviours such as synchronization of oscillations and noise-induced stabilization. Next, we consider the market partition dynamics between two recurrent service providers in a closed topology, where the customers' satisfaction depends as before in a nonlinear fashion on the elapsed waiting time to receive service. We describe the periodic cannibalization effects that might emerge in this system. Further, we introduce spatial considerations within the dynamics of a system composed of two servers competing for a stationary incoming flow of customers. More particularly, we study explicitly the market sharing dynamics between these two service providers when customers are not only sensitive to costs related to waiting time but also to transportation costs. In this context, we fully characterize the phase transition that occurs between regimes where waiting time considerations are predominant and regimes where transportation aspects dominate. While the multi-agent type of dynamics considered in this work is in essence inspired by human behaviour, the present modelling framework is by far not only restricted to social systems. Indeed, to attach RFID or "smart tags" on any type of circulating units (raw materials, finished goods, carrying pallets,...) allows for the implementation of such type of decentralized dynamics in logistics, supply or manufacturing networks dealing with highly customized products. To illustrate this assertion, we propose a new dynamic fully decentralized load sharing policy (LSP) which optimally dispatches the incoming workload according to the current availability of a set of operators. The underlying decentralized decisions rely on a "smart tasks" paradigm in which each incoming task is endowed with specific autonomous routing decision mechanisms. By optimal LSP, we mean here that our "smart tasks" based algorithm permanently requires the engagement of a minimum number of operators while still respecting due dates. The numerous stigmergic interactions between these autonomous tasks solely cause the optimal LSP to emerge.