A Single Server Queue A Single Server Queue Section 1 2 Discrete Event Simulation A First Course Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Section 1 2 A Single Server Queue arrivals queue server departures service node Single sever service node consists of a server plus its queue If only one service technician the machine shop model from section 1 1 is a single server queue Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Queue Discipline Queue discipline the algorithm used when a job is selected from the queue to enter service FIFO first in first out LIFO last in first out SIRO serve in random order Priority typically shortest job first SJF Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Assumptions FIFO is also known as first come first serve FCFS The order of arrival and departure are the same This observation can be used to simplify the simulation Unless otherwise specified assume FIFO with infinite queue capacity Service is non preemptive Once initiated service of a job will continue until completion Service is conservative Server will never remain idle if there is one or more jobs in the service node Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Specification Model For a job i The arrival time is ai The delay in the queue is di The time that service begins is bi ai di The service time is si The wait in the node is wi di si The departure time is ci ai wi wi di si ai Section 1 2 A Single Server Queue bi time ci Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Arrivals The interarrival time between jobs i 1 and i is ri ai ai 1 where by definition a0 0 ri ai 2 ai 1 ai time ai 1 Note that ai ai 1 ri and so by induction ai r1 r2 ri Section 1 2 A Single Server Queue i 1 2 3 Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Algorithmic Question Given the arrival times and service times can the delay times be computed For some queue disciplines this question is difficult to answer If the queue discipline is FIFO di is determined by when ai occurs relative to ci 1 There are two cases to consider Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Cases If ai ci 1 job i arrives before job i 1 completes di 1 si 1 ci 1 ai 1 bi 1 t ci bi si ri di ai If ai ci 1 job i arrives after job i 1 completes di 1 si 1 ci 1 ai 1 bi 1 ai t ci si ri Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Calculating Delay for Each Job Algorithm 1 2 1 c0 0 0 assumes that a0 0 0 i 0 while more jobs to process i ai GetArrival if ai ci 1 di ci 1 ai else di 0 0 si GetService ci ai di si n i return d1 d2 dn Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Example 1 2 2 Algorithm 1 2 1 used to process n 10 jobs read from file from algorithm read from file i ai di si 1 15 0 43 2 47 11 36 3 71 23 34 4 111 17 30 5 123 35 38 6 152 44 40 7 166 70 31 8 226 41 29 9 310 0 36 10 320 26 30 For future reference note that for the last job an 320 cn an dn sn 320 26 30 376 Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Output Statistics The purpose of simulation is insight gained by looking at statistics The importance of various statistics varies on perspective Job perspective wait time is most important Manager perspective utilization is critical Statistics are broken down into two categories Job averaged statistics Time averaged statistics Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Job Averaged Statistics Job averaged statistics computed via typical arithmetic mean Average interarrival time n r 1X an ri n n i 1 1 r is the arrival rate Average service time n 1X s si n i 1 1 s is the service rate Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Example 1 2 3 For the 10 jobs in Example 1 2 2 average interarrival time is r an n 320 10 32 0 seconds per job average service is s 34 7 seconds per job arrival rate is 1 r 0 031 jobs per second service rate is 1 s 0 029 jobs per second The server is not quite able to process jobs at the rate they arrive on average Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Job Averaged Statistics The average delay and average wait are defined as n d 1X di n n w i 1 1X wi n i 1 Recall wi di si for all i n n n n i 1 i 1 i 1 i 1 1X 1X 1X 1X w wi di si di si d s n n n n Sufficient to compute any two of w d s Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Example 1 2 4 From the data in Example 1 2 2 d 26 7 From Example 1 2 3 s 34 7 Therefore w 26 7 34 7 61 4 Recall verification is one difficult step of model development Consistency check used to verify that a simulation satisfies known equations Compute w d and s independently Then verify that w d s Section 1 2 A Single Server Queue Discrete Event Simulation c 2006 Pearson Ed Inc 0 13 142917 5 A Single Server Queue Time Averaged Statistics Time averaged statistics defined by area under a curve integration For SSQ need three additional functions l t number of jobs in the service node at time t q t number of jobs in the queue at time t x t number of jobs …