SIMULATION EXAMPLES Simulation of Queuing Systems The queuing or waiting-line system may be described as follows: +A facility or group of facilities is maintained to meet the demand for service created by a population of individuals called units. These units form a queue or waiting line and receive service in accordance with a predetermined waiting-line discipline (FIFO/LIFO/Priority Queue/RAN). In most cases, the served units rejoin (with replacement) the population and again become candidates for service. + The primary objective of the queuing system is to meet the demand for service at minimum cost. Some Popular Queuing Systems ystem ‘Customers _Server(s, Reception desk People Receptionist Repair facity Mechines Repairperson lsarage Trucks Mechanic hwarenouse Pallets Crane fsirport Airplanes Runway road network cars Traffic light lcrocery shoppers Checkout counters Jcomputer obs CPU, disk [retepnone calls exchange Iricket office Cricket fans Clerk Mess transit Riders BusesTypes of Queuing Systems — Single server queues = Multi-server queues How to run a = Manually - using simulation tables - Through Computer- Using a simulator or a language Simpk ing System pre-assumption: ~A Queuing System includes a server, unit being serviced, & units in the queue -Infinite Calling population; means if a unit leaves the calling population and joins the waiting line or enters service, there is no change in the arrival rate of other units that may need service i.e; probability of occurrence is equally likely -Event: a set of circumstances that cause an instantaneous change in the state of the system ~Event occurs: arrival or departure -State variables: # of units in the system & the status of server, busy or idle -Arrivals of units in random fashion, one at a time, described by a distribution of the time between arrivals -Service times are of of random length according to a probability distribution and does not change over time -Unlimited system capacity -Single channel FIFO service -Overalll effective arrival rate < maximum service rate (otherwise unstable)- In a single channel queuing system there are only two possible events; the arrival event and the departure event + Simulations of queuing systems generally require the maintenance of an event list in the form of table to indicate the times at which the different types of event occur for each unit in the queuing system + The events usually occur at random to portray uncertainty # The randomness needed to imitate real life is made possible through the use of. random numbers Example: simple queueing system + Queueing system: — unit population, nature of anivals, service mechanism, system capacity, ‘ueuing discipline Waiting line Customer population - infinite € at given time Tavidom service times rice discipline a : Priority queue, FIFO, —_LIFO, ee (frat in, rst out) (last in, first out) Note: Average arrival rate < average service rate why? 5A Single Channel Queuing system components Static Entities: server, queue State Variables: Number of units (customers for the bank example) in the system, Q Server status: busy/idle, S = {B, I}. Events: Arrivals Departures Simulation clock: tracks simulated time Actions: Different actions, depending on the type of the event (arrival or departure) and the current system state Flowcharts for actions following both arrival and departure events are as follows:Flowchart for departure pamenin)~ <> EEE Begin saraeing the unt Howdace system ato chara? Wowuor eds =o a= 0,001 Fre theos vale 1-0, G0, 5-87 Wa yoe=o1S=17) * Flowchart for arrival arco PAE , Customer / FIFO Leaves the bank Random inter-arrival times: | Uniformly distributed on (1.8) | minutes (equal probable) I Random service times Distributed on (1,6) minutesTable (2.6) Table (2.7) DISTRIBUTION OF TIME BETWEEN ARRIVALS _ SERVICE-TIME DISTRIBUTION Time Probability Cumulative Random Service Probability Cumulative Random between (occurrence Probability digit Time (not equaily Probability digit Arrivals of event) assignment | |(minutes) _ likely to assignment (minutes) (equally occur) likely to occur) T 0.125 0.125 001-125 T 0.10 0.10 01-10 2 0.125 0.250 126 - 250 2 0.20 030 11-30 3 0.125 0.375 251-375 3 0.30 0.60 31-60 4 0.125 0.500 376 - S00 4 0.25 0.85 61-85 5 0.125 0.625 501 - 625 5 0.10 0.95 86-95 6 0.125 0.750 626 - 750 6 0.05 1,00 96 - 00 7 0.125 0.875 751-875 8 0.125 1,000 __ 876 - 000 ‘* The random digit assignment columns are used to generate random arrivals and random service times ‘+ Random digits are converted to random numbers by placing the decimal at the appropriate point In this case, three-place random numbers will be sufficient, Three digits are needed since the probability distribution is described with three-digit accuracy There are 1000 three-digit values possible (001 through 000) That is, there are 10 digits (0-9), therefore 10° = 10*10*10=1000 three-digit values possible from 001 through 000‘+ Probability of time between arrival of 1 minute is 0.125, that is 125 of 1000 random digit values are assigned to such an occurrence and so on, described in the above table ‘+ A column of random digit is developed to generate random numbers from table A.1 as in the following table ‘+ List only 19 random numbers to generate time between arrivals The first arrival is assumed to occur at time 0 + Time between arrivals for 19 customers are generated by listing 19 three -digit values from table A.1 and comparing them to the random digit assignment column of above table 2.6 ‘TIME-BETWEEN-ARRIVAL DETERMINATION (Table 2.8) Customer Random Time between] Customer Random Time digits Arrivals digits between (from (minutes) (from Arrivals table A.1) table A.1) (minutes) 7 Si 7 109) 1 2 913 8 2 093 1 3 727 6 3 607 5 4 01s 1 14 738 6 5 48, 8 45 359 3 6 309 3 16 888 8 7 922 8 7 106 1 8 753 7 18 212 2 9 235 2 19 493 4 10 302 3 20 535 5SERVICE TIMES GENERATED (Table 2.9) ‘Similarly from table 2.7 Customer Random Service Time | Customer Rendam Service digits (minutes) digits Time (from (from (minutes) table 4.1, table AL) 7 34 4 iT 32 3 2 10 1 2 94 5 3 74 4 3 79 4 4 53 3 13 05 1 5 7 2 45 79 5 6 73 4 16 84 4 ? 1 5 7 52 3 8 67 4 18 55 3 9 89 5 19 30 2 10 38 3 20 50 3 '¢ The core of a manual simulation is the simulation table. ‘* These tables are designed for the situation at hand and further structured to answer the questions posed How to construct a simulation table? ~ Columns in the table: inputs and response(s) - Rows: repetitions of system operation (because the inputs are changing) - Often, inputs are random variables, and are characterized by probability distributionsExample of a generic simulation table Repetition] i 1SIMULATION TABLE FOR QUEUING PROBLEM (Table 2.10) Be 2 3 4 5 6 ee 8 9 Tastomer Time ance Arrival time Service Time Time Time Time Tete a lastarrval (clock in. time service customer service customer server (inter — minutes) (minutes) begins ‘waits in’ ends spends im (minutes) Arrival) Ce Duration (S+ayit ‘queue (S44) system (5-7) (minutes) >3,7 (minutes) (minutes) else 3 (5-3) (a6) 7 : 7 7 ° ° 7 4 3 2 8 8 i 8 ° 5 i 4 3 6 15 4 14 3 18 4 5 4 3 as 3 18 3 2 8 ° 5 @ 23 2 23 ° 25 2 2 6 3 26 4 26 ° 30 4 1 7 3 3a 5 3a 3 3 5 4 a 7 a 4 41 ° 45 4 2 8 2 3 5 45 2 50 7 3 10 3 45 3 50 4 53 7 ° n 3 47 3 53 6 56 9 ° 2 1 46 5 56 8 61 B ° Fes 5 33 4 61 8 ee 3 14 6 59 1 65 6 68 7 ° 15 3 62 5 66 4 1 3 ° 16 8 70 4 n 1 75 5 ° ” 3 n 3 35 4 % 7 ° 18 2 3 3 Ps 5 a 8 3 19 4 7 2 a1 4 83 6 3 20 5 82 3 83 1 86 4 3 a2 ea 3E Te 16System Statistics Some of the findings from this short-term simulation are as follows: Called estimates of the measures of performance. 1. The average waiting time for a customer is 2.8 minutes. This is determined in the following manner: Average waiting time (minutes) = Total time customers wait in queue (minutes} Total number of customers 56 = 2.8 minutes 20 2. The probability that a customer has to wait in the queue is 0.65. This is determined in the following manner: Probability (wait) = number of customers who wait Total number of customers = 13/20 =0.65 3. The Fraction of idle time for server is 0.21. This is determined in the following manner: total run time of server (minutes) as idle Total run time of simulation (minutes) = 18/86 = 0.21 The probability of the server being busy is the complement of 0.21, or 0.79= (1-0.21). Probability of idle server = P(idle! 4. The average service time is 3.4 minutes. This is determined in the following manner:Average service time (minutes) = total service time (minutes) Total number of customers = 68 / 20 = 3.4 minutes This result can be compared with the expected service time by finding the mean of the service- time distribution using the equation Theoretical mean = Expected service time = E(S)= Es * p(s) ; E(X)= EX * P(X) Applying the expected value equation to the service time distribution in the table gives Expected service time = 1(0.10)+2(0.20)+3(0.30)+4(0.25)+5(0.10)+6(0.05) = 3.2 minutes The expected service time is slightly lower than the average service time in the simulation. The longer the simulation sample size, the closer the average will be to E (S).. . The average time between arrivals is 4.3 minutes. This is determined in the following manner: Average time between arrivals (minute) = Sum of all times between arrivals (minutes) Number of arrivals ~ 1 82 / 19 = 4.3 minutes One is subtracted from the denominator because the first arrival is assumed to occur at time 0. This result can be compared to the expected time between arrivals by finding the mean of the discrete uniform distribution whose end points are a=1 & b=8 (it is used for the integer number varying among a through b but about which little else is known). The mean is given by Theoretical mean = E (A) =a +b= 2 1+8)/2 = 4.5 minutesThe expected time between arrivals is slightly higher than the average. However, in a longer simulation the average value of the time between arrivals should approach the theoretical mean, E(A) . The average waiting time of those who wait is 4.3 minutes. This is determined in the following manner: Average waiting time of those who wait (minutes) ‘Total time customers wait in queue (minutes) = 56 / 13 = 4,3 minutes Total number of customers . The average time a customer spends in the system is 6.2 minutes. This can be determined in 2 ways. First, the computation can be achieved by the following relationship: (i) Average time customer spends in the system (mins) = Total time customer spends in the system (mins) Total number of customers = 124 / 20 = 6.2 minutes (ii) The 2" way of computing the same result is to realize that the following relationship must hold: Average time customer Average time customer Average time customer Spends in the system (min) = spends waiting in the queue (min) + spends in service (min) 56/20 + 68/20 2.8 + 3.4 = 6.2 minutes‘some subjective inferences can be drawn at this point: Most customers have to wait; however the average waiting time is not excessive The server does not have an unjustified amount of idle time Objective function about the results: depends on balancing the cost of waiting with the cost of additional serversWhat if we add another teller? ‘See table for Teller 2/ service times Waiting line Customer leaves the bank FIFO. Random inter-arrival times: Uniformly distributed on (1,8) minutes (equal probable) Teller 2: service time distribution Random service times Distributed on (1,6) minutes Probability Service policy: 035 025 020 020 If both tellers are idle, Teller 1 serves the next customer Otherwise, the customer is served by the next available teller’Simulation table for the bank teller example — two tellersSimulation table for the bank teller example — two tellers Tletme | Active Tt | time T2Queueing statistics comparisons Scenario Queueing time (min) Fraction of idle time teller 1 (min) Fraction of | Fraction of active time | idle time teller 2 teller 2 (min) (min) 1 Teller 0.21 2 TellersWhat if questions - examples + What if you change the service policy ? — If both tellers free, flip a coin and randomly choose one to service the next customer — Add second teller to serve only preferred customers (gold membership) + Two separate lines (queues) + Two queueing times, for regular customers and for gold customers + What if you add a more rapid teller (with a higher salary) instead of the two slower tellers? Which solution is the most economical appealing while guaranteeing good service for customers?Example: Multi-Channel Queue (Two servers single queue) ‘* Consider a drive-in restaurant where carhops take orders & bring food to the car. Cars arrive in the manner shown in the table “Inter arrival distribution of Cars" ‘« Their are two carhops-Able & Baker, Able is better able to do the job, & works somewhat faster than Baker. ‘* The distribution of service times is shown in tables “Service distribution of Able” and “Service distribution of Baker’. ‘+ A simplifying rule is that Able gets customers if both carhops are idle. + The problem is to find how well the current arrangement is working. To es! system measures, a simulation of 1-hour operation will be used. + A longer simulation will be more reliable, but for purposes of illustration 1-hour period has been selected INTERARRIVAL DISTRIBUTION OF CARS Time between | Probability (not) CumulativeRandom digit Arrivals (minutes) equally likely) | Probability Jassignment i 0.25 0.25 [01-25 2 0.40 0.65 [26-65 3 0.20 0.85 (66-85 4 0.15) 1.00 |g6- 00SERVICE DISTRIBUTION OF ABLE SERVICE DISTRIBUTION OF BAKER Service | Probability | Cumulative Random eee | eae | earns eeneon aa Time Probability |digit Time Probability assignment (minutes) lassignment | | (minutes) 2 0.30 0.30__|01 -30 3 0.35 0.35 (01-35 3 0.28 0.58 [31-58 4 0.25 0.60 [36 - 60, 4 0.25 0.83 (59-83 5 0.20 0.80 [61 - 80 5 0.17 1,00___|84— 00 6 0.20 1,00__|81-00SIMULATION TABLE FOR CARHOP EXAMPLE 7 Table 2 3 Table _Able4 Able-S Able-6 Baker? Gaker@ Gakerd 10 Customer | Random |iime | Clock time | Random | Time ] Service ] Time | Time | Service | Time | Timelm digits for \between | of Arrival | digits for | service | time | service | service | time | service | queue arrival. arrivals. | (t-hour | service | begins | (minutes) | ends | begins | (minutes) | ends | (minutes) operation, (see 3) |atrun time| (445) | (see 3) |atrun time| (748) | (4/7-3) = 5 ° 5 3 25 2 z z z 38 Sr = z 30 32 10 5 26. 29 a2 35. is 7 13 18 0 a 20 68 30) 22, ry ea 28 35, 27, 3a 33 5 35 30 2a OL 3 81 35 63 55 35, BL 3 30 64 42 OL a 56. 67 45 38 1 18 a7 w Si 75 7 37 3 16 87 92 47 =Some important findings: # Idle time of Able and Baker (able=6; baker=19) ‘¢ Busy time of Able and Baker (able=56; baker=43) '¢ Average waiting time of all customers in queue = 11/26 = 0.42 minutes ‘¢ Average waiting time of those who waits = 11/9 = 1.22 minutes The analysis of "Simulation table for carhop example” results in the following 1. Over the 62-minute period, Able was busy 90% of the time. (= 56/62) 2. Baker was busy only 69% of the time. The seniority rule keeps Baker less busy. (= 43/62) 3.9 of the 26 arrivals (~35%) had to wait. The average waiting time for all customers was 0.42 minutes, which is very small. 4. Those 9, who did have to wait, only waited an average of 1.22 minutes, which is quite low. Conclusion: ‘+ The system seems well balanced. + One server cannot handle all the diners, and 3 servers would probably be too many. ‘+ Adding an additional server would surely reduce the waiting time to nearly zero. + However, the cost of waiting would have to be quite high to justify an additional server.Simulation of Inventory Systems + ‘An important class of simulation problems involves inventory systems. Concepts of a simple inventory system: . ‘Suppose a distributor maintains an inventory of a particular item, drawing off from inventory to meet customer orders If the distributor is out of stock, the customer will seek another source for the unfilled demand, rather than wait for a back order When the inventory falls bellow a certain level, the distributor orders additional inventory from the manufacturer Each day the distributor receives orders from customers and at the end of the day takes inventory to determine if additional stock should be ordered from the manufacturer (perio: = after 24 hours) If the distributor places an order, it is likely to arrive in some days later The distributor has an inventory policy described by the quantity of the replenishment (re) order and the level of inventory, or reorder point, which triggers a new order to the manufacturer The distributor, when selecting an inventory policy, attempts to trade off the costs of carrying inventory, costs of ordering, penalty costs (associated with not being able to satisfy a customer's order), and so on’ The objective of the distributor is to minimize the total of the carrying, ordering, and penalty costsFormally an inventory system is defined by the figure below: Beginning I End/Bep I End Beg Il End Araeunt in inves This inventory system has a periodic review of length N at which time the inventory level is checked An order is made (placed and received) to bring the inventory up to the level M At the end of the first review period, an order quantity Q, is placed In this inventory system the lead time (length of time between the placement and receipt of an order) is zero Since demands are not usually known with certainty, the order quantities are probabilistic Demands are also not uniform and do fluctuate over time One possibility is that demands all occur at the beginning of the cycle Another realistic possibility is that the lead time is other than zero and probabilistic* In the second cycle, the amount in inventory drops below zero, indicating a shortage # In the figure above, these units are backordered; when the order arrives, the demand for the backordered items is satisfied first Inventory Costs: + Carrying stock in inventory has an associated cost attributed to the interest paid on the funds borrowed to buy the items # It is also considered as the loss from not having the funds available for other investment purposes + Other costs includes: renting of storage space, hiring guards, and so on + An alternative to carrying high inventory is to make more frequent reviews, and consequently, more frequent purchases (reorders) + This has an associated cost: the ordering cost. # Also there is a cost in being short: customers may get angry, with a subsequent loss of good will No doubt; Larger inventories decreases the possibilities of shortages These costs must be traded off in order to minimize the total cost of an inventory system, The total cost (or total profit) of an inventory system is the measure of performance This can be affected by the policy alternatives For example; the decision maker can control the maximum inventory level M, and the length of the cycle N + Inan (M, N) inventory system, the events that may occur are: © The demand for items in the inventory © The review of the inventory position, and © The receipt of an order at the end of each review period + When the lead time is zero, the last two events occur simultaneouslyTHE INVENTORY PROBLEM Example: The newspaper seller’s problem (of single time period) + A classical inventory problem concerns the purchase & sale of newspapers. + Only a single time period of fixed length is relevant and only a single procurement is made for this length. Inventory remaining at the end of the single time period is sold for scrap or discarded The paper seller buys the papers for 33 cents each & sells them for 50 cents each. The newspapers not sold at the end of day are sold as scrap for 5 cents each. Newspapers can be purchased in bundles of 10. Thus, the paper seller can buy 50, 60, & 0 on. + There are 3 types of Newsdays, “good”, “fair”, & “poor”, with probabilities of 0.35, 0.45, & 0.20 respectively. (Total=1.00) + The distribution of papers demanded on each of these days is given in the table below. # The problem is to determine the optimal number of papers the news seller should purchase. * Simulating demands for 20 days & recording profits from sales each day will accomplish this + The profits are given by the following relationship: + Profit = (revenue from sales) - (cost of newspapers) - (lost profit from excess demand) + (salvage from sale of scrap papers) e.g; Profit/paper = 50 - 33 - 17 + 5 = 5 cents/paper # To solve this problem by simulation requires setting a policy of buying a certain # of papers each day, then simulating the demands for papers over the 20-day time period to determine the total profit.DISTRIBUTION OF NEWSPAPERS DEMANDED. Thitial Demand Probabiity Distnbuten assumption prob. of occurrence) Demand | Good day Poor day 40 o0s Oe 3 05 O2z 0 as O68 7 Tae ae 80 035 0.06 30 os 0.00 700 a7 3.00 700 T09 RANDOM DIGIT ASSIGNMENT FOR TYPE OF NEWSDAY Type of | Propabinty | Cumulative | Random aigie newsday Probapiity | assignment Good as os was Fair O45 080 36-80 Poor 0.20 1.00 31-00 ‘Cumulative Distribution Random digit assignment Demand Good Fair Poor Good Fair Poor 40 a2 ae 144 or os EU rae 30 0.08 028 0.66 04-08 125 1566 60 O83 068 0.82 09-33 2968 7 70, as 0.88 034 Baas 3988 aoa 20 oe 036 Toy wa 78 39-96 35-00 30 055 700 100 73-33 37-00 = 700 1.00 100 100 34-00 The simulation table for purchasing 70 newspapers is shown below; here order quantity is fixed for each day. i.e; 70SIMULATION TABLE FOR PURCHASE OF 70 NEWSPAPERS i 2 3 4 5 6 7 8 9 10 Day | Random | Type ot | Random [Demand] Revenue] CostTor70 | Lost prof | Salvege | Daly promt agits for |newsday| digs for | (cheek | rom sates | papers | rom excess| trom sole | (6-7-6+9) ‘ype of demand | 384) | (0 cen wdorand | ofseep newadey (table) otto teeth gece | Pot [ate cee | eeorar| ee s0-001 |e gna5.a0 mi) geatsmacn| smm0.80 | ar g740 [see |e [ ng 00g 25.1030] mart | sem00 [ig=2i90 a PS a [4s [Fair [es | 70 [$35.00 [$23.10 [¢ -[¢- | si1.90 ST ILS | 32“ Good[ 6s | “90 ¢ 35.0] $23.10 | ¢ 1.70 |¢ = | $i0.20 7 [49 rar 86 | 70 | $35.00] $2310 |g ]s-_| s11.90 on ns Boe |e 7 eo eg es90,007) eq n2e 0a] gear] ¢OLNO [21§17 40 sa Good eae a |e 70.) 35.00! |TSi23-10503] sea | oo |S 0.90 1024 | Good |g | “go [$35.00 | $2310 1s 70 Ls $10.20 n1 [31 | Good [60 | 80 [$35.00 $23.10 1s -.70 1s $10.20 is 9 oes a ETO | gn 007 sig va 10] | gm [slg 90 i eset ie] eee | eg 29007 |g v2 20] gests |g tc00 |r gi2.90 1461 | Fa_| 90] 80 | $35.00] $23.10 |s 701s $10.20 a EE FFT ie [8 | Good_[ 73 | s0[ $35.00 § 23:10 [s 270 fs = | s10.20 7s 5S oe | OU | eg 30.007 sega. 105] gn Se 9 LOWNO [acig7 40 A A I PT 19 sz] rar 76 | 70] $35.00] $2310 |g Ig | i490 ose a al eto |e seg a6 001|urgues 107] (501 7a] § $10.70 1370 [$645.00] $ 462.00_[s13.60__|$ 5.50] $174.90)Measures of Performance: + Cost for 70 papers = $ 23.1 # Average no. of demands = 1370/20 = 68.5 (imp) + Average Daily profit (table) = 174.90/20 = $ 8.745 Or it can be calculated by: + Average Revenue from sales = $ 32.25 Average lost profit = $ 0.68 Average Salvage = $ 0.275 Average Daily Profit (formula) = 32.25 - 23.1 - 0.68 + 0.275 = $8.745 profit No. of profits for 50 demand = 04 times ($2.90 each) No. of profits for 60 demand = 03 times ($7.40 each) No. of profits for 70 demand = 06 times ($11.90 each) No. of profits for 80 demand = 06 times ($10.20 each) No. of profits for 90 demand = 01 time ($8.50 each) jote: + The policy (no. of news papers purchased) is moved to other values until the daily profit decreases at the level before and the level after that value. The value in between is a good estimate for the number of papers the newspapers seller should purchase Conclusion: + The scrap, not sold during the day, makes more loss in daily profit than from the excess demand loss Assignment: + Find the same for the purchase of 60 and 80 Newspapers respectively, and analyze the optimal number of papers the seller may purchase.