Simulation à événements discrets — Wikipédia

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

La simulation à évènements discrets consiste en une modélisation informatique où le changement de l'état d'un système, au cours du temps, est une suite d'évènements discrets. Chaque évènement arrive à un instant donné et modifie l'état du système.

De nos jours, cette technique est couramment utilisée tant par les industries et les entreprises de services afin de concevoir, optimiser et valider leurs organisations que par les centres de recherche dans l’optique d’étudier les systèmes complexes non linéaires.

L’idée de recourir à la simulation pour étudier le comportement des systèmes complexes apparaît dans les années 1950 avec les travaux de Jay Wright Forrester sur la dynamique des systèmes. Certains systèmes dits non linéaires, c'est-à-dire comportant des boucles de rétroaction ou des phénomènes aléatoires échappent en effet à une analyse statique. L’objectif de Forrester était alors de mettre au service de la gestion d’entreprise ses connaissances en ingénierie, c’est ainsi qu’il met en place les premiers modèles destinés à l’étude des systèmes organisationnels.

C’est dans les années 1960 qu’apparaissent les premiers langages informatiques de simulations à évènements discrets avec notamment Simula.  Les années 1970  marquent alors l’émergence des logiciels de simulation équipés d’une interface graphique permettant à l’utilisateur de s’affranchir du langage, ces nouveaux logiciels permettent aussi de construire une animation graphique de ses modèles. 

Les années 1980 voient apparaître les premiers logiciels commerciaux de simulation de flux avec TECNOMATIX Plant Simulation, SIMAN, WITNESS, Promodel ou encore ExtendSim (même si pour ce dernier, le moteur à évènements discrets n'apparaît qu’en 1990).

À partir de 1990, la multiplication de la puissance de calcul des ordinateurs personnels permet aux industriels (notamment General Motors, Ford, PSA ou Renault) de recourir massivement à la simulation. Certains d’entre eux vont même jusqu’à imposer une étude de simulation pour valider tout investissement opérationnel au-delà d’un certain montant. 

Depuis le début des années 2010, certains logiciels proposent un module permettant d’animer les modèles en 3D. À noter qu'aujourd’hui, l’utilisation de logiciels de simulations à événements discrets n’est plus restreinte à l’industrie ou à la recherche mais s’étend également au secteur tertiaire, notamment dans les domaines de la santé ou de la logistique^[1]. 

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ée 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.

C’est la simulation à événements discrets qui est la plus utilisée dans le monde de l’industrie, des transports et des services, car elle permet de décrire de manière réaliste le comportement des systèmes représentés. Les décideurs l’utilisent comme une assurance par rapport à leur choix divers^[6] :

• Dimensionnement d’installations, de stocks, d’entrepôts,
• Impact de pannes/maintenances sur des équipements,
• Circulation de personnes dans des lieux publics (contrôles, attentes, évacuation),
• Validation d’ordonnancement, de tailles de lots, de réapprovisionnement,
• Estimation des temps de transfert et de manutention,
• Choix d’équipes de personnel,

Les problématiques sont multiples.

• Histoire de la simulation de flux
• Cas d’étude dans le milieu de la santé publique

• Aide à la décision
• Simula
• Discrete Event System Specification : formalisme de spécification des systèmes à évènements discrets
• Méthode de Monte-Carlo
• Simulation de phénomènes
• QSS, méthode d'intégration à évènements discrets.

• Portail de l'informatique théorique