Théorie des files d’attente 1

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 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.

Les algorithmes d’approximation de diffusion (AAD) des systèmes et réseaux de files d’attente markoviens sont basés sur l’idée d’une description simplifiée de leurs modèles mathématiques. L’effet de simplification se fondent sur le fait que toute la variété des paramètres d’origine caractérisant l’évolution d’un système stochastique se transforme en trois fonctions qui déterminent un processus de diffusion : dérive de centrage, dérive-diffusion et variance. Une particularité essentielle de l’AAD consiste en une réelle possibilité d’application aux problèmes d’optimisation et de contrôle qui sont bien développés pour les processus de diffusion.

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.

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.

La simulation rapide de Monte Carlo est appliquée pour résoudre deux problèmes combinatoires à grande dimension. Le premier concerne l’estimation du nombre de sous-espaces k-dimensionnels d’un poids arbitraire d’un espace vectoriel n-dimensionnel sur un corps de Galois contenant q éléments. Les limites supérieures et inférieures sont construites grâce à une analytico-statistique. Le second problème concerne l’évaluation des « bonnes » permutations. La méthode de simulation rapide est proposée.

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.

L’objectif de ce chapitre est de donner un aperçu des résultats récents sur les systèmes de files d’attente avec rappel à source finie à serveur unique avec collision de clients. Il s’agit notamment de déterminer lorsque le serveur est fiable et de modéliser les pannes et les réparations aléatoires du serveur selon qu’il est inactif ou occupé. Les méthodes numériques, de simulation et asymptotiques, assistées par des outils, sont considérées sous la condition d’un nombre croissant et illimité de sources.

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.

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.