Academic literature on the topic 'Théorie de files d’attente'

Résumé Le développement d’une problématique sur l’anticipation de l’échec ou de la réussite dans les organismes scolaires incite les auteurs à formuler un modèle basé sur des notions phénoménologiques et interprété dans un contexte systémique. Ce modèle, mis en convergence avec la théorie de l’apprentissage scolaire par la pédagogie de la maîtrise, permet de considérer un nouveau type d’attente, de caractère positif et non restrictif.

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.

L’abstention est un sujet de débat omniprésent dans la plupart des démocraties et ce pour deux raisons. Une de ces raisons est son importance croissante. Dans de nombreux pays démocratiques, un pourcentage croissant de la population décide de ne pas voter, suscitant de nombreux débats scientifiques, politiques et médiatiques. Même en Belgique, où le vote est obligatoire, nous sommes loin des 100 % de participation. En 1995, 9 % de la population avec droit de vote s’est abstenue, alors qu’en 1977 ils n’étaient que 5 %. Le cadre légal permettant de faire respecter la loi du vote obligatoire n’est en effet pas très strict. Entre 1987 et 1990, parmi les 500.000 personnes s’étant abstenues, seules 153 d’entre elles ont été jugées, et 138 condamnées à une amende symbolique. L’autre raison est beaucoup plus inquiétante : les citoyens qui décident de ne pas voter sont très souvent les plus défavorisés (moins riches, moins éduqués, ouvriers). Cette inégalité est loin d’être négligeable. Pour un ensemble de sept pays européens et le Canada, l’écart entre la participation des citoyens les plus éduqués et de leurs concitoyens moins diplômés a été estimé à 10 points de pourcent; en Suisse, pour les referenda menés entre 1981 et 1991, on a estimé l’écart à 25 points de pourcent; aux Etats-Unis, pour l’élection de 1972, il était de 40 points de pourcent. Est-ce problématique ? Le politologue Arend Lijphart affirme que la sous-représentation des plus défavorisés est l’équivalent fonctionnel des règles de vote censitaire existantes dans beaucoup de démocraties à la fin du dix-neuvième siècle, ce qui est intolérable. Cette position n’est cependant pas consensuelle. John Stuart Mill, par exemple, était de l’avis que les moins éduqués ne devraient pas voter parce qu’ils sont incapables de juger quelles sont les politiques favorables au bien-être de la communauté. Les données ne confirment cependant pas cette affirmation, mais elles montrent clairement que les pays ayant plus d’abstention sont ceux où la distribution du revenu est la plus inégale. Cela confirme la crainte de Lijphart de sous-représentation des opinions politiques des moins favorisés. Cette crainte est aussi renforcée par le fait qu’une diminution de l’abstention bénéficie principalement aux partis de gauche. Un phénomène de ce type peut partiellement expliquer les positions des différents partis sur le vote obligatoire en Belgique. En effet, selon les politologues belges Johan Ackaert et Lieven De Winter, son abolition peut gonfler ou diminuer fortement les résultats électoraux de certains partis. Quels sont alors les facteurs qui influencent l’abstention ? Le vote obligatoire a un impact déterminant sur le taux d’abstention. Dans une enquête menée en Belgique en 1991, 27 % des répondants affirment qu’ils ne voteraient plus jamais aux élections parlementaires si la loi sur le vote obligatoire était abolie. Pour l’élection du Parlement européen, on a estimé que le vote obligatoire diminuait l’abstention d’environ 20 à 23 points de pourcent. Par ailleurs, l’abstention varie selon le type d’élection (nationale, locale, européenne), le système électoral (proportionnel ou majoritaire), le jour de la semaine où ont lieu les élections (week-end ou jour ouvrable), l’existence ou pas d’un processus préalable d’inscription en tant qu’électeur (plus d’abstention dans les pays où c’est le cas), le nombre d’élections annuelles (l’abstention augmente lorsqu’il y en a beaucoup), le résultat espéré (moins d’abstention lorsqu’un résultat plus serré est attendu). La décision de voter ou de s’abstenir intéresse les économistes depuis que Downs a publié "An Economic Theory of Democracy" en 1957. L’auteur y décrit le comportement de l’électeur en tant qu’individu rationnel, qui évalue le bénéfice et le coût de voter. Le bénéfice correspond au gain de voir son parti préféré gagner l’élection, pondéré par la probabilité que son propre vote soit déterminant pour un tel résultat. Avec des millions d’électeurs, le vote d’un individu a un impact très faible sur le résultat, rendant presque nul le bénéfice de voter. Les coûts associés à l’acte de voter incluent le déplacement, le temps d’attente au bureau de vote et la récolte d’information préalable. L’électeur rationnel devrait donc s’abstenir. Downs conclut que si les citoyens votent malgré tout, c’est parce qu’ils attachent de la valeur au système démocratique et qu’ils veulent éviter son effondrement. C’est ce qu’il appelle la "valeur de long terme" de la démocratie. Ces éléments nous permettent d’interpréter les faits empiriques. Voter un jour ouvrable et le fait de devoir s’inscrire sont des coûts, qui font augmenter l’abstention. Le bénéfice de l’élection de son parti préféré est supérieur lorsque l’enjeu de l’élection est plus grand, ce qui explique la moindre abstention aux élections nationales par rapport aux européennes. Un résultat espéré très serré augmente l’impact du vote individuel sur le résultat des élections, ce qui fait diminuer l’abstention. Si on pense au coût d’obtention de l’information nécessaire à la décision de voter, la plus forte participation des plus diplômés devient claire : ce sont eux qui ont le plus de facilités à obtenir et interpréter cette information. Downs a aussi mis l’accent sur le paradoxe fondamental du vote. Si aucun individu ne vote parce qu’il ne peut influencer le résultat, chaque citoyen peut décider de voter et ainsi élire son parti préféré, puisque tous ses concitoyens se sont abstenus. Mais si tous parviennent à la même conclusion, ils votent donc tous et chaque vote individuel perd sa valeur. Ce raisonnement fait appel à deux aspects fondamentaux de l’acte de voter. D’un côté la compétition, qui pousse les gens à voter : les sympathisants d’un parti veulent voter pour que l’autre parti ne gagne pas. D’un autre le phénomène du "tire-au-flanc", qui amène les gens à s’abstenir : les sympathisants d’un même parti ont tendance à reporter l’un sur l’autre la responsabilité de voter, car cela leur évite le coût du vote tout en gardant le bénéfice de voir son parti élu. Le message des approches économiques face au problème de l’abstention est que son existence n’est pas étonnante, bien au contraire. Cependant, dans le souci d’augmenter la participation, on peut éliminer certains aspects institutionnels qui rendent l’acte de voter coûteux. De nombreuses études empiriques ont démontré l’importance des aspects institutionnels, et la théorie nous permet de comprendre pourquoi des tels facteurs influencent la décision de voter. Parmi les différentes mesures que l’on peut mettre en place pour faire baisser l’abstention, la plus effective mais aussi la plus controversée est sans doute le vote obligatoire, qui permet à la fois de faire descendre l’abstention à des niveaux très faibles et d’éliminer le biais social. La Belgique a le système le plus ancien et le mieux établi de vote obligatoire. Ce n’est cependant pas le seul pays à l’avoir adopté. L’introduction du vote obligatoire n’est cependant pas exempte de critiques. La plus importante concerne la liberté de choix. Les défenseurs du vote obligatoire tels que Arend Lijphart affirment que le droit de ne pas voter reste intact (par un vote blanc ou nul), c’est l’obligation de se déplacer jusqu’au bureau de vote qui est en cause. En outre, tout dépend de l’échelle des valeurs : si l’on préfère la liberté individuelle à l’égalité de représentation et d’opportunité, le vote obligatoire a en effet peu de sens. Enfin, ne pas voter est une attitude de tire-au-flanc comme beaucoup d’autres dans la vie économique, que l’Etat doit souvent éliminer en imposant une obligation.

L’abstention est un sujet de débat omniprésent dans la plupart des démocraties et ce pour deux raisons. Une de ces raisons est son importance croissante. Dans de nombreux pays démocratiques, un pourcentage croissant de la population décide de ne pas voter, suscitant de nombreux débats scientifiques, politiques et médiatiques. Même en Belgique, où le vote est obligatoire, nous sommes loin des 100 % de participation. En 1995, 9 % de la population avec droit de vote s’est abstenue, alors qu’en 1977 ils n’étaient que 5 %. Le cadre légal permettant de faire respecter la loi du vote obligatoire n’est en effet pas très strict. Entre 1987 et 1990, parmi les 500.000 personnes s’étant abstenues, seules 153 d’entre elles ont été jugées, et 138 condamnées à une amende symbolique. L’autre raison est beaucoup plus inquiétante : les citoyens qui décident de ne pas voter sont très souvent les plus défavorisés (moins riches, moins éduqués, ouvriers). Cette inégalité est loin d’être négligeable. Pour un ensemble de sept pays européens et le Canada, l’écart entre la participation des citoyens les plus éduqués et de leurs concitoyens moins diplômés a été estimé à 10 points de pourcent; en Suisse, pour les referenda menés entre 1981 et 1991, on a estimé l’écart à 25 points de pourcent; aux Etats-Unis, pour l’élection de 1972, il était de 40 points de pourcent. Est-ce problématique ? Le politologue Arend Lijphart affirme que la sous-représentation des plus défavorisés est l’équivalent fonctionnel des règles de vote censitaire existantes dans beaucoup de démocraties à la fin du dix-neuvième siècle, ce qui est intolérable. Cette position n’est cependant pas consensuelle. John Stuart Mill, par exemple, était de l’avis que les moins éduqués ne devraient pas voter parce qu’ils sont incapables de juger quelles sont les politiques favorables au bien-être de la communauté. Les données ne confirment cependant pas cette affirmation, mais elles montrent clairement que les pays ayant plus d’abstention sont ceux où la distribution du revenu est la plus inégale. Cela confirme la crainte de Lijphart de sous-représentation des opinions politiques des moins favorisés. Cette crainte est aussi renforcée par le fait qu’une diminution de l’abstention bénéficie principalement aux partis de gauche. Un phénomène de ce type peut partiellement expliquer les positions des différents partis sur le vote obligatoire en Belgique. En effet, selon les politologues belges Johan Ackaert et Lieven De Winter, son abolition peut gonfler ou diminuer fortement les résultats électoraux de certains partis. Quels sont alors les facteurs qui influencent l’abstention ? Le vote obligatoire a un impact déterminant sur le taux d’abstention. Dans une enquête menée en Belgique en 1991, 27 % des répondants affirment qu’ils ne voteraient plus jamais aux élections parlementaires si la loi sur le vote obligatoire était abolie. Pour l’élection du Parlement européen, on a estimé que le vote obligatoire diminuait l’abstention d’environ 20 à 23 points de pourcent. Par ailleurs, l’abstention varie selon le type d’élection (nationale, locale, européenne), le système électoral (proportionnel ou majoritaire), le jour de la semaine où ont lieu les élections (week-end ou jour ouvrable), l’existence ou pas d’un processus préalable d’inscription en tant qu’électeur (plus d’abstention dans les pays où c’est le cas), le nombre d’élections annuelles (l’abstention augmente lorsqu’il y en a beaucoup), le résultat espéré (moins d’abstention lorsqu’un résultat plus serré est attendu). La décision de voter ou de s’abstenir intéresse les économistes depuis que Downs a publié "An Economic Theory of Democracy" en 1957. L’auteur y décrit le comportement de l’électeur en tant qu’individu rationnel, qui évalue le bénéfice et le coût de voter. Le bénéfice correspond au gain de voir son parti préféré gagner l’élection, pondéré par la probabilité que son propre vote soit déterminant pour un tel résultat. Avec des millions d’électeurs, le vote d’un individu a un impact très faible sur le résultat, rendant presque nul le bénéfice de voter. Les coûts associés à l’acte de voter incluent le déplacement, le temps d’attente au bureau de vote et la récolte d’information préalable. L’électeur rationnel devrait donc s’abstenir. Downs conclut que si les citoyens votent malgré tout, c’est parce qu’ils attachent de la valeur au système démocratique et qu’ils veulent éviter son effondrement. C’est ce qu’il appelle la "valeur de long terme" de la démocratie. Ces éléments nous permettent d’interpréter les faits empiriques. Voter un jour ouvrable et le fait de devoir s’inscrire sont des coûts, qui font augmenter l’abstention. Le bénéfice de l’élection de son parti préféré est supérieur lorsque l’enjeu de l’élection est plus grand, ce qui explique la moindre abstention aux élections nationales par rapport aux européennes. Un résultat espéré très serré augmente l’impact du vote individuel sur le résultat des élections, ce qui fait diminuer l’abstention. Si on pense au coût d’obtention de l’information nécessaire à la décision de voter, la plus forte participation des plus diplômés devient claire : ce sont eux qui ont le plus de facilités à obtenir et interpréter cette information. Downs a aussi mis l’accent sur le paradoxe fondamental du vote. Si aucun individu ne vote parce qu’il ne peut influencer le résultat, chaque citoyen peut décider de voter et ainsi élire son parti préféré, puisque tous ses concitoyens se sont abstenus. Mais si tous parviennent à la même conclusion, ils votent donc tous et chaque vote individuel perd sa valeur. Ce raisonnement fait appel à deux aspects fondamentaux de l’acte de voter. D’un côté la compétition, qui pousse les gens à voter : les sympathisants d’un parti veulent voter pour que l’autre parti ne gagne pas. D’un autre le phénomène du "tire-au-flanc", qui amène les gens à s’abstenir : les sympathisants d’un même parti ont tendance à reporter l’un sur l’autre la responsabilité de voter, car cela leur évite le coût du vote tout en gardant le bénéfice de voir son parti élu. Le message des approches économiques face au problème de l’abstention est que son existence n’est pas étonnante, bien au contraire. Cependant, dans le souci d’augmenter la participation, on peut éliminer certains aspects institutionnels qui rendent l’acte de voter coûteux. De nombreuses études empiriques ont démontré l’importance des aspects institutionnels, et la théorie nous permet de comprendre pourquoi des tels facteurs influencent la décision de voter. Parmi les différentes mesures que l’on peut mettre en place pour faire baisser l’abstention, la plus effective mais aussi la plus controversée est sans doute le vote obligatoire, qui permet à la fois de faire descendre l’abstention à des niveaux très faibles et d’éliminer le biais social. La Belgique a le système le plus ancien et le mieux établi de vote obligatoire. Ce n’est cependant pas le seul pays à l’avoir adopté. L’introduction du vote obligatoire n’est cependant pas exempte de critiques. La plus importante concerne la liberté de choix. Les défenseurs du vote obligatoire tels que Arend Lijphart affirment que le droit de ne pas voter reste intact (par un vote blanc ou nul), c’est l’obligation de se déplacer jusqu’au bureau de vote qui est en cause. En outre, tout dépend de l’échelle des valeurs : si l’on préfère la liberté individuelle à l’égalité de représentation et d’opportunité, le vote obligatoire a en effet peu de sens. Enfin, ne pas voter est une attitude de tire-au-flanc comme beaucoup d’autres dans la vie économique, que l’Etat doit souvent éliminer en imposant une obligation.

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)

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

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

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.

Dans cette thèse, nous étudions deux problèmes d'apprentissage automatique : (I) la détection des communautés et (II) l'appariement adaptatif. I) Il est bien connu que beaucoup de réseaux ont une structure en communautés. La détection de ces communautés nous aide à comprendre et exploiter des réseaux de tout genre. Cette thèse considère principalement la détection des communautés par des méthodes spectrales utilisant des vecteurs propres associés à des matrices choisiesavec soin. Nous faisons une analyse de leur performance sur des graphes artificiels. Au lieu du modèle classique connu sous le nom de « Stochastic Block Model » (dans lequel les degrés sont homogènes) nous considérons un modèle où les degrés sont plus variables : le « Degree-Corrected Stochastic Block Model » (DC-SBM). Dans ce modèle les degrés de tous les nœuds sont pondérés - ce qui permet de générer des suites des degrés hétérogènes. Nous étudions ce modèle dans deux régimes: le régime dense et le régime « épars », ou « dilué ». Dans le régime dense, nous prouvons qu'un algorithme basé sur une matrice d'adjacence normalisée réussit à classifier correctement tous les nœuds sauf une fraction négligeable. Dans le régime épars il existe un seuil en termes de paramètres du modèle en-dessous lequel n'importe quel algorithme échoue par manque d'information. En revanche, nous prouvons qu'un algorithme utilisant la matrice « non-backtracking » réussit jusqu'au seuil - cette méthode est donc très robuste. Pour montrer cela nous caractérisons le spectre des graphes qui sont générés selon un DC-SBM dans son régime épars. Nous concluons cette partie par des tests sur des réseaux sociaux. II) Les marchés d'intermédiation en ligne tels que des plateformes de Question-Réponse et des plateformes de recrutement nécessitent un appariement basé sur une information incomplète des deux parties. Nous développons un modèle de système d'appariement entre tâches et serveurs représentant le comportement de telles plateformes. Pour ce modèle nous donnons une condition nécessaire et suffisante pour que le système puisse gérer un certain flux de tâches. Nous introduisons également une politique de « back-pressure » sous lequel le débit gérable par le système est maximal. Nous prouvons que cette politique atteint un débit strictement plus grand qu'une politique naturelle « gloutonne ». Nous concluons en validant nos résultats théoriques avec des simulations entrainées par des données de la plateforme Stack-Overflow
In this thesis, we study two problems of machine learning: (I) community detection and (II) adaptive matching. I) It is well-known that many networks exhibit a community structure. Finding those communities helps us understand and exploit general networks. In this thesis we focus on community detection using so-called spectral methods based on the eigenvectors of carefully chosen matrices. We analyse their performance on artificially generated benchmark graphs. Instead of the classical Stochastic Block Model (which does not allow for much degree-heterogeneity), we consider a Degree-Corrected Stochastic Block Model (DC-SBM) with weighted vertices, that is able to generate a wide class of degree sequences. We consider this model in both a dense and sparse regime. In the dense regime, we show that an algorithm based on a suitably normalized adjacency matrix correctly classifies all but a vanishing fraction of the nodes. In the sparse regime, we show that the availability of only a small amount of information entails the existence of an information-theoretic threshold below which no algorithm performs better than random guess. On the positive side, we show that an algorithm based on the non-backtracking matrix works all the way down to the detectability threshold in the sparse regime, showing the robustness of the algorithm. This follows after a precise characterization of the non-backtracking spectrum of sparse DC-SBM's. We further perform tests on well-known real networks. II) Online two-sided matching markets such as Q&A forums and online labour platforms critically rely on the ability to propose adequate matches based on imperfect knowledge of the two parties to be matched. We develop a model of a task / server matching system for (efficient) platform operation in the presence of such uncertainty. For this model, we give a necessary and sufficient condition for an incoming stream of tasks to be manageable by the system. We further identify a so-called back-pressure policy under which the throughput that the system can handle is optimized. We show that this policy achieves strictly larger throughput than a natural greedy policy. Finally, we validate our model and confirm our theoretical findings with experiments based on user-contributed content on an online platform

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.

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.

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.

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.