Simulation à événements discrets

La simulation à événements discrets s’oppose à une simulation continue, où le temps est découpé en tranches égales, sans que l’on puisse distinguer des événements. À chaque tranche, pas de temps ou Δt, on examine l’état du système. Ainsi si l’on observe de l’eau qui chauffe, on ne considère aucun événement : l’eau chauffe en permanence, continûment, et l’on choisira d’observer sa température toutes les secondes, toutes les minutes, toutes les millisecondes. Quel que soit le moment où on l’observe, l’eau aura une température- en fonction de laquelle une décision pourra être prise. Et la granularité d’observation (=Δt, ou l’épaisseur de la tranche) sera le choix de l’observateur[2]. Un tel système pourra souvent se formaliser par les mathématiques, sous forme d’équations différentielles.

Dans la simulation à événements discrets, il faut qu’il se passe quelque chose pour que l’on observe et que l’on prenne des décisions. Ce sont ces instants de modification de l’état du système que l’on appelle événement[3]. Ainsi dans le cas d’un péage d’autoroute, si aucune voiture ne se présente au péage, il n'y a donc pas d’événement et le système ne change pas et donc il n'y a rien à observer. Il peut se passer beaucoup ou très peu de temps entre deux événements (ici l’arrivée d’une nouvelle voiture au péage), et l’on ne connaît pas à l’avance le nombre d’événements que comportera une simulation.

Il importe aussi de voir le lien entre la gestion discrète du temps, et la nature discrète ou continue du système modélisé et des flux qu’il comporte. Il n’y a pas de doute que le modèle d’un fast-food doive être traité par une simulation à événements discrets, et que les flux qu’il comporte (clients, serveurs, cuisiniers, hamburgers) sont discrets. De même il semblera s’imposer de traiter un modèle de dynamique de populations dans un écosystème par une simulation continue. Mais faut-il traiter avec un outil discret ou continu le cas d’une usine de peinture ou un équipement d’extraction/transformation de produits gaziers ? Les flux sont continus, exprimés par des débits. Les discrétiser amènerait à des découpages artificiels qui ralentiraient les temps de calcul ; utiliser un outil continu conduirait à réévaluer le système à des instants où rien ne se passe. Des approches respectant la représentation par débits et utilisant des seuils pour déclencher des événements [4] permettent de tels systèmes continus à événements discrets ou systèmes hybrides.

Suivant les outils informatiques de simulation, la gestion du temps discret se fera de différentes façons, mais avec quelques constantes :

Une fonction va gérer l’avancement chronologique du temps simulé, depuis le temps de début de la simulation jusqu’à son temps de fin. Le temps de la simulation va progresser par sauts de l’heure d’un événement à l’heure de l’événement suivant. Le modèle va être réévalué à chaque événement, donnant lieu à des nouveaux résultats débouchant sur d’éventuelles décisions, et créant d’éventuels nouveaux événements futurs.

La fonction de pilotage du temps va donc maintenir à jour en permanence un échéancier ou liste des événements, où les heures de tous les événements futurs sont inscrites. Pour calculer l’heure de l’événement suivant, il faut regarder l’heure de l’événement le plus proche de l’heure présente.

Comment est renseignée cette liste ? Dans un modèle de simulation à événements discrets, certaines fonctions génèrent par définition des événements : toute activité qui dure un certain temps (par ex. le temps de service à un guichet, la durée d’une opération sur un équipement) peut prévoir un changement d’état du système lorsque cette activité sera terminée (parfois on considère un événement en début et en fin d’une activité). De même des phénomènes liés à des lois de distribution, aléatoires ou non, créent un événement car ils changent l’état du système (l’arrivée d’une panne, un coup de téléphone entrant, l’arrivée d’un client). Ces exemples n’excluent pas d’autres opérations générant des événements.

Ainsi, dans un modèle discret représentant le fonctionnement d’un fast-food, l’arrivé d’un nouveau client (indiquée par une loi de distribution), la fin de la prise de commande (estimée à la prise en charge du nouveau client), la mise à disposition de hamburgers (déduite du début de cuisson/conditionnement du hamburger) seraient autant d’éléments du modèle générant des événements pour alimenter l’échéancier.

Il est courant qu’à une même heure soient annoncés plusieurs événements qui sont donc simultanés. Les éléments du modèle qui en sont à l’origine peuvent être indépendants, ou corrélés. Que se passe-t-il concrètement lorsqu’arrive un événement ? Est-ce l’état du modèle complet qui est réévalué, ou seulement le composant qui a publié l’événement ? Dans quel ordre évaluer deux composants ou plus qui publient un événement à la même heure ? Cela peut avoir une grande incidence sur l’enchaînement des actions et la fluidité générale des flux. C’est la situation courante d’une ressource que l’on cherche à allouer dès qu’elle est libérée[5]. Si dans le fast-food la transaction précédente se termine à l’heure même où arrive un nouveau client, il importe que la disponibilité du serveur soit constatée avant l’arrivée du client, et non l’inverse.

Le début et la fin de la simulation peuvent aussi soulever des questions. En général une simulation discrète s’arrête non pas parce qu’il n’y a plus aucun événement prévu, mais arbitrairement, parce qu’on a souhaité simuler 30 heures de temps réel ou la fabrication de 1000 tonnes de produits – et il reste alors des événements futurs dans l’échéancier. Au début de la simulation, il faut souvent une période de montée en régime pour que tous les composants du modèle aient été activés et aient donc eu l’occasion de publier des événements – à moins que l’outil permette une initialisation du modèle qui pourra ne pas démarrer à vide. Afin que les résultats soient fiables, il faut de toute façon savoir estimer et écarter de l’analyse ceux émis durant la cette phase initiale transitoire.

La pertinence de ces questions dépend fortement de la nature du système modélisé et des flux qui le composent. Les divers outils du marché ont chacun leur réponse, il importe surtout au modélisateur d’être conscient des implications que chaque implémentation peut avoir sur son modèle, en termes de validation du modèle comme d’exécution.