Une solution pour optimiser les files d'attente
NooLib The Blog | le 21-11-2017
Catégorie : Economie
Voici la problématique. Vous avez acheté un pantalon en grande surface. Malheureusement, celui-ci est trop serré et vous devez l'échanger. Vous appelez le magasin afin qu'il vous réserve la taille juste au-dessus. Le samedi suivant, votre ticket de caisse en main, vous retournez en magasin. Malheureusement, cinq personnes attendent déjà à la caisse. Après quelques minutes d'observation, vous estimez que la caissière traite un client en moyenne toutes les 4 minutes. Votre temps d'attente devrait donc être de 20 minutes environ. Mais 20 minutes d'attente est considérable compte tenu de votre demande. Que faire ? Revenir plus tard ? Continuer d'attendre ?
La problématique de la file d'attente n'est pas nouvelle dans nos sociétés actuelles et des mathématiciens tels qu'Alexandre Iakovlevitch Khintchine ou David George Kendall l'ont très bien compris à tel point qu'ils n'ont pas hésité à élaborer des théories mathématiques afin d'optimiser les flux [1-2]. Elles sont ordinairement nommées les théories des files d'attente. Elles peuvent s’appliquer à différentes situations comme la gestion des avions au sein d'un aéroport, l'attente des clients à un guichet ou bien encore dans le stockage des programmes informatiques avant leur traitement. Par exemple, la loi de Little [3] énonce que le nombre moyen ⟨N⟩ de clients dans un système stable est égal à leur fréquence moyenne d'arrivée λ multipliée par leur temps moyen τ passé dans le système, soit :
\langle N \rangle = \lambda \times \tau
Notre problématique de départ possède néanmoins une particularité intéressante. En effet, dans une file d'attente, le temps d'attente pour chaque client n'est pas nécessairement identique. En l’occurrence, il est même assez courant de trouver des temps d'attente assez différents entre les clients, ne serait-ce que parce que les problèmes des clients sont différents. Ainsi, dans notre problématique de départ, la difficulté est que la requête (échanger un pantalon) demande un temps d’exécution nettement moindre pour la caissière que les autres requêtes des clients. Et finalement, vous êtes pénalisés.
Dans le domaine de l'informatique, il existe également des problèmes de files d'attente et certains informaticiens ont élaboré des systèmes très sophistiqués afin d'y répondre. Tel est le cas, par exemple, du serveur NodeJS. NodeJS est une plateforme logicielle libre écrite en JavaScript et orientée vers les applications réseau qui doivent pouvoir monter en charge. Vous pouvez ainsi utiliser NodeJs afin de construire un serveur web et l'utiliser pour diffuser votre site web. Mais vous pouvez surtout utiliser NodeJs afin de construire des applications comprenant des entrées/sorties (I/O) de manière asynchrone comme, par exemple, un serveur de messagerie instantané incluant plusieurs utilisateurs. La particularité de NodeJS est qu'il repose sur une infrastructure événementielle ce qui lui permet justement de travailler de manière asynchrone. Cette propriété fait que NodeJS devient un système non-bloquant pour les programmes (voir figure 1).
Lors du déroulement d'un script, il y a souvent des phases "d'attente" où le script doit attendre la réponse d'une partie extérieure au système (entrées/sorties) pour pouvoir poursuivre son exécution. Pendant ce temps, le script ne peut pas traiter de nouvelles tâches et le système est bloqué. Au sein de NodeJS, les choses sont différentes puisque le système ne va pas attendre que le script se termine pour exécuter un autre script. NodeJS va lancer plusieurs scripts en parallèle. Grâce à sa structure événementielle, le système sera informé sur les scripts en attentes et sur les scripts qui doivent être exécutés. Ainsi, toutes les opérations au sein du système se déroulent de manière asynchrone et l'infrastructure globale permet d'éviter les files d'attente.
Dans l'exemple à la figure 1, nous avons deux fichiers en téléchargement. Dans un système bloquant, les deux téléchargements sont réalisés l'un après l'autre. Ainsi, le temps global d'attente dépasse les 10 secondes. Dans le système non bloquant, les deux téléchargements sont réalisés en parallèle, ce qui permet de réduire le temps d'attente global. A noter, néanmoins que, pris séparément, le téléchargement des fichiers 1 et 2 sera généralement plus long dans un système non bloquant que dans un système bloquant. Cependant, pris dans leur globalité, le temps de téléchargement est plus court dans un système non bloquant que dans un système bloquant.
Mais revenons, à présent, à notre problématique initiale. Si nous appliquons la logique d'un système non bloquant, tel que NodeJS, à notre file d'attente en magasin, nous avons la solution suivante : il suffirait d'évaluer le temps d'attente de la demande de chaque client inscrit dans la file d'attente et de mettre en attente temporairement les clients dont la demande est trop longue pour laisser passer les clients dont la demande est plus courte. Une fois la demande courte du client terminée, la caissière peut reprendre le client dont la demande est longue. Si la demande de ce même client est encore trop longue, celui-ci est remis de côté et le client ayant une demande plus courte passe en caisse. Et ainsi de suite. Nous obtenons alors une file d'attente non bloquante, asynchrone et événementielle.
Cependant, cette solution ne pourra fonctionner qu'avec l'accord de l'ensemble des clients de la file d'attente. En effet, un client qui ne souhaite pas participer au système non bloquant et donc qui ne souhaite pas être mis de côté afin de laisser la place à un autre client, dont la requête est plus rapide, bloquera inexorablement le système et nous retomberons sur un système dit bloquant. Cette nouvelle problématique rejoint les travaux de John Nash. Dans cette situation, le point d'équilibre de Nash n'est pas atteint car une des personnes au moins ne joue pas le jeu du système non bloquant.
La problématique de la file d'attente n'est pas nouvelle dans nos sociétés actuelles et des mathématiciens tels qu'Alexandre Iakovlevitch Khintchine ou David George Kendall l'ont très bien compris à tel point qu'ils n'ont pas hésité à élaborer des théories mathématiques afin d'optimiser les flux [1-2]. Elles sont ordinairement nommées les théories des files d'attente. Elles peuvent s’appliquer à différentes situations comme la gestion des avions au sein d'un aéroport, l'attente des clients à un guichet ou bien encore dans le stockage des programmes informatiques avant leur traitement. Par exemple, la loi de Little [3] énonce que le nombre moyen ⟨N⟩ de clients dans un système stable est égal à leur fréquence moyenne d'arrivée λ multipliée par leur temps moyen τ passé dans le système, soit :
Notre problématique de départ possède néanmoins une particularité intéressante. En effet, dans une file d'attente, le temps d'attente pour chaque client n'est pas nécessairement identique. En l’occurrence, il est même assez courant de trouver des temps d'attente assez différents entre les clients, ne serait-ce que parce que les problèmes des clients sont différents. Ainsi, dans notre problématique de départ, la difficulté est que la requête (échanger un pantalon) demande un temps d’exécution nettement moindre pour la caissière que les autres requêtes des clients. Et finalement, vous êtes pénalisés.
Dans le domaine de l'informatique, il existe également des problèmes de files d'attente et certains informaticiens ont élaboré des systèmes très sophistiqués afin d'y répondre. Tel est le cas, par exemple, du serveur NodeJS. NodeJS est une plateforme logicielle libre écrite en JavaScript et orientée vers les applications réseau qui doivent pouvoir monter en charge. Vous pouvez ainsi utiliser NodeJs afin de construire un serveur web et l'utiliser pour diffuser votre site web. Mais vous pouvez surtout utiliser NodeJs afin de construire des applications comprenant des entrées/sorties (I/O) de manière asynchrone comme, par exemple, un serveur de messagerie instantané incluant plusieurs utilisateurs. La particularité de NodeJS est qu'il repose sur une infrastructure événementielle ce qui lui permet justement de travailler de manière asynchrone. Cette propriété fait que NodeJS devient un système non-bloquant pour les programmes (voir figure 1).
Figure 1. Fonctionnement simplifié de NodeJs. NodeJS est un système non bloquant. Ainsi, il est possible de réaliser plusieurs tâches en parallèle plutôt que d’exécuter les tâches en série.
Lors du déroulement d'un script, il y a souvent des phases "d'attente" où le script doit attendre la réponse d'une partie extérieure au système (entrées/sorties) pour pouvoir poursuivre son exécution. Pendant ce temps, le script ne peut pas traiter de nouvelles tâches et le système est bloqué. Au sein de NodeJS, les choses sont différentes puisque le système ne va pas attendre que le script se termine pour exécuter un autre script. NodeJS va lancer plusieurs scripts en parallèle. Grâce à sa structure événementielle, le système sera informé sur les scripts en attentes et sur les scripts qui doivent être exécutés. Ainsi, toutes les opérations au sein du système se déroulent de manière asynchrone et l'infrastructure globale permet d'éviter les files d'attente.
Dans l'exemple à la figure 1, nous avons deux fichiers en téléchargement. Dans un système bloquant, les deux téléchargements sont réalisés l'un après l'autre. Ainsi, le temps global d'attente dépasse les 10 secondes. Dans le système non bloquant, les deux téléchargements sont réalisés en parallèle, ce qui permet de réduire le temps d'attente global. A noter, néanmoins que, pris séparément, le téléchargement des fichiers 1 et 2 sera généralement plus long dans un système non bloquant que dans un système bloquant. Cependant, pris dans leur globalité, le temps de téléchargement est plus court dans un système non bloquant que dans un système bloquant.
Mais revenons, à présent, à notre problématique initiale. Si nous appliquons la logique d'un système non bloquant, tel que NodeJS, à notre file d'attente en magasin, nous avons la solution suivante : il suffirait d'évaluer le temps d'attente de la demande de chaque client inscrit dans la file d'attente et de mettre en attente temporairement les clients dont la demande est trop longue pour laisser passer les clients dont la demande est plus courte. Une fois la demande courte du client terminée, la caissière peut reprendre le client dont la demande est longue. Si la demande de ce même client est encore trop longue, celui-ci est remis de côté et le client ayant une demande plus courte passe en caisse. Et ainsi de suite. Nous obtenons alors une file d'attente non bloquante, asynchrone et événementielle.
Cependant, cette solution ne pourra fonctionner qu'avec l'accord de l'ensemble des clients de la file d'attente. En effet, un client qui ne souhaite pas participer au système non bloquant et donc qui ne souhaite pas être mis de côté afin de laisser la place à un autre client, dont la requête est plus rapide, bloquera inexorablement le système et nous retomberons sur un système dit bloquant. Cette nouvelle problématique rejoint les travaux de John Nash. Dans cette situation, le point d'équilibre de Nash n'est pas atteint car une des personnes au moins ne joue pas le jeu du système non bloquant.
Commentaire(s)