La théorie des files d'attente

La théorie des files d'attente est une branche des mathématiques qui étudie et modélise l'acte d'attente dans les lignes. Cet article examinera brièvement la formulation de la théorie des files d'attente ainsi que des exemples des modèles et des applications de leur utilisation. Le but du document est de fournir au lecteur suffisamment d'information pour modéliser correctement un système de file d'attente de base dans l'une des catégories que nous allons examiner, si possible. En outre, le lecteur devrait commencer à comprendre les idées de base de la façon de déterminer des informations utiles telles que les temps d'attente moyen d'un système de file d'attente particulier.

Le premier article sur la théorie des files d'attente, «La théorie des probabilités et des conversations téléphoniques» a été publié en 1909 par A.K. Erlang, maintenant considéré comme le père du champ. Son travail avec la compagnie de téléphone de Copenhague est ce qui a incité sa première incursion dans le domaine. Il a réfléchi au problème de déterminer combien de circuits téléphoniques étaient nécessaires pour fournir un service téléphonique qui empêcherait les clients d'attendre trop longtemps pour un circuit disponible. En développant une solution à ce problème, il a commencé à réaliser que le problème de minimiser le temps d'attente était applicable à de nombreux domaines, et a commencé à développer la théorie plus loin.

Le modèle de mise en file d'attente de base :

Pour commencer à comprendre les files d'attente, nous devons d'abord avoir une certaine connaissance de la théorie des probabilités. En particulier, nous examinerons les distributions de probabilité exponentielle et de Poisson.

1-Distributions de probabilité exponentielle et de Poisson.

La distribution exponentielle avec le paramètre λ est donnée par . λexp(-λt)

 Si T est une variable aléatoire qui représente les temps inter arrivés avec la distribution exponentielle, alors 

Cette répartition se prête bien à la modélisation des temps d'inter-parcours ou des temps de service pour un certain nombre de raisons. Le premier est le fait que la fonction exponentielle est une fonction strictement décroissante de t. Cela signifie qu'après une arrivée, la quantité de temps d'attente jusqu'à l'arrivée suivante est plus petite que grande. Une autre propriété importante de la distribution exponentielle est ce que l'on appelle la propriété sans mémoire. La propriété sans mémoire suggère que le temps jusqu'à la prochaine arrivée ne dépendra jamais de combien de temps a déjà passé. Cela rend intuitif un modèle où nous mesurons les arrivées de clients car les actions des clients sont clairement indépendantes les unes des autres.

Il est également utile de noter la relation de la distribution exponentielle avec la distribution de Poisson. La distribution de Poisson est utilisée pour déterminer la probabilité d'un certain nombre d'arrivées se produisant dans une période de temps donnée. La distribution de Poisson avec le paramètre λ est donné par :

((λt)exp(-λt)) ∕ n !

Où n est le nombre d'arrivées. Nous trouvons que si on pose n = 0, la distribution de Poisson nous donne :

exp(-λt)

Qui est égal à P (T> t) de la distribution exponentielle.

La relation ici aussi a un sens. Après tout, nous devrions être en mesure de rapporter la probabilité que des arrivées nulles se produisent dans une période de temps donnée avec la probabilité qu'un temps d'inter-croisement sera d'une certaine longueur. Le temps d'inter-arrivée ici, bien sûr, est le temps entre les arrivées de clients, et est donc une période de temps avec zéro arrivée.

Avec ces distributions à l'esprit, nous pouvons commencer à définir les processus d'entrée et de sortie d'un système de file d'attente de base, à partir duquel nous pouvons commencer à développer le modèle plus loin.

2- Le processus d'entrée. Pour commencer à modéliser le processus d'entrée, nous définissons ti comme le moment où le ième client arrive. Pour tout i >= 1, on définit Ti = ti + 1 -ti  comme étant le ième temps d'inter-croisement. Nous supposons également que toutes les Ti sont des variables aléatoires continues et indépendantes, que nous représentons par la variable aléatoire A avec densité de probabilité a (t). Typiquement, A est choisi pour avoir une distribution exponentielle de probabilité avec le paramètre λ Définie comme le taux d'arrivée, c'est-à-dire     a (t) = exp(-λt) 

Il est facile de montrer [W 1045] que si A a une distribution exponentielle, alors pour toutes les valeurs non négatives de t et h,

P(A > t + h \ A>= t) = P(A > h)

Ceci est un résultat important parce qu'il reflète la propriété sans mémoire de la distribution exponentielle, ce qui est une propriété importante à prendre en compte si nous modélisons les temps d'inter-croisement.

Une autre distribution peut être utilisée pour modéliser les temps d'inter-croisement (si la distribution exponentielle ne semble pas appropriée) est la distribution d'Erlang. Une distribution d'Erlang est une variable aléatoire continue dont la fonction de densité repose sur un paramètre de fréquence R et un paramètre de forme k. La fonction de densité de probabilité Erlang est :

3-Le processus de sortie. Tout comme le processus d'entrée, nous commençons l'analyse du processus de sortie en supposant que les temps de service des différents clients sont des variables aléatoires indépendantes représentées par la variable aléatoire S avec la densité de probabilité s (t) = μexp(-μt). Nous définissons également μ comme le taux de service, avec des unités de clients par heure. Idéalement, le processus de sortie peut également être modélisé comme une variable aléatoire exponentielle, car il rend le calcul beaucoup plus simple. Imaginez un exemple où quatre clients sont dans une banque avec trois guichets avec des temps de service exponentiellement distribués. Trois d'entre eux reçoivent un service immédiatement, tandis que le quatrième doit attendre un poste pour vider. Quelle est la probabilité que le quatrième client sera le dernier à terminer le service?

En raison de la propriété de non-mémoire de la distribution exponentielle, lorsque le quatrième client arrive enfin à un guichet, les trois clients restants ont une chance égale de finir leur service en dernier, car le temps de service dans cette situation n'est pas régi par combien de temps Ils ont déjà été servis. Ainsi, la réponse à la question est 1/3.

Malheureusement, la distribution exponentielle ne représente pas toujours exactement les temps de service. Pour un service qui nécessite plusieurs phases de service (par exemple, la numérisation des produits d'épicerie, le paiement de l'épicerie et l'ensachage des produits d'épicerie), une distribution Erlang peut être utilisée avec le paramètre k égal au nombre de différentes phases de service.

4-Processus de naissances et morts. Nous nous intéresserons enfin au cas général dans lequel on considère l’évolution d’une population qui connait à la fois des naissances et des morts. 

Il y a beaucoup des à dire sur ce sujet . Pour plus d'informations , il existe des documentations sur La théorie des files d'attente . Voila un document

Cas pratique de la théorie de fils d'attente (réseau routier)
Coordination locale et optimisation distribuée du trafic de véhicules autonomes dans un réseau routier