Modeling__Simulation computer science and engineering

notes on computer science and engineering .
modeling and simulation

1. DISCOVER . LEARN . EMPOWER Introduction to Simulation UNIVERSITY INSTITUTE OF ENGINEERING COMPUTER SCIENCE ENGINEERING Bachelor of Engineering (Computer Science & Engineering) Subject Name: Simulation and Modeling Subject Code: CSB-433, ITB-433 Prepared By: Dr Shuaib Khan

2. Introduction to Computer Simulation

3. SIMULATION There are many decision making situations that cannot be accurately modeled using other decision technology applications. Simulation provides the modeler with flexibility to evaluate the performance of many systems. Specifically, simulation allows the modeling and analysis of complex, real-world systems, when one or more variables or relationships are probabilistic.

4. SIMULATION A simulation model evaluates a course of action by simulating the operation of the system for an extended period of time. For example, waiting line or queueing statistics at a bank could be estimated by simulating 1000 days of operation.

5. SIMULATION Some approaches to modeling produce prescriptive models, simulation produces descriptive models. This means that simulation describes a system rather than optimizing it. However, it can test a series of complex policies for cost/benefit analysis. Comparing simulation to other modeling techniques is like comparing a moving picture to a snapshot.

6. ADDING A NEW SERVICE BAY Consider a decision faced by an automotive repair shop ( Quik Lube): should an extra service bay be added? There are a variety of uncertain events, including the customer arrival rate, the service rate, the amount of time a customer will wait for service before leaving, the profit generated by different categories of service, etc.

7. ADDING A NEW SERVICE BAY A simulation model can enable you to analyze this problem and select the best alternative. Also, one can determine a range of conditions under which adding the service bay would be preferred - a form of sensitivity analysis.

8. ADVANTAGES OF SIMULATION Simulation is a flexible modeling tool that can handle complex relationships with relative ease. Some examples of complex relationships: - limited number of spaces for cars to wait for service; - customers are only willing to wait 10 minutes for service before they leave.

9. ADVANTAGES OF SIMULATION Simulation models are easy to explain and understand. Diagrams can be drawn to illustrate the various process flow steps and simplify the explanation of the modeling relationships. Computer simulation can be accomplished in a variety of environments. These include Excel, Visual BASIC, C++, and special purpose languages such as Extend, GPSS, Automod , ProModel , Flexsim ED, Witness, Arena, Simul8, and SLX.

10. CLASSES OF SIMULATION MODELS There are two types of simulation modeling: discrete event and continuous . Discrete event : The system changes only when an event occurs. Time advances based on the occurrence of the next event . For our car repair center, the system changes when a car arrives or when service begins or ends.

11. CLASSES OF SIMULATION MODELS Continuous : The system changes continuously over time. Time advances in a fixed increment and the behavior of the system is updated during each increment.

12. CLASSES OF SIMULATION MODELS For example, simulating the flight of an airplane on autopilot is continuous since changes, such as the aircraft's position or velocity, can change continuously over time. If the time fixed increment is 0.05 seconds, changes in flight information during this interval are used to automatically adjust the flight plan. We will use discrete event simulation for process analysis and continuous for financial analysis.

13. TIME MECHANISMS e 1 e 2 e 3 e 4 e 5 T 1 T 2 T 3 T 4 T 5 Time Next Event Fixed Increment e 1 e 2 e 3 e 4 e 5 I 4 Time I 3 I 2 I 1

14. MONTE CARLO SIMULATION Suppose that we want to simulate the performance of Quik Lube. We need to define probability distributions that describe the time between customer arrivals and how long service takes. Assume that we are interested in generating the amount of time between customer arrivals.

15. MONTE CARLO SIMULATION After gathering data, we found that the possible interarrival times and their relative frequency of occurrence (or probability) are as follows: Probability Interarrival Time 0.15 5 0.35 10 0.50 15

16. MONTE CARLO SIMULATION Using this information, how can we generate a sequence of interarrival times for Quik Lube? Clearly these times must be random but the chance that a given interarrival time will occur must correspond to its probability. The process of generating a sequence of random values from a probability distribution is called Monte Carlo simulation .

17. MONTE CARLO SIMULATION To understand how this can be accomplished envision a roulette wheel with 100 identical slots. Since each slot has the same chance of occurrence on the spin of the wheel, we can partition the slots according to the probabilities given and link the results of a spin with the interarrival time.

18. Interarrival Time Probability Random Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99 25 26 75 74 51 50 49 48 98 99 00 01 12 13 14 15

19. If the ball lands on slot 74, what interarrival time is generated? Interarrival Time Probability Random Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99 25 26 75 74 51 50 49 48 98 99 00 01 12 13 14 15

20. Interarrival Time Probability Random Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99 If the ball lands on slot 74, what interarrival time is generated? 15 minutes 25 26 75 74 51 50 49 48 98 99 00 01 12 13 14 15

21. MONTE CARLO SIMULATION Unless you happen to have a roulette wheel in your back pocket, a simpler procedure is needed. A table of random digits prepared by, whom else, the Rand Corporation in 1955, can be used. This table appears on the next page.

22. RANDOM DIGITS 63271 59986 71744 51102 15141 80714 58683 93108 13554 79945 88547 09896 95436 79115 08303 01041 20030 63754 08459 28364 55957 57243 83865 09911 19761 66535 40102 26646 60147 15702 46276 87453 44790 67122 45573 84358 21625 16999 13385 22 782 55363 07449 34835 15290 76616 67191 12777 21861 68689 03263 69393 92785 49902 58447 42048 30378 87618 26933 40640 16281 13186 19431 88190 04588 38733 81290 89541 70290 40113 08243 17726 28652 56836 78351 47327 18518 92222 55201 27340 10493 36520 64465 05550 30157 82242 29520 69753 72602 21756 54935 81628 36100 39254 56835 37636 02421 98063 89641 64953 99337 84649 38968 75215 75498 49539 74240 03466 49292 36401 45525 63291 11618 12613 75055 43915 26488 41116 64531 56827 30825 70502 53225 03 655 05915 37140 57051 48393 91322 25653 06543 06426 24771 59935 49801 11082 66762 94477 02494 88215 27191 20711 55609 29430 70165 45406 78484 31639 52009 18873 96927 This table is reproduced with permission from The Rand Corporation, A Million Random Digits , The Free Press, New York, 1955 and 1983.

23. MONTE CARLO SIMULATION What does it mean for these digits to be random? Every digit in the table is equally likely to be 0 through 9. The patterns of random digits do not repeat. The table can be used at any starting point, and in blocks of 1, 2, 3, etc. digits. For simplicity, we will start in the upper left hand corner.

24. QUIK LUBE EXAMPLE Suppose we want to generate a sequence of 20 interarrival times. We use blocks of two random digits starting in the upper left corner and moving across the table. Each value randomly generated from a probability distribution is called a trial .

25. QUIK LUBE EXAMPLE Random digits Interarrival Time 63 Inter. Time Prob Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99

26. QUIK LUBE EXAMPLE Random digits Interarrival Time 63 15 Inter. Time Prob Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99

27. QUIK LUBE EXAMPLE Random digits Interarrival Time 63 15 27 Inter. Time Prob Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99

28. QUIK LUBE EXAMPLE Random digits Interarrival Time 63 15 27 10 Inter. Time Prob Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99

29. QUIK LUBE EXAMPLE Random digits Interarrival Time 63 15 27 10 15 10 99 15 86 15 71 15 74 15 45 10 11 5 02 5 15 10 14 5 18 10 07 5 14 5 58 15 68 15 39 10 31 10 08 5 Inter. Time Prob Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99

30. QUIK LUBE EXAMPLE Random digits Interarrival Time 63 15 27 10 15 10 99 15 What is the simulated 86 15 average interarrival time? 71 15 74 15 45 10 11 5 02 5 15 10 14 5 18 10 07 5 14 5 58 15 68 15 39 10 31 10 08 5 Inter. Time Prob Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99

31. QUIK LUBE EXAMPLE Random digits Interarrival Time 63 15 27 10 15 10 99 15 What is the simulated 86 15 average interarrival time? 71 15 74 15 Avg = [6(5) + 7(10) + 7(15)] / 20 = 10.25 45 10 11 5 02 5 15 10 14 5 18 10 07 5 14 5 58 15 68 15 39 10 31 10 08 5 Inter. Time Prob Interval 5 0.15 00-14 10 0.35 15-49 15 0.50 50-99

32. QUIK LUBE EXAMPLE Random digits Interarrival Time 63 15 27 10 15 10 99 15 What is the simulated 86 15 average interarrival time? 71 15 74 15 Avg = [6(5) + 7(10) + 7(15)] / 20 = 10.25 45 10 11 5 02 5 15 10 14 5 18 10 07 5 14 5 58 15 68 15 39 10 31 10 08 5 Original Simulated Inter. Time Prob Prob 5 0.15 6/20=.30 10 0.35 7/20=.35 15 0.50 7/20=.35 Notice that the simulated distribution does not match the original probability distribution.

33. QUIK LUBE EXAMPLE The expected interarrival time is: EV = (.15) (5) + (.35)(10) + (.50)(15) = 11.75 Why is there a difference between the simulated average and the expected value? The simulation average will approach the expected value as we increase the number of trials. In validating simulation models, one should check that the random values generated closely fit the original probability distribution.

34. PSEUDO RANDOM NUMBERS To simplify computer generation of random numbers, pseudo-random number generators are used. Formulas are used which will generate a long series of integers before the sequence repeats itself. Programming languages have built in pseudo-random number generators, for example, RAND( ) in Visual Basic.

35. PSEUDO RANDOM NUMBERS IN EXCEL A spreadsheet, such as Excel, can generate a pseudo-random number between 0 and 1. The =RAND() function in Excel returns a random number between 0 and 1 -- try it! To generate a new random number press F9.

36. PSEUDO RANDOM NUMBERS IN EXCEL We recommend that you set the spreadsheet to manual calculation mode so that new random values will be generated only when F9 is pressed. This is accomplished by using the Tools , Options , Calculations , and Manual commands. The Quik Lube simulation that we did with random digits can be done in Excel using the =VLOOKUP command and the =RAND() function.

37. SIMULATION IN EXCEL We first set up the following random interval table (assuming 2 significant digits): Interarrival Time Random number interval 5 0.00 - 0.14 10 0.15 - 0.50 15 0.51 - 1.00

38. USING THE =VLOOKUP COMMAND The =VLOOKUP command uses the format: =VLOOKUP(X,BLOCK,COLUMN) Starting in the last row of the “block,” =VLOOKUP searches for the first value that is less than or equal to "X" and returns the value located in the "column" column in the "block." This allows you to access information in data tables. Doesn’t this sound like a definition from a software manual?

39. HOW TO USE =VLOOKUP For Quik Lube, first determine the cumulative probabilities. Cumulative Interarrival Time Probability Probability 5 0.15 0.15 10 0.35 0.50 15 0.50 1.00 ------ 1.00

40. HOW TO USE =VLOOKUP The lookup table would be: Cumulative Probability Interarrival Time 0.00 5 0.15 10 0.50 15 1.00 0

41. HOW TO USE =VLOOKUP The lookup table would be: Cumulative Probability Interarrival Time 0.00 5 0.15 10 0.50 15 1.00 0 The lookup command would be: =VLOOKUP(+B14,$A$8:$B$11,2)

42. HOW TO USE =VLOOKUP The 0.00 in the cumulative probability column is in A8 and the 0 in the interarrival time column is in B11. A random number is generated in cell B14. If the random number is less than 0.15, then the interarrival time is 5. If the random number is less than 0.50 but greater than or equal to 0.15, then the time is 10. If the random number is less than 1.00 but greater than or equal to 0.50, then the time is 15.

43. HOW TO USE =VLOOKUP The 0 in the interarrival time column can be any number since this cell will never be used because a random number exactly equal to 1.00 is never generated. The 2 in the =VLOOKUP command indicates that the interarrival times are located in the second column of the “block,” that is, in the B-column.

44. BUILDING LARGER MODELS IN EXCEL Using several probability distributions we can build more complex models in Excel. Often, we need additional Excel commands, such as, =IF, =MAX, and =MIN.

45. REFRIGERATOR SERVICE A service technician for a major refrigerator appliance manufacturer is trained to service two refrigerators, the Alpha and the Beta. Approximately 60% of the technician's service calls are for the Alpha and 40% are for the Beta. The service time distributions for the two models are as follows:

46. Alpha Beta Time Relative Time Relative (Minutes) Frequency (Minutes) Frequency 25 0.50 20 0.40 30 0.25 25 0.40 35 0.15 30 0.10 40 0.10 35 0.10 REFRIGERATOR SERVICE

47. Show the random number intervals that can be used to simulate the type of refrigerator to be serviced and the length of the service time for each model. Simulate 20 service calls. What is the total service time spent on the 20 calls? REFRIGERATOR SERVICE

48. The three =VLOOKUP tables are: Probs Call type Probs Alpha Probs Beta 0 1 0 25 0 20 0.6 2 0.5 30 0.4 25 1 0 0.75 35 0.8 30 0.9 40 0.9 35 1 0 1 0 REFRIGERATOR SERVICE

49. The =IF and =VLOOKUP commands are: =VLOOKUP(RAND(),$A$4:$B$6,2) =IF(A23=1,(VLOOKUP(RAND(),$A$9:$B$13,2)), (VLOOKUP(RAND(),$A$16:$B$20,2))) REFRIGERATOR SERVICE

50. Thanks You Questions ????