3.2 Simulation d'une file d'attente GI/GI/1

3.2.1 Routine principale

Passons maintenant à la simulation d'une file d'attente simple, c'est à dire avec des arrivées et des services indépendants (ce que veut dire le I de GI/GI/1). Si nous modélisons la file d'attente par une liste séquentielle, nous devons en premier lieu la dimensionner sa longueur de façon à ce que la probabilité d'un débordement au cours d'une simulation de taille donnée soit négligeable. En second lieu nous devrons translater le contenu de cette liste à chaque départ d'un client.

Dans une simulation par blocs, on peut éviter ces réécritures en disposant d'une liste de longueur . La liste est alors adressée au moyen de deux pointeurs et avec . Lorsque la file est vide, et dans le cas contraire contient le premier client, et contient le dernier. On peut alors attendre la fin de chaque lot avant de procéder à une translation de la queue.

Dans ce qui suit, nous avons préféré modéliser la file par une liste chaînée, la tête de liste représentant le client en train d'être servi. Une telle structure a l'avantage de se redimensionner "spontanément" et en outre ne nécessiter pas de recalage lors du départ d'un client. Il convient d'être attentif au fait que les deux solutions (liste séquentielle à deux pointeurs et liste chaînée) peuvent nécessiter des temps de calcul très différents selon le langage de programmation utilisé : un essai comparatif s'impose.

Dans l'algorithme 46, est le temps à attendre jusqu'à la nouvelle arrivée, tandis que est (lorsque la file n'est pas vide) le temps à attendre jusqu'à la fin du service en cours. On détermine donc la nature (arrivée ou départ) du premier événement à survenir. Pour une arrivée, on diminue le temps de service restant du client en cours (s'il existe), puis on détermine la date de la prochaine arrivée, ainsi que le futur temps de service de l'arrivant (utilisant l'hypothèse d'indépendance), que l'on rajoute en fin de liste. Pour un départ, il suffit de mettre à jour la durée d'attente jusqu'à la prochaine arrivée, puis de supprimer le client concerné.

Le programme est écrit de façon à ce que le moment d'observation (procédure ) corresponde effectivement à ce que voit le client lors de son arrivée. En particulier la longueur de la file n'a pas encore augmenté.

3.2.2 Programmation des observations

L'encadré 47 décrit la procédure permettant d'observer

1. le processus des inter-arrivées
2. le service résiduel, c'est à dire le service du client qui est en cours de service au moment de l'arrivée du nouveau client (lorsqu'il arrive sur une file non vide)
3. le deuxième service, c'est à dire la durée prévue pour le service du client en tête de la file d'attente (variable définie seulement si la file comporte au moins deux clients lors de l'arrivée qui déclanche l'observation)
4. la longueur de la file d'attente au moment de l'arrivée (l'arrivant non compris)
5. la charge de travail restante, c'est à dire le temps d'attente de l'arrivant avant de pouvoir être servi.