3 Quelques mots sur les files d'attente

3.1 Objectif poursuivi

1. Nécessité. Pour modéliser les contraintes résultant de la réalité des processus industriels, il est nécessaire d'avoir quelques connaissances concernant les phénomènes d'attente. Ainsi est-il possible d'accélérer la rotation des camions en augmentant les moyens de chargement-déchargement (en personnels, en engins, en locaux). Mais alors, ce seront ces moyens supplémentaires qui attendront qu'il y ait des camions à décharger.
2. Principe fondamental : pour réduire les processus d'attente, il faut réduire la variance des processus.
3. Mise en garde. Le modèle M/M développé ci-dessous est le modèle le plus facile à calculer. Il est souvent un mauvais modèle.
4. Description
   • [Clients]On appelle ainsi les objets ou personnes qui arrivent dans le processus, attendent s'il y a lieu, sont traités et repartent. On suppose que les clients arrivent un par un, et sont servis dans l'ordre d'arrivée.
   • [Interarrivée]L'intervalle de temps séparant l'arrivée de deux clients successifs s'appelle interarrivée. On suppose que ces interarrivées sont indépendantes les unes des autres et suivent la même loi de probabilité.
     $$Pr\left( interarrivee\in \left[ t, t+ \mathrm{d}t\right] =a\left( t\right) \mathrm{d}t \right)$$

   • [Service]Le temps de séjour total dans le système est la somme du temps d'attente et de la durée du service effectif. On suppose que les services sont indépendants les unes des autres et suivent la même loi de probabilité.
     $$Pr\left( service\in \left[ t, t+ \mathrm{d}t\right] =b\left( t\right) \mathrm{d}t \right)$$

   Figure: File d'attente élémentaire.

   

5. Critique. Dans une situation réelle, l'indépendance des interarrivées est à peu près vraisemblable. Celle des services l'est beaucoup moins.
6. Évidence. Une condition nécessaire de fonctionnement est que la capacité de traitement du service, qui vaut $\mu \doteq 1/\mathrm{E}\left( b \right)$ clients par unité de temps, soit supérieure au nombre moyen de clients qui arrivent dans le système, qui vaut $\lambda \doteq 1/\mathrm{E}\left( a \right)$.
   $$\lambda =\rho \mu \quad avec\quad \rho <1$$

3.2 Processus markovien

1. Définition. Une file M/M est une file dont les deux lois (d'interarrivée et de service) sont exponentielles.
2. Rappel. Une variable exponentielle de paramètre $\lambda >0$ est une variable positive $X$ telle que
   $$Pr\left( X\in \left[ t, t+ \mathrm{d}t\right] \right) =Cte\times \exp \left( -\lambda t\right) \mathrm{d}t$$

3. Valeur de la constante. Le changement de variable $x=\lambda t$ montre que la constante vaut $Cte=\lambda$. En effet
   $$1=\int _{t=0}^{t=\infty }Cte \exp \left( -\lambda t\right) \... ...\exp \left( -x\right) \frac{1}{\lambda } \mathrm{d}x=\frac{1}{\lambda } Cte$$

4. Moyenne. On a $\mathrm{E}\left( t \right) =\frac{1}{\lambda }$. En effet
   $$\mathrm{E}\left( t \right) =\int _{t=0}^{t=\infty }t \exp \left... ... }\frac{1}{\lambda }x \exp \left( -x\right) \mathrm{d}x=\frac{1}{\lambda }$$
   Variance. On a $\mathrm{var}\left( t \right) =\frac{1}{\lambda ^{2}}$. En effet $\mathrm{E}\left( t^{2} \right) =\frac{2}{\lambda ^{2}}$ comme le montre
   $$\mathrm{E}\left( t^{2} \right) =\int _{t=0}^{t=\infty }t^{2} \e... ...mbda ^{2}}x^{2} \exp \left( -x\right) \mathrm{d}x=\frac{1}{\lambda ^{2}}2!$$

5. La loi exponentielle s'applique lorsque $Pr\left( t>A+B \vert t>B \right) =Pr\left( t>A \right)$. Autrement dit la loi du temps restant à attendre d'ici la prochaine arrivée est la même quelque soit le point de départ l'observation. En effet,
   $$Pr\left( t>A+B \right) =\int _{t=A+B}^{t=\infty }\exp \left( -\la... ...ght) =\exp \left( -\lambda A\right) \times \exp \left( -\lambda B\right)$$

3.3 Loi du nombre d'arrivées dans un intervalle de temps donné

1. Probabilité d'aucune arrivée dans l'intervalle $\left[ 0, T\right]$. Cette probabilité est celle de $t>T$, et vaut $p_{0}=\exp \left( -\lambda T\right)$.
2. Probabilité d'exactement une arrivée dans l'intervalle $\left[ 0, T\right]$. Pour que $n=1$, il faut que la première interarrivée soit dans $\left[ t, t+ \mathrm{d}t\right]$ avec $t<T$, puis qu'il n'arrive personne dans l'intervalle $T-t$ restant. Par la formule des probabilités totales, nous obtenons
   $$p_{1}=\int _{t=0}^{t=T} \exp \left( -\lambda \left( T-t\right) ... ...ght) \lambda \mathrm{d}t=\lambda T \exp \left( -\lambda T\right)$$
   (les exponentielles contenant $t$ se simplifient).
3. Probabilité d'exactement deux arrivées dans l'intervalle $\left[ 0, T\right]$. Pour que $n=2$, il faut que la première interarrivée soit dans $\left[ t, t+ \mathrm{d}t\right]$ avec $t<T$, puis qu'il arrive exactement un client dans l'intervalle $T-t$ restant. Par la formule des probabilités totales, nous obtenons
   $$p_{2}=\int _{t=0}^{t=T} \lambda \left( T-t\right) \exp \left( -... ...left( -\lambda T\right) \int _{t=0}^{t=T} \left( T-t\right) \mathrm{d}t$$

4. Plus généralement, la probabilité pour que exactement $n$ clients arrivent dans l'intervalle $\left[ 0, T\right]$ est donnée par la loi de Poisson
   $$Pr\left( n=k \right) =\frac{\left( \lambda T\right) ^{k}}{k!}\exp \left( -\lambda T\right)$$

5. Paramètres de dispersion. On a
   $$\mathrm{E}\left( n \right) =\lambda T\qquad ;\qquad \mathrm{var}\left( n \right) =\lambda T$$
   Le fait que l'espérance de $n$ soit $\lambda T$ confirme le fait que $\lambda$ est le débit du flot de clients. Le fait que la variance de $n$ ait la même dimension que $n$ confirme le fait que $n$ est un nombre. On en rappelle le principe de calcul :
   $$\mathrm{var}\left( n \right) =\mathrm{E}\left( n^{2}-n \right) +\mathrm{E}\left( n \right) -\left( \mathrm{E}\left( n \right) ^{2}\right)$$
   $$\mathrm{E}\left( n^{2}-n \right) =e^{-\lambda T} \sum _{k=0}k\l... ...}=e^{-\lambda T} p^{2} \sum _{k=2}\frac{p^{k-2}}{\left( k-2\right) !}=p^{2}$$

3.4 Espérances individuelles et espérances temporelles

1. Service individuel. On choisit un client par son numéro de client, avec une loi uniforme sur les numéros de clients et on note le temps de service de ce client. La loi de répartition de ce genre d'observations est la loi $b$ déjà définie.
2. Service temporel. On choisit une date d'observation, avec une loi uniforme sur les dates possibles. Si un client est en cours de service, on note le temps total de service de ce client. Si non, on choisit une autre date (on recommence jusqu'à trouver un client en cours de service). La loi de répartition de ce genre d'observations est une autre loi (notée $B$ dans ce qui suit).
3. Service résiduel. On procède comme pour le service temporel, mais on note le temps de service restant pour ce client. La date d'observation étant indépendante du service, on a $\mathrm{E}\left( service residuel \right) =\frac{1}{2}\mathrm{E}\left( service temporel \right)$
4. Exemple : service déterministe. La loi du service temporel est aussi déterministe tandis que la loi du service résiduel est uniforme sur $\left[ 0, \frac{1}{\mu }\right]$.
5. Théorème. La loi du service temporel est donnée par
   $$B\left( t\right) =\frac{t}{\mathrm{E}\left( t \right) }b\left( t\right)$$
   En effet, la probabilité d'un service de durée donnée $t\in \left[ x, x+ \mathrm{d}x\right]$ est $b \mathrm{d}t$, tandis que ses chances d'observation sont proportionnelles à cette durée. On a donc $B\left( t\right) =Cte t b\left( t\right)$ et on trouve la constante en résolvant $\int Cte t b\left( t\right) \mathrm{d}t=1$.
6. Loi uniforme. Si la loi de service (individuel) est uniforme sur $\left[ 0, T\right]$ alors $b\left( t\right) =\frac{1}{T}$, $\mathrm{E}\left( t \right) =\frac{T}{2}$ et $B\left( t\right) =\frac{2 t}{T^{2}}$.
7. Services Markov. Si les services (individuels) sont exponentiels, on a $b\left( t\right) =\mu \exp \left( -\mu t\right)$, $\mathrm{E}\left( t \right) =\frac{1}{\mu }$ et donc $B\left( t\right) =\mu ^{2} t \exp \left( -\mu t\right)$. On en déduit $\mathrm{E}\left( B \right) =\frac{2}{\mu }$ : le client qui est en cours de service quand vous arrivez est plus long à servir que les autres (en moyenne deux fois plus long).
8. Remarque. Pour des services de Markov, l'espérance du service résiduel est la même que l'espérance d'un service (individuel) ordinaire.

3.5 Théorème des débits de Poisson

1. Théorème. Dans une file d'attente M/M avec un débit d'arrivée $\lambda$ et une capacité de service $\mu$, le système se comporte comme un processus exponentiel, avec un débit $\mu -\lambda$. Le temps de séjour moyen d'un client dans le système est donc
   $$Sejour moyen=\frac{1}{\mu -\lambda }$$

2. Commentaire : dans ce théorème, la valeur du débit est évidente. Le contenu du théorème est que le phénomène de transit soit un processus exponentiel, permettant de passer de la durée moyenne au nombre moyen de clients traités dans cette durée.
3. Exemple. On suppose un cabinet médical où les patients arrivent environ toutes les 20 mn. Si les consultations durent en moyenne 15 mn et si le processus est M/M, la durée de séjour totale moyenne sera : une heure (la différence de débit étant un patient par heure). En utilisant $\lambda$, on voit qu'il y aura en moyenne (temporelle) 3 patients en tout dans le cabinet médical. Et en utilisant $\mu$, on voit que le nombre moyen de patients présents juste après une arrivée sera de quatre en tout, y compris celui qui vient d'arriver et, s'il existe, celui qui était en cours de consultation au moment de l'arrivée.