I am trying to solve the following exercise but I actually have no clue on how to start doing this. I've found some code in my book that looks like it but it's a completely different exercise and I don't know how to relate them to eachother. How can I start simulating arrivals and how do I know when they are finished? I know how to store them and calculate a,b,c,d according to that. But I don't know how I actually need to simulate the monte carlo simulation.
Could someone please help me get started? I know this isn't a place where your questions get answered for you but only solved instead. But the problem is I don't know how to start.
An IT support help desk represents a queuing system with five
assistants taking calls from customers. The calls occur according to a Poisson process with
the average rate of one call every 45 seconds. The service times for the 1st, 2nd, 3rd, 4th, and
5th assistants are all Exponential random variables with parameters λ1 = 0.1, λ2 = 0.2,
λ3 = 0.3, λ4 = 0.4, and λ5 = 0.5 min−1, respectively (the jth help desk assistant has
λk = k/10 min−1). Besides the customers who are being assisted, up to ten other customers
can be placed on hold. At times when this capacity is reached, the new callers receive a
busy signal.
Use the Monte Carlo methods to estimate the following performance characteristics,
(a) the fraction of customers who receive a busy signal;
(b) the expected response time;
(c) the average waiting time;
(d) the portion of customers served by each help desk assistant;
EDIT : what I have so far is (not much) :
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++;
}
}
Best Answer
This is one of the most instructive and fun kinds of simulation to perform: you create independent agents in the computer, let them interact, keep track of what they do, and study what happens. It is a marvelous way to learn about complex systems, especially (but not limited to) those that cannot be understood with purely mathematical analysis.
The best way to construct such simulations is with top-down design.
At the very highest level the code should look something like
(This and all subsequent examples are executable
R
code, not just pseudo-code.) The loop is an event-driven simulation:get.next.event()
finds any "event" of interest and passes a description of it toprocess
, which does something with it (including logging any information about it). It returnsTRUE
for as long as things are running well; upon identifying an error or the end of the simulation, it returnsFALSE
, ending the loop.If we imagine a physical implementation of this queue, such as people waiting for a marriage license in New York City or for a driver's license or train ticket almost anywhere, we think of two kinds of agents: customers and "assistants" (or servers). Customers announce themselves by showing up; assistants announce their availability by turning on a light or sign or opening a window. These are the two kinds of events to process.
The ideal environment for such a simulation is a true object-oriented one in which objects are mutable: they can change state to respond independently to things around them.
R
is absolutely terrible for this (even Fortran would be better!). However, we can still use it if we take some care. The trick is to maintain all the information in a common set of data structures that can be accessed (and modified) by many separate, interacting procedures. I will adopt the convention of using variable names IN ALL CAPS for such data.The next level of the top-down design is to code
process
. It responds to a single event descriptore
:It has to respond to a null event when
get.next.event
has no events to report. Otherwise,process
implements the "business rules" of the system. It practically writes itself from the description in the question. How it works should require little comment, except to point out that eventually we will need to code subroutinesput.on.hold
andrelease.hold
(implementing a customer-holding queue) andserve
(implementing the customer-assistant interactions).What is an "event"? It must contain information about who is acting, what kind of action they are taking, and when it is occurring. My code therefore uses a list containing these three kinds of information. However,
get.next.event
only needs to inspect the times. It is responsible only for maintaining a queue of events in whichAny event can be put into the queue when it is received and
The earliest event in the queue can easily be extracted and passed to the caller.
The best implementation of this priority queue would be a heap, but that's too fussy in
R
. Following a suggestion in Norman Matloff's The Art of R Programming (who offers a more flexible, abstract, but limited queue simulator), I have used a data frame to hold the events and simply search it for the minimum time among its records.There are many ways this could have been coded. The final version shown here reflects a choice I made in coding how
process
reacts to an "Assistant" event and hownew.customer
works:get.next.event
merely takes a customer out of the hold queue, then sits back and waits for another event. It will sometimes be necessary to look for a new customer in two ways: first, to see whether one is waiting at the door (as it were) and second, whether one has come in when we weren't looking.Clearly,
new.customer
andnext.customer.time
are important routines, so let's take care of them next.CUSTOMERS
is a 2D array, with data for each customer in columns. It has four rows (acting as fields) that describe customers and record their experiences during the simulation: "Arrived", "Served", "Duration", and "Assistant" (a positive numerical identifier of the assistant, if any, who served them, and otherwise-1
for busy signals). In a highly flexible simulation these columns would be dynamically generated, but due to howR
likes to work it's convenient to generate all customers at the outset, in a single large matrix, with their arrival times already generated at random.next.customer.time
can peek at the next column of this matrix to see who's coming next. The global variableCUSTOMER.COUNT
indicates the last customer to arrive. Customers are managed very simply by means of this pointer, advancing it to obtain a new customer and looking beyond it (without advancing) to peek at the next customer.serve
implements the business rules in the simulation.This is straightforward.
ASSISTANTS
is a dataframe with two fields:capabilities
(giving their service rate) andavailable
, which flags the next time at which the assistant will be free. A customer is served by generating a random service duration according to the assistant's capabilities, updating the time when the assistant next becomes available, and logging the service interval in theCUSTOMERS
data structure. TheVERBOSE
flag is handy for testing and debugging: when true, it emits a stream of English sentences describing the key processing points.How assistants are assigned to customers is important and interesting. One can imagine several procedures: assignment at random, by some fixed ordering, or according to who has been free the longest (or shortest) time. Many of these are illustrated in commented-out code:
The rest of the simulation is really just a routine exercise in persuading
R
to implement standard data structures, principally a circular buffer for the on-hold queue. Because you don't want to run amok with globals, I put all of these into a single proceduresim
. Its arguments describe the problem: the number of customers to simulate (n.events
), the customer arrival rate, the assistants' capabilities, and the size of the hold queue (which can be set to zero to eliminate the queue altogether).It returns a list of the data structures maintained during the simulation; the one of greatest interest is the
CUSTOMERS
array.R
makes it fairly easy to plot the essential information in this array in an interesting way. Here is one output showing the last $50$ customers in a longer simulation of $250$ customers.Each customer's experience is plotted as a horizontal time line, with a circular symbol at the time of arrival, a solid black line for any waiting on hold, and a colored line for the duration of their interaction with an assistant (the color and line type differentiate among the assistants). Beneath this Customers plot is one showing the experiences of the assistants, marking the times when they were and were not engaged with a customer. The endpoints of each interval of activity are delimited by vertical bars.
When run with
verbose=TRUE
, the simulation's text output looks like this:(Numbers at the left are the times each message was emitted.) You can match these descriptions to the portions of the Customers plot lying between times $160$ and $165$.
We can study the customers' experience on hold by plotting on-hold durations by customer identifier, using a special (red) symbol to show customers receiving a busy signal.
(Wouldn't all these plots make a wonderful real-time dashboard for anybody managing this service queue!)
It is fascinating to compare the plots and statistics that you get upon varying the parameters passed to
sim
. What happens when customers arrive too quickly to be processed? What happens when the hold queue is made smaller or eliminated? What changes when assistants are selected in different manners? How do the numbers and capabilities of the assistants influence the customer experience? What are the critical points where some customers start getting turned away or start getting put on hold for long times?Normally, for evident self-study questions like this one, we would stop here and leave the remaining details as an exercise. However, I do not want to disappoint readers who may have gotten this far and are interested in trying this out for themselves (and maybe modifying it and building on it for other purposes), so appended below is the full working code.
(The $\TeX$ processing on this site will mess up the indentation at any lines containing a $\$$ symbol, but readable indentation should be restored when the code is pasted into a text file.)