Academic literature on the topic 'Théorie des files d’attentes'

International audience For a random permutation sampled from the stationary distribution of the TASEP on a ring, we show that, conditioned on the event that the first entries are strictly larger than the last entries, the $\textit{order}$ of the first entries is independent of the $\textit{order}$ of the last entries. The proof uses multi-line queues as defined by Ferrari and Martin, and the theorem has an enumerative combinatorial interpretation in that setting. Finally, we present a conjecture for the case where the small and large entries are not separated. Pour une permutation randomisée tirée de la mesure stationnaire du TASEP, nous démontrons, conditionnée à l’évènement que les premières lettres sont plus grandes que les dernières lettres, que l’ordre des petites lettres est indépendant de l’ordre des grandes lettres. La preuve utilise les files d’attente multilignes de Ferrari et Martin, et le théorème a une interprétation combinatoire énumérative dans ce contexte. Finalement, nous présentons une conjecture pour le cas où les petits et les grandes lettres ne sont pas séparées.

Cette étude vise à mettre en évidence le rôle des méthodes quantitatives de la recherche opérationnelle dans la prise de décision au niveau des institutions économiques, le succès de l'une d'elles dépendent de sa capacité à utiliser les ressources disponibles d’une manière optimale, cela nécessite également une grande efficace pour trouver des solutions appropriées aux différents problèmes qui concernent la façon de gérer ces ressources, d’où l'importance accrue de l'utilisation de la RO pour résoudre ces problèmes, surtout après avoir prouvé son efficacité au niveau des différents institutions et administrations. Parmi les problèmes les plus courants et au niveau des institutions de prestation de service, tel que les banques commerciales, par exemple , c’est le problème de la gestion du temps pour offrir un service à leurs clients, à travers cet article, nous avons essayé de traiter ce genre de problème, grâce à l'utilisation de la théorie des files d'attente dans les banques commerciales en Algérie (la Banque Extérieure d’Algérie – agence de Msila074 - modèle), cela est dû au fait qu’elle est considérée comme un moyen très approprié pour déterminer le temps attendu par les clients de la banque dans les files d'attente, et donc trouver des solutions adéquates par les décideurs de manière à améliorer la qualité de leurs services.

The paper describes methods of linking by machine, the machine-readable data base of the HPB project, the cataloging records of the National Union Catalog: pre-1956 Imprints3 and selected bibliographical tools. One result, in the form of a machine-readable register of Canadian locations, can be selectively expanded into a substitute in machine-readable form for the present Canadian Union Catalog (CANUC). The theory and practice underlying the creation of the HPB main file and its highly specialized collocation files are described and possibilities for integrating the project into evolving systems for universal bibliographical control of retrospective materials suggested. On explique dans ces pages des méthodes pour lier par ordinateur les donnés lisibles dans la machine du projet HPB, les dossiers du catalogue collectif National Union Catalog: pre-1956 Imprints et les renseignements bibliographiques pris dans des bibliographies choisies. Un des resultats, en forme d’un registre de sigles des bibliothèques possédantes, est capable de devenir peu à peu un index établi par ordinateur pour développer un Catalogue collectif automatisé de dossiers retrospectifs qui remplacera les tiroirs de fiches de la Bibliotheque nationale. On explique aussi la théorie et la pratique du projet HPB, c'est â dire le fichier principal (main file) et les fichiers d’arrangement spécialisés (collocation files), avec ses possibilités de liaison avec les systèmes de contrôle bibliographique universelle qui sont en train de se développer actuellement.

La génération aléatoire d'objets combinatoires est un problème qui se pose dans de nombreux domaines de recherche (réseaux de communications, physique statistique, informatique théorique, combinatoire, etc.). Couramment, la distribution des échantillons est définie comme la distribution stationnaire d'une chaîne de Markov ergodique. En 1996, Propp et Wilson ont proposé un algorithme permettant l'échantillonnage sans biais de la distribution stationnaire. Ce dernier appelé aussi algorithme de simulation parfaite, requiert la simulation en parallèle de tous les états possibles de la chaîne. Plusieurs stratégies ont été mises en œuvre afin de ne pas avoir à simuler toutes les trajectoires. Elles sont intrinsèquement liées à la structure de la chaîne considérée et reposent essentiellement sur la propriété de monotonie, la construction de processus bornants qui exploitent la structure de treillis de l'espace d'états ou le caractère local des transitions. Dans le domaine des réseaux de communications, on s'intéresse aux performances des réseaux de files d'attente. Ces derniers se distinguent en deux groupes : ceux dont la distribution stationnaire possède une forme produit qui est facile à évaluer par le calcul et les autres. Pour ce dernier groupe, on utilise la génération aléatoire pour l'évaluation de performances. De par la structure des chaînes qui leurs sont associées, les réseaux ouverts de files d'attente se prêtent bien à la simulation via l'algorithme de simulation parfaite mais pas les réseaux fermés. La difficulté réside dans la taille de l'espace des états qui est exponentielle en le nombre de files à laquelle s'ajoute une contrainte globale à savoir le nombre constant de clients. La contribution principale de cette thèse est une nouvelle structure de données appelée diagramme. Cette structure est inspirée de la programmation dynamique et introduit une nouvelle technique de construction de processus bornant. La première partie du manuscrit est consacrée à la mise en œuvre de l'algorithme de Propp et Wilson pour des réseaux fermés n'étant pas nécessairement à forme produit. La représentation des états par un diagramme et l'opération de transition pour le processus bornant a dès lors une complexité polynomiale en le nombre de files et de clients. Cette technique est ensuite étendue aux réseaux fermés multiclasses ainsi qu'aux réseaux possédant des synchronisations. Une spécification des ensembles d'objets pouvant être représentés par un diagramme ainsi que des algorithmes agissant sur cette structure de données sont également proposés dans cette thèse. La méthode de Botzmann est une autre technique de simulation sans biais. Basée sur la combinatoire analytique, elle permet l'échantillonnage uniforme d'objets appartenant à une même classe combinatoire. Elle est employée dans la seconde partie de cette thèse afin d'échantillonner la distribution stationnaire de réseaux fermés à forme produit et pour la génération des multi-ensembles de taille fixe. Dans ce cadre, les diagrammes sont une nouvelle fois mis à profit. Enfin, la troisième partie présente les logiciels découlant des travaux présentés tout au long de ce travail, et qui implémentent les diagrammes et mettent en œuvre la simulation parfaite de réseaux fermés de files d'attente
Random generation of combinatorial objects is an important problem in many fields of research (communications networks, theoretical computing, combinatorics, statistical physics, ...). This often requires sampling the stationary distribution of an ergodic Markov chain. In 1996, Propp and Wilson introduced an algorithm to produce unbiased samples of the stationary distribution, also called a perfect sampling algorithm. It requires parallel simulation of all possible states of the chain. To avoid simulating all the trajectories, several strategies have been implemented. But they are related to the structure of the chain and require a monotonicity property, or a construction of a bounding chain that exploits the lattice structure of the state space or the local character of the transitions.In the field of communications networks, attention is paid to the performance of queueing networks, that can be distinguished into two groups: the networks that have a product form stationary distribution which is easy to compute. Random generation can be used for the others. Perfect sampling algorithms can be used for open queueing networks, thanks to the lattice structure of their state space. Unfortunately, that is not the case for closed queueing networks, due to the size of the state space which is exponential in the number of queues and a global constraint (a constant number of customers). The main contribution of this thesis is a new data structure called a diagram. It is inspired by dynamic programming and allows a new technique of construction of bounding processes. The first part of the manuscript is devoted to the implementation of the Propp and Wilson algorithm for closed queueing networks. The representation of a set of states by a diagram and the transition operation for the bounding process has a polynomial complexity in the number of queues and customers. This technique is extended to closed multi-class networks and to networks with synchronizations. Specification of sets of objects that can be represented by a diagram and generic algorithms that use this data structure are proposed in this manuscript. The Boltzmann method is another unbiased sampling technique. It is based on analytical combinatorics and produces uniform samples from objects that belong to the same combinatorial class. It is used in the second part of this thesis in order to sample the stationary distribution of closed networks with product form and for the generation of multisets of fixed cardinality. Diagrams are used again in this context. Finally, the third part presents the software produced during this thesis, implementing diagrams and perfect simulation of closed queueing networks

Dans cette thèse nous nous intéressons à des problèmes pratiques relevant des domaines des files d’attente et du risque qui débouchent sur des modélisations markoviennes dont la résolution exacte et même asymptotique est considérablement difficile. Nous proposons des solutions analytiques qui font usage de deux approches : le numérique (avec deux contributions à la théorie des files d’attente) et le symbolique-numérique (avec une contribution à la théorie des files d’attente et une contribution à la théorie de la ruine)
This thesis deals with practical problems in the areas of queuing and risk that lead to Markov models whose exact or even asymptotic resolution is considerably difficult. We provide analytical solutions which use two approaches : the numeric (with two contributions to queueing theory) and the symbolic-numeric (with a contribution to queueing theory and a contribution to ruin theory)

Les futurs réseaux mobiles promettent des opportunités sans précédent pour l'innovation et des cas d'utilisation disruptifs. L'engagement des réseaux 5G et au-delà à fournir des applications critiques nécessite un réseau polyvalent, évolutif, efficace et rentable, capable d'adapter son allocation de ressources pour répondre aux exigences de services hétérogènes. Pour relever ces défis, le découpage du réseau s'est imposé comme l'un des concepts fondamentaux proposés pour améliorer l'efficacité des réseaux mobiles 5G et leur conférer la plasticité requise. L'idée est de fournir des ressources à différentes industries verticales en construisant plusieurs réseaux logiques de bout en bout sur une infrastructure virtualisée partagée. Chaque "tranche de réseau" ainsi définie est personnalisée pour fournir un service spécifique en adaptant son architecture et ses technologies d'accès radio.Précisément, des applications telles que l'automatisation industrielle ou les communications entre véhicules imposent aux réseaux cellulaires des exigences strictes en matière de latence et de fiabilité. Étant donné que le réseau mobile actuel ne peut pas répondre à ces exigences, les communications ultra-fiables et à faible temps de latence constituent un sujet de recherche essentiel qui a suscité un élan considérable de la part du monde universitaire et des alliances industrielles. Pour répondre à ces exigences, l'utilisation de la multi-connectivité, c'est-à-dire l'exploitation simultanée de plusieurs liaisons radio comme voies de communication, est une approche prometteuse.L'objectif du présent manuscrit est d'étudier des techniques d'allocation de resources exploitant la couverture redondante des utilisateurs, garantie dans de nombreux scénarios 5G. Nous examinons d'abord l'évolution des réseaux mobiles et discutons des diverses considérations relatives à l'architecture de découpage du réseau et de son impact sur la conception des méthodes d'allocation des ressources. Nous utilisons ensuite les outils de la théorie des files d'attente pour modéliser un système dans lequel un ensemble d'utilisateurs URLLC sont connectés simultanément à deux stations de base ayant la même bande passante ; nous appelons ce scénario le cas homogène. Nous introduisons des politiques d'allocation appropriées et évaluons leurs performances respectives en évaluant leur fiabilité. Ensuite, nous étendons les résultats du cas homogène à un cadre plus général où les interfaces physiques gèrent des bandes passantes différentes, que nous appelons le cas hétérogène. Enfin, nous fusionnons les éléments ci-dessus pour valider le choix des schémas d'allocation des ressources en tenant compte de l'architecture déployée
Future mobile networks envision unprecedented innovation opportunities and disruptive use cases. As a matter of fact, the 5G and beyond networks' pledge to deliver mission-critical applications mandates a versatile, scalable, efficient, and cost-effective network capable of accommodating its resource allocation to meet the services' heterogeneous requirements. To face these challenges, network slicing has emerged as one of the fundamental concepts proposed to raise the 5G mobile networks' efficiency and provide the required plasticity. The idea is to provide resources for different vertical industries by building multiple end-to-end logical networks over a shared virtualized infrastructure. Each network slice is customized to deliver a specific service and adapts its architecture and radio access technologies.Precisely, applications such as industrial automation or vehicular communications pose stringent latency and reliability requirements on cellular networks. Given that the current mobile network cannot meet these requirements, ultra-reliable low-latency communications (URLLC) embodies a vital research topic that has gathered substantial momentum from academia and industrial alliances. To reach URLLC requirements, employing multi-connectivity (MC), i.e., exploiting multiple radio links as communication paths at once, is a promising approach.Therefore, the objective of the present manuscript is to investigate dynamic scheduling techniques, exploiting redundant coverage of users, guaranteed in numerous 5G radio access network scenarios. We first review the evolution of mobile networks and discuss various considerations for network slicing architecture and its impact on resource allocation design. Then, we use tools from queuing theory to model a system in which a set of URLLC users are connected simultaneously to two base stations having the same bandwidth; we refer to this scenario as the homogenous case. We introduce suitable scheduling policies and evaluate their respective performances by assessing their reliability. Next, we extend the homogenous case's results to a more general setting where the physical interfaces manage different bandwidths, referred to as the heterogeneous case. Finally, we merge the above elements to validate the choice of resource allocation schemes considering the deployed architecture

Face à des systèmes de file d’attente, les clients prennent des décisions stratégiques afin de rejoindre ou non ces systèmes d’une manière optimale. Un nouvel aspect intéressant est apparu et étudié ces dernières années : l’impact de l’information de la longueur de la file sur les décisions stratégiques des clients, sur l’équilibre et les performances du système. Les clients ne sont pas tous semblables face aux informations fournies par le système et cette hétérogénéité impacte également les équilibres et performances. Dans certains cas, le fournisseur de service peut avoir un intérêt à divulguer l’information sur l’état du système à certains clientset même de la cacher à d’autres afin d’optimiser certains objectifs. Dans d’autres cas, l’obtention de l’information est déterminée stratégiquement par les clients qui décident alors de l’inspecter ou non selon leurs contraintes et leurs souhaits. La motivation principale de cette thèse est d’étudier l’impact de l’information dans des systèmes d’attente avec usagers stratégiques et information contrôlée. Nos contributions permettent de déterminer l’équilibre et d’optimiser les performances des systèmes en fonction de l’accessibilité de l’information. Des solutions théoriques et analytiques ont été proposées pour résoudre les problèmes étudiés
Faced to queuing systems, customers can make their strategic decisions in order to join or not these systems. An interesting new aspect has emerged and studied in recent years, which is about the impact of current queue-length information on strategic decisions of customers, on the equilibrium and the performance of the system. Customers are not necessarily homogeneous in their behavior and their access to the information, which implies different equilibrium and performances solutions.In some cases, service provider may have an interest to give to customers the system state information and withholding it to others in order to optimize certain objectives. In other cases, obtaining the information is mainly the choice of customers and therefore thay have to decide to inspect or to collect the information or not, according to their constrainsts and their wishes.The main motivation for this thesis is to study the impact of the queue length information on the strategic decisions of customers and to analyze the performance of such strategic queuing systems with controlled information. Our contributions allow to determine the equilibuim and optimize the performance of the systems according to the queue length information. Theoretical and analytical solutions have been proposed to solve the studied problems

Au cours des vingt dernières années, le secteur des services est devenu le secteur le plus important en nombre d'actifs occupés dans l’économie mondiale, en particulier dans les pays développés. Par ailleurs, la concurrence et la coopération dans le secteur des services sont devenues de plus en plus populaires dans le contexte de la mondialisation économique. Comment collaborer avec un accord gagnant-gagnant apporte une source fertile de problèmes de management des opérations dans le domaine des services. Dans cette thèse, nous étudions des stratégies de collaboration dans des systèmes de services homogènes. Nous nous concentrons en particulier sur les stratégies de pooling des ressources de service.Dans les deux premières parties, nous étudions le problème de partage des coûts entre les fournisseurs de services indépendants avec des temps de service qui suivent une distribution générale et en tenant compte de l'abandon des clients. Nous modélisons à la fois chaque fournisseur de services et la coalition coopérative comme des files d'attente avec serveur unique, et spécialisons les stratégies de pooling avec les capacités de services fixes et modifiables. Dans la dernière partie, nous abordons le problème de pooling dans le cadre multiserveur pour évaluer la qualité de l'hypothèse "superserveur". Nous étudions numériquement l'impact de la variabilité de la durée de service et l'abandon des clients sur les jeux de mise en commun des ressources. Nous comparons aussi les partages des coûts entre le système de "super-serveur" et multiserveur
In past twenty years, the service sector has emerged as the primary sector in the world economy, especially in developed countries. Competition and cooperation in service industries have become more and more popular in the context of economic globalization. How to operate the collaboration with a win-win agreement brings a fertile source of operations management issues in service science. In this thesis, we study collaborations between homogeneous service systems in terms of resource pooling strategies.In the first two parts, we investigate the cost-sharing problem among independent service providers with general service times and accounting for the customer abandonment. We model both the service provider and the cooperative coalition as single server queues, and specialize the capacity pooling strategies with the fixed and optimized service capacities.Finally, we address the service pooling problem in the multi-serverpooling setting to assess the quality of the "super-server" assumption.We numerically investigate the impact of service duration variability and customer abandonment on the pooling game. We compare between cost-sharing results of the two resource pooling concepts, with or without the "super-server" assumptions

Parallèlement au prix, le délai de livraison est un facteur clé de compétitivité pour les entreprises. De plus les entreprises sont plus que jamais obligées de respecter ce délai promis. La combinaison du choix du prix et du délai promis implique de nouveaux compromis et offre de nombreuses perspectives. Un délai plus court peut entraîner une augmentation de la demande, mais augmente également le risque de livraison tardive et donc décourager les clients. A contrario un délai plus long ou un prix plus élevé entraîne généralement une baisse de la demande. Or malgré le rôle stratégique conjoint du prix et des délais et leurs impacts sur la demande, dans la littérature en gestion des opérations on suppose très généralement une demande exogène (fixée a priori) même si la conception de la chaîne impacte fortement les délais (localisation des sites, positionnement des stocks,..) et donc la demande. Nous nous sommes donc intéressés à ces choix de fixation des délais promis et du prix dans un contexte de demande endogène.La littérature traitant du choix du délai et du prix sous demande endogène a principalement considéré un contexte de fabrication à la commande (Make to Order). Un papier fondateur de Palaka et al en 1998 a présenté cette problématique avec une modélisation de l’entreprise par une file d’attente M/M/1 et nos travaux se placent dans la suite de ce travail. Notre revue de la littérature a permis d'identifier de nouvelles perspectives et nous proposons trois extensions dans cette thèse.Dans notre première contribution, en utilisant le cadre de Palaka et al, nous considérons que le coût de production est une fonction décroissante du délai. Dans tous les articles publiés dans ce contexte, le coût de production unitaire a été supposé constant. Pourtant en pratique, le coût de production unitaire dépend du délai promis, l'entreprise pouvant mieux gérer le processus de production et réduire les coûts de production en proposant des délais plus longs aux clients.Dans la deuxième contribution, nous considérons toujours le cadre de Palaka et al, mais modélisons l'entreprise comme une file d'attente M/M/1/K, pour laquelle la demande est donc rejetée s'il y a déjà K clients dans le système. Dans la littérature issue du travail de Palaka seule la file d'attente M/M/1 a été utilisée, ce qui signifie que tous les clients sont acceptés, ce qui peut entraîner de longues durées de séjour dans le système. Notre idée est basée sur le fait que rejeter certains clients, même si cela peut apparaitre dans un premier temps comme une perte de demande, pourrait aider à proposer un délai plus court pour les clients acceptés, et finalement conduire à une demande et donc un profit plus élevé.Dans la troisième contribution nous étudions un nouveau cadre pour le problème du délai et du prix en fonction de la demande endogène, en modélisant une chaîne logistique composée de deux étapes de production, modélisée par un réseau de files d’attente tandem (M/M/1-M/M/1). Dans la littérature avec ce cadre multi-entreprise, tous les articles ont considéré qu'un seul acteur avait des opérations de production, l'autre acteur ayant un délai nul. Nous avons étudié les scénarios centralisés et décentralisés.Pour chacun des nouveaux problèmes nous avons proposé des formulations maximisant le profit composé du revenu diminué des coûts de production, de stockage et pénalité de retard, et fourni des résolutions optimales, analytiques ou numériques. Ces résolutions nous ont amenés à démontrer de nouveaux résultats (retard moyen dans une M/M/1/K ; condition pour que des contraintes de service locales permettent d’assurer une contrainte de service globale dans un système en tandem). Nous avons mené des expériences numériques pour voir l’influence des différents paramètres
Along with the price, the delivery lead time has become a key factor of competitiveness for companies and an important purchase criterion for many customers. Nowadays, firms are more than ever obliged to meet their quoted lead time, which is the delivery lead time announced to the customers. The combination of pricing and lead time quotation implies new trade-offs and offers opportunities for many insights. For instance, on the one hand, a shorter quoted lead time can lead to an increase in the demand but also increases the risk of late delivery and thus may affect the firm’s reputation and deter future customers. On the other hand, a longer quoted lead time or a higher price generally yields a lower demand. Despite the strategic role of joint pricing and lead time quotation decisions and their impacts on demand, in the operations management literature an exogenous demand (a priory a known demand) is generally used in supply chain models, even if the design of the supply chain has a strong impact on lead times (i.e., sites location, inventory position, etc.) and thus affects the demand. Therefore, we are interested in the lead time quotation and pricing decisions in a context of endogenous demand (i.e., demand sensitive to price and quoted lead time).The literature dealing with pricing and lead time quotation under an endogenous demand mainly considered a make to order (MTO) context. A pioneer paper, Palaka et al. (1998), investigated this issue by modeling the company as an M/M/1 queue, and our work follows their footsteps. Our review of the literature allowed to identify new perspectives for this problem, which led to three main contributions in this thesis.In our first contribution, using Palaka et al.’s framework, we consider the unit production cost to be a decreasing function in quoted lead time. In most published papers, the unit production cost was assumed to be constant. In practice, the unit production cost generally depends on the quoted lead time. Indeed, the firm can manage better the production process and reduce the production cost by quoting longer lead time to the customers.In the second contribution, we still consider Palaka et al.’s framework but model the firm as an M/M/1/K queue, for which demand is rejected if there are already K customers in the system. In the literature on single firm setting following Palaka et al.’s research, only the M/M/1 queue was used, i.e., where all customers are accepted, which might lead to long sojourn times in the system. Our idea is based on the fact that rejecting some customers, might help to quote shorter lead time for the accepted ones, which might finally lead to a higher profitability, even if in the first glance we lose some demand.In the third contribution, we study a new framework for the lead time quotation and pricing problem under endogenous demand as we model the supply chain by two production stages in a tandem queue (M/M/1-M/M/1). In the literature with multi-firm setting, all papers considered that only one actor has production operations and the other actor has zero lead time. We investigated both the centralized and decentralized decision settings.For each problem studied, we formulated a profit-maximization model, where the profit consists of a revenue minus the production, storage and lateness penalty costs, and provides the optimum result (analytically or numerically). These resolutions led us to demonstrate new theoretical results (such as the expected lateness in an M/M/1/K, and the sufficient condition required to satisfy the global service constraint in a tandem queue by only satisfying the local service constraints). We also conducted numerical experiments and derived managerial insights

Nous étudions des modèles mathématiques issus de la théorie des files d’attente pour évaluer et optimiser les performances des mécanismes de partage de ressources entre flots dans les réseaux. Dans une première partie, nous proposons des approximations simples et explicites des principales métriques de performance des flots élastiques dans les réseaux à partage de bande passante opérant sous le mode ”équité équilibré”. Nous étudions ensuite le partage de bande passante entre flux élastiques et flux de streaming en supposant que le nombre de ces derniers est limité par un mécanisme de contrôle d’admission et proposons des approximations de performance basées sur une hypothèse de quasi stationnarité. Les résultats de simulation montrent le bon niveau de précision des approximations proposées.Dans une deuxième partie, nous étudions le compromis entre délai et énergie dans les réseaux à partage de bande passante dont les noeuds peuvent réguler leur vitesse en fonction de la charge du système. En supposant que le réseau est initialement dans un état de congestion, on s’intéresse à la politique optimale d’allocation de débit permettant de le vider à coût minimal. L’analyse de la politique stochastique optimale via la théorie des processus de décision markoviens étant extrêmement difficile, nous proposons de l’approximer en utilisant un modèle fluide déterministe qui peut être résolu grâce à des techniques de contrôle optimal. Pour le cas d’un seul lien partagé par plusieurs classes de trafic, on montre que la politique optimale correspond à la règle cμ et on propose une expression explicite de la vitesse optimale. Enfin, dans une troisième partie, on s’intéresse aux plateformes de Cloud Computing dans le cadre du modèle SaaS. En supposant un partage équitable des ressources physiques entre machines virtuelles s’exécutant de manière concurrente, nous proposons des modèles de file d’attente simples pour prédire les temps de réponse des applications. Les modèles proposés prennent explicitement en compte le comportement des différentes classes d’application (tâches interactives, de calcul ou permanentes). Les expérimentations menées sur une plateforme réelle montrent que les modèles mathématiques obtenus permettent de prédire les temps de réponse avec une bonne précision
We study queueing-theoretic models for the performance evaluation and optimization of bandwidth-sharing networks. We first propose simple and explicit approximations for the main performance metrics of elastic flows in bandwidth-sharing networks operating under balanced fairness. Assuming that an admission control mechanism is used to limit the number of simultaneous streaming flows, we then study the competition for bandwidth between elastic and streaming flows and propose performance approximations based on a quasi-stationary assumption. Simulation results show the good accuracy of the proposed approximations. We then investigate the energy-delay tradeoff in bandwidth-sharing networks in which nodes can regulate their speed according to the load of the system. Assuming that the network is initially congested, we investigate the rate allocation to the classes that drains out the network with minimum total energy and delay cost. We formulate this optimal resource allocation problem as a Markov decision process which proves tobe both analytically and computationally challenging. We thus propose to solve this stochastic problem using a deterministic fluid approximation. For a single link sharedby an arbitrary number of classes, we show that the optimal-fluid solution follows thewell-known cμ rule and give an explicit expression for the optimal speed. Finally, we consider cloud computing platforms under the SaaS model. Assuming a fair share of the capacity of physical resources between virtual machines executed concurrently, we propose simple queueing models for predicting response times of applications.The proposed models explicitly take into account the different behaviors of the different classes of applications (interactive, CPU-intensive or permanent applications). Experiments on a real virtualized platform show that the mathematical models allow to predict response times accurately

Nous nous intéressons dans cette thèse à une file d'attente fluide unique ou à un réseau de files d'attente fluides pilotés par un processus stationnaire. Les niveaux des files à chaque instant sont alors modélisés comme solution d'une équation différentielle réfléchie. Le modèle peut être du second ordre, i. E. Une composante brownienne et un coefficient de diffusion peuvent intervenir dans la modélisation: l'équation différentielle devient alors une équation différentielle stochastique. Nous étudions d'abord la stabilité des files. Nous donnons différents critères permettant à la file unique ou au réseau de files de converger en distribution vers un état stationnaire. Nous regardons ensuite la distribution de la loi stationnaire. Dans différents cas nous donnons la transformée de Laplace de la loi stationnaire ou au moins ses moments d'ordre deux.

On considère une file d'attente fluide dont les taux d'arrivées et de service sont controlés par une chaîne de Markov en temps continu. On étudie les distributions du niveau et de la période d'occupation de la file fluide en régimes transitoire et stationnaire. En régime transitoire, on résoud pour cela un système infini d'équations aux dérivées partielles hyperbolique à coefficients constants. Les solutions sont exprimées sous forme d'une série entière. Le calcul des coefficients associés est très stable et précis. Pour une file fluide pilotée par une file d'attente M/M/1, la convergence des coefficients est établie et permet de réduire le nombre de calcul. En régime stationnaire, différentes solutions sont présentées, généralement basées sur la factorisation de Wiener-Hopf. Dans le cas particulier précédent, la distribution stationnaire du niveau d'occupation de la file fluide est exprimée sous forme d'une série entière dont les coeffficients sont explicitement donnés.

Présentation des outils d'analyse pour les réseaux a files (réseaux à files à choix libre topologique et réseaux linéaires). Utilisation du réseau coloré associé permettant de décider la quasi-vivacité, la terminaison infinie et la vivacité. Détermination du centre des réseaux. Forme générale du langage d'entrée des files. Description du langage d'un système de deux processus communiquant par files (langage d'un réseau de Pétri)

Dans ce chapitre sont proposés deux modifications à un système de file d’attente avec rappel premier entré, premier sorti, introduits par Laszlo Lakatos en 1994. Ces modèles prennent notamment en compte la réservation de temps pour le service client. Ces modèles semblent augmenter le rendement du système de file d’attente par rapport au système de file d’attente de type Lakatos.

Dans plusieurs systèmes de files d’attente réels les temps d’interarrivée et de service sont, dans une certaine mesure, interdépendants. Ce concept n’a pas reçu toute l’attention qu’il mérite dans la littérature sur les files d’attente. Dans ce chapitre nous étudions les systèmes de files d’attente à temps discret dans lesquels les temps d’interarrivées dépendent des temps de service, puis nous généralisons l’idée au cas où les temps de service et les temps d’interarrivées sont interdépendants.

Ce chapitre traite du régime transitoire des files markoviennes les plus fondamentales (M/M/1, M/M/1/H, etc.). Il s’agit d’un article de synthèse centrée sur l’obtention d’expressions analytiques des distributions du nombre de clients dans la file à l’instant t, ainsi que sur l’intérêt de l’uniformisation pour leur obtention, puis également pour obtenir des procédés de calcul numérique de ces lois.

Ce chapitre concerne les files d’attente variables dans le temps, avec abandon des clients et salles d’attente finies. Une approche en chaîne de Markov à deux échelles temporelles est utilisée. Les écarts modérés et les écarts importants sont pris en compte lorsque la séparation des échelles de temps est en vigueur. Dans l’étude, une expression générale de la fonction de taux est fournie. Un exemple numérique est également inclus pour illustrer le calcul de la fonction de taux.

Les méthodes d’inférence inductives maximales de Rényi et de Tsallis sont utilisées pour caractériser de nouvelles probabilités d’état pour une file d’attente M/G/1 stable avec des queues lourdes et des interactions à longue portée de l’ordre q (0.5 q < 1). Ces probabilités s’affichent exactement lorsque les temps de service suivent deux nouvelles familles distinctes de distributions exponentielles généralisées (EG). Une exploration plus poussée de cette méthodologie analytique peut avoir un impact significatif sur l’étude des systèmes de file d’attente complexes.

Sigman et Levi, ainsi que Melikov et Molchanove ont indépendamment introduit le système de gestion de stocks à file d’attente en 1992. La gestion de stocks (GS) combine l'inventaire classique avec la théorie classique des files d'attente. Dans le premier cas, on suppose que le temps de service est négligeable, dans le second, le besoin d'un article pour fournir un service aux clients n'est PAS pris en considération. Cependant, dans la GS, la présence du client et de l'inventaire est essentielle pour le début du service. Nous avons examiné le travail effectué jusqu'à présent en GS dans divers scénarios : classique, nouvel essai, production, fabrication, réservation de billets, annulation, inventaire avec durée de vie commune.

Nous considérons deux modèles de files d’attente à serveur infini avec un processus d’arrivée de Poisson. La particularité est que l’intensité de l’arrivée est rééchantillonnée à des intervalles de temps exponentiels (modèle 1) ou à l’époque du changement d’état du processus de Markov (modèle 2). Nos principaux résultats incluent les instants en régime transitoire et en régime permanent du nombre de clients.

Ce chapitre donne des résultats de base sur la diffusion et l’approximation gaussienne des réseaux de files d’attente multicanaux dans des conditions de trafic dense. L’approche locale est utilisée pour l’approximation de diffusion du processus de service dans le cas d’une structure clairement définie des flux d’entrée. Pour les flux d’entrée plus complexes, le processus limite est décrit comme un processus gaussien multidimensionnel. Les caractéristiques des processus limites dans les deux cas sont spécifiées via les paramètres du réseau. Ce chapitre donne des résultats de base sur la diffusion et l’approximation gaussienne des réseaux de files d’attente multicanaux dans des conditions de trafic dense. L’approche locale est utilisée pour l’approximation de diffusion du processus de service dans le cas d’une structure clairement définie des flux d’entrée. Pour les flux d’entrée plus complexes, le processus limite est décrit comme un processus gaussien multidimensionnel. Les caractéristiques des processus limites dans les deux cas sont spécifiées via les paramètres du réseau.

Ce chapitre traite des files d’attente fluides markoviennes à capacité finie ou infinie. Notre méthode d’analyse se fonde sur l’étude des probabilités de passage conditionnellement au niveau maximal atteint pendant une période d’activité. Elle aboutit au calcul du taux de perte et à une caractérisation de la distribution de la durée de congestion et d’information perdue pendant une telle période.

Dans ce chapitre, nous présentons une synthèse des résultats sur l’application de la méthode de stabilité forte à l’étude de la robustesse des systèmes et des réseaux de files d’attente. En plus de l’affirmation qualitative de la stabilité forte, nous obtenons souvent des bornes de perturbation. Enfin, l’utilisation des méthodes d’estimation non paramétrique de densité dans ce contexte est discutée.