Words: 9923
www. ncetianz. webs. com System Modeling And Simulation Notes —————— Presented By Nc et ia nz www. ncetianz. webs. com CHAPTER – 1 INTRODUCTION TO SIMULATION Nc et ia -1- nz www. ncetianz. webs. com Simulation A Simulation is the imitation of the operation of a real-world process or system over time. Brief Explanation • The behavior of a system as it evolves over time is studied by developing a simulation model. • This model takes the form of a set of assumptions concerning the operation of the system.
The assumptions are expressed in o Mathematical relationships o Logical relationships o Symbolic relationships Between the entities of the system. Measures of performance The model solved by mathematical methods such as differential calculus, probability theory, algebraic methods has the solution usually consists of one or more numerical parameters which are called measures of performance. 1. 1 When Simulation is the Appropriate Tool • Simulation enables the study of and experimentation with the internal interactions of a complex system, or of a subsystem within a complex system. Informational, organizational and environmental changes can be simulated and the effect of those alternations on the model’s behavior can be observer. • The knowledge gained in designing a simulation model can be of great value toward suggesting improvement in the system under investigation. • Simulation can be used as a pedagogical device to reinforce analytic solution methodologies. Nc et ia -2- • By changing simulation inputs and observing the resulting outputs, valuable insight may be obtained into which variables are most important and how variables interact. nz www. ncetianz. webs. com Simulation can be used to experiment with new designs or policies prior to implementation, so as to prepare for what may happen. • Simulation can be used to verify analytic solutions. • By simulating different capabilities for a machine, requirements can be determined. • Simulation models designed for training, allow learning without the cost and disruption of on-the-job learning. • Animation shows a system in simulated operation so that the plan can be visualized. • The modern system(factory, water fabrication plant, service organization, etc) is so complex that the interactions can be treated only through simulation. . 2 When Simulation is Not Appropriate • Simulation should be used when the problem cannot be solved using common sense. • Simulation should not be used if the problem can be solved analytically. • Simulation should not be used, if it is easier to perform direct experiments. • Simulation should not be used, if the costs exceeds savings. • Simulation should not be performed, if the resources or time are not available. • If no data is available, not even estimate simulation is not advised. • If there is not enough time or the person are not available, simulation is not appropriate.
Nc et ia -3- nz www. ncetianz. webs. com • If managers have unreasonable expectation say, too much soon – or the power of simulation is over estimated, simulation may not be appropriate. • If system behavior is too complex or cannot be defined, simulation is not appropriate. 1. 3 Advantages of Simulation • Simulation can also be used to study systems in the design stage. • Simulation models are run rather than solver. • New policies, operating procedures, decision rules, information flow, etc can be explored without disrupting the ongoing operations of the real system. New hardware designs, physical layouts, transportation systems can be tested without committing resources for their acquisition. • Hypotheses about how or why certain phenomena occur can be tested for feasibility. • Time can be compressed or expanded allowing for a speedup or slowdown of the phenomena under investigation. • Insight can be obtained about the interaction of variables. • Insight can be obtained about the importance of variables to the performance of the system. • A simulation study can help in understanding how the system operates rather than how individuals think the system operates. “what-if” questions can be answered. Useful in the design of new systems. Nc et ia -4- nz • Bottleneck analysis can be performed indication where work-inprocess, information materials and so on are being excessively delayed. www. ncetianz. webs. com 1. 4 Disadvantages of simulation • Model building requires special training. • Simulation results may be difficult to interpret. • Simulation modeling and analysis can be time consuming and expensive. • Simulation is used in some cases when an analytical solution is possible or even preferable. 1. 5 Applications of Simulation Manufacturing Applications 1.
Analysis of electronics assembly operations 2. Design and evaluation of a selective assembly station for highprecision scroll compressor shells. 3. Comparison of dispatching rules for semiconductor manufacturing using large facility models. 4. Evaluation of cluster tool throughput for thin-film head production. 5. Determining optimal lot size for a semiconductor backend factory. 6. Optimization of cycle time and utilization in semiconductor test manufacturing. 7. Analysis of storage and retrieval strategies in a warehouse. 8. Investigation of dynamics in a service oriented supply chain. 9.
Model for an Army chemical munitions disposal facility. Semiconductor Manufacturing 1. Comparison of dispatching rules using large-facility models. 2. The corrupting influence of variability. 3. A new lot-release rule for wafer fabs. 4. Assessment of potential gains in productivity due to proactive retied management. 5. Comparison of a 200 mm and 300 mm X-ray lithography cell. 6. Capacity planning with time constraints between operations. 7. 300 mm logistic system risk reduction. Construction Engineering 1. Construction of a dam embankment. 2. Trench less renewal of underground urban infrastructures.
Nc et ia -5- nz www. ncetianz. webs. com 3. Activity scheduling in a dynamic, multiproject setting. 4. Investigation of the structural steel erection process. 5. Special purpose template for utility tunnel construction. Military Applications 1. Modeling leadership effects and recruit type in a Army recruiting station. 2. Design and test of an intelligent controller for autonomous underwater vehicles. 3. Modeling military requirements for nonwarfighting operations. 4. Multitrajectory performance for varying scenario sizes. 5. Using adaptive agents in U. S. Air Force retention.
Logistics, Transportation and Distribution Applications 1. Evaluating the potential benefits of a rail-traffic planning algorithm. 2. Evaluating strategies to improve railroad performance. 3. Parametric Modeling in rail-capacity planning. 4. Analysis of passenger flows in an airport terminal. 5. Proactive flight-schedule evaluation. 6. Logistic issues in autonomous food production systems for extended duration space exploration. 7. Sizing industrial rail-car fleets. 8. Production distribution in newspaper industry. 9. Design of a toll plaza 10. Choosing between rental-car locations. 11.
Quick response replenishment. Business Process Simulation 1. Impact of connection bank redesign on airport gate assignment. 2. Product development program planning. 3. Reconciliation of business and system modeling. 4. Personal forecasting and strategic workforce planning. Human Systems 1. Modeling human performance in complex systems. 2. Studying the human element in out traffic control. 1. 6 Systems Nc et ia -6- nz www. ncetianz. webs. com A system is defined as an aggregation or assemblage of objects joined in some regular interaction or interdependence toward the accomplishment of some purpose.
Example : Production System Production Control System Purchasing Department Fabrication Department Assembly Department Shipping Department In the above system there are certain distinct objects, each of which possesses properties of interest. There are also certain interactions occurring in the system that cause changes in the system. 1. 7 Components of a System Entity An entity is an object of interest in a system. Ex: In the factory system, departments, orders, parts and products are The entities. Attribute An attribute denotes the property of an entity.
Ex: Quantities for each order, type of part, or number of machines in a Department are attributes of factory system. Activity Any process causing changes in a system is called as an activity. Ex: Manufacturing process of the department. Nc State of the System et ia -7- nz www. ncetianz. webs. com The state of a system is defined as the collection of variables necessary to describe a system at any time, relative to the objective of study. In other words, state of the system mean a description of all the entities, attributes and activities as they exist at one point in time.
Event An event is define as an instaneous occurrence that may change the state of the system. 1. 8 System Environment The external components which interact with the system and produce necessary changes are said to constitute the system environment. In modeling systems, it is necessary to decide on the boundary between the system and its environment. This decision may depend on the purpose of the study. Ex: In a factory system, the factors controlling arrival of orders may be considered to be outside the factory but yet a part of the system environment.
When, we consider the demand and supply of goods, there is certainly a relationship between the factory output and arrival of orders. This relationship is considered as an activity of the system. Endogenous System The term endogenous is used to describe activities and events occurring within a system. Ex: Drawing cash in a bank. Exogenous System The term exogenous is used to describe activities and events in the environment that affect the system. Ex: Arrival of customers. Open system A system for which there is exogenous activity and event is said to be a open. Ex: Bank system. Nc et ia -8- z Closed System A system for which there is no exogenous activity and event is said to be a closed. Ex: Water in an insulated flask. www. ncetianz. webs. com Discrete and Continuous Systems Continuous Systems Systems in which the changes are predominantly smooth are called continuous system. Ex: Head of a water behind a dam. Head Of Water Behind The dam Time t Discrete Systems Systems in which the changes are predominantly discontinuous are called discrete systems. Ex: Bank – the number of customers changes only when a customer arrives or when the service provided a customer is completed. 0 Time t Nc et ia -9- No. of Customers Waiting in The Line 2 nz www. ncetianz. webs. com 1. 10 Model of a system A model is defined as a representation of a system for the purpose of studying the system. It is necessary to consider only those aspects of the system that affect the problem under investigation. These aspects are represented in a model, and by definition it is a simplification of the system. 1. 11 Types of Models The various types models are • • • • • • • Mathematical or Physical Model Static Model Dynamic Model Deterministic Model Stochastic Model Discrete Model Continuous Model
Mathematical Model Uses symbolic notation and the mathematical equations to represent a system. Static Model Represents a system at a particular point of time and also known as Monte-Carlo simulation. Deterministic Model Contains no random variables. They have a known set of inputs which will result in a unique set of outputs. Ex: Arrival of patients to the Dentist at the scheduled appointment time. Stochastic Model Nc et ia – 10 – nz Dynamic Model Represents systems as they change over time. Ex: Simulation of a bank www. ncetianz. webs. com Has one or more random variable as inputs. Random inputs leads to random outputs.
Ex: Simulation of a bank involves random interarrival and service times. Discrete and Continuous Model Used in an analogous manner. Simulation models may be mixed both with discrete and continuous. The choice is based on the characteristics of the system and the objective of the study. 1. 12 Discrete-Event System Simulation Modeling of systems in which the state variable changes only at a discrete set of points in time. The simulation models are analyzed by numerical rather than by analytical methods. Analytical methods employ the deductive reasoning of mathematics to solve the model.
Eg: Differential calculus can be used to determine the minimum cost policy for some inventory models. Numerical methods use computational procedures and are ‘runs’, which is generated based on the model assumptions and observations are collected to be analyzed and to estimate the true system performance measures. Real-world simulation is so vast, whose runs are conducted with the help of computer. Much insight can be obtained by simulation manually which is applicable for small systems. 1. 13 Steps in a Simulation study 1. Problem formulation Every study begins with a statement of the problem, provided by policy makers.
Analyst ensures its clearly understood. If it is developed by analyst policy makers should understand and agree with it. 2. Setting of objectives and overall project plan The objectives indicate the questions to be answered by simulation. At this point a determination should be made concerning whether simulation is the appropriate methodology. Assuming it is appropriate, the overall project plan should include • A statement of the alternative systems • A method for evaluating the effectiveness of these alternatives • Plans for the study in terms of the number of people involved
Nc et ia – 11 – nz www. ncetianz. webs. com • Cost of the study • The number of days required to accomplish each phase of the work with the anticipated results. 3. Model conceptualization The construction of a model of a system is probably as much art as science. 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 • To enrich and elaborate the model until a useful approximation results Thus, it is best to start with a simple model and build toward greater complexity.
Model conceptualization enhance the quality of the resulting model and increase the confidence of the model user in the application of the model. 4. Data collection There is a constant interplay between the construction of model and the collection of needed input data. Done in the early stages. Objective kind of data are to be collected. 5. Model translation Real-world systems result in models that require a great deal of information storage and computation. It can be programmed by using simulation languages or special purpose simulation software. Simulation languages are powerful and flexible.
Simulation software models development time can be reduced. Nc 7. Validated It is the determination that a model is an accurate representation of the real system. Achieved through calibration of the model, an iterative process of comparing the model to actual system behavior and the discrepancies between the two. – 12 – et ia nz 6. Verified It pertains to he computer program and checking the performance. If the input parameters and logical structure and correctly represented, verification is completed. www. ncetianz. webs. com 8. Experimental Design The alternatives that are to be simulated must be determined.
Which alternatives to simulate may be a function of runs. For each system design, decisions need to be made concerning • Length of the initialization period • Length of simulation runs • Number of replication to be made of each run 9. Production runs and analysis They are used to estimate measures of performance for the system designs that are being simulated. 10. More runs Based on the analysis of runs that have been completed. The analyst determines if additional runs are needed and what design those additional experiments should follow. 11. Documentation and reporting Two types of documentation. Program documentation • Process documentation Program documentation Can be used again by the same or different analysts to understand how the program operates. Further modification will be easier. Model users can change the input parameters for better performance. Process documentation Gives the history of a simulation project. The result of all analysis should be reported clearly and concisely in a final report. This enable to review the final formulation and alternatives, results of the experiments and the recommended solution to the problem.
The final report provides a vehicle of certification. 12. Implementation Nc et ia – 13 – nz www. ncetianz. webs. com Success depends on the previous steps. If the model user has been thoroughly involved and understands the nature of the model and its outputs, likelihood of a vigorous implementation is enhanced. The simulation model building can be broken into 4 phases. I Phase • Consists of steps 1 and 2 • It is period of discovery/orientation • The analyst may have to restart the process if it is not fine-tuned • Recalibrations and clarifications may occur in this phase or another phase. Consists of steps 3,4,5,6 and 7 • A continuing interplay is required among the steps • Exclusion of model user results in implications during implementation II Phase III Phase • • • • Consists of steps 8,9 and 10 Conceives a thorough plan for experimenting Discrete-event stochastic is a statistical experiment The output variables are estimates that contain random error and therefore proper statistical analysis is required. Nc et ia – 14 – nz IV Phase • Consists of steps 11 and 12 • Successful implementation depends on the involvement of user and every steps successful completion. www. ncetianz. webs. com Problem formulation
Setting of objectives and overall project plan Model conceptualization Data collection Model translation Verified Yes No Validat ed No Experimental design Production runs and analysis Y Y More Runs Documentation and reporting Implementation Nc et ia – 15 – No nz www. ncetianz. webs. com Chapter 2 Simulation Examples • Simulation is often used in the analysis of queueing models. In a simple typical queueing model, shown in fig 1, customers arrive from time to time and join a queue or waiting line, are eventually served, and finally leave the system. Waiting line of customers Calling population of potential customers ig 1: Simple Queuing Model • The term “customer” refers to any type of entity that can be viewed as requesting “service” from a system. 2. 1 Characteristics of Queueing Systems • • • The key elements, of a queueing system are the customers and servers. The term “customer” can refer to people, machines, trucks, mechanics, patients—anything that arrives at a facility and requires service The term “server” might refer to receptionists, repairpersons, CPUs in a computer, or washing machines…. any resource (person, machine, etc. which provides the requested service. Table 1 lists a number of different queueing systems.
System Reception desk Repair facility Garage Tool crib Hospital Warehouse Airport Production line Warehouse Road network Grocery Laundry Job shop Lumberyard Saw mill Computer Telephone Ticket office Mass transit Customers People Machines Trucks Mechanics Patients Pallets Airplanes Cases Orders Cars Shoppers Dirty linen Jobs Trucks Logs Jobs Calls Football fans Riders Server(s) Receptionist Repairperson Mechanic Tool-crib clerk Nurses Crane Runway Case packer Order picker Traffic light Checkout station Washing machines/dryers Machines/workers Overhead crane Saws CPU, disk, tapes Exchange Clerk Buses, trains
Nc et ia – 16 – nz www. ncetianz. webs. com Table 1: Examples of Queueing Systems The elements of a queuing system are:- • The Calling Population:- The population of potential customers, referred to as the calling population, may be assumed to be finite or infinite. For example, consider a bank of 5 machines that are curing tires. After an interval of time, a machine automatically opens and must be attended by a worker who removes the tire and puts an uncured tire into the machine. The machines are the “customers”, who “arrive” at the instant they automatically open.
The worker is the “server”, who “serves” an open machine as soon as possible. The calling population is finite, and consists of the five machines. In systems with a large population of potential customers, the calling population is usually assumed to be finite or infinite. Examples of infinite populations include the potential customers of a restaurant, bank, etc. The main difference between finite and infinite population models is how the arrival rate is defined. In an infinite-population model, the arrival rate is not affected by the number of customers who have left the calling population and joined the queueing system.
On the other hand, for finite calling population models, the arrival rate to the queueing system does depend on the number of customers being served and waiting. • System Capacity:In many queueing systems there is a limit to the number of customers that may be in the waiting line or system. For example, an automatic car wash may have room for only 10 cars to wait in line to enter the mechanism. An arriving customer who finds the system full does not enter but returns immediately to the calling population. Some systems, such as concert ticket sales for students, may be considered as having unlimited capacity.
There are no limits on the number of students allowed to wait to purchase tickets. • The Arrival Process:- Arrival process for infinite-population models is usually characterized in terms of interarrival times of successive customers. Arrivals may occur at scheduled times or at random times. When at random times, the interarrival times are usually characterized by a probability distribution Nc et ia – 17 – nz When a system has limited capacity, a distinction is made between the arrival rate (i. e. , the number of arrivals per time unit) and the effective arrival rate (i. . , the number who arrive and enter the system per time unit). www. ncetianz. webs. com The most important model for random arrivals is the Poisson arrival process. If An represents the interarrival time between customer n-1 and customer n (A1 is the actual arrival time of the first customer), then for a Poisson arrival process. An is exponentially distributed with mean I/? time Units. The arrival rate is ? customers per time unit. The number of arrivals in a time interval of length t, say N ( t ) , has the Poisson distribution with mean ? t customers.
The Poisson arrival process has been successfully employed as a model of the arrival of people to restaurants, drive-in banks, and other service facilities. A second important class of arrivals is the scheduled arrivals, such as patients to a physician’s office or scheduled airline flight arrivals to an airport. In this case, the interarrival times [ A n , n = 1,2,. . . } may be constant, or constant plus or minus a small random amount to represent early or late arrivals. A third situation occurs when at least one customer is assumed to always be present in the queue, so that the server is never idle because of a lack of customers.
For example, the "customers” may represent raw material for a product, and sufficient raw material is assumed to be always available. For finite-population models, the arrival process is characterized in a completely different fashion. Define a customer as pending when that customer is outside the queueing system and a member of the potential calling population. Runtime of a given customer is defined as the length of time from departure from the queueing system until that customer’s next arrival to the queue. Let Ai(i), A2(i),… e the successive runtimes of customer /, and let S(i)1, S(i)2….. be the corresponding successive system times; that is, S(i)n is the total time spent in the system by customer i during the nth visit. Figure 2 illustrates these concepts for machine 3 in the tire-curing example. The total arrival process is the superposition of the arrival times of all customers. Fig 2 shows the first and second arrival of machine 3. Fig 2: Arrival process for a finite-population model. A1(3) S1(3) A2(3) St2(3) Machine 3 pending First arrival of machine 3 Second arrival of machine 3
One important application of finite population models is the machine repair problem. The machines are the customers and a runtime is also called time to failure. When a machine fails, it "arrives” at the queuing g system (the repair facility) and remains there until it is "served” (repaired). Times to failure for a given class of machine have been characterized by the exponential, the Nc et ia – 18 – nz open pending (System time) open (System time) www. ncetianz. webs. com Weibull, and the gamma distributions. Models with an exponential runtime are sometimes analytically tractable. Queue Behavior and Queue Discipline:- Queue behavior refers to customer actions while in a queue waiting for service to begin. In some situations, there is a possibility that incoming customers may balk (leave when they see that the line is too long), renege (leave after being in the line when they see that the line is moving too slowly), or jockey (move from one line to another if they think they have chosen a slow line). Queue discipline refers to the logical ordering of customers in a queue and determines which customer will be chosen for service when a server becomes free.
Common queue disciplines include first-in, first-out (FIFO); last-in firstout (LIFO); service in random order (SIRO); shortest processing time first |(SPT) and service according to priority (PR). In a job shop, queue disciplines are sometimes based on due dates and on expected processing time for a given i type of job. Notice that a FIFO queue discipline implies that services begin in the same order as arrivals, but that customers may leave the system in a different order because of differentlength service times. • Service Times and the Service Mechanism:-
The service times of successive arrivals are denoted by S1, S2, S3…They may be constant or of random duration. The exponential,Weibull, gamma, lognormal, and truncated normal distributions have all been used successfully as models of service times in different situations. . Sometimes services may be identically distributed for all customers of a given type or class or priority, while customers of different types may have completely different service-time distributions. In addition, in some systems, service times depend upon the time of day or the length of the waiting line.
For example, servers may work faster than usual when the waiting line is long, thus effectively reducing the service times. • Example 1:- Nc o n e et ia – 19 – Consider a discount warehouse where customers may either serve themselves; or wait f o r nz A queueing system consists of a number of service centers and interconnecting queues. Each service center consists of some number of servers, c, working in parallel; that is, upon getting to the head of the line, a customer takes the first available server. Parallel service mechanisms are either single server (c = 1), multiple server (1 ; c ; ? , or unlimited servers (c= ? ). (A self-service facility is usually characterized as having an unlimited number of servers. ) www. ncetianz. webs. com of three clerks, and finally leave after paying a single cashier. The system is represented by the flow diagram in figure 1 below: Figure 1: Discount warehouse with three service centers The subsystem, consisting of queue 2 and service center 2, is shown in more detail in figure 2 below. Other variations of service mechanisms include batch service (a server serving several customers simultaneously) or a customer requiring several servers simultaneously.
Service center 2 gh Arrivals Departure Figure 2: Service center 2, with c = 3 parallel servers. • Example 2:-A candy manufacturer has a production line which consists of three machines separated by inventory-in-process buffers. The first machine makes and wraps the individual pieces of candy, the second packs 50 pieces in a box, and the third seals and wraps the box. The two inventory buffers have capacities of 1000 boxes each. As illustrated by Figure 3, the system is modeled as having three service centers, each center having c = 1 server (a machine), with queue-capacity constraints between machines.
It is assumed that a sufficient supply of raw material is always available at the first queue. Because of the queue-capacity constraints, machine 1 shuts down whenever the inventory buffer fills to capacity, while machine 2 shuts down whenever the buffer empties. In brief, the system consists of three single-server queues in series with queue-capacity constraints and a continuous arrival stream at the first queue. Machine 1 Queue 2 Queue 1 Capacity 1000 Machine 2 Queue 3 Capacity 1000 Candy maker/wrapper Packer Nc et ia Machine 3 Sealer/ wrapper nz – 20 – www. ncetianz. webs. com Figure 3: Candy production line 2. Queueing Notation:. Recognizing the diversity of queueing systems, Kendall [1953] proposed a notational system for parallel server systems which has been widely adopted. An abridged version of this convention is based on the format A /B / c / N / K. These letters represent the following system characteristics: A represents the interarrival time distribution. B represents the service-time distribution. [Commo[Common symbols for A and B include M (exponential or Markov), D (constant or deterministic), Ek (Erlang of order k), PH (phase-type), H (hyperexponential), G (arbitrary or general), and GI (General independent). c represents the number of parallel servers. N represents the system capacity. K represents the size of the calling population For example, M / M / 1 / ? / ? indicates a single-server system that has unlimited queue capacity and an infinite population of potential arrivals. The interarrival times and service times are exponentially distributed. When N and K are infinite, they may be dropped from the notation. For example, M / M / 1 / ? / ? is often shortened to M/M/l. Additional notation used for parallel server systems is listed in Table 1 given below.
The meanings may vary slightly from system to system. All systems will be assumed to have a FIFO queue discipline. Table 1. Queueing Notation for Parallel Server Systems LQ Nc Pn Pn,(t) ? ?e µ ? An Sn, Wn WnQ L(t) L Q(t) L Steady-state probability of having n customers in system Probability of n customers in system at time t Arrival rate Effective arrival rate Service rate of one server Server utilization Interarrival time between customers n — 1 and n Service time of the nth arriving customer Total time spent in system by the nth arriving customer Total time spent in the waiting line by customer n .
The number of customers in system at time / The number of customers in queue at time t Long-run time-average number of customers in system Long-run time-average number of customers in queue et ia – 21 – nz www. ncetianz. webs. com ? ? Q Long-run average time spent in system per customer Long-run average time spent in queue per customer 2. 3 Simulation of Queuing systems A queueing system is described by its calling population, the nature of the arrivals, the service mechanism, the system capacity, and the queueing discipline. A single-channel queueing system is portrayed in figure1. Calling population aiting line server Figure 1: Queueing System In the single-channel queue, the calling population is infinite; that is, 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. In addition, 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.
Finally, units are served in the order of their arrival by a single server or channel. Arrivals and services are defined by the distributions 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. When queues grow without bound, they are termed "explosive” or unstable. The state of the system is the number of units in the system and the status of the server, busy or idle.
An event is 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. They are the entry of a unit into the system. The completion of service on a unit. Nc The queueing system includes the server, the unit being serviced, and units in the queue. he simulation clock is used to track simulated time. 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. t ia – 22 – nz www. ncetianz. webs. com Departure Event Begin Server Idle time Another unit waiting? Remove the waiting unit from the queue Begin Servicing the unit Figure 2: Service-just-completed flow diagram The arrival event occurs when a unit enters the system. The flow diagram for the arrival event is shown in figure 3. The unit may find the server either idle or busy; therefore, either the unit begins service immediately, or it enters the queue for the server. The unit follows the course of action shown in fig 4. Arrival Event Server Busy? Figure 3: Unit-Entering system flow diagram
If the server is busy, the unit enters the queue. If the server is idle and the queue is empty, the unit begins service. It is not possible for the server to be idle and the queue to be nonempty. Nc et ia – 23 – nz Unit Enters Service Unit Enters Queue for service www. ncetianz. webs. com Queue Status Not Empty Busy Server Status Idle Enter Queue Impossible Empty Enter Queue Enter Service Figure 4: Potential unit actions upon arrival After the completion of a service the service may become idle or remain busy with the next unit. The relationship of these two outcomes to the status of the queue is shown in fig 5.
If the queue is not empty, another unit will enter the server and it will be busy. If the queue is empty, the server will be idle after a service is completed. These two possibilities are shown as the shaded portions of fig 5. It is impossible for the server to become busy if the queue is empty when a service is completed. Similarly, it is impossible for the server to be idle after a service is completed when the queue is not empty. Queue Status Not Empty Busy Server Status Idle Impossible Empty Impossible Figure 5: Server outcomes after service completion Nc et ia – 24 –
Random numbers are distributed uniformly and independently on the interval (0, 1). Random digits are uniformly distributed on the set {0, 1, 2… 9}. Random digits can be used to form random numbers by selecting the proper number of digits for each random number and placing a decimal point to the left of the value selected. The proper number of digits is dictated by the accuracy of the data being used for input purposes. If the input distribution has values with two decimal places, two digits are taken from a random-digits table and the decimal point is placed to the left to form a random number. z 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. In these cases, a statistical model of the data is developed from either data collected and analyzed, or subjective estimates and assumptions. www. ncetianz. webs. com When numbers are generated using a procedure, they are often referred to as pseudorandom numbers. Since the method is known, it is always possible to know the sequence of numbers that will be generated prior to the simulation.
In a single-channel queueing system, interarrival times and service times are generated from the distributions of these random variables. The examples that follow show how such times are generated. For simplicity, assume that the times between arrivals were generated by rolling a die five times and recording the up face. Table 1 contains a set of five interarrival times are used to compute the arrival times of six customers at the queuing system. Table 1: Interarrival and Clock Times Customer Interarrival Time Arrival Time on Clock 0 2 6 7 9 15 C 1 2 3 Table 2. 3 4 5 6 -2 4 1 2 6
The first customer is assumed to arrive at clock time 0. This starts the clock in operation. The second customer arrives two time units later, at a click time of 2. The third customer arrives four time units later, at a clock time of 6; and so on. The second time of interest is the service time. The only possible service times are one, two, three, and four time units. 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.
Table 2 was designed specifically for a single-channel queue which serves customers on a first-in, first-out (FIFO) basis. It keeps track of the clock time at which each event occurs. The second column of table 2 records the clock time of each arrival event, while the last column records the clock time of each departure event. Nc et ia – 25 – nz Now, the interarrival times and service times must be meshed to simulate the singlechannel queueing system. As shown in table 2, the first customer arrives at clock time 0 and immediately begins service, which requires two minutes.
Service is completed at clock time 2. The second customer arrives at clock time 2 and is a finished at clock time 3. Note that the fourth customer arrived at clock time 7, but service could not begin until clock time 9. This occurred because customer 3 did not finish service until clock time 9. www. ncetianz. webs. com Table 2: Simulation Table emphasizing Clock Times A Customer No. B Arrival Time (Clock) 0 2 6 7 9 15 C Time Service Begins (Clock) 0 2 6 9 11 15 D 2 Service Time 1 (Duration) 3 2 1 3 2 1 4 E Time Service Ends (Clock) 2 3 9 11 12 19 1 2 3 4 5 6
EXAMPLE 1: Single-Channel Queue A small grocery store has only one checkout counter. Customers arrive at this checkout counter at random from 1 to 8 minutes apart. Each possible value of interarrival time has the same probability of occurrence. The service times vary from 1 to 6 minutes with the probabilities shown in table 5. The problem is to analyze the system by simulating the arrival and service of 20 customers. Table 5: Service Time Distribution Service Time (Min) 1 2 3 4 5 6 Probability 0. 10 0. 20 0. 30 0. 25 0. 10 0. 05 Cumulative Frequency 0. 10 0. 30 0. 60 0. 5 0. 95 1. 00 Random Digit Assignment 01-10 11-12 31-60 61-85 86-95 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: 1. The set of random numbers is uniformly distributed between 0 and 1. Nc et ia – 26 – nz 96-00 www. ncetianz. webs. com 2. Successive random numbers are independent.
The time-between-arrival determination is shown in table 6. Note that the first random digits are 913. To obtain the corresponding time between arrivals, enter the fourth column of table 4 and read 8 minutes from the first column of the table. Alternatively, we see that 0. 913 is between the cumulative probabilities 0. 876 and 1. 000, again resulting in 8 minutes as the generated time Table 6: Time between Arrivals Determination Customers Random Digits Time Between Arrivals (Min) Customers Random Digits Time Between Arrivals (Min) 1 2 3 4 5 6 7 8 9 10 913 727 015 948 309 922 753 235 302 -8 6 1 8 3 8 . 7 2 3 11 12 13 14 15 16 17 18 19 20 109 093 607 738 359 888 106 212 493 535 1 1 5 6 3 8 1 2 4 5 Service times for all 20 customers are shown in table 7. These service times were generated based on the methodology described above, together with the aid of table 5. The first customer’s service time is 4 minutes because the random digits 84 fall in the bracket 61-85, or alternatively because the derived random number 0. 84 falls between the cumulative probabilities 0. 61 and 0. 85. Table 7: Service Times Generated
Customer 1 2 3 4 5 6 7 8 9 10 Random Digits 84 10 74 53 17 79 91 67 89 38 Service Time (Min) 4 1 4 3 2 4 5 4 5 3 Customer 11 12 13 14 15 16 17 18 19 20 Random Digits 32 94 79 05 79 84 52 55 30 50 Service Time (Min) 3 5 4 1 5 4 3 3 2 3 The essence of a manual simulation is the simulation table. These tables are designed for the problem at hand, with columns added to answer the questions posed. The simulation table for the single-channel queue, shown, in table 8 that is an extension of table 2. The first step is to initialize the table by filling in cells for the first customer. Nc
The first customer is assumed to arrive at time 0. Service begins immediately and finishes at time 4. The customer was in the system for 4 minutes. After the first customer, subsequent rows in the table are based on the random numbers for interarrival time and et ia – 27 – nz www. ncetianz. webs. com service time and the completion time of the previous customer. For example, the second customer arrives at time 8. Thus, the server was idle for 4 minutes. Skipping down to the fourth customer, it is seen that this customer arrived at time 15 but could not be served until time 18.
This customer had to wait in the queue for 3 minutes. This process continues for all 20 customers. Table 8: Simulation Table for the queueing problem A Customers 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 B Time since last Arrival (Min) -8 6 1 8 3 8 7 2 3 1 1 5 6 3 8 1 2 4 5 C Arrival Time 0 8 14 15 23 26 34 41 43 46 47 48 53 59 62 70 71 73 77 82 D Service Time 4 1 4 3 2 4 5 4 5 3 3 5 4 1 5 4 3 3 2 3 68 E Time Service Begins 0 8 14 18 23 26 34 41 45 50 53 56 61 65 66 71 75 78 81 83 F Time customer waits in queue 0 0 0 3 0 0 0 0 2 4 6 8 8 6 4 1 4 5 4 1 56
G Time Service Ends 4 9 18 21 25 30 39 45 50 53 56 61 65 66 71 75 78 81 83 86 H Time customer spends in system 4 1 4 6 2 4 5 4 7 7 9 13 12 7 9 5 7 8 6 4 124 I Idle Time of Server 0 4 5 0 2 1 4 2 0 0 0 0 0 0 0 0 0 0 0 0 18 1. The average waiting time for a customer is 2. 8minutes. this is determined in the following manner: Total time customers wait in queue (min) _________________________________ Total no. of customers = 56 = 2. 8 minutes 20 Average Waiting Time = Probability (wait) = number of customers who wait Total number of customers 13 = 20 = 0. 65 3.
The fraction of idle time of the server is 0. 21. This is determined in the following manner: Total idle time of server (minutes) Nc et ia – 28 – nz 2. The probability that a customer has to wait in the queue is 0. 65. This is determined in the following manner: www. ncetianz. webs. com Probability of idle server = Total run time of simulation (minutes) 18 = 0. 21 86 The probability of the server being busy is the complement of 0. 21, or 0. 79. = 4. The average service time is 3. 4 minutes, determined as follows: Total service time Average service time (minutes) = Total number of customers 68 = = 3. minutes 20 This result can be compared with the expected service time by finding the mean of the service-time distribution using the equation E(s) = ? sp (s) Applying the expected-value equation to the distribution in table 2. 7 gives an expected service time of: = 1(0. 10) + 2(0. 20) + 3(0. 30) + 4(0. 25) + 5(0. 10) + 6(0. 50) = 3. 2 minutes The expected service time is slightly lower than the average time in the simulation. The longer simulation, the closer the average will be to E (S). 5. The average time between arrivals is 4. 3 minutes.
This is determined in the following manner: Sum (minutes) Average time between arrivals (minutes) = Number of arrivals – 1 82 = 19 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 endpoints are a = 1 and b = 8. The mean is given by a+b E (A) = 2 = 2 1+8 = 4. 5 minutes = 4. 3 minutes of all times between arrivals Nc The expected time between arrivals is slightly higher than the average.
However, as the simulation becomes longer, the average value of the time between arrivals will approach the theoretical mean, E (A). et ia – 29 – nz www. ncetianz. webs. com 6. 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 = Total number of customers who wait 56 = 13 = 4. 3 minutes 7. The average time a customer spends in the system is 6. 2 minutes. This can be determined in two ways. First, the computation can be achieved by the following relationship:
Average time customer Spends in the system total time customers spend in the system = Total number of customers 124 = 20 = 6. 2 minutes The second way of computing this same result is to realize that the following relationship must hold: Average time customer average time customer average time customer Spends in the system = spends waiting in the queue + spends in service From findings 1 and 4 this results in: Average time customer spends in the system = 2. 8+ 3. 4 = 6. 2 minutes. EXAMPLE 2:- The Able Baker Carhop Problem Time Between arrivals (Min) 1 2 3 4 Probability 0. 5 0. 40 0. 20 0. 15 Cumulative Probability 0. 25 0. 65 0. 85 1. 00 Random Digit Assignment 01-25 26-65 66-85 86-00 Nc et ia – 30 – Table 1: Interarrival distribution of Cars nz This example illustrates the simulation procedure when there is more than one service channel. Consider a drive-in restaurant where carhops take orders and bring food to the car. Cars arrive in the manner shown in table 1. There are 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 are shown in tables 2 and 3. ww. ncetianz. webs. com The simulation proceeds in a manner similar to example 1, except that it its more complex because of the two servers. A simplifying rule is that Able gets the customer if both carhops are idle. Perhaps, Able has seniority. (The solution would be different if the decision were made at random or by any other rule. ) Table 2: Service Distribution of Able Service Time Service Time (minutes) (Minutes) 2 3 4 5 Probability Cumulative Probability 0. 30 0. 58 0. 83 1. 00 Random-Digit Assignment 01-30 31-58 59-83 84-00 0. 30 0. 28 0. 25 0. 17
Table 3: Service Distribution of Baker Table 3: Service Distribution of Baker Service Time Service Time (minutes) (Minutes) 3 4 5 6 Probability Cumulative Probability 0. 35 0. 60 0. 80 1. 00 Random-Digit Assignment 01-35 36-60 61-80 81-00 0. 35 0. 25 0. 20 1. 00 Here there are more events: a customer arrives, a customer begins service from able, a customer completes service from Able, a customer begins service from Baker, and a customer completes service from Baker. The simulation table is shown in table 4. After the first customer, the cells for the other customers must be based on logic and formulas.
For example, the "clock time of arrival” in the row for the second customer is computed as follows: D2 = D1+C2 . The logic to compute who gets a given customer, and when that service begins, is more complex. The logic goes as follows when a customer arrives: if the customer finds able idle, the customer begins service immediately with able. If able is not idle but baker is, then the customer begins service immediately with baker. If both are busy, the customer begins service with the first server to become free. The analysis of table 4 results in the following: 1.
Over the 62-minute period able was busy 90% of the time. 2. Baker was busy only 69% of the tome. The seniority rule keeps baker less busy. 3. Nine of the 26 arrivals had to wait. The average waiting time for all customers was only about 0. 42 minute, which is very small. 4. Those nine who did have to wait only waited an average of 1. 22 minutes, which is quite low. 5. 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. Table 4: Simulation Table for the Carhop Example A Customer No. B Random Digits for Arrival C Time between Arrivals D Clock time Arrival E Random Digits for Service F Time Service Begins G Service Time H Time Service Ends I Time Service Begins J Service Time K Time Service Ends Nc et ia L Time In Queue nz – 31 – www. ncetianz. webs. com 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 -26 98 90 26 42 74 80 68 22 48 34 45 24 34 63 38 80 42 56 89 18 51 71 16 92 2 4 4 2 2 3 3 3 1 2 2 2 1 2 2 2 3 2 2 4 1 2 3 1 4 0 2 6 10 12 14 17 20 23 24 26 28 30 31 33 35 37 40 42 44 48 49 51 54 55 59 95 21 51 92 89 38 13 61 50 49 39 53 88 01 81 53 81 64 01 67 01 47 75 57 87 47 0 6 10 15 18 20 24 27 30 35 39 43 45 49 54 59 56 5 3 5 3 2 4 3 3 5 4 4 2 4 3 3 3 5 2 9 15 12 18 20 24 23 27 30 28 35 32 39 35 43 40 45 49 48 52 51 57 56 62 3 5 6 18 4 27 4 3 4 5 32 35 39 45 3 5 6 43 51 56 62 0 0 0 0 0 1 1 0 0 0 1 0 0 1 2 0 2 0 1 1 0 0 0 0 1 0 11 2. 4 Simulation of Inventory Systems An important class of simulation problems involves inventory systems.
A simple inventory system is shown in fig 1. 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. At the end of the review period, an order quantity, Q1, is placed. In this inventory system the lead time is zero. Demand is shown as being uniform over the time period in fig 1. In actuality, demands are not usually uniform and do fluctuate over time. One possibility is that demands all occur at the beginning of the cycle. Another is that the lead time is random of some positive length.
Notice that in the second cycle, the amount in inventory drops below zero, indicating a shortage. In fig 1, these units are backordered. When the order arrives, the demand for the backordered items is satisfied first. To avoid shortages, a buffer, or safety, stock would need to be carried. Carrying stock in inventory has an associated cost attributed to the interest paid on the funds borrowed to buy the items. Other costs can be placed in the carrying or holding cost column: renting of storage space, hiring guards, and so on. The total cost of an inventory system is the measure of performance.
This can be affected by the policy alternatives. For example, in fig 1, the decision maker can control the maximum inventory level, M, and the cycle, N. Nc et ia – 32 – An alternative to carrying high inventory is to make more frequent reviews, and consequently, more frequent purchases or replenishments. This has an associated cost: the ordering cost. Also, there is a cost in being short. Larger inventories decrease the possibilities of shortages. These costs must be traded off in order to minimize the total cost of an inventory system. nz www. ncetianz. webs. com
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. When the lead time is zero, as in fig 1, the last two events occur simultaneously. • The Newspaper Seller’s Problem A classical inventory problem concerns the purchase and sale of newspapers. The paper seller buys the papers for 33 cents each and sells them for 50 cents each. Newspapers not sold at the end of the 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, and so on. There are three types of Newsday’s, "good,” "fair,” and "poor,” with probabilities of 0. 35, 0. 45, and 0. 25, respectively. The distribution of papers demanded on each of these days is given in table 2. 15. 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 Profit = form sales cost of newspapers lost profit form excess demand salvage from sale of scrap papers
Table 5: Distribution of Newspaper Demanded Demand Probability Distribution Demand 40 50 60 Good 0. 03 0. 05 0. 15 Fair 0. 10 0. 18 0. 40 Poor 0. 44 0. 22 0. 16 Tables 6 and 7 provide the random-digit assignments for the types of Newsday’s and the demands for those Newsday’s. Table 6: Random Digit Assignment for Type of Newsday Nc et ia – 33 – Form the problem statement, the revenue from sales is 50 cents for each paper sold. The Cost 9 of newspapers is 33 cents for each paper purchased. The lost profit from excess demand is 17 cents for each paper demanded that could not be provided.
Such a shortage cost is somewhat controversial but makes the problem much more interesting. The salvage value of scrap papers is 5 cents each. nz www. ncetianz. webs. com Type of Newsday Good Fair Poor Probability 0. 35 0. 45 0. 20 Cumulative probability 0. 35 0. 80 1. 00 Random Digit Assignment 01 – 35 36 – 80 81 – 00 Table 7: Random Digit Assignment for Newspapers Demanded Cumulative Distribution Demand Good Fair Poor Good Random Digit Assignment Fair Poor 40 50 60 0. 03 0. 08 0. 23 0. 10 0. 28 0. 68 0. 44 0. 66 0. 82 01 – 03 04- 08 09 – 23 01 – 10 11 – 28 29 – 68 1 – 44 45 – 66 67 – 82 The simulation table for the decision to purchase 70 newspapers is shown in table 8. On day 1 the demand is for 60 newspapers. The revenue from the sale of 60 newspapers is $30. 00. Ten newspapers are left over at the end of the day. The salvage value at 5 cents each is 50 cents. The profit for the first day is determined as follows: Profit = $30. 00 – $ 23. 10 – 0 + $. 50 = $7. 40 Table 8: Simulation table fro purchase of 70 newspapers Day Random digits for type of Newsday Type of Newsday Random digits for demand 80 20 15 Demand Revenue from sales
Lost profit from excess demand – Salvage from sale of scrap Daily profit 1 2 3 94 77 49 Poor Fair Fair 60 50 50 $30 $25 $25 $0. 50 $1. 0 $1. 0 $7. 40 $2. 90 $2. 90 On the fifth day the demand is greater than the supply. The revenue from sales is $35. 00, since only 70 papers are available under this policy. An additional 20 papers could have been sold. Thus, a lost profit of $3. 40 (20*17 cents) is assessed. The daily profit is determined as follows: Profit = $35. 00 – $23. 10 – $3. 40 + 0 = $8. 50 Total profit = $645 – $462 – $13 . 60 + $5. 50 = $174. 90
In general, since the results of one day are independent of those of previous days, inventory problems of this type are easier than queueing problems. Nc et ia – 34 – The profit for the 20-day period is the sum of the daily profits, $174. 90. it can also be computed from the totals for the 20 days of the simulation as follows: nz www. ncetianz. webs. com Simulation of an (M, N) Inventory System Suppose that the maximum inventory level, M, is 11 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 9. In this example, lead-time is a random variable, as shown in table 10. Assume that orders are placed at the close of business and are received for inventory at the beginning as determined by the lead-time. Table 9: Random digits assignments for daily demand Demand 0 1 2 Probability 0. 10 0. 25 0. 35 Cumulative Probability 0. 10 0. 35 0. 70 Random digits assignments 01 – 10 11 – 35 36 – 70 Random digits assignments Table 10: Random digit assignments for lead time Lead Time (Days) 1 2 3 Probability Cumulative Probability 0. 0. 9 1. 0 Random digits assignments 1–6 7–9 0 0. 6 0. 3 0. 1 Table 11: Simulation table for (M, N) Inventory System Cycle Day Beginning Inventory Random digits for demand Demand Ending Inventory Shortage quantity Order quantity Random digits For lead time Days order arr 1 1 2 3 4 5 3 2 9 7 4 24 35 65 81 54 1 1 2 3 2 2 1 7 4 2 0 0 0 0 0 9 5 Note : Refer cycle 2,3,4,5 from Text book page no 47. To make an estimate of the mean units in ending inventory, many cycles would have to be simulated. For purposes of this example, only five cycles will be shown.
The reader is asked to continue the example as an exercise at the end of the chapter. The random-digit assignments for daily demand and lead time are shown in the rightmost columns of tables 9 and 10. The resulting simulation table is shown in table 11. 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. Nc Following the simulation table for several selected days indicates how the process operates. The order for 8 units is available on the morning of the third day of the first cycle, raising the inventory level from 1 unit to 9 units; t ia – 35 – nz www. ncetianz. webs. com demands during the remainder of the first cycle reduced the ending inventory level to 2 units on the fifth day. Thus, an order for 9 units was placed. The lead time for this order was 1 day. The order of 9 units was added to inventory on the morning of day 2 of cycle 2. 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 ay 4 of cycle 3 there was a beginning inventory of 9 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. 5 (88/25) units. On 2 of 25 days a shortage condition existed. Nc et ia – 36 – nz www. ncetianz. webs. com 3_____ General Principles Introduction • This chapter develops a common framework for the modeling of complex systems using discrete-event simulation. • It covers the basic building blocks of all discrete-event simulation models: entities and attributes, activities and events. In discrete-event simulation, 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 rep-j resent system resources; and the activities and events that cause system state to change. • This chapter deals exclusively with dynamic, stochastic system (i. e. involving time and containing random elements) which changes in a discrete manner. • The concept of a system and a model of a system were discussed briefly in earlier chapters. • This section expands on these concepts and develops a framework for the development of a discrete-event model of a system. The major concepts are briefly defined and then illustrated with examples: • System: A collection of entities (e. g. , people and machines) that ii together over time to accomplish one or more goals. • 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 3. Concepts in Discrete-Event Simulation Nc et ia – 37 – nz www. ncetianz. webs. com time. • Entity: Any object or component in the system which requires explicit representation in the model (e. g. , a server, a customer, a machine). o Attributes: The properties of a given entity (e. g. , the priority of a v customer, the routing of a job through a job shop). o 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 as an arrival of a new customer). o 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. o Event list: A list of event notices for future events, ordered by time of occurrence; also known as the future event list (FEL). o Activity: A duration of time of specified length (e. g. , a service time or arrival time), which is known when it begins (although it may be defined in terms of a statistical distribution). Delay: A duration of time of unspecified indefinite length, which is not known until it ends (e. g. , a customer’s delay in a last-in, first-out waiting line which, when it begins, depends on future arrivals). o Clock: A variable representing simulated time. • The future event list is ranked by the event time recorded in the event notice. • 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:
Nc et ia – 38 – nz www. ncetianz. webs. com 1. Deterministic-for example, always exactly 5 minutes. 2. Statistical-for example, as a random draw from among 2,5,7 with equal probabilities. 3. A function depending on system variables and/or entity attributes. • The duration of an activity is computable from its specification at the instant it begins . • A delay’s duration is not specified by the modeler ahead of time, but rather is determined by system conditions. • A delay is sometimes called a conditional wait, while an activity is called unconditional wait. The completion of an activity is an event, often called primary event. • The completion of a delay is sometimes called a conditional or secondary event. (Able and Baker, Revisited) Consider the Able-Baker carhop system of Example 2. 2. A discrete- event model has the following components: System state LQ(t), the number of cars waiting to be served at time t LA(t), 0 or 1 to indicate Able being idle or busy at time t LB (t), 0 or 1 to indicate Baker being idle or busy at time t Entities Neither the customers (i. e. cars) nor the servers need to be explicitly represented, except in terms of the state variables, unless certain customer averages are desired (compare Examples 3. 4 and 3. 5) Events Arrival event Service completion by Able Service completion by Baker EXAMPLE 3. 1 Nc et ia – 39 – nz www. ncetianz. webs. com Activities Interarrival time, defined in Table 2. 11 Service time by Able, defined in Table 2. 12 Service time by Baker, defined in Table 2. 13 Delay A customer’s wait in queue until Able or Baker becomes free. 3. The Event-Scheduling/Time-Advance Algorithm • The mechanism for advancing simulation time and guaranteeing that all events occur in correct chronological order is based on the future event list (FEL). • This list contains all event notices for events that have been scheduled to occur at a future time. • At any given time t, the FEL contains all previously scheduled future events and their associated event times • The FEL is ordered by event time, meaning that the events are arranged chronologically; that is, the event times satisfy t < t1