Td corrigé Chapitre 3 - grainiabid pdf

Chapitre 3 - grainiabid

Dans ce modèle, quand l'enseignant se connecte sur Internet, ou corrige les ... Les réseaux de Petri permettent ainsi de décrire les relations temporelles ...




part of the document



Chapitre 3  La simulation informatique

3.1 Introduction 
L’idée de la simulation informatique (computer simulation) est venue de l’utilisation des ordinateurs pour imiter, simuler, les opérations des différents types de facilités ou processus du monde réel. Ces processus sont appelés des systèmes, et dans un but de les étudier scientifiquement nous faisons souvent des formulations sur leur fonctionnement. Ces formulations, qui prennent souvent la forme mathématique où relations logiques, constituent un modèle qui est utilisé pour essayer de comprendre comment le système correspondant se comporte.
Si les relations qui composent le modèle sont simples, il est possible d’utiliser des méthodes mathématiques pour obtenir des informations exactes sur des questions qui nous intéressent. C’est ce qu’on appelle une solution analytique. Cependant, la vaste majorité des systèmes du monde réel sont si complexes pour permettre d’avoir des modèles réalistes afin de les évaluer analytiquement, et ces modèles doivent être étudiés par le moyen de la simulation.

3.2 Les systèmes, les modèles et la simulation
Un système est défini comme étant une collection d’entités, par exemple des personnes où des machines, qui agissent et interagissent ensemble dans un but d’accomplir une fin logique. Cette définition a été propose par [Schmidt et Taylor 1970] :
‘’A system is defined to be a collection of entities, e.g. people and machines, that act and interact together toward the accomplishment of some logical end”.
En pratique, ce qui forme un système dépend des objectifs de l’étude visée. L’ensemble des entités qui composent le système dans une étude peut être un sous ensemble de tout le système dans une autre étude. La description des entités, des attributs et des activités en un point de temps qui est nécessaire pour prédire le comportement futur d’un système définit l’état du système et les variables correspondantes sont appelées les variables d’état. Les variables d’état relient le passé au futur via le présent.
Le choix du nombre et la nature des variables d ‘état sont dictées par les exigences et les besoins de l’étude en cause. Ce choix impose de faire une abstraction sur les composants du système et prendre en considération ceux qui aident et donnent une forte sémantique lors de l’analyse des résultats de l’étude.
Dans l’étude des systèmes on a tendance à les classer en deux catégories : les systèmes discrets et les systèmes continus. Un système discret est celui dont les variables d’état changent en des points de temps séparés. Un système continu est celui dont les variables d’état changent continuellement. En réalité peu de systèmes sont totalement discrets ou totalement continus, mais le fait qu’un type de changement prédomine on classifie le système soit qu’il est continu où discret.
En des moments du cycle de vie d’un grand nombre de systèmes, il y a un besoin de les étudier pour se faire une idée sur leur comportement et cela dans un objectif de les évaluer. La figure 3.1 indique les différentes manières d’étudier un système.







 SHAPE \* MERGEFORMAT 
Ainsi, l’étude d’un système se fait au moyen d’un modèle qui est une représentation imaginaire ou abstraite, et dont l’évolution dans une perspective préalablement définie, représente celles de certains aspects du système en cause. Un même système peut être représenté par plusieurs modèles, selon l’aspect concerné par l’étude ; et la valeur du modèle se juge par la contribution qu’il apporte à l’explication du système tout en restant dans le contexte de l’étude.
Les modèles sont utilisés dans la simulation dans le but d’observer les comportements futurs et éventuels d’un système. En d’autres termes, un modèle de simulation a pour fonction de déduire le comportement dans des situations non encore observées, à partir d’une bonne connaissance du système ou de certains de ses aspects. De cette présentation, il ressort que l’étude des systèmes en se basant sur un modèle et en utilisant l’ordinateur forme ce qu’on appelle une simulation informatique (a computer simulation).
La littérature propose plusieurs définitions de la simulation informatique. Ces définitions sont parfois proches, équivalentes ou complémentaires [Pritsker 1986] [Fishwick 1997]. Selon [Shannon 1975] par exemple, elle est définie comme étant le processus de conceptualisation d’un modèle informatique d’un système (où d’un processus) et la conduite d’expériences avec ce modèle dans un but soit de comprendre le comportement du système où d’évaluer les différentes stratégies de fonctionnement du système.
‘’Simulation is the process of designing a computerized model of a system (or a process) and conducting experiments with this model for the purpose either of understanding the behaviour of the system or evaluating various strategies for the operation of the system”.
Du fait de la nécessité d’avoir un bon modèle pour mener à bien une simulation, il est suggéré de classifier les modèles de simulation selon les dimensions suivantes [Law et al. 1991] :
Modèle de simulation statique : un modèle de simulation statique est une représentation du système en un point du temps, où simplement celui qui peut être utilisé pour représenter un système où le temps ne joue aucun rôle.
Modèle de simulation dynamique : un modèle de simulation dynamique représente un système quand il évolue dans le temps.
Modèle de simulation déterministe : un modèle de simulation déterministe ne contient aucun composant aléatoire.
Modèle de simulation stochastique : un modèle de simulation stochastique contient des composants aléatoires.
Modèle de simulation continu : un modèle de simulation représente un système continu.
Modèle de simulation discret : un modèle de simulation discret représente un système discret.
De cette taxonomie et de ce dimensionnement de la modélisation, la simulation est généralement catégorisée comme suit :
La simulation continue, où le système se présente sous la forme d' HYPERLINK "http://fr.wikipedia.org/wiki/%C3%89quation_diff%C3%A9rentielle" \o "Équation différentielle" équations différentielles à résoudre. Elle permet de suppléer à la résolution  HYPERLINK "http://fr.wikipedia.org/wiki/Fonction_analytique" \o "Fonction analytique" analytique quand celle-ci est impossible. Effectuée au départ sur des  HYPERLINK "http://fr.wikipedia.org/wiki/Calculateur_analogique" \o "Calculateur analogique" calculateurs analogiques.
La simulation statistique où de Monte Carlo, où le système en cause présente des phénomènes stochastiques, c'est-à-dire on fait appel à des techniques probabilistes. Le nom de ces méthodes fait allusion aux  HYPERLINK "http://fr.wikipedia.org/wiki/Jeu_de_hasard" \o "Jeu de hasard" jeux de hasard pratiqués à  HYPERLINK "http://fr.wikipedia.org/wiki/Monte-Carlo" \o "Monte-Carlo" Monte-Carlo.
La simulation par agents, où la simulation est segmentée en différentes entités qui interagissent entre elles. Elle est surtout utilisée dans les simulations économiques et sociales, où chaque agent représente un individu ou un groupe d'individus. Par nature, son fonctionnement est asynchrone.
La simulation discrète dans laquelle le système est soumis à une succession d'évènements qui le modifient. Ces simulations ont vocation à appliquer des principes simples à des systèmes de grande taille.

Dans cette thèse, on s’intéresse aux modèles de simulation discrets d’où le type de la simulation discrète par évènements (Discrete-Event Simulation).
3.3 Processus de simulation 
Quand on fait appel à la simulation pour étudier un problème, les quatre phases suivantes sont appliquées [Shannon 1975] :
Phase d’observation et d’identification du système : elle permet d’établir une certaine relation entre un observateur et un système du monde réel.
Phase de formulation où de modélisation : elle est généralement formulée de deux étapes. La première étape est celle de la représentation du système, ou des images symboliques d’objets, des rapports et des modèles de comportement sont liées dans des structures, des hypothèses et des concepts. La deuxième étape est celle de la conception du modèle. Dans le contexte de la simulation informatique, [Zeigler et al. 1979] considère un modèle comme étant un ensemble d’instructions pour générer un comportement (séquences temporisées de valeurs de variables). D’ici l’étape de conception prend en charge la transformation des images symboliques et les hypothèses sur les objets en des structures de données et des procédures de calcul exprimées par une certaine forme informatique.
Conduite d’expériences : dans le contexte informatique c’est l’exécution de l’ensemble des instructions (computer simulation program) représentant le système en cause.
Phase d’analyse : durant cette phase on essai de comprendre le comportement généré par les expériences en évaluant les différentes stratégies pour le fonctionnement du système en cause.
De manière relativement simplifiée, le processus de simulation peut être présenté selon la figure 3.2. La modélisation fournit un modèle symbolique (modèle de connaissance), la programmation fournit un modèle informatique (modèle d’action), la simulation ou l’expérimentation fournit les résultats obtenus du modèle, l’analyse des résultats permet d’évaluer le processus à modéliser.
 SHAPE \* MERGEFORMAT 

3.4 Gestion du temps et des évènements de la simulation discrète 
3.4.1 Introduction
En simulation discrète, nous ne savons pas à l’avance la valeur d’incrémentation du temps; au contraire cette valeur est déterminée individuellement pour chaque pas de temps, en se basant sur les actions qui composent le modèle. Les évènements sont déterminés par la séquence de chaque entité à commencer et à terminer une activité. Les actions globales de la simulation sont la conquête dans ces séquences à avoir ces entités concourantes. La discrétisation du temps est d’ici implicite dans le système lui-même, plutôt que d’être imposer par le simulateur. Le programme de simulation d’ici s’intéresse aux évènements intercalés entre les activités, sans pour autant se soucier des périodes de l’action active, menant à une inversion distinctive du souci.
L’utilisation du mot ‘’évènement’’, dans ce contexte, est une spécialisation de sa sémantique de tous les jours, qui veut dire simplement l’arrivée et la production (happening)  de quelque chose signifiante. Son origine étymologique du mot latin est ex-venire (va venir ; yet to come). Pour nos objectifs, on sépare les idées des arrivées instantanées de celles qui ont une durée significative ; pour les premières se sont des évènements discrets, ou tout simplement des évènements, et les dernières sont les activités. Ce choix nous permet de considérer l’avancement du temps d’un évènement à un autre. [Zeigler 1976] décrit l’avancement du temps dans les systèmes à évènements discrets comme un moyen de liaison des frontières d’un intervalle de temps entre un évènement et un autre en supposant que rien ne se passe dans cet intervalle.

3.4.2 Mécanismes de gestion du temps de la simulation discrète
Dans un modèle de simulation, la variable temps est capitale, car elle intervient pour synchroniser les éléments constitutifs du modèle, et pour ordonner les activités.
Due à la nature dynamique des modèles de simulation discrète, nous devons avoir le moyen de connaître le temps actuel de simulation et avoir aussi un mécanisme d’avancement du temps quand la simulation avance c'est-à-dire quand les évènements apparaissent.
En simulation l’unité de représentation du temps varie de la petite unité qui pourrait être la seconde, la minute, l’heure, le jour, le mois, l’année et même le siècle. La nature du système sous l’étude impose le choix de l’unité du temps. Traditionnellement, La variable temps où l’horloge de simulation peut être gérée de deux façons :
Méthode de l’horloge où à incrément fixe : l’horloge de la simulation (c’est-à-dire la variable qui enregistre le temps courant de la simulation) progresse d’une unité de temps fixe ("t), tout au long de la simulation, pour explorer la liste des évènements et déterminer si l un d eux doit avoir lieu à cette date. Le choix de cette unité ("t) est très important pour une bonne simulation. En général cette méthode est utilisée dans les systèmes déterministes. Figure 3.3 est une illustration de cette méthode.
Méthode de l’échéancier où à incrément variable: dans cette méthode (Figure 3.4) les seuls temps accessibles sont les dates d’évènements. L’horloge de simulation est avancée du temps (T) au temps (T + ´t) si un où plusieurs évènements sont programmés à cette date (T + ´t). Ainsi seuls les évènements sont représentés explicitement ; et les temps morts sont traités comme inactifs.


 SHAPE \* MERGEFORMAT 

 SHAPE \* MERGEFORMAT 

3.4.3 Structure d’une notification d’un évènement futur
Dans une simulation discrète, les évènements proviennent d’un ensemble de notifications d’évènements futurs qui est géré par l’exécutif de la simulation. Une notification d’un évènement futur peut être vue comme une entrée à un calendrier détenant un rendez vous futur. Quand la date et l’heure du rendez vous arrive, celui-ci aura lieu. Naturellement, quand un rendez vous ait lieu on l’enlève du calendrier.
Les opérations sur le calendrier ont des analogies directes dans les opérations de l’exécutif de la simulation. Au lieu d’un ‘calendrier’, nous appelons la collection des notifications des évènements futurs l’ensemble des évènements futurs. Les notifications d’évènements futurs sont recherchées dans l’ensemble des évènements futurs selon l’ordre croissant du temps : la base sur laquelle l’horloge de simulation avance. Par contre, les notifications nouvelles d’évènements futurs, provenant des actions effectuées lors de l’occurrence d’un évènement quelconque, sont insérées dans l’ensemble des évènements futurs (Figure 3.5). Les opérations effectuées sur cet ensemble sont appelées programmation d’évènements futurs.









D’ici il y a deux informations essentielles qu’on doit associer à une notification d’évènement futur :
Le temps d’occurrence de l’évènement,
Un pointeur aux actions de l’évènement de ce temps.
Le parcours des temps d’occurrence des évènements futurs dans le modèle pour choisir le minimum sera certainement suffisant pour exécuter la fonction d’activation d’évènements dans la séquence temporelle correcte. Mais comme le nombre de notifications futures devient grand, cette méthode deviendra consommatrice de temps d’exécution et inefficace. La première amélioration, évitant le parcours de toutes les occurrences futures, est de lier les notifications des évènements futurs dans l’ordre chronologique de leur apparition.
Si l’ordonnancement entre les notifications des évènements futurs est fait d’une manière ascendante comme indiqué dans la figure 3.6, un parcours simple à partir du début de la liste (la notification la plus proche) permettra facilement d’insérer une nouvelle notification d’évènement futur juste avant la première notification qui a juste un temps supérieur à elle.
 SHAPE \* MERGEFORMAT 
3.5 Outils de modélisation de la simulation discrète
3.5.1 Introduction
La plupart des applications de la simulation discrète sont des systèmes de files d’attente d’une manière ou d’une autre. La file d’attente est généralement constituée d’un ensemble d’entités qui attendent la satisfaction et la vérification de certaines conditions, ou la disponibilité de certaines ressources, pour commencer et participer dans des activités. Une file d’attente peut être un ensemble de tâches d’un système manufacturier attendant d’être traitées par une ou plusieurs machines, comme elle peut être un ensemble de clients dans un supermarché attendant leur tour pour être servi. On a coutume, dans la littérature, d’appeler ces types de files d’attente par Le modèle clients/serveur ou le modèle producteur/consommateur. La figure 3.7 est une schématisation de ces modèles.


Arrivées




La modélisation des systèmes dans un but de simulation nécessite la prise en compte des systèmes à ressources multiples. Ces structures complexes imposent l’étude et la prise en charge des réseaux de files d’attente, plutôt qu’à celle des files d’attente simples. De ce fait, un ensemble d’outils de modélisation est, généralement, utilisé pour générer le modèle de simulation du système en cause. Les outils et les dispositifs de modélisation qu’on introduit ici, vu leur importance à la simulation, sont les diagrammes de cycles d’activités et les réseaux de Petri.

3.5.2 Les diagrammes de cycles d’activités
Les ACD (Activity Cycle Diagrams) dus à [Tocher 1962] sont un moyen de modélisation des interactions des entités et sont particulièrement utiles pour les systèmes à files d’attente complexes. Leur popularité revient aux travaux de [Hills 1971] qui les a associés au système de simulation à trois phases qui sera développé dans le prochain chapitre. Les ACD font utilisation de trois éléments graphiques, comme c’est indiqué dans la figure 3.8. Un grand cercle représente une file d’attente ou un état oisif d’une classe d’entité, un rectangle représente une activité ou un état actif et un petit cercle représente une ressource.
 SHAPE \* MERGEFORMAT 
Le diagramme en lui-même est un schéma du cycle de vie de chaque classe d’entités et montre graphiquement leurs interactions. Chaque classe d’entités a un cycle de vie formé d’un ensemble d’états. Les entités passent d’un état à un autre au fur et à mesure que leur durée de vie s’écoule.
Un état actif englobe souvent la coopération des différentes classes d’entités. La durée de l’état actif est souvent connue à l’avance et déterminée par l’échantillonnage à partir d’une distribution de probabilité si le modèle de simulation est stochastique.
En utilisant les ACD, modélisons les activités quotidiennes d’un enseignant universitaire qui passe sa journée entre les locaux pédagogiques (Amphi, salle de cours, salle de TD, salle de TP ou laboratoire) et son bureau faisant des consultations avec ses étudiants ou dans certaines situations dans une réunion (un comité pédagogique, un conseil scientifique, préparation de manifestations scientifiques etc.).
Pour un objectif visé, on distingue ici 3 classes d’entités ;
un enseignant faisant ses tâches ;
locaux pédagogiques ;
une salle de réunion.

Nous modélisons les activités de chacune de ces classes.
i) L’enseignant :
L’enseignant a trois activités essentielles  (En cours, En consultation, En Réunion). Quand l’enseignant n’est pas dans une de ces activités on peut le considérer comme il est dans un état oisif. D’ici le diagramme de cycle d’activités de l’enseignant est comme prend la forme de la figure 3.9.










ii) Les locaux pédagogiques:
Un local peut être dans une des deux activités (En Cours, En entretien) sinon il est dans un état libre (figure 3.10).














iii) La salle de réunion :
La salle de réunion, comme le montre la figure 3.11, peut être dans une des deux activités (En réunion, En nettoyage) sinon elle est dans un état oisif (fermée).

 SHAPE \* MERGEFORMAT 
Les trois cycles peuvent être combinés pour former le diagramme des cycles d’activités de ce modèle comme il est illustré dans la figure 3.12.
 SHAPE \* MERGEFORMAT 
Dans ce modèle, quand l’enseignant se connecte sur Internet, ou corrige les examens ou prépare son cours est considéré comme une oisiveté ou une activité non concernée par la modélisation.
La logique de modélisation en utilisant les ACD impose le respect de certaines règles de base où une file d’attente contient un seul type d’entités, une activité est toujours précédée et suivie d’une file d’attente (la même ou une autre) et tout le cycle de vie d’une entité doit être fermé.

3.5.3 Les diagrammes de cycles d’activités étendus
Pour plus d’efficacité dans la modélisation des systèmes discrets, [Pooley 1991a, 1991b] et [Pooley et al. 1991] ont proposé des extensions aux ACD qui couvrent certains aspects manquants au niveau des ACD simples. Cette extension est connue sous le nom des X-ACD [Extended Activity Cycle Diagrams). Les X-ACD ont principalement amené une amélioration dans la spécification des producteurs d’entités entrants dans le système en fonction d’une loi et les consommateurs d’entités sortantes du système. En plus une distinction est faite entre les files d’attentes selon que l’attente est conditionnelle ou non conditionnelle. La figure 3.13 résume ces extensions.
 SHAPE \* MERGEFORMAT 
Comme illustration de l’utilisation des X-ACD dans un objectif de simulation, considérons un système d’utilité particulière à notre santé qui est celui d’un hôpital. Nous nous intéressons dans ce système aux classes de patients qui sont admis pour suivre un traitement particulier et aux patients qui nécessitent une opération chirurgicale ou une intervention particulière.
Dans ce système, on peut constater qu’il y a deux classes d’entités (Patient 1 et Patient 2) et une entité particulière modélisant le bloc opératoire. La figure 3.14 représente Le modèle X-ACD de l’hôpital.

 SHAPE \* MERGEFORMAT 
L’accès à l’hospitalisation n’est conditionné que par la disponibilité d’un lit au sens médical. Il n y a pas de manques de ressources humaines spécialisées. Une hospitalisation de traitement dure une période selon le cas.
Dans une hospitalisation qui nécessite une intervention chirurgicale, le patient doit passer une période avant l’opération à faire un bilan et il doit rester aussi une durée post-opération de convalescence.

3.5.4 Les réseaux de Petri 
En premier lieu, notons que le formalisme des réseaux de Petri [Petri 1962] est un cas particulier du formalisme général des systèmes de transitions. L’exemple le plus connu de systèmes de transitions est celui des automates à états finis où l’on donne explicitement tous les états, et tous les changements possibles d’états. Par rapport aux automates finis, les réseaux de Petri introduisent la possibilité d’avoir un ensemble infini d’états, et une notion de localité : un système est considéré comme composé d’un ensemble de sites. La possibilité d’effectuer une action dépend de conditions locales à certains sites, et cette action modifie uniquement l’état de certains sites.
Le parallélisme, c'est-à-dire le fait que plusieurs actions soient effectuées simultanément, est possible quand ces actions dépendent de sites différents, ou bien que les conditions sur un site commun à certaines de ces actions ne sont pas incompatibles. Les réseaux de Petri permettent ainsi de décrire les relations temporelles existant entre les différentes actions. Un système est vu au travers de ces relations, et les propriétés du système prouvables à partir du réseau qui le représente proviendront de ces relations.
Structurellement, un réseau de Petri est donné par des objets de quatre types :
- Les places qui correspondent à des sites.
- Le marquage d’une place (représentant l’état d’un site) est un nombre pouvant indiquer la satisfaction de conditions, ou plus généralement le nombre de ressources présentes dans le site.
- Les transitions qui correspondent aux actions.
- La fonction de transition donne pour chaque transition (action) les conditions qui doivent être remplies pour chacun des sites afin que cette action soit possible. Elle indique aussi l’effet de chaque transition sur l’état des sites.
Par exemple, dans un atelier d’assemblage de téléviseurs, une action consiste à placer le châssis au tube cathodique et visser avec quatre vis à l’aide d’un tournevis pneumatique. Un site contient les tubes cathodiques, le deuxième contient les châssis, le troisième contient les vis, le quatrième l’élément assemblé. L’un des aspects les plus agréables des réseaux de Petri est qu’il est extrêmement aisé de les visualiser.
En effet, un réseau de Petri utilise la forme géométrique du cercle pour représenter un site avec une appellation de place et le point pour exprimer les éléments du site avec une appellation de jeton. Le trait représente une action appelée ‘une transition’. Les places et les transitions sont reliées par des arcs étiquetés entrants et sortants. L’étiquette sur un arc entrant à une transition provenant d’une place, qui est généralement un nombre naturel, exprime le nombre de ressources nécessaires à l’action. L’étiquette sur un arc sortant d’une transition vers une place, qui est généralement un nombre naturel, exprime l’effet du passage de la transition sur la structure du système. Enfin, un état initial du réseau de Petri est exprimé par un certain nombre initial de jetons dans chaque site.
L’atelier décrit plus haut sera modélisé par le réseau de Petri de la figure 3.15.
 SHAPE \* MERGEFORMAT 
3.5.5 Les réseaux de Petri temporisés
La nature dynamique des modèles de simulation discrète impose l’idée qu’on doit avoir un mécanisme qui se charge et contrôle la variable temps qui est primordiale. Le temps est introduit dans les réseaux de Petri pour modéliser la réalité comme un ensemble d’activités en interaction prenant en compte leur temps de début et leur temps de terminaison. Le temps peut être introduit dans les réseaux selon différentes approches [Hillion 1989]. On peut l’associer aux places, aux jetons et aux transitions.
De cela, on peut avoir des places temporisées, des jetons temporisés et des transitions temporisées. Le temps peut être associé aux places où les jetons générés, dans une place de sortie d’une transition, deviennent disponibles pour franchir une transition seulement après l’écoulement d’un certain délai; le délai est un attribut de la place. Par exemple dans la figure 3.16, la place temporisée P1 contient deux jetons prêts à tirer à partir, peut être, des moments différents et elle contient aussi trois autres jetons qui attendent l’écoulement de certains délais peut être différents.
 SHAPE \* MERGEFORMAT 
Quand le temps est associé aux jetons, ces derniers prennent des durées comme des étiquettes ou des timbres (Time stamp) comme il est indiqué dans la figure 3.17. Ces temps indiquent les dates de disponibilité de tirer une transition ; ces dates peuvent être incrémentés en cas de besoin.
 SHAPE \* MERGEFORMAT 

Dans le cas où le temps est associé avec les transitions (Figure 3.18), on peut assumer qu’une transition correspond à une activité dont le temps de son début correspond à la date de début de franchissement de la transition et sa fin correspond à la fin du franchissement de la transition.

 SHAPE \* MERGEFORMAT 

Quand le temps est associé aux transitions, [Azeme et al. 1997] ont proposé plusieurs stratégies de franchissement :
Franchissement à trois phases :
Les jetons sont consommés des places en entrée quand la transition est prête à être franchie.
Ecoulement du délai.
Des jetons sont générés dans les places de sortie.
Franchissement atomique :
Les jetons restent dans places d’entrée jusqu’à écoulement du délai de la transition ; ils sont consommés des places d’entrée et générés dans des places de sortie une fois la transition tire.

3.6 Outils statistiques de la simulation
3.6.1 Introduction
La simulation discrète représente, dans plusieurs situations, une expérimentation statistique contrôlée. Les modèles de simulation incluent généralement des éléments stochastiques de nature. Par exemple, des expériences sont conduites par des séquences d’entrée aléatoires, comme le temps des arrivées à un système, et produisent des séquences de sortie aléatoires, comme le temps de service.
L’utilisation d’une distribution de probabilité pour représenter le temps de service implique que le temps tiré pour un service particulier a deux propriétés. Premièrement, le temps tiré se trouve à l’intérieur des valeurs de cette distribution. Deuxièmement, la probabilité d’apparition de certaines valeurs particulières est guidée par la loi de cette distribution. D’ici, il est connu à l’avance l’intervalle du temps de service mais ce qui n’est pas connu exactement c’est quand est ce que ces valeurs apparaissent. Ces phénomènes sont généralement représentés par une variable aléatoire épuisant ses valeurs à partir d’un générateur de nombres aléatoires.

3.6.2 Les générateurs de nombres aléatoires
Selon l’encyclopédie libre WIKIPEDIA [www.fr.wikipedia.org], un générateur de nombres aléatoires est ‘’un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Cependant, les sorties d'un tel générateur ne sont pas entièrement aléatoires.’’ Elles s'approchent seulement des propriétés idéales des sources complètement aléatoires.
La raison pour laquelle on se contente d’un rendu pseudo-aléatoire est : d’une part qu’il est difficile d’obtenir de « vrais » nombres aléatoires et que, dans certaines situations, il est possible d’utiliser des nombres pseudo-aléatoires, en lieu et place de vrais nombres aléatoires ; d’autre part, que ce sont des générateurs particulièrement adaptés à une implémentation informatique, donc plus facilement et plus efficacement utilisables.
Générer des nombres aléatoires sur ordinateur revient à créer une suite d'entiers:
Sn+1 = f(Sn)
Où f est une fonction qui doit être choisie judicieusement pour que la répartition des nombres Sn ne puisse pas être distinguée de ce que donnerait le hasard. On parle alors de nombres pseudo aléatoires.
La suite peut fournir M nombres aléatoires dans l'intervalle [0, M-1]. M dépend du type des entiers :
entiers 16 bits : M = 216 = 65 536
entiers 32 bits : M = 232 = 4 294 967 296 (soit plus de 4 milliards de nombres aléatoires)
La valeur de départ S0, appelée graine (seed), doit être fournie par l'utilisateur. La même graine donnera toujours la même suite de nombres. D'autre part, la suite se reproduit au bout d'un nombre de valeurs appelé période. Cette période doit être la plus grande possible.
Si la fonction f a été correctement choisie, chaque nombre a la même probabilité d'apparaître. On dit que les nombres aléatoires suivent une loi uniforme.
Nous décrivons ici une des méthodes permettant de générer des nombres aléatoires qui est celles des générateurs congruentiels, c'est à dire définis par le choix de la valeur entière initiale S0 (le "random seed") et par la récurrence on aura :
Sj+1 = modp(Sj x a + b, p) c'est-à-dire
Sj+1 = Le reste de [(Sj x a + b)/ p)
Les nombres fournis par le générateur étant les restes de (Sj x a + b)/ p. On peut en effet calculer aisément la période d'un tel générateur.
Examinons les cas réellement utiles : p = 2m et p premier. L'intérêt du premier cas est évident car l'arithmétique modulaire se simplifie considérablement lorsque 2m est égal à la taille du "mot machine" ou est une puissance de celui-ci.
Prenant comme exemple (simpliste) p = 2m = 8 et a= 5, b= 1 on obtient :
 INCLUDEPICTURE "http://193.48.37.48/~douillet/preprint/simul/img73.gif" \* MERGEFORMATINET 
Prenant comme exemple (simpliste) p = 7 a= 5, b= 0 on obtient :
 INCLUDEPICTURE "http://193.48.37.48/~douillet/preprint/simul/img77.gif" \* MERGEFORMATINET 
Un exemple "réel" de ce procédé est le générateur lgm, proposé par [Lewis et al. 1973] en 1969. On part d'un nombre et l'on calcule ses successeurs par la récurrence Sj+1 = modp(Sj x a + b, p) où le nombre p = 2147483647, le nombre a= 16807 et b= 0. On obtient l'algorithme (figure 2.19) dans lequel lgm_seed contient les instanciations successives de l'entier Sj.


LGM := proc PR( ) global lgm_seed
lgm_seed := modp(lgm_seed X 16807, 214783647)
return evalf(lgm_seed % 214783647)
Figure 3. 19 Générateur lgm(Lewis, Goodman, Miller, 1969)
Si pour un intérêt plus particulier avec plus détail sur les générateurs de nombres aléatoires, nous suggérons le site web [www.random.org].
3.6.3 Quelques générateurs pseudo-aléatoires
Dans cette section on présente quelques pseudo-aléatoires générateurs congruentiels utilisés sur des gammes d’ordinateurs ou par des logiciels connus. Le générateur congruentiel linéaire (linear congruentiel generator) est initialement proposé par [Lehmer 1948].
Le pseudo générateur est de la fome :
Yn+1 = [ayn + b] (mod m) et un seed y0 et on l’exprime par LCG(m,a,b, y0)
ANSIC : est le générateur utilisé par le ANSIC rand() fonction, version BSD .et proposé par [Park et al. 1988]
LCG(231,1103515245,12345,12345)
MINSTD: Ce générateur a été suggéré par [Lewis et al. 1969]
LCG(231- 1, 16807, 0, 1)
SIMSCRIPT: Ce générateur [Fishman et al 1982], [Fishman et al 1986, Fishman 1996]] est implémenté dans le langage de simulation SIMSCRIPT II.
LCG(231 - 1, 630360016, 0, 1)
BCSLIB: Ce générateur provient de [Knuth 67] et il a été utilsé par BCSLIB (Boeing Computer Services).
LCG(235 , 515 , 7261067085,0)
APPLE : Ce générateur est implémenté sur les machines Apple en se basant sur les travaux de [Jennergren 1983].
LCG(235 , 513 = 1220703125, 0,1)
3. 7 Résumé du chapitre

Les concepts fondamentaux de la modélisation et la simulation discrète ont été présentés. La simulation est le processus d’imiter le comportement d’un système réel à travers la réalisation d’un modèle représentatif pour l’exploiter dans différentes expériences. Un ensemble d’outils de conceptualisation des éléments composants le système sous l’étude est nécessaire. Ces outils s’intéressent à la représentation des entités, des attributs, des évènements, des activités et des processus de ces systèmes.
La modélisation se fait en tenant compte des aspects déterministes et/ou stochastiques du système. Le fait que la simulation utilise les données du présent pour comprendre les données futures du système ; un ensemble d’outils statistiques, à l’exemple des générateurs des nombres pseudo aléatoires, est nécessaire.






Chapitre 4 Paradigmes des approches de modélisation de la
simulation discrète

4.1 Introduction

Pour écrire un programme simulant les interactions entre les entités d’un système il faut, comme suggéré dans le chapitre précédent, identifier l’ensemble des classes d’entités et dresser leur cycle de vie d’une manière ou d’une autre en utilisant un outil de modélisation. Cependant, quand cette phase est achevée, la question qui se pose c’est comment transformer les interactions entre les entités en une forme convenable et transformable en un programme informatique.
La simulation discrète, comme son nom l’indique, est celle qui emploie la technique de gestion de temps à incrément variable surtout, ou encore méthode de l’échéancier pour contrôler l’exécution de la simulation.
Pour incarner et refléter exactement la dynamique d’un système sous une forme programmable, le modèle prêt à la programmation doit se concevoir en se basant sur une des quatre approches :
l’approche par évènements ;
l’approche par activités ;
l’approche par interaction de processus ;
l’approche à trois phases.
Il est conseillé de ne jamais s’aventurer à écrire des simulations discrètes sans le positionnement dans une de ces quatre approches [Pidd 84] et sans considérer le fait qu’un système de simulation est une hiérarchie à trois niveaux en interaction:
le modèle de simulation résultat de une des quatre approches ;
l’exécutif de simulation chargé du contrôle du modèle ;
la bibliothèque d’outils statistiques nécessaires au modèle.
Notons que la logique opérationnelle de l’exécutif de simulation et celle du modèle suit la logique de l’approche de modélisation choisie.

4.2 L’approche par évènements
4.2.1 Introduction
Cette approche est implémentée dans le langage SIMSCRIPT [Markowitz et al. 1963). Elle est très répandue au USA qu’en Europe. Le souci majeur dans une simulation est l’ordonnancement des évènements suivant leur temps d’apparition pour refléter l’ordonnancement des évènements dans le système réel. Il est tout à fait clair que la structure de notifications d’évènements futurs forme un support très approprié pour prendre en charge ce souci dans les différentes approches avec plus au moins des petits amendements pour chacune d’entre elles.

4.2.2 Méthodologie des routines d’évènements
La méthodologie est basée sur l’identification des composants des modules d’évènements. L’observation du système en termes d’entités et de ressources, est la première étape. Puis une liste d’évènements qui peuvent apparaître est dressée. Chaque évènement est analysé individuellement en tenant compte de l’interaction particulière entre l’entité et la ressource. Cette description prend la forme d’une procédure, appelée dans beaucoup de situations routine d’évènement ‘Event Routine’, qui sera déclenchée une fois l’évènement correspondant se produit ; c'est-à-dire quand une notification d’évènement correspondant à ce type d’évènement est rencontrée dans l’ensemble des évènements futurs.
Considérons le cas d’un modèle client/serveur ou producteur consommateur ou les clients arrivent d’une manière aléatoire à la file d’attente et sont servis sur le principe du premier arrivée premier servi (First In First Out). Dans ce cas, il y a deux changements d’état du système :
l’arrivée d’un nouveau client ou une production ;
la fin de service et départ du client ou fin de consommation.
Dans le cas ou il n y a pas de différences entre les clients, les figures 4.1 et 4.2 sont une représentation algorithmique de ces deux évènements, respectivement, en supposant que les temps des inter-arrivées et les temps de service ou de consommation sont générés à partir de procédures d’échantillonnage en utilisant un générateur pseudo aléatoire. Les évènements eux même sont programmés en interaction avec l’exécutif de simulation.
Les actions de ‘Event Routine Producteur’ consistent à générer le temps de la prochaine arrivée afin de lui créer une notification d’évènement futur dans l’échéancier. Par la suite, une vérification du consommateur s’il est libre est faite. Dans le cas positif, le serveur est mis dans un état ‘engagé’ puis une génération du temps de fin de consommation est faite pour créer la notification de l’évènement ‘fin de consommation’. Dans le cas contraire, la file d’attente est augmentée d’un client.
Event Routine Producteur
BEGIN
Générer temps de la prochaine production
Programmer la prochaine production
IF (consommateur libre) THEN
Engager consommateur
Générer temps de consommation
Programmer fin de consommation
ELSE
Augmenter file d’attente de un client.
ENDIF
END Event Routine Producteur

Figure 4.1 L’évènement Producteur
Les actions de ‘Event Routine Consommateur’ Consistent à libérer le client. Puis voir s’il y a au moins un client dans la file d’attente. Dans le cas affirmatif, on enlève un client de la file d’attente et on génère son temps de service ou de consommation afin de créer une notification de l’évènement futur ‘fin de consommation’. Dans le cas contraire, on libère le consommateur ou le serveur.
Event Routine Consommateur
BEGIN
Libérer le client
IF (file d’attente non vide) THEN
Diminuer file d’attente de un client
Générer temps de consommation
Programmer fin de consommation
ELSE
Libérer consommateur
ENDIF
END Event Routine Consommateur

Figure 4.2 L’évènement Consommateur

4.2.3 L’exécutif basé évènements à deux phases 
Une fois le modèle de simulation établi, on le soumet à un exécutif qui se charge de son exécution. Dans la première phase, l’action principale qu’effectue un exécutif basé évènements est l’avancement du temps de l’horloge de simulation pour le faire correspondre avec la plus proche date de l’évènement ou des évènements se trouvant dans la liste de notification des évènements futurs. Une fois ce réglage de l’horloge de simulation est terminé, la liste des évènements notifiés à cette date est formulée. Dans la deuxième phase, l’exécutif parcourt cette liste appelée liste des évènements courants et les exécute l’un après l’autre. Le pseudo code de la figure 4.3 est une illustration de l’ensemble des opérations qu’effectue l’exécutif basé évènements.
BEGIN
WHILE (non fin de simulation) DO
Avancer le temps et régler l’horloge de simulation
Former la liste des évènements courants
Exécuter les évènements courants
ENDDO

Figure 4.3 L’exécutif basé évènement ou à deux phases
On peut remarquer dans cette approche, que les évènements arrivant à une même date peuvent être dépendants entre eux du fait qu’il n y a pas de distinction entre leur nature. L’ordre d’exécution de ces évènements parallèles nécessite un entretien particulier de la part du modeleur afin que la logique de son modèle ne dévie pas de celle du système réel. Chose qui peut devenir très compliqué dans le cas où le modèle est formé d’un grand nombre d’évènements avec une forte dépendance entre eux. L’affectation de priorité est appliquée dans plusieurs situations.

4.3 L’approche orientée activités ou à trois phases
4.3.1 Introduction
D’une manière générale, l’approche basée activités est très utilisée en Grande Bretagne depuis son implémentation dans le langage de programmation CSL [Buxton et al. 1962], puis après les améliorations apportées par [Tocher 1963] elle est devenue connue sous le nom de l’approche à trois phases. L’avantage de cette approche c’est qu’elle s’appuie sur les diagrammes de cycles d’activités qui sont un outil très répandu dans la modélisation d’un système. En plus dans cette approche, une séparation nette est faite dans la nature de l’activité avec celle de l’évènement.

4.3.2 Méthodologie des activités ‘B’ et des activités ‘C’
Dans cette approche les interactions entre les entités du système sont vues comme des participations dans des activités qui, pour certaines, durent une certaine période de temps. Les activités sont de deux catégories :
Les activités ‘B’ [Bound activities] : Ce sont les opérations et actions qui apparaissent sans aucune condition.
Les activités ‘C’ [Conditional activities] : Ce sont les opérations et actions dont leur exécution dépend soit de la coopération des différentes classes d’entités ou de la satisfaction de certaines conditions.
Pour enlever les ambiguïtés, de compréhension et de séparation du concept ‘évènement’ du concept ‘activité’, qui existaient ; [Crookes 1981] a suggéré de considérer une activité conditionnelle comme un ensemble d’actions qui se passent dans une durée de temps avec une date de début et une date de fin. La date ou le point de début de l’activité correspond à un évènement conditionnel ‘C’ (Conditional event : C-Event) et la date où le point de la fin de l’activité correspond à un évènement certain ‘B’ (Bound Event : B-Event). En plus, on considère tous les processus d’arrivées de type producteur comme étant aussi des évènements certains.
De cette approche, le modèle Client/Serveur (Producteur/Consommateur) devient l’ensemble des évènements suivants :
Deux évènements certains (B events) :
Arrivée d’un client ou Production.
Départ du client et fin de service ou fin de consommation.
Un évènement conditionnel (C events) :
Début de service ou début de consommation.  
Les actions de l’évènement ‘B-Event Producteur’, indiquées dans la figure 4.4, consistent à augmenter la taille de la file et générer le temps de la prochaine arrivée ou production afin de créer une notification à cet évènement.

B-Event Producteur
BEGIN
Augmenter file d’attente de un client.
Générer temps de la prochaine production
Programmer la prochaine production
END B-Event Producteur

Figure 4.4 L’évènement ‘B’ Producteur

Les actions de l’évènement ‘B-Event Fin-de-consommation’, indiquées dans la figure 4.5, consistent à libérer le client et le consommateur.

B-Event Fin-de-consommation
BEGIN
Libérer le client
Libérer le consommateur
END B-Event Fin-de-consommation

Figure 4.5 L’évènement ‘B’ Fin-de-consommation

Les actions de l’évènement ‘C-Event Début-de-consommation’, indiquées dans la figure 4.6, consistent à tester si la file d’attente n’est pas vide et le consommateur est libre. Dans le cas positif, on enlève un client de la file, on engage le consommateur et on génère le temps de consommation afin de créer une notification d’évènement de fin de consommation.
C-Event Début-de-consommation
BEGIN
IF (file d’attente non vide) THEN
IF (consommateur libre) THEN
Diminuer file d’attente d’un client
Engager consommateur
Générer temps de consommation
Programmer fin de consommation
ENDIF
ENDIF
END C-Event Début-de-consommation

Figure 4.6 L’évènement début-de-consommation


4.3.3 L’exécutif basé activités ou à trois phases 
Une fois le modèle de simulation établi, on le soumet à un exécutif qui se charge de son exécution. Dans la première phase, l’action principale qu’effectue un exécutif basé activités est l’avancement du temps de l’horloge de simulation pour le faire correspondre avec la plus proche date de l’évènement ‘B’ ou des évènements ‘B’ se trouvant dans la liste de notification des évènements futurs. Une fois ce réglage de l’horloge de simulation est terminé, la liste des évènements ‘B’ notifiés à cette date est formulée. Dans la deuxième phase, l’exécutif parcourt cette liste appelée liste des évènements ‘B’ courants et les exécute l’un après l’autre. Dans la troisième phase, l’exécutif tente l’exécution de tous les évènements conditionnels ‘C’ du fait qu’il se peut qu’il y a eu libération de certaines entités et ressources nécessaires pour commencer certaines activités. Le pseudo code de la figure 4.7 est une illustration de l’ensemble des opérations qu’effectue l’exécutif basé évènements.

BEGIN
WHILE (non fin de simulation) DO
Avancer le temps et régler l’horloge de simulation
Former la liste des évènements ‘B’ courants
Exécuter les évènements ‘B’ courants
FOR (i=1 à nombre d’évènements ‘C’) DO
Exécuter évènement C-evenement(i)
ENDFOR
ENDDO
Figure 4.7 L’exécutif basé activités ou à trois phases

On peut remarquer dans cette approche, que les seuls évènements programmables avec une notification d’évènement futur sont les évènements certains ‘B’ qui sont totalement indépendants entre eux. L’ordre d’exécution des évènements ‘B’ parallèles arrivant à une même date n’influent pas sur la logique du modèle. Cependant, après l’exécution de l’ensemble des évènements ‘B’ pouvant apparaître à une date t, il faut tenter l’exécution de tous les évènements conditionnels ‘C’.

4.4 L’approche orientée processus
4.4.1 Introduction
L’approche basée processus est une combinaison de l’approche basée évènements et l’approche basée activités. Au lieu d’observer le système comme étant un ensemble d’évènements ou un ensemble d’activités, cette approche le considère comme un ensemble de processus. Cette approche est au cœur du langage de programmation SIMULA [Hills 73] et du langage de simulation GPSS [Greenberg 1972].


4.4.2 Méthodologie des processus
En simulation, un processus est regardé comme étant une séquence d’opérations à travers lesquelles une entité doit passer durant son cycle de vie dans le système. Il est important de noter que dans l’approche par processus on fait une classification entre les classes d’entités. On appelle entité permanente celle qui dure tout le long de la simulation depuis sa création ; et on appelle entité temporaire celle qui se crée et participe dans des activités pendant une période donnée et quitte le système avant la fin de la simulation.
Considérons une nouvelle fois le système Client/Serveur ou Producteur/Consommateur qui peut être modélisé par le processus suivant :
Le Client arrive ou Production arrive;
attend jusqu’à tête de la file  d’attente;
avance vers le serveur ou le Consommateur pour être servi ou consommé;
reste avec le serveur ou le consommateur jusqu’à fin de service ou fin de consommation.
quitte le système.
D’ici on déduit qu’un processus passe par des états actifs intercalés par des états de suspension. Typiquement, les suspensions ou les attentes de processus sont, dans certaines situations, conditionnelles ; par exemple l’attente de la disponibilité d’une ressource. Dans d’autres situations, les attentes sont inconditionnelles ; par exemple l’attente de l’écoulement d’un délai. Chaque processus dans ce cas possède des points de suspension et des points de réactivation.
L’implémentation informatique d’un processus impose une description de son fonctionnement en termes de blocs qui peuvent être vus comme des évènements certains ou conditionnels ou une combinaison des deux. L’activation et la réactivation se font à partir du début d’un bloc. La suspension conditionnelle ou inconditionnelle prend effet juste après la fin d’un bloc quelconque. La figure 4.8 indique une forme d’implémentation de processus.

PROCESS
BEGIN
CASE (évènement courant) OF
BEGINCASE
1: < Premier bloc>;
2: < Deuxième bloc> ;
:
Etc.
ENDCASE
ENDPROCESS

Figure 4.8 Forme d’implémentation d’un processus

Du modèle Client/Serveur ou Producteur/Consommateur, on peut considérer que le processus client se réactive quand il arrive, quand il commence à être servi et quand il termine d’avoir être servi.
De ce fait trois points d’activation ou de réactivation seront considérés. Le premier bloc génère le temps de la prochaine arrivée en créant la notification de l’évènement correspondant et teste s’il y a des clients en attente ou le serveur est occupé. Si oui, le client ‘processus’ s’insère dans la file d’attente. Le second bloc correspond à l’engagement du serveur et la programmation de la notification d’évènement ‘fin de service’. Le troisième bloc est le point de réactivation où on libère le serveur et le client. Le pseudo code de ce processus peut prendre la forme de la figure 4.9.

PROCESS Client
BEGIN
Générer temps de l’arrivée prochaine
Programmer arrivée prochaine
IF ((file d’attente non vide) OR (serveur occupé)) THEN
Augmenter file d’attente d’un client
Attendre jusqu’à arrivée à tête de file et serveur libre
 ENDIF
Engager serveur et diminuer file d’un client
Générer temps de service
Programmer fin de service
Libérer serveur
Libérer client
ENDPROCESS client
Figure 4.9 Processus d’un client


4.4.3 L’exécutif basé processus
Le mécanisme de fonctionnement de l’exécutif de simulation basé processus est plus compliqué que celui de l’approche orientée évènements ou l’approche orientée activités, parce qu’il contrôle l’allocation des ressources aux entités. D’ici, la tâche difficile des changements dans les files d’attente et les ressources est transférée à l’exécutif.
La stratégie de cet exécutif est basée sur l’utilisation et la maintenance de deux listes ordonnées. La première liste est un calendrier des notifications des évènements courants dont leur temps correspondant au temps de simulation actuel qui n’est que le temps de réactivation de certains processus suspendus en raison d’attentes inconditionnelles. La deuxième liste est une chaîne des entités suspendues. Cette dernière est une structure contenant toutes les entités qui ont été suspendues quelque part durant leur processus ou qui sont en attentes conditionnelles. La chaîne est ordonnée selon le temps des arrivées.
D’ici, l’exécutif de simulation basé processus fonctionne selon un principe presque similaire à l’exécutif à trois phases : avancement du temps, exécution des évènements courants et la vérification d’exécution des processus suspendus. La figure 4.10 est une illustration des actions de cet exécutif.

BEGIN
WHILE (non fin de simulation) DO
Avancer le temps et régler l’horloge de simulation
Former la liste des évènements courants
Exécuter les évènements courants
FOREACH (processus suspendu) DO
Tenter sa réactivation
ENDFOREACH
ENDDO
Figure 4.10 L’exécutif basé processus

On peut remarquer dans cette approche, que les seuls évènements programmables avec une notification d’évènement futur sont les évènements dus à une suspension inconditionnelle. En plus, les tentatives de réactivation de tous les processus suspendus peuvent ne pas être positives; ce qui peut rendre la chaîne des processus suspendus très grande.

4.5 Résumé du chapitre
Les trois approches importantes de modélisation et simulation traitées dans ce chapitre offrent un ensemble de stratégies différentes pour produire des modèles de simulation valides. Chacune de ses stratégies possède des avantages et des inconvénients. La comparaison peut se faire sur la base des avantages offerts au niveau de la modélisation et la programmation des modèles. L’approche basée évènements ou à deux phase exige du modeleur un effort considérable pour anticiper des solutions à l’avance au cas de production d’un ensemble d’évènements au même temps et qui sont en forte dépendance entre eux. Son avantage majeur réside dans la disponibilité de langages de simulation spécialisés utilisant cette approche à l’exemple de SIMSCRIPT.
L’approche basée activité ou à trois phases offre un cadre adéquat de production d’un modèle surtout si on se base sur les diagrammes des cycles d’activités où il est facile d’arriver à un modèle composé d’un ensemble d’unités structurées qui sont les évènements certains ‘B’ et les évènements conditionnels ‘C’. Cette structuration a son effet positif sur la maintenance du modèle de simulation.
Cependant, du point de vue programmation ; elle est coûteuse en terme de temps d’exécution au niveau de sa troisième phase où on est obligé de parcourir tous les évènements conditionnels ‘C’ pour tester leur condition pour une possibilité d’exécution. En plus, elle n’offre pas des langages de simulation spécialisés au sens propre du mot.
D’un point de vue conceptuel, l’approche basée processus offre un moyen facile de regarder les entités du système comme des processus réels. Son deuxième avantage réside, aussi, dans la disponibilité de langages spécialisés de simulation à l’exemple de GPSS et SIMULA. Cependant, elle risque de consommer un temps d’exécution énorme au cas où les processus représentant le système passent par un grand nombre d’états de suspension. Elle est généralement évitée dans le cas de non disponibilité d’un langage spécialisé du fait de la complication à programmer son exécutif.











La simulation informatique Par Boubetra Abdelhak -Département d’informatique -CUBBA
______________________________________________________________________________

PAGE 


PAGE 62



Expérimentation avec le système réel

Expérimentation avec un modèle

Modèle
physique

Modèle mathématique

Solution analytique

Simulation

Figure 3.1 Façons d’étude des systèmes ; Source : [Law et al. 1991]





Processus à modéliser

Modèle
symbolique

Modèle
informatique

Résultats
obtenus du
modèle

Modélisation

Programmation

Expérimentation

Analyse

Figure 3.2 Processus de simulation

Début

Initialiser l’horloge de simulation

Fin de simulation ?

Changer l état du système si un évènement a eu lieu

Incrémenter l horloge d un temps "t

Fin

oui

non

Figure 3.3 : Méthode de l horloge

Début

Initialiser l horloge de simulation

Fin de simulation
?

Fin

Avancer l horloge au temps du prochain ensemble d’évènements

Changer l’état du système en fonction de cet ensemble d’évènements

Figure 3.4 : Méthode de l’échéancier

oui

non

Activations futures

Ensemble d’évènements futurs


Notifications d’évènements futurs


Modèle



Actions d’évènements


Insertion d’évènements programmés

Recherche du prochain évènement

Activation courante

Figure 3.5 Relation entre l’ensemble des évènements futurs et l’activation du modèle.

Temps Actions
d’occurrence = 11 de l’évènement

Temps Actions
d’occurrence = 17 de l’évènement

Temps Actions
d’occurrence = 23 de l’évènement

Figure 3.6. Liste chaînée des notifications d’évènements futurs.

Début

Départs

Serveur ou Consommateur

Clients ou Producteur

Figure 3.7 Le modèle clients/serveur ou producteur/consommateur

Etat oisif

Etat actif

Figure 3.8 Symboles de diagramme de cycle d’activités

Ressource










En cours

En consultation


 '(:* + [ 
6
O
R
ñ
ñò&'(*+ÿ—¶¾Ìÿ
¯ÂÄá£ÂÃÄ=Œ®ùOöêöâÚÓâÚÓȼȰӬÓ❒}âÓ¬ÓÚÓÚÓ°ÓÚÓuÓuÓÚÓuÓuÓuÓhor÷hA©6(jhuzhA©CJUaJmHnHuhuzhA©CJaJjhuzhA©CJUaJhA©hor÷hA©6mH sH hA©hA©5mH sH hA©hA©mH sH  hor÷hA©hor÷hA©5hA©CJaJh°*ÄhA©5CJ aJ hA©5CJ aJ .'(:_
* + [ R
ñ
ò*
 
  
+ôôôååÝÝλÎÎÎÎôôôôôôôô$„H„Ádà]„H^„Áa$gdA©$„dà`„a$gdA©dhgdA©$„dà`„a$gdA©
$dha$gdA©7áâ0iýýý+ÿ
Ä£ŒùO­&‡s‡t‡u‡v‡w‡x‡y‡z‡…‡¢‡ª‡È‡Ñ‡Ù‡òãò×òãÉ×ò×ò×ò×Áº¯ò¤º¤òº ºò–º¯òã¯ÁºÁ‹{i{i{"h5hA©56CJaJmH sH h5hA©5CJaJmH sH h
{dhA©CJaJh
 :