Ce document présente plusieurs méthodes de renormalisation utilisées dans l'étude des réseaux stochastiques. En premier lieu il s'agit d'analyser les limites de processus markoviens de sauts renormalisés en temps et en espace suivant une échelle d'Euler (type loi fonctionnelle des grands nombres). Plusieurs aspects sont détaillés: la question des limites non déterministe et ses conséquences, ainsi que le cas de la dimension infinie intervenant pour les processus de Markov à valeurs dans<br />les chaînes de caractères. L'étude des réseaux avec un grand nombre de noeuds (limite thermodynamique) ou avec des liens de capacité très grandes (Régime limite de Kelly) est discuté ainsi que les perspectives de ce type d'étude.<br />L'étude mathématique de plusieurs algorithmes distribués gérant des réseaux stochastiques est présentée. L'accent est mis sur les méthodes probabilistes utilisées dans un contexte qui n'est pas nécessairement probabiliste, elles permettent notamment d'étendre et de simplifier une partie des résultats connus dans ce domaine.

With the increasing effect of disasters and long term issues on human well-being and economy over the recent years, effective management of humanitarian supply chains has become more important. This thesis work focuses on three problems in humanitarian supply chains where uncertainty is inherent, namely (i) post-disaster debris clearance with uncertain debris amounts, (ii) allocation of a health/humanitarian commodity in a developing country setting with multiple demand types, and (iii) distribution of specialized nutritious foods by a large scale humanitarian organization. In each of the three parts, the problem is formally defined, and a novel optimal solution approach incorporating the inherent uncertainty in the environment and updates is proposed. In cases where optimal models cannot be solved within reasonable time, novel heuristics are developed. Through structural analysis and computational experiments based on real data, the proposed approaches are compared to those that ignore the uncertainty in the environment and/or updates of information as new data becomes available. Using computational experiments, the proposed approaches are compared to those that are applied in practice, and the aspects of the system where performance improvements are more significant are analyzed.

Stochastic fluctuations can have profound impacts on engineered systems. Nonetheless, we can achieve significant benefits such as cost reduction based upon expanding our fundamental knowledge of stochastic systems. The primary goal of this thesis is to contribute to our understanding by developing and analyzing stochastic models for specific types of engineered systems. The knowledge gained can help management to optimize decision making under uncertainty. This thesis has three parts. In Part I, we study many-server queues that model large-scale service systems such as call centers. We focus on the positive recurrence of piecewise Ornstein-Uhlenbeck (OU) processes and the validity of using these processes to predict the steady-state performance of the corresponding many-server queues. In Part II, we investigate diffusion processes constrained to the positive orthant under infinitesimal changes in the drift. This sensitivity analysis on the drift helps us understand how changes in service capacities at individual stations in a stochastic network would affect the steady-state queue-length distributions. In Part III, we study the trading mechanism known as limit order book. We are motivated by a desire to better understand the interplay among order flow rates, liquidity fluctuation, and optimal executions. The goal is to characterize the temporal evolution of order book shape on the “macroscopic” time scale.

Αντικείμενο της παρούσας μεταπτυχιακής εργασίας είναι η διερεύνηση βελτιωμένων τεχνικών εφαρμογής του μοντέλου κυκλοφοριακού σχεδιασμού SATURN. Για το σκοπό αυτό επιλέγονται να μελετηθούν δύο διαφορετικές περιοχές στην υφιστάμενη και σε μία νέα κατάσταση. Συγκεκριμένα, η πρώτη περιοχή μελετάται ως ρυθμιστικό δίκτυο και οι αλλαγές στη νέα της κατάσταση αφορούν αλλαγή λειτουργίας κάποιων υφιστάμενων οδών όπως είναι αλλαγή κατεύθυνσης ροής οχημάτων και οι μονοδρομήσεις, και η δεύτερη ως προσομοίωσης και οι αλλαγές στη νέα της κατάστασης αφορούν την πεζοδρόμηση μίας οδού. Τα δίκτυα αυτά μελετώνται και ως ντετερμινιστικά και ως στοχαστικά με τη χρήση του αλγόριθμου Frank & Wolf και του Burrell αντίστοιχα, αλγόριθμους που διατίθενται μέσω του SATURN. Από την ανάλυση των αποτελεσμάτων παρατηρείται ότι οι αλλαγές που εφαρμόστηκαν στα δύο δίκτυα της παρούσας εργασίας φορτίζουν τα δίκτυο περισσότερο με αποτέλεσμα να επιβαρύνουν την κυκλοφοριακή κατάσταση. Επιπλέον διαπιστώθηκε ότι οσο πιο απλό είναι ένα δίκτυο τόσο πιο εύκολη είναι η επιλογή της συντομότερης διαδρομής από τους χρήστες, ενώ όσο πληθαίνουν οι εναλλακτικές διαδρομές παρατηρούνται διαφορές στην κατανομή των φόρτων σε αυτές και στην επίλυση του προβλήματος καταμερισμού, καθώς επίσης και ότι σε περιπτώσεις όπου οι εναλλακτικές διαδρομές καθίστανται ανταγωνιστικές παρατηρείται διασπορά των μετακινούμενων σε αυτές. Επιπροσθέτως ενδείκνυται το στοχαστικό μοντέλο ως καταλληλότερο και στις δύο εφαρμογές. Τέλος τo SATURN αποτελεί ένα χρήσιμο προγράμματα ανάλυσης δικτύων, προσομοίωσης και κατανομής της κυκλοφορίας. / The subject of this thesis is the investigation of improved application techniques of model transport planning SATURN. For this purpose, two different networks were chosen to study in two situations, one in an existing and one in a new situation . Specifically , the first area is being studied as a buffer network. The changes in the new situation are changes as the flow direction of vehicles and one-way. The second area is being studies as simulation network. In the new situation one street become way for pedestrian. These networks are studied as deterministic and stochastic using the algorithm Frank & Wolf and Burrell respectively, these algorithms are available through the SATURN. After the analysis of the results, it is observed that changes implemented in both networks affect in a worse way the traffic situation. In addition it was found that the simpler is a network the easier is to select the shortest route from the users. Opposed to this, increasing the alternative routes observed differences in the distribution of flows in them and in the assignment problem’s solution. Moreover in cases where alternative routes become competitive, dispersion of traveling is observed in them. Additionally stochastic model is showed to be appropriate in both applications . Finally to SATURN is a useful network analysis programs of simulation and assignment of traffic to urban road networks.

Este trabalho apresenta a caracterização de limites no sentido fraco dos sistemas de filas em redes que podem enviar e receber sinais. Estes sinais podem ser usados, entre outras coisas, para que as filas se auto controlem. Mostra-se que, sob certas condições, o sistema pode ser aproximado por uma equação diferencial estocástica refletida. Os benefícios de tais aproximações são que elas descrevem a evolução transiente destes sistemas e possibilitam a introdução de controles. Em seguida, uma abordagem mais abrangente é apresentada através de redes de Petri estocásticas. Uma nova classe destas redes é introduzida como uma forma unificadora para tratar sistemas que podem ser descritos por quantidades discretas que sofrem trocas estocásticas ao longo do tempo. A classe é geral o suficiente para incluir as redes de Petri estocásticas, as redes de Jackson, e as redes de Gelenbe com sinais do tipo "cliente negativo" e do tipo "triggers". O objetivo principal é obter, de maneira unificada, uma aproximação por difusão que possa ser facilmente aplicável em um número grande de problemas práticos.

Made available in DSpace on 2015-03-04T18:51:13Z (GMT). No. of bitstreams: 1 TESE_SAUL_LEITE_2009_FINAL.pdf: 1365437 bytes, checksum: 554d576e8e68cd79166b918a25e97d51 (MD5) Previous issue date: 2009-07-31 / Conselho Nacional de Desenvolvimento Cientifico e Tecnologico / This work is concerned with the characterization of weak-sense limits of networks of queues which can send and receive signals. These signals can be used, among other things, to auto control the queues. It is shown that, under certain conditions, the system can be approximated by a reflected stochastic differential equation. The benefits of such an approximation are that it describes the transient evolution of these systems and allows for the introduction of controls. Following that, a more general approach is presented using stochastic Petri nets. A new class of these nets is introduced to serve as an unifying approach to treat systems that can be described by discrete quantities that suffer stochastic changes in time. The class is general enough to include the stochastic Petri nets, the Jackson network, and Gelenbe's network with signals of the type "negative customer" and "triggers." The main goal in this approach is to obtain, in a unifying way, an approximation that can be readily applied in several practical problems. / Este trabalho apresenta a caracterização de limites no sentido fraco dos sistemas de filas em redes que podem enviar e receber sinais. Estes sinais podem ser usados, entre outras coisas, para que as filas se auto controlem. Mostra-se que, sob certas condições, o sistema pode ser aproximado por uma equação diferencial estocástica refletida. Os benefícios de tais aproximações são que elas descrevem a evolução transiente destes sistemas e possibilitam a introdução de controles. Em seguida, uma abordagem mais abrangente é apresentada através de redes de Petri estocásticas. Uma nova classe destas redes é introduzida como uma forma unificadora para tratar sistemas que podem ser descritos por quantidades discretas que sofrem trocas estocásticas ao longo do tempo. A classe é geral o suficiente para incluir as redes de Petri estocásticas, as redes de Jackson, e as redes de Gelenbe com sinais do tipo "cliente negativo" e do tipo "triggers". O objetivo principal é obter, de maneira unificada, uma aproximação por difusão que possa ser facilmente aplicável em um número grande de problemas práticos.