J'essaie de résoudre l'exercice suivant, mais je n'ai en fait aucune idée de la façon de commencer à le faire. J'ai trouvé un code dans mon livre qui lui ressemble mais c'est un exercice complètement différent et je ne sais pas comment les relier les uns aux autres. Comment puis-je commencer à simuler des arrivées et comment savoir quand elles sont terminées? Je sais comment les stocker et calculer a, b, c, d en fonction de cela. Mais je ne sais pas comment j'ai réellement besoin de simuler la simulation de monte carlo. Quelqu'un pourrait-il m'aider à démarrer? Je sais que ce n'est pas un endroit où vos questions obtiennent une réponse pour vous, mais seulement résolues à la place. Mais le problème est que je ne sais pas par où commencer.
Un service d'assistance informatique représente un système de mise en file d'attente avec cinq assistants prenant les appels des clients. Les appels se produisent selon un processus de Poisson avec le taux moyen d'un appel toutes les 45 secondes. Les durées de service des 1er, 2e, 3e, 4e et 5e assistants sont toutes des variables aléatoires exponentielles avec les paramètres λ1 = 0,1, λ2 = 0,2, λ3 = 0,3, λ4 = 0,4 et λ5 = 0,5 min − 1, respectivement (le jth help desk assistant a λk = k / 10 min − 1). Outre les clients assistés, jusqu'à dix autres clients peuvent être mis en attente. Lorsque cette capacité est atteinte, les nouveaux appelants reçoivent un signal occupé. Utilisez les méthodes de Monte Carlo pour estimer les caractéristiques de performance suivantes,
a) la fraction de clients qui reçoivent un signal occupé;
(b) le temps de réponse attendu;
c) le temps d'attente moyen;
d) la proportion de clients servis par chaque assistant du service d'assistance;
EDIT: ce que j'ai jusqu'à présent est (pas beaucoup):
pa = 1/45sec-1
jobs = rep(1,5); onHold = rep(1,10);
jobsIndex = 0;
onHoldIndex = 0;
u = runif(1)
for (i in 1:1000) {
if(u <= pa){ # new arrival
if(jobsIndex < 5) # assistant is free, #give job to assistant
jobsIndex++;
else #add to onHold array
onHoldIndex++;
}
}
la source
Réponses:
C'est l'un des types de simulation les plus instructifs et amusants à effectuer: vous créez des agents indépendants dans l'ordinateur, les laissez interagir, gardez une trace de ce qu'ils font et étudiez ce qui se passe. C'est une merveilleuse façon d'en apprendre davantage sur les systèmes complexes, en particulier (mais sans s'y limiter) ceux qui ne peuvent pas être compris avec une analyse purement mathématique.
La meilleure façon de construire de telles simulations est la conception descendante.
Au plus haut niveau, le code devrait ressembler à quelque chose
(Cet exemple et tous les exemples suivants sont du code exécutable
R
, pas seulement du pseudo-code.) La boucle est une simulation événementielle :get.next.event()
trouve tout "événement" d'intérêt et en transmet une descriptionprocess
, ce qui en fait quelque chose (y compris la journalisation de tout informations à ce sujet). Il revientTRUE
tant que les choses fonctionnent bien; lors de l'identification d'une erreur ou de la fin de la simulation, il revientFALSE
, terminant la boucle.Si nous imaginons une implémentation physique de cette file d'attente, comme des personnes attendant un permis de mariage à New York ou un permis de conduire ou un billet de train presque n'importe où, nous pensons à deux types d'agents: les clients et les "assistants" (ou serveurs) . Les clients s'annoncent en se présentant; les assistants annoncent leur disponibilité en allumant une lumière ou une pancarte ou en ouvrant une fenêtre. Ce sont les deux types d'événements à traiter.
L'environnement idéal pour une telle simulation est un véritable environnement orienté objet dans lequel les objets sont mutables : ils peuvent changer d'état pour répondre indépendamment aux choses qui les entourent.
R
est absolument terrible pour cela (même Fortran serait mieux!). Cependant, nous pouvons toujours l'utiliser si nous y prenons garde. L'astuce consiste à conserver toutes les informations dans un ensemble commun de structures de données accessibles (et modifiées) par de nombreuses procédures distinctes et interactives. J'adopterai la convention d'utilisation des noms de variables EN TOUTES MAJUSCULES pour ces données.Le niveau suivant de la conception descendante consiste à coder
process
. Il répond à un seul descripteur d'événemente
:Il doit répondre à un événement nul lorsqu'il
get.next.event
n'a aucun événement à signaler. Sinon,process
implémente les "règles métier" du système. Il s'écrit pratiquement à partir de la description de la question. Comment cela fonctionne devrait nécessiter peu de commentaires, sauf pour souligner que nous devrons éventuellement coder des sousput.on.hold
- routines etrelease.hold
(implémenter une file d'attente client) etserve
(implémenter les interactions client-assistant).Qu'est-ce qu'un "événement"? Il doit contenir des informations sur qui agit, sur le type d’action qu’il entreprend et sur le moment où il se produit. Mon code utilise donc une liste contenant ces trois types d'informations. Cependant, il
get.next.event
suffit d'inspecter les temps. Il est uniquement responsable du maintien d'une file d'attente d'événements dans lesquelsTout événement peut être placé dans la file d'attente lors de sa réception et
Le premier événement de la file d'attente peut facilement être extrait et transmis à l'appelant.
La meilleure implémentation de cette file d'attente prioritaire serait un tas, mais c'est trop difficile
R
. Suite à une suggestion dans The Art of R Programming de Norman Matloff (qui propose un simulateur de file d'attente plus flexible, abstrait mais limité), j'ai utilisé un bloc de données pour contenir les événements et simplement le rechercher le temps minimum parmi ses enregistrements.Il y a plusieurs façons de coder cela. La version finale présentée ici reflète un choix que j'ai fait en codant comment
process
réagit à un événement "Assistant" et commentnew.customer
fonctionne: ilget.next.event
suffit de retirer un client de la file d'attente, puis de s'asseoir et d'attendre un autre événement. Il sera parfois nécessaire de rechercher un nouveau client de deux manières: premièrement, pour voir si l'on attend à la porte (pour ainsi dire) et deuxièmement, si on est entré alors que nous ne regardions pas.De toute évidence,
new.customer
etnext.customer.time
sont des routines importantes , alors prenons-en soin ensuite.CUSTOMERS
est un tableau 2D, avec des données pour chaque client en colonnes. Il comporte quatre lignes (faisant office de champs) qui décrivent les clients et enregistrent leurs expériences au cours de la simulation : "Arrivé", "Servi", "Durée" et "Assistant" (un identificateur numérique positif de l'assistant, le cas échéant, qui a servi et sinon-1
pour les signaux occupés). Dans une simulation très flexible, ces colonnes seraient générées dynamiquement, mais en raison de la façon dontR
aime travailler, il est pratique de générer tous les clients au départ, dans une seule grande matrice, avec leurs heures d'arrivée déjà générées au hasard.next.customer.time
peut jeter un œil à la colonne suivante de cette matrice pour voir qui vient ensuite. La variable globaleCUSTOMER.COUNT
indique le dernier client arrivé. Les clients sont gérés très simplement au moyen de ce pointeur, l'avançant pour obtenir un nouveau client et regardant au-delà (sans avancer) pour jeter un coup d'œil au client suivant.serve
implémente les règles métier dans la simulation.C'est simple.
ASSISTANTS
est une trame de données avec deux champs:capabilities
(donnant leur taux de service) etavailable
, qui marque la prochaine fois que l'assistant sera libre. Un client est servi en générant une durée de service aléatoire en fonction des capacités de l'assistant, en mettant à jour l'heure à laquelle l'assistant devient disponible et en enregistrant l'intervalle de service dans laCUSTOMERS
structure de données. LeVERBOSE
drapeau est pratique pour les tests et le débogage: lorsqu'il est vrai, il émet un flux de phrases en anglais décrivant les points de traitement clés.La façon dont les assistants sont affectés aux clients est importante et intéressante. On peut imaginer plusieurs procédures: assignation au hasard, par une commande fixe, ou selon qui a été libre le plus longtemps (ou le plus court). Beaucoup d'entre eux sont illustrés dans du code commenté:
Le reste de la simulation n'est en fait qu'un exercice de routine pour persuader
R
de mettre en œuvre des structures de données standard, principalement un tampon circulaire pour la file d'attente en attente. Parce que vous ne voulez pas vous fâcher avec les globaux, j'ai mis tout cela en une seule procéduresim
. Ses arguments décrivent le problème: le nombre de clients à simuler (n.events
), le taux d'arrivée des clients, les capacités des assistants et la taille de la file d'attente (qui peut être définie sur zéro pour éliminer complètement la file d'attente).Il renvoie une liste des structures de données maintenues pendant la simulation; le plus intéressant est le50 250
CUSTOMERS
tableau.R
permet de tracer assez facilement les informations essentielles dans ce tableau de manière intéressante. Voici une sortie montrant les derniers clients dans une simulation plus longue de clients.250L'expérience de chaque client est tracée sous la forme d'une ligne de temps horizontale, avec un symbole circulaire au moment de l'arrivée, une ligne noire continue pour toute attente, et une ligne colorée pour la durée de leur interaction avec un assistant (la couleur et le type de ligne différencier les assistants). Sous ce graphique des clients se trouve celui montrant les expériences des assistants, marquant les moments où ils étaient et n'étaient pas engagés avec un client. Les points limites de chaque intervalle d'activité sont délimités par des barres verticales.
Lorsqu'il est exécuté avec
verbose=TRUE
, la sortie texte de la simulation ressemble à ceci:(Les nombres à gauche sont les heures d'émission de chaque message.) Vous pouvez faire correspondre ces descriptions aux parties du tracé Clients situées entre les heures et .165160 165
Nous pouvons étudier l'expérience des clients en attente en traçant les durées d'attente par identifiant client, en utilisant un symbole spécial (rouge) pour montrer aux clients qui reçoivent un signal occupé.
(Tous ces graphiques ne feraient-ils pas un merveilleux tableau de bord en temps réel pour quiconque gère cette file d'attente de services!)
Il est fascinant de comparer les graphiques et les statistiques que vous obtenez en variant les paramètres transmis
sim
. Que se passe-t-il lorsque les clients arrivent trop rapidement pour être traités? Que se passe-t-il lorsque la file d'attente est réduite ou supprimée? Qu'est-ce qui change lorsque les assistants sont sélectionnés de différentes manières? Comment le nombre et les capacités des assistants influencent-ils l'expérience client? Quels sont les points critiques où certains clients commencent à se faire refuser ou à se mettre en attente pendant longtemps?Normalement, pour des questions d'autoformation évidentes comme celle-ci, nous nous arrêterions ici et laisserions les détails restants comme un exercice. Cependant, je ne veux pas décevoir les lecteurs qui sont peut-être allés si loin et qui sont intéressés à essayer cela par eux-mêmes (et peut-être à le modifier et à le développer à d'autres fins), donc ci-dessous est le code de travail complet.
(Le traitement sur ce site gâchera l'indentation sur toutes les lignes contenant un symbole , mais l'indentation lisible doit être restaurée lorsque le code est collé dans un fichier texte.)$TEX $
la source
R
qui débutent et qui souhaitent une autre perspective (mais assez similaire) sur les simulations de files d'attente. En écrivant ce petit simulateur, je me suis beaucoup réfléchi à ce que j'avais appris en étudiant le code dans (la première édition de) le texte d' Andrew Tanenbaum Operating Systems / Design and Implementation. J'ai également appris des structures de données pratiques, telles que des tas, grâce aux articles de Jon Bentley dans CACM et sa série de livres Programming Pearls . Tanenbaum et Bentley sont de grands auteurs que tout le monde devrait lire.