Ich versuche, die folgende Übung zu lösen, habe aber keine Ahnung, wie ich damit anfangen soll. Ich habe in meinem Buch einen Code gefunden, der so aussieht, aber es ist eine völlig andere Übung, und ich weiß nicht, wie ich sie miteinander in Beziehung setzen soll. Wie kann ich mit der Simulation von Ankünften beginnen und woher weiß ich, wann sie fertig sind? Ich weiß, wie man sie speichert und a, b, c, d danach berechnet. Aber ich weiß nicht, wie ich die Monte-Carlo-Simulation tatsächlich simulieren muss. Könnte mir bitte jemand beim Einstieg helfen? Ich weiß, dass dies kein Ort ist, an dem Ihre Fragen für Sie beantwortet, sondern nur gelöst werden. Aber das Problem ist, dass ich nicht weiß, wie ich anfangen soll.
Ein IT-Support-Helpdesk stellt ein Warteschlangensystem dar, in dem fünf Assistenten Anrufe von Kunden entgegennehmen. Die Anrufe erfolgen nach einem Poisson-Prozess mit einer durchschnittlichen Rate von einem Anruf alle 45 Sekunden. Die Servicezeiten für den 1., 2., 3., 4. und 5. Assistenten sind alle exponentielle Zufallsvariablen mit den Parametern λ1 = 0,1, λ2 = 0,2, λ3 = 0,3, λ4 = 0,4 bzw. λ5 = 0,5 min - 1 (die Der j-te Helpdesk-Assistent hat λk = k / 10 min - 1). Neben den Kunden, die unterstützt werden, können bis zu zehn weitere Kunden in die Warteschleife gestellt werden. Zu Zeiten, in denen diese Kapazität erreicht ist, erhalten die neuen Anrufer ein Besetztzeichen. Verwenden Sie die Monte-Carlo-Methoden, um die folgenden Leistungsmerkmale abzuschätzen:
(a) der Anteil der Kunden, die ein Besetztzeichen erhalten;
(b) die erwartete Antwortzeit;
(c) die durchschnittliche Wartezeit;
(d) den Anteil der Kunden, die von jedem Helpdesk-Assistenten bedient werden;
EDIT: was ich bisher habe ist (nicht viel):
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++;
}
}
quelle
Antworten:
Dies ist eine der lehrreichsten und unterhaltsamsten Arten von Simulationen: Sie erstellen unabhängige Agenten im Computer, lassen sie interagieren, verfolgen, was sie tun, und untersuchen, was passiert. Es ist eine wunderbare Möglichkeit, komplexe Systeme kennenzulernen, insbesondere (aber nicht ausschließlich) solche, die mit rein mathematischer Analyse nicht verstanden werden können.
Der beste Weg, solche Simulationen zu erstellen, ist das Top-Down-Design.
Auf der höchsten Ebene sollte der Code ungefähr so aussehen
(Dieses und alle nachfolgenden Beispiele sind ausführbarer
R
Code, nicht nur Pseudocode.) Die Schleife ist eine ereignisgesteuerte Simulation: Sieget.next.event()
findet jedes "Ereignis" von Interesse und übergibt eine Beschreibung davon anprocess
, die etwas damit zu tun hat (einschließlich der Protokollierung eines beliebigen) Informationen darüber). Es kehrt zurück,TRUE
solange die Dinge gut laufen. Wenn ein Fehler oder das Ende der Simulation identifiziert wird, kehrt er zurückFALSE
und beendet die Schleife.Wenn wir uns eine physische Implementierung dieser Warteschlange vorstellen, z. B. Menschen, die fast überall in New York auf eine Heiratsurkunde oder auf einen Führerschein oder eine Fahrkarte warten, denken wir an zwei Arten von Agenten: Kunden und "Assistenten" (oder Server). . Kunden melden sich an, indem sie auftauchen; Assistenten geben ihre Verfügbarkeit bekannt, indem sie ein Licht oder ein Schild einschalten oder ein Fenster öffnen. Dies sind die beiden Arten von Ereignissen, die verarbeitet werden müssen.
Die ideale Umgebung für eine solche Simulation ist eine echte objektorientierte Umgebung, in der Objekte veränderlich sind : Sie können den Zustand ändern, um unabhängig auf Dinge um sie herum zu reagieren.
R
ist absolut schrecklich dafür (sogar Fortran wäre besser!). Wir können es jedoch weiterhin verwenden, wenn wir vorsichtig sind. Der Trick besteht darin, alle Informationen in einem gemeinsamen Satz von Datenstrukturen zu verwalten, auf die durch viele separate, interagierende Verfahren zugegriffen (und geändert) werden kann. Ich werde die Konvention der Verwendung von Variablennamen IN ALL CAPS für solche Daten übernehmen.Die nächste Ebene des Top-Down-Designs ist das Codieren
process
. Es reagiert auf einen einzelnen Ereignisdeskriptore
:Es muss auf ein Nullereignis reagieren, wenn
get.next.event
keine Ereignisse zu melden sind. Andernfalls werdenprocess
die "Geschäftsregeln" des Systems implementiert. Es schreibt sich praktisch aus der Beschreibung in der Frage. Wie es funktioniert, sollte wenig Kommentar erfordern, außer um darauf hinzuweisen, dass wir schließlich Unterprogrammeput.on.hold
undrelease.hold
(Implementieren einer Kundenwarteschlange) undserve
(Implementieren der Kunden-Assistenten-Interaktionen) codieren müssen .Was ist ein "Ereignis"? Es muss Informationen darüber enthalten, wer handelt, welche Art von Maßnahmen sie ergreifen und wann sie stattfinden. Mein Code verwendet daher eine Liste mit diesen drei Arten von Informationen. Muss jedoch
get.next.event
nur die Zeiten überprüfen. Es ist nur für die Aufrechterhaltung einer Warteschlange von Ereignissen verantwortlich, in denenJedes Ereignis kann in die Warteschlange gestellt werden, wenn es empfangen wird und
Das früheste Ereignis in der Warteschlange kann einfach extrahiert und an den Anrufer übergeben werden.
Die beste Implementierung dieser Prioritätswarteschlange wäre ein Haufen, aber das ist zu pingelig
R
. Nach einem Vorschlag in Norman Matloffs The Art of R Programming (der einen flexibleren, abstrakteren, aber begrenzten Warteschlangensimulator bietet) habe ich einen Datenrahmen verwendet, um die Ereignisse zu speichern und sie einfach nach der minimalen Zeit in den Datensätzen zu durchsuchen.Es gibt viele Möglichkeiten, wie dies codiert werden könnte. Die hier gezeigte endgültige Version spiegelt eine Entscheidung wider, die ich beim Codieren getroffen habe, wie
process
auf ein "Assistent" -Ereignis reagiert und wie esnew.customer
funktioniert:get.next.event
Nimmt lediglich einen Kunden aus der Warteschlange, lehnt sich zurück und wartet auf ein anderes Ereignis. Es wird manchmal notwendig sein, auf zwei Arten nach einem neuen Kunden zu suchen: erstens, um zu sehen, ob einer an der Tür wartet (sozusagen) und zweitens, ob man hereingekommen ist, als wir nicht gesucht haben.Klar,
new.customer
undnext.customer.time
sind wichtige Routinen , also kümmern wir uns als nächstes um sie.CUSTOMERS
ist ein 2D-Array mit Daten für jeden Kunden in Spalten. Es verfügt über vier Zeilen (als Felder), die Kunden beschreiben und ihre Erfahrungen während der Simulation aufzeichnen : "Angekommen", "Bedient", "Dauer" und "Assistent" (eine positive numerische Kennung des Assistenten, falls vorhanden, der gedient hat) sie und sonst-1
für Besetztzeichen). In einer hochflexiblen Simulation würden diese Spalten dynamisch generiert. Aufgrund derR
Arbeitsweise ist es jedoch praktisch, alle Kunden zu Beginn in einer einzigen großen Matrix zu generieren, deren Ankunftszeiten bereits zufällig generiert wurden.next.customer.time
Ich kann in die nächste Spalte dieser Matrix schauen, um zu sehen, wer als nächstes kommt. Die globale VariableCUSTOMER.COUNT
gibt den zuletzt ankommenden Kunden an. Kunden werden sehr einfach mit diesem Zeiger verwaltet, indem sie ihn weiterentwickeln, um einen neuen Kunden zu gewinnen, und darüber hinaus schauen (ohne voranzukommen), um einen Blick auf den nächsten Kunden zu werfen.serve
implementiert die Geschäftsregeln in der Simulation.Das ist unkompliziert.
ASSISTANTS
ist ein Datenrahmen mit zwei Feldern:capabilities
(unter Angabe der Servicerate) undavailable
, der das nächste Mal markiert , wenn der Assistent frei ist. Ein Kunde wird bedient, indem eine zufällige Servicedauer gemäß den Fähigkeiten des Assistenten generiert, die Zeit aktualisiert wird, zu der der Assistent das nächste Mal verfügbar ist, und das Serviceintervall in derCUSTOMERS
Datenstruktur protokolliert wird . DasVERBOSE
Flag ist praktisch zum Testen und Debuggen: Wenn true, wird ein Strom englischer Sätze ausgegeben, die die wichtigsten Verarbeitungspunkte beschreiben.Wie Assistenten den Kunden zugewiesen werden, ist wichtig und interessant. Man kann sich mehrere Verfahren vorstellen: zufällige Zuordnung, durch eine feste Reihenfolge oder je nachdem, wer die längste (oder kürzeste) Zeit frei hatte. Viele davon sind in auskommentiertem Code dargestellt:
Der Rest der Simulation ist eigentlich nur eine Routineübung , um
R
zu überzeugen , Standarddatenstrukturen zu implementieren, hauptsächlich einen kreisförmigen Puffer für die Warteschlange in der Warteschleife. Da Sie nicht mit Globals Amok laufen möchten, habe ich all dies in einer einzigen Prozedur zusammengefasstsim
. Seine Argumente beschreiben das Problem: die Anzahl der zu simulierenden Kunden (n.events
), die Kundenankunftsrate, die Fähigkeiten der Assistenten und die Größe der Warteschlange (die auf Null gesetzt werden kann, um die Warteschlange insgesamt zu beseitigen).CUSTOMERS
R
Die Erfahrung jedes Kunden wird als horizontale Zeitlinie mit einem kreisförmigen Symbol zum Zeitpunkt der Ankunft, einer durchgezogenen schwarzen Linie für Wartezeiten und einer farbigen Linie für die Dauer der Interaktion mit einem Assistenten (Farbe und Linientyp) dargestellt zwischen den Assistenten unterscheiden). Unter diesem Kundenplot befindet sich einer, der die Erfahrungen der Assistenten zeigt und die Zeiten angibt, zu denen sie mit einem Kunden beschäftigt waren und nicht. Die Endpunkte jedes Aktivitätsintervalls werden durch vertikale Balken begrenzt.
Bei Ausführung mit
verbose=TRUE
sieht die Textausgabe der Simulation folgendermaßen aus:Wir können die Erfahrung der Kunden in der Warteschleife untersuchen, indem wir die Dauer der Warteschleife anhand der Kundenkennung aufzeichnen und ein spezielles (rotes) Symbol verwenden, um Kunden anzuzeigen, die ein Besetztzeichen erhalten.
(Würden nicht alle diese Diagramme ein wunderbares Echtzeit-Dashboard für jeden sein, der diese Servicewarteschlange verwaltet!)
Es ist faszinierend, die Diagramme und Statistiken zu vergleichen, die Sie erhalten, wenn Sie die übergebenen Parameter variieren
sim
. Was passiert, wenn Kunden zu schnell ankommen, um bearbeitet zu werden? Was passiert, wenn die Warteschlange kleiner oder kleiner wird? Was ändert sich, wenn Assistenten auf unterschiedliche Weise ausgewählt werden? Wie beeinflussen die Anzahl und die Fähigkeiten der Assistenten das Kundenerlebnis? Was sind die kritischen Punkte, an denen einige Kunden abgewiesen oder für längere Zeit in die Warteschleife gelegt werden?Normalerweise würden wir bei offensichtlichen Fragen zum Selbststudium wie dieser hier anhalten und die verbleibenden Details als Übung belassen. Ich möchte jedoch Leser nicht enttäuschen, die möglicherweise so weit gekommen sind und daran interessiert sind, dies selbst auszuprobieren (und es möglicherweise zu ändern und für andere Zwecke darauf aufzubauen). Im Folgenden finden Sie den vollständigen Arbeitscode.
quelle
R
, die eine andere (aber ziemlich ähnliche) Perspektive auf Warteschlangensimulationen wünschen. Während ich diesen kleinen Simulator schrieb, dachte ich viel darüber nach, wie viel ich durch das Studium des Codes in (der ersten Ausgabe von) Andrew Tanenbaums Text Betriebssysteme / Design und Implementierung gelernt habe . Ich habe auch praktische Datenstrukturen wie Haufen aus Jon Bentleys Artikeln in CACM und seiner Buchreihe Programming Pearls gelernt . Tanenbaum und Bentley sind großartige Autoren, die jeder lesen sollte.