Many of them are also animated. PowerPoint PPT presentation free to view. Guang Yang. Lecture 5: Discrete Event Simulation - Breakdown demon, break angel. May have multiple realizations instances in system concurrently Informal model of system. Management is Simulation Studies. Algorithm 1. Discrete Event Simulation Other estimates from hub-bound travel statistics. Event Driven Simulation Models. Time Driven Dynamics.
Event Driven Dynamics Transform them to become uniform over the interval [-1, Introduction to Simulation Experimental Design step 3 - Same response as for step 7. Production Runs step 9 - See discussion of step 5 above. Documentation and Reporting step 11 - Software is available for documentation assistance and for report preparation.
The problem requests that the simulation for each policy should run for 5 days. This is a very short run length to make a policy decision.
Let 1 denote the fastest server, 2 the second fastest server, and so on. Arrival event No Server 1 Served by 1 busy? Yes No Served by 2 Server 2 busy?
Departure event from server j Begin server j No Another Yes Remove the waiting idle time unit unit from the queue waiting? Shown on simulation tables Then, simulate for two taxis for 5 days. Comparison Smalltown Taxi would have to decide which is more important—paying for about 43 hours of idle time in a five day period with no customers having to wait, or paying for around 4 hours of idle time in a five day period, but having a probability of waiting equal to 0.
Continue this process for 5 replications and estimate the desired probability. Time Serv. In Exercise 20, the modal value is in the bin 1. In Figure 2. In Exercise 20, the median value is about 1.
Bin Frequency No. Waiting Time in each bin 30 25 25 Occurrences No. In Exercise 21, the modal value is in the bin 2. There are three addition higher valued bins that have frequencies of one less. In Exercise 21, the median value is about 3. Waiting Time in each bin 8 7 7 6 6 6 6 Occurrences No. But, with simulation, it may or may not happen. Number of Trials Minimum Maximum 25 0. This shows why you should not conduct just one trial.
It might be the low value, 0. Or, it might be the high value, 3. This is what is expected in simulation. When there are more observations, there is a greater opportunity to have a smaller or larger value. The difference between these two is less than would be anticipated.
We also determined the ranges. On 50 trials, the range of observation on the maximum values is 4. With trials, the comparable value is 3. The average value for 50 trials and trials is close 0. But, the variation in the values is much larger when there are 50 trials vs trials 0. With more observations, there is a greater opportunity to have larger or smaller values. But, with more observations, there is more information so that the averages are more consistent. With 50 trials, the best policy is to order 60 or, perhaps, 70 papers.
More trials for the policies of 60 and 70 papers are advised. These 10 days can be considered as independent trials 10 x These days of information helps to answer Exercise 28 better. The more information, the better.
Review period days Avg. Ending Inventory 4 3. Maximum Inventory Avg. Ending Inventory 10 2. There is a much greater opportunity for a large or small value with ten times as many trials. Average lead time demand is 8. Original data Bin Frequency Occurrences No. New input data Expmt Middle Expmt Middle Expmt Middle Expmt Middle 1 6 11 16 2 7 12 17 3 8 13 18 4 9 14 19 5 10 15 20 a Bin Frequency Occurrences No.
Chapter 3 General Principles For solutions check the course web site at www. The variance and mean are equal. Note: Since both Beta and Uniform distributions are continuous, the density at the end points are 0. Then Xi is normally distributed. Since The solution for this system is given by Figure 6. The solution is identical to that of Exercise On the other hand, actual unloading times are probably less variable than the exponential distribution.
A table comparing one crane and two cranes follows: one crane two cranes c 1 2 LQ 6. It is an art that is learned over time and through experience. Furthermore, if two models are constructed by two competent individuals, they may have similarities, but it is highly unlikely that they will be the same. Simulation results may be difficult to interpret.
Since most simulation outputs are essentially random variables they are usually based on random inputs , it may be hard to determine whether an observation is a result of system interrelationships or randomness.
Simulation modeling and analysis can be time consuming and expensive. Skimping on resources for modeling and analysis may result in a simulation model or analysis that is not sufficient for the task. Simulation is used in some cases when an analytical solution is possible, or even preferable, as discussed in Section 1. This might be particularly true in the simulation of some waiting lines where closedform queueing models are available. Semiconductor Manufacturing Comparison of dispatching rules using large-facility models The corrupting influence of variability A new lot-release rule for wafer fabs.
Assessment of potential gains in productivity due to proactive reticle management Comparison of a mm and mm X-ray lithography cell Capacity planning with time constraints between operations mm logistic system risk reduction.
Construction of a dam embankment Trenchless renewal of underground urban infrastructures Activity scheduling in a dynamic, multiproject setting Investigation of the structural steel erection process Special-purpose template for utility tunnel construction. Military Application Modeling leadership effects and recruit type in an Army recruiting station Design and test of an intelligent controller for autonomous underwater vehicles Modeling military requirements for nonwarfighting operations Multitrajectory performance for varying scenario sizes Using adaptive agent in U.
S Air Force pilot retention. Evaluating the potential benefits of a rail-traffic planning algorithm Evaluating strategies to improve railroad performance Parametric modeling in rail-capacity planning Analysis of passenger flows in an airport terminal Proactive flight-schedule evaluation Logistics issues in autonomous food production systems for extendedduration space exploration Sizing industrial rail-car fleets Product distribution in the newspaper industry Design of a toll plaza Choosing between rental-car locations Quick-response replenishment.
Impact of connection bank redesign on airport gate assignment Product development program planning Reconciliation of business and systems modeling Personnel forecasting and strategic workforce planning.
Human Systems Modeling human performance in complex systems Studying the human element in air traffic control. System defined as a group of objects that are joined together in some regular interaction or interdependence toward the accomplishment of some purpose.
The decision on the boundary between the system and its environment may depend on the purpose of the study. Entity : an object of interest in the system. Attribute : a property of an entity. Activity : a time period of specified length. State : the collection of variables necessary to describe the system at any time, relative to the objectives of the study. Event : an instantaneous occurrence that may change the state of the system. Endogenous : to describe activities and events occurring within a system.
Exogenous : to describe activities and events in an environment that affect the system. Systems can be categorized as discrete or continuous. Bank : a discrete system The head of water behind a dam : a continuous system. Model a representation of a system for the purpose of studying the system a simplification of the system sufficiently detailed to permit valid conclusions to be drawn about the real system.
Static or Dynamic Simulation Models Static simulation model called Monte Carlo simulation represents a system at a particular point in time. Dynamic simulation model represents systems as they change over time. Deterministic or Stochastic Simulation Models Deterministic simulation models contain no random variables and have a known set of inputs which will result in a unique set of outputs Stochastic simulation model has one or more random variables as inputs.
Random inputs lead to random outputs. The simulation models are analyzed by numerical rather than by analytical methods Analytical methods employ the deductive reasoning of mathematics to solve the model. Numerical methods employ computational procedures to solve mathematical models. Setting of objectives and overall project plan Model conceptualization The art of modeling is enhanced by an ability to abstract the essential features of a problem, to select and modify basic assumptions that characterize the system, and then to enrich and elaborate the model until a useful approximation results.
Data collection As the complexity of the model changes, the required data elements may also change. Is the computer program performing properly?
Debugging for correct input parameters and logical structure. The determination that a model is an accurate representation of the real system. Validation is achieved through the calibration of the model. Experimental design The decision on the length of the initialization period, the length of simulation runs, and the number of replications to be made of each run. More runs? Documentation and reporting Program documentation : for the relationships between input parameters and output measures of performance, and for a modification Progress documentation : the history of a simulation, a chronology of work done and decision made.
Four phases according to Figure 1. Three steps of the simulations Determine the characteristics of each of the inputs to the simulation. Quite often, these may be modeled as probability distributions, either continuous or discrete. Construct a simulation table. Each simulation table is different, for each is developed for the problem at hand. For each repetition i, generate a value for each of the p inputs, and evaluate the function, calculating a value of the response yi.
The input values may be computed by sampling values from the distributions determined in step 1. A response typically depends on the inputs and one or more previous responses. The simulation table provides a systematic method for tracking system state over time. A queueing system is described by its calling population, the nature of the arrivals, the service mechanism, the system capacity, and the queueing discipline.
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. Arrivals for service occur one at a time in a random fashion. Once they join the waiting line, they are eventually served. Service times are of some random length according to a probability distribution which does not change over time. The system capacity has no limit, meaning that any number of units can wait in line.
Arrivals and services are defined by the distribution of the time between arrivals and the distribution of service times, respectively. For any simple single- or multi-channel queue, the overall effective arrival rate must be less than the total service rate, or the waiting line will grow without bound.
In some systems, the condition about arrival rate being less than service rate may not guarantee stability. System state : the number of units in the system and the status of the server busy or idle. Event : a set of circumstances that cause an instantaneous change in the state of the system. In a single-channel queueing system there are only two possible events that can affect the state of the system.
If a unit has just completed service, the simulation proceeds in the manner shown in the flow diagram of Figure 2. Note that the server has only two possible states : it is either busy or idle. Departure Event. The arrival event occurs when a unit enters the system. The unit may find the server either idle or busy. Idle : the unit begins service immediately Busy : the unit enters the queue for the server. Simulations of queueing systems generally require the maintenance of an event list for determining what happens next.
Simulation clock times for arrivals and departures are computed in a simulation table customized for each problem. In simulation, events usually occur at random times, the randomness imitating uncertainty in real life. Random numbers are distributed uniformly and independently on the interval 0, 1. The proper number of digits is dictated by the accuracy of the data being used for input purposes. Table 2. Interarrival and Clock Times Assume that the times between arrivals were generated by rolling a die five times and recording the up face.
Service Times Assuming that all four values are equally likely to occur, these values could have been generated by placing the numbers one through four on chips and drawing the chips from a hat with replacement, being sure to record the numbers selected. The only possible service times are one, two, three, and four time units. The interarrival times and service times must be meshed to simulate the single-channel queueing system.
The occurrence of the two types of events arrival and departure event in chronological order is shown in Table 2. Figure 2. The chronological ordering of events is the basis of the approach to discrete-event simulation described in Chapter 3.
Assumptions Only one checkout counter. Customers arrive at this checkout counter at random from 1 to 8. Each possible value of interarrival time has the same probability of occurrence, as shown in Table 2.
The service times vary from 1 to 6 minutes with the probabilities shown in Table 2. The problem is to analyze the system by simulating the arrival and service of 20 customers. A simulation of a grocery store that starts with an empty system is not realistic unless the intention is to model the system from startup or to model until steady-state operation is reached.
A set of uniformly distributed random numbers is needed to generate the arrivals at the checkout counter. Random numbers have the following properties: The set of random numbers is uniformly distributed between 0 and 1. Successive random numbers are independent. Random digits are converted to random numbers by placing a decimal point appropriately. Table A. The rightmost two columns of Tables 2. Example 2.
To obtain the corresponding time between arrivals, enter the fourth column of Table 2. The essence of a manual simulation is the simulation table. The simulation table for the single-channel queue, shown in Table 2. Statistical measures of performance can be obtained form the simulation table such as Table 2.
Statistical measures of performance in this example. Each customer's time in the system The server's idle time. In order to compute summary statistics, totals are formed as shown for service times, time customers spend in the system, idle time of the server, and time the customers wait in the queue. The probability that a customer has to wait in the queue : 0.
This result can be compared with the expected service time by finding the mean of the service-time distribution using the equation in table 2. The longer the simulation, the closer the average will be to. The average time a customer spends in the system : 6. A drive-in restaurant where carhops take orders and bring food to the car. Assumptions Cars arrive in the manner shown in Table 2. Two carhops Able and Baker - Able is better able to do the job and works a bit faster than Baker.
The distribution of their service times is shown in Tables 2. A simplifying rule is that Able gets the customer if both carhops are idle. If both are busy, the customer begins service with the first server to become free. To estimate the system measures of performance, a simulation of 1 hour of operation is made.
The problem is to find how well the current arrangement is working. The row for the first customer is filled in manually, with the randomnumber function RAND in case of Excel or another random function replacing the random digits. After the first customer, the cells for the other customers must be based on logic and formulas. IF condition, value if true, value if false. The logic requires that we compute when Able and Baker will become free, for which we use the built-in Excel function for maximum over a range, MAX.
If the first condition Able idle when customer 10 arrives is true, then the customer begins immediately at the arrival time in D Otherwise, a second IF function is evaluated, which says if Baker is idle, put nothing.. Otherwise, the function returns the time that Able or Baker becomes idle, whichever is first [the minimum or MIN of their respective completion times].
The analysis of Table 2. The seniority rule keeps Baker less busy and gives Able more tips. The average waiting time for all customers was only about 0. Those nine who did have to wait only waited an average of 1. In summary, this system seems well balanced. One server cannot handle all the diners, and three 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. This inventory system has a periodic review of length N, at which time the inventory level is checked. An order is made to bring the inventory up to the level M. In this inventory system the lead time i. Demand is shown as being uniform over the time period.
Notice that in the second cycle, the amount in inventory drops below zero, indicating a shortage. Two way to avoid shortages Carrying stock in inventory : cost - the interest paid on the funds borrowed to buy the items, renting of storage space, hiring guards, and so on.
Making more frequent reviews, and consequently, more frequent purchases or replenishments : the ordering cost.
The total cost of an inventory system is the measure of performance. The decision maker can control the maximum inventory level, M, and the length of the cycle, N. In an 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.
The paper seller buys the papers for 33 cents each and sells them for 50 cents each. The lost profit from excess demand is 17 cents for each paper demanded that could not be provided. Newspapers not sold at the end of the day are sold as scrap for 5 cents each. Thus, the paper seller can buy 50, 60, and so on.
There are three types of newsdays, good, fair, and poor, with probabilities of 0. The problem is to determine the optimal number of papers the newspaper seller should purchase. This will be accomplished by simulating demands for 20 days and recording profits from sales each day. The profits are given by the following relationship: revenue cost of lost profit from salvage from sale Pofit from sales newspapers excess demand of scrap papers.
The distribution of papers demanded on each of these days is given in Table 2. Tables 2. The simulation table for the decision to purchase 70 newspapers is shown in Table 2.
Ten newspapers are left over at the end of the day. The salvage value at 5 cents each is 50 cents. Suppose that the maximum inventory level, M, is11 units and the review period, N, is 5 days. The problem is to estimate, by simulation, the average ending units in inventory and the number of days when a shortage condition occurs.
The distribution of the number of units demanded per day is shown in Table 2. In this example, lead time is a random variable, as shown in Table 2. Assume that orders are placed at the close of business and are received for inventory at the beginning of business as determined by the lead time. For purposes of this example, only five cycles will be shown. The random-digit assignments for daily demand and lead time are shown in the rightmost columns of Tables 2.
The simulation has been started with the inventory level at 3 units and an order of 8 units scheduled to arrive in 2 days' time. The lead time for this order was 1 day. Notice that the beginning inventory on the second day of the third cycle was zero. An order for 2 units on that day led to a shortage condition.
The units were backordered on that day and the next day also. On the morning of day 4 of cycle 3 there was a beginning inventory of 9 units. The 4 units that were backordered and the 1 unit demanded that day reduced the ending inventory to 4 units.
Based on five cycles of simulation, the average ending inventory is approximately 3. On 2 of 25 days a shortage condition existed. It takes 20 minutes to change one bearing, 30 minutes to change two bearings, and 40 minutes to change three bearings. A proposal has been made to replace all three bearings whenever a bearing fails.
The cumulative distribution function of the life of each bearing is identical, as shown in Table 2. The delay time of the repairperson's arriving at the milling machine is also a random variable, with the distribution given in Table 2.
Note that there are instances where more than one bearing fails at the same time. This is unlikely to occur in practice and is due to using a rather coarse grid of hours.
It will be assumed in this example that the times are never exactly the same, and thus no more than one bearing is changed at any breakdown.
Sixteen bearing changes were made for bearings 1 and 2, but only 14 bearing changes were required for bearing 3. Notice that bearing life is taken from Table 2. Since the proposed method uses more bearings than the current method, the second simulation uses new random digits for generating the additional lifetimes.
The random digits that lead to the lives of the additional bearings are shown above the slashed line beginning with the 15th replacement of bearing 3. A classic simulation problem is that of a squadron of bombers attempting to destroy an ammunition depot shaped as shown in Figure 2.
If a bomb lands anywhere on the depot, a hit is scored. Otherwise, the bomb is a miss. The aircraft fly in the horizontal direction. Ten bombers are in each squadron. The aiming point is the dot located in the heart of the ammunition dump. The point of impact is assumed to be normally distributed around the aiming point with a standard deviation of meters in the horizontal direction and meters in the vertical direction.
The problem is to simulate the operation and make statements about the number of bombs on target. The standardized normal variate, Z, with mean 0 and standard deviation 1, is distributed as. In this example the aiming point can be considered as 0, 0 ; that is, the in the horizontal direction is 0, and similarly for the value in the. The values of Z are random normal numbers.
These can be generated from uniformly distributed random numbers, as discussed in Chapter 7. Alternatively, tables of random normal numbers have been generated. A small sample of random normal numbers is given in Table A. The table of random normal numbers is used in the same way as the table of random numbers. The mnemonic stands for.
The first random normal number used was 0. The random normal number to generate the y coordinate was 0. Taken together, , is a miss, for it is off the target. The resulting point and that of the third bomber are plotted on Figure 2. The 10 bombers had 3 hits and 7 misses. Many more runs are needed to assess the potential for destroying the dump. This is an example of a Monte Carlo, or static, simulation, since time is not an element of the solution. The lead time is the time from placement of an order until the order is received.
In a realistic situation, lead time is a random variable. During the lead time, demands also occur at random. Leadtime demand is thus a random variable defined as the sum of T the demands over the lead time, or D. The distribution of lead-time demand is determined by simulating many cycles of lead time and building a histogram based on the results.
The daily demand is given by the following probability distribution:. The random digits for the first cycle were This generates a lead time of 2 days. This example illustrates how simulation can be used to study an unknown distribution by generating a random sample from the distribution. This chapter introduced simulation concepts via examples in order to illustrate general areas of application and to motivate the remaining chapters. The next chapter gives a more systematic presentation of the basic concepts.
A more systematic methodology, such as the event-scheduling approach described in Chapter 3, is needed. Ad hoc simulation tables were used in completing each example. Events in the tables were generated using uniformly distributed random numbers and, in one case, random normal numbers. The examples illustrate the need for determining the characteristics of the input data, generating random variables from the input models, and analyzing the resulting response. The basic building blocks of all discrete-event simulation models : entities and attributes, activities and events.
A system is modeled in terms of its state at each point in time the entities that pass through the system and the entities that represent system resources the activities and events that cause system state to change. Discrete-event models are appropriate for those systems for which changes in system state occur only at discrete points in time. This chapter deals exclusively with dynamic, stochastic systems i. System : A collection of entities e.
Model : An abstract representation of a system, usually containing structural, logical, or mathematical relationships which describe a system in terms of state, entities and their attributes, sets, processes, events, activities, and delays. System state : A collection of variables that contain all the information necessary to describe the system at any time.
Entity : Any object or component in the system which requires explicit representation in the model e. Attributes : The properties of a given entity e.
List : A collection of permanently or temporarily associated entities, ordered in some logical fashion such as all customers currently in a waiting line, ordered by first come, first served, or by priority. Event : An instantaneous occurrence that changes the state of a system such as an arrival of a new customer. Event notice : A record of an event to occur at the current or some future time, along with any associated data necessary to execute the event; at a minimum, the record includes the event type and the event time.
Event list : A list of event notices for future events, ordered by time of occurrence also known as the future event list FEL. Activity : A duration of time of specified length e. Delay : A duration of time of unspecified indefinite length, which is not known until it ends e. An activity typically represents a service time, an interarrival time, or any other processing time whose duration has been characterized and defined by the modeler.
An activity's duration may be specified in a number of ways:. Deterministic-for example, always exactly 5 minutes; 2. Statistical-for example, as a random draw from among 2, 5, 7 with equal probabilities; 3. The duration of an activity is computable from its specification at the instant it begins.
To keep track of activities and their expected completion time, at the simulated instant that an activity duration begins, an event notice is created having an event time equal to the activity's completion time. A delay's duration Not specified by the modeler ahead of time, But rather determined by system conditions.
Quite often, a delay's duration is measured and is one of the desired outputs of a model run. How long to wait? A customer's delay in a waiting line may be dependent on the number and duration of service of other customers ahead in line as well as the availability of servers and equipment. System state, entity attributes and the number of active entities, the contents of sets, and the activities and delays currently in progress are all functions of time and are constantly changing over time.
System state L t : the number of cars waiting to be served at time t Q L t : 0 or 1 to indicate Able being idle or busy at time t A. LB t : 0 or 1 to indicate Baker being idle or busy at time t Entities : Neither the customers i. Activities Interarrival time, defined in Table 2. A description of the dynamic relationships and interactions between the components is also needed.
A discrete-event simulation : the modeling over time of a system all of whose state changes occur at discrete points in time-those points when an event occurs. A discrete-event simulation proceeds by producing a sequence of system snapshots or system images which represent the evolution of the system through time.
The mechanism for advancing simulation time and guaranteeing that all events occur in correct chronological order is based on the future event list FEL. Future Event List FEL to contain all event notices for events that have been scheduled to occur at a future time.
Scheduling a future event means that at the instant an activity begins, its duration is computed or drawn as a sample from a statistical distribution and the end-activity event, together with its event time, is placed on the future event list. List processing : the management of a list.
The efficiency of this search depends on the logical organization of the list and on how the search is conducted. The system snapshot at time 0 is defined by the initial conditions and the generation of the so-called exogenous events. The specified initial conditions define the system state at time 0. In Figure 3. How future events are generated? To generate an arrival to a queueing system - The end of an interarrival interval is an example of a primary event. A service-completion event will be generated and scheduled at the time of an arrival event, provided that, upon arrival, there is at least one idle server in the server group.
Beginning service : a conditional event triggered only on the condition that a customer is present and a server is free. Service completion : a primary event.
Service time : an activity. By a service-completion event in a queueing simulation Cont. A conditional event is triggered by a primary event occurring Only primary events appear on the FEL. To generate runtimes and downtimes for a machine subject to breakdowns At time 0, the first runtime will be generated and an end-of-runtime event scheduled.
Whenever an end-of-runtime event occurs, a downtime will be generated and an end-of-downtime event scheduled on the FEL. When the CLOCK is eventually advanced to the time of this end-ofdowntime event, a runtime is generated and an end-of-runtime event scheduled on the FEL. An end of runtime and an end of downtime : primary events.
A runtime and a downtime : activities. Every simulation must have a stopping event, here called E, which defines how long the simulation will run.
0コメント