Les systèmes tels que les usines, les centres de distribution et les magasins qui fournissent certains services aux clients doivent fonctionner dans un environnement incertain qui comprend des fluctuations probabilistes (telles que des arrivées aléatoires de clients et des pannes d'équipement). .. Par conséquent, lors de l'évaluation de ses performances, il est nécessaire de suivre l'évolution de l'état du système placé dans un environnement probabiliste donné au fil du temps. En collectant un grand nombre de ces données de transition d'état du système, il devient possible d'évaluer statistiquement les performances du système.
À l'heure actuelle, il est généralement difficile de réaliser un grand nombre d'expériences dans un système tel qu'une usine ou un magasin réel, de sorte qu'une expérience de simulation utilisant un modèle est efficace. En particulier, une technique appelée simulation d'événements discrets est souvent utilisée pour des expériences de simulation de systèmes de production, de distribution et de fourniture de services. Dans cet article, comprenons les bases de cette simulation d'événements discrets et acquérons les compétences nécessaires pour créer un modèle de simulation d'événements discrets simple à l'aide du module SimPy de Python.
Cette fois, comme première étape à cette fin, nous visons à comprendre le mécanisme de base de la simulation d'événements discrets.
On peut dire que la simulation d'un système simule la façon dont l'état du système change dans le temps, c'est-à-dire l'évolution temporelle de l'état du système. À ce stade, dans la simulation d'événement discret, on considère que l'état du système cible change (uniquement) lorsqu'un événement se produit. Cette façon de penser les changements d'état est la caractéristique de base de la simulation d'événements discrets.
Par conséquent, lors de l'exécution d'une simulation d'événement discret,
Doit être clairement défini. Plus précisément, ceux-ci sont déterminés en fonction du type de système visé, de l’aspect du système qui vous intéresse, etc. On peut dire que la modélisation pour la simulation d'événements discrets consiste exactement à les définir de manière appropriée et claire.
Le moment de l'occurrence d'un événement probabiliste est souvent modélisé en considérant l'intervalle d'occurrence de l'événement comme une variable stochastique et en spécifiant sa distribution. Par exemple, rappelez-vous que les intervalles entre les événements aléatoires suivent une distribution exponentielle. En outre, le cas où une activité comprenant une incertitude sur la durée se termine est lorsque la distribution de la durée de l'activité est modélisée, par exemple, par une distribution normale, et un nombre aléatoire qui suit la distribution de la durée est ajouté à l'heure de début. Il serait bon que cela se produise.
La méthode la plus élémentaire pour mettre en œuvre la fonction de simulation d'événements discrets consiste à disposer d'une liste d'événements classés par ordre croissant de leur synchronisation d'occurrence, à supprimer les événements un par un depuis le début et à les provoquer en séquence. Est. Cette liste s'appelle un calendrier d'événements. Chaque fois qu'un événement est extrait du calendrier des événements, le temps de simulation est avancé au moment de l'occurrence de l'événement. Ensuite, les valeurs des variables qui représentent l'état du système sont mises à jour selon les règles qui décrivent comment l'état du système change lorsque l'événement se produit.
Voyons maintenant une implémentation (très simple) du calendrier des événements et des événements.
class Event:
def __init__(self, time, kind):
self.time = time # when this event occurs
self.kind = kind # the type of this event
def __str__(self):
return self.kind
class Calendar:
def __init__(self, horizon):
self.queue = [Event(horizon, 'end')] # list of events
def append(self, e): # add a new event to the list
self.queue.append(e)
self.queue.sort(key=lambda x: x.time) # sort events chronologically
def trigger(self): # trigger the first event in the list
e = self.queue.pop(0)
return e
L'événement est une classe d'événements. Pour le moment, cette classe contient deux informations, l'heure d'occurrence («time») et le type d'événement («kind»). Si nécessaire, vous pouvez également ajouter d'autres paramètres.
Calendar est une classe de calendrier d'événements. Il y a une liste nommée queue, et un événement du type end (événement de fin) y est ajouté. Il s'agit d'un événement pour terminer la simulation, et la longueur de la période de simulation doit être passée à l'argument «horizon», qui indique le moment de son occurrence, lorsque l'instance est créée. ʻAppend (e) est une méthode qui ajoute un nouvel événement ʻe au calendrier. Après avoir ajouté l'événement «e» à la liste «queue», on peut voir qu'il est réorganisé par ordre croissant de synchronisation d'occurrence.
trigger () est une méthode pour récupérer le premier événement de la liste queue. Dans ce cas, l'événement est simplement retiré de la liste et «renvoyé», et divers processus associés à l'occurrence de l'événement doivent être mis en œuvre séparément. De plus, par souci de simplicité, la gestion des exceptions lorsque la `file 'est vide est omise.
De plus, j'ai expliqué ci-dessus que le calendrier des événements est une liste, et même dans cet exemple d'implémentation, il est en fait implémenté sous forme de liste, mais bien sûr, si les événements peuvent être stockés et peuvent être récupérés un par un dans l'ordre du moment de l'occurrence, du tas, etc. , D'autres structures de données peuvent être utilisées.
Ensuite, obtenons une image du montage du corps principal du modèle de simulation à l'aide de ces pièces. A titre d'exemple, un squelette simple est montré.
import random
class Skelton:
def __init__(self, horizon):
self.now = 0 # simulation time
self.cal = Calendar(horizon) # event calendar
self.add_some_event() # an initial event is added
self.count = 0 # an example state variable (the number of events triggered)
def add_event(self, dt, kind):
e = Event(self.now +dt, kind)
self.cal.append(e)
def add_some_event(self):
self.add_event(random.expovariate(1), 'some_event')
def print_state(self):
print('{} th event occurs at {}'.format(self.count, round(self.now)))
def run(self):
while True:
self.print_state()
e = self.cal.trigger()
print(e)
self.now = e.time # advance the simulation time
self.count += 1 # increment the event counter
if e.kind == 'end': # time is up
break
else:
self.add_some_event() # next event is added
Skelton est une classe de modèles de simulation (squelettes) du système cible. Le temps de simulation est géré par la variable "now" (la valeur initiale est 0). On peut également voir que «cal» est une instance du calendrier des événements et est généré en héritant de l'argument «horizon» passé au moment de la génération du modèle. count est une variable factice de la variable d'état du système, qui compte le nombre d'occurrences d'un événement. Lors de la mise en œuvre d'un modèle pratique, il est judicieux de le remplacer par les variables d'état requises.
ʻAdd_event () est une méthode qui prend le temps et le type jusqu'au moment de l'occurrence comme arguments et ajoute le nouvel événement au calendrier des événements. De plus, une méthode ʻadd_some_event () ʻ est également définie qui ajoute un événement factice du type some_event donné par un nombre aléatoire qui suit une distribution exponentielle avec un temps d'apparition. priint_state ()` est une méthode qui écrit l'état du système sur la console.
Le final run () est la méthode pour lancer la simulation. Dans la boucle while, on peut voir qu'après la première écriture de l'état du système, l'événement est extrait du calendrier des événements, le type de l'événement est écrit, le temps de simulation est avancé et le nombre d'occurrences de l'événement count est incrémenté. Si l'événement qui s'est produit est terminé, la simulation se termine par la boucle while, mais sinon, un nouvel événement some_event est ajouté au calendrier des événements et le processus passe à la boucle suivante.
Déplaçons en fait ce modèle de simulation (squelette). Pour ce faire, créez d'abord une instance, puis exécutez-la avec la méthode run () (n'oubliez pas d'exécuter également le code pour les classes Event, Calendar et Model ci-dessus. Choses à garder).
model = Skelton(200)
model.run()
On peut voir que les événements se produisent un par un au hasard, et le temps de simulation progresse en conséquence. Ce flux simple est la structure de base de l'algorithme de simulation d'événements discrets, gardons-le donc à l'esprit ici.
Ensuite, étoffons un peu le squelette ci-dessus et créons un modèle de simulation concret (ce qui est très simple). Modélisons une situation dans laquelle les clients visitent au hasard un magasin qui gère l'inventaire d'un certain article par une méthode de commande à quantité fixe et achètent l'article. On suppose que le client achète un article s'il est en stock au magasin lorsqu'il arrive au magasin et le retourne, et s'il est en rupture de stock, une perte d'opportunité se produit. Supposons également que l'intervalle d'arrivée moyen des clients soit de 1.
Nous définirons la classe Model en utilisant la classe Event et la classe Calendar telles quelles, en héritant de la classe Skelton et en étoffant un peu selon cet exemple concret. Le code ci-dessous est un exemple.
class Model(Skelton):
def __init__(self, horizon, op, oq, lt, init):
self.now = 0 # simulation time
self.cal = Calendar(horizon) # event calendar
self.add_arrival() # an arrival event is added
self.op = op # ordering point
self.oq = oq # order quantity
self.lt = lt # replenishment lead time
self.at_hand = init # how many items you have at hand
self.loss = 0 # opportunity loss
self.orders = [] # list of back orders
@property
def total(self): # total inventory level including back orders
return sum(self.orders) +self.at_hand
def add_arrival(self): # arrival of a customer
self.add_event(random.expovariate(1), 'arrival')
def add_fill_up(self): # replenishment of ordered items
self.add_event(self.lt, 'fill_up')
def sell_or_apologize(self):
if self.at_hand > 0:
self.at_hand -= 1 # an item is sold
else:
self.loss += 1 # sorry we are out of stock
def fill_up(self): # receive the first order in the list
if len(self.orders) > 0:
self.at_hand += self.orders.pop(0)
def stocktake(self):
if self.total <= self.op:
self.orders.append(self.oq)
return True # ordered
return False # not ordered
def print_state(self):
print('[{}] current level: {}, back order: {}, lost sales: {} '.format(round(self.now), self.at_hand, self.orders, self.loss))
def run(self):
while True:
self.print_state()
e = self.cal.trigger()
print(e)
self.now = e.time # advance the simulation time
if e.kind == 'end': # time is up
break
elif e.kind == 'fill_up':
self.fill_up()
elif e.kind == 'arrival':
self.sell_or_apologize()
self.add_arrival()
ordered = self.stocktake()
if ordered:
self.add_fill_up()
En plus de la période de simulation (horizon), le point de commande (ʻop), la quantité de commande (ʻoq), le délai de réapprovisionnement ( lt) et la quantité de stock initiale sont spécifiés comme arguments lors de la création d'une instance du modèle de simulation. Quatre (ʻinit`) ont été ajoutés. De plus, la variable d'état «count» a été supprimée, et à la place, une liste de l'inventaire en vente libre («à la main»), le nombre de pertes d'opportunité («loss») et les commandes non réapprovisionnées (commandes en souffrance) («commandes») a été ajoutée. A été fait. De plus, on peut voir qu'un événement d'arrivée est ajouté au calendrier des événements au début. Il s'agit de l'événement correspondant à la première visite du client.
En regardant les méthodes, nous pouvons voir que ʻadd_arrival () et ʻadd_fill_up () jouent un rôle dans l'ajout de nouveaux événements d'arrivée et fill_up au calendrier des événements, respectivement. sell_or_apologize () décrit comment traiter avec les clients qui viennent au magasin (en vendre un si en stock, ajouter une perte d'opportunité sinon). Par contre, fill_up () est une méthode correspondant au remplissage. stocktake () permet de vérifier le niveau de stock (total y compris la commande en souffrance), de décider de passer une commande selon les règles de la méthode de commande à quantité fixe et de commander une quantité prédéterminée si nécessaire. Cela correspond.
Dans la méthode run (), le traitement lorsqu'un événement se produit est légèrement modifié en fonction du système cible cette fois. Plus précisément, si l'événement qui s'est produit est un événement fill_up, la méthode fill_up () est simplement appelée. S'il s'agit d'un événement d'arrivée, effectuez le support client (méthode sell_or_apologize ()), ajoutez l'événement d'arrivée suivant au calendrier des événements, puis vérifiez le niveau de stock et déterminez la commande (méthode stocktake ()). Vous pouvez voir qu'il y en a. Si une commande est passée ici, l'événement fill_up correspondant à la commande est ajouté au calendrier des événements.
Par exemple, exécutez ce modèle avec la période de simulation horizon = 200, le point de commande ʻop = 10, la quantité de commande ʻoq = 20, le délai de réapprovisionnement lt = 10 et la quantité initiale de stock ʻinit = 20`. Pour le voir, exécutez le code ci-dessous.
model = Model(200, 10, 20, 10, 20) # horizon, op, oq, lt, init
model.run()
Comme il est difficile de comprendre si le résultat de la simulation s'écoule simplement à l'écran sous forme de chaîne de caractères, envisagez de l'afficher dans un graphique. À cette fin, introduisons d'abord une classe de journal simple. Ce type de classe sera également utile lorsque vous souhaitez écrire les résultats de la simulation dans un fichier csv ou autre.
class Log:
def __init__(self):
self.time = []
self.at_hand = []
self.loss = []
self.total = []
def extend(self, model):
self.time.append(model.now)
self.at_hand.append(model.at_hand)
self.loss.append(model.loss)
self.total.append(model.total)
def plot_log(self):
plt.plot(self.time, self.at_hand, drawstyle = "steps-post")
plt.xlabel("time (minute)")
plt.ylabel("number of items")
plt.show()
Pour le moment, pour chaque fois que l'événement se produit, les valeurs du montant de l'inventaire du magasin (ʻat_hand), le nombre d'occurrences de perte d'opportunité (loss) et le niveau de stock total ( total) à ce moment-là sont stockés dans le journal. J'irai. Préparez une liste pour stocker les valeurs de chacune de ces variables et implémentez la méthode ʻextend (model) pour ajouter la valeur de chaque variable de model à ce moment-là à la liste correspondante. Vous pouvez voir qu'il y en a. La méthode plot_log () est une méthode pour afficher le résultat sous forme de graphique linéaire, mais les détails sont omis ici.
Ajoutons ceci au modèle créé ci-dessus. J'ai ajouté seulement 3 lignes, mais la classe Model4Plot modifiée est affichée ci-dessous (elle hérite de la classe Model ci-dessus, et les 3 lignes ajoutées reçoivent un commentaire pour le clarifier).
class Model4Plot(Model):
def __init__(self, horizon, op, oq, lt, init):
super().__init__(horizon, op, oq, lt, init)
self.log = Log() # <-- added
self.log.extend(self) # <-- added
def run(self):
while True:
self.print_state()
self.log.extend(self) # <-- added
e = self.cal.trigger()
print(e)
self.now = e.time
if e.kind == 'end':
break
elif e.kind == 'fill_up':
self.fill_up()
elif e.kind == 'arrival':
self.sell_or_apologize()
self.add_arrival()
ordered = self.stocktake()
if ordered:
self.add_fill_up()
Avec cela, l'état du système pendant la simulation sera enregistré dans le journal (model.log) en séquence. En conséquence, après l'exécution de la simulation, il est devenu possible d'utiliser ces données pour afficher la transition de l'inventaire du magasin dans un graphique en traits interrompus, par exemple, avec le code suivant.
import matplotlib.pyplot as plt
model = Model4Plot(200, 10, 20, 10, 20) # horizon, op, oq, lt, init
model.run()
model.log.plot_log()
Enfin, essayons de créer un modèle de simulation de système simple basé sur le squelette présenté ci-dessus. L'objectif de cette fois est le système suivant.
= cap).= ub), le client ne s'alignera pas dans la colonne et abandonnera et reviendra (une perte d'opportunité se produira).= mt, variance = vt).Cette fois, nous avons présenté le mécanisme de base de la simulation d'événements discrets et un exemple de mise en œuvre simple. Comme mentionné dans "Introduction", je voudrais vous présenter le module SimPy de la prochaine fois (qui n'apparaît pas cette fois).