BREADTH-FIRST ALGORlTHM FOR
QUALITATIVE DISCRETE
EVE T SIMULATION
By
NITIN SATYANARAYAN AGRAWAL
Bachelor of Engineering
University of Mumbai
M umbai, India
July, 1998
Submitted to the Faculty of the
Graduate College ofthe
Oklahoma State University
in partial fulfillment of
the requirements for
the Degree of
MASTER OF SCIENCE
December, 2003
BREADTH-FIRST ALGORITHM FOR
QUALITATIVE DISCRETE
EVENT SIMULATION
Thesis Approved:
__M~~),<~
Dr. Manj~h Kamath -Committee Member
~~.
Dean of the Graduate Colleg
11
ACKNOWLEDGEMENTS
I wish to express my sincere appreciation to my advisor Dr. Ricki G. Ingalls for his intelligent supervision, guidance, inspiration and SUpp011. I am grateful to rum for all the extra time and effort he invested so that I could complete my thesis on time. My sincere thanks extend to my other committee members Dr. David B. Pratt and Dr. Manjunath Kamath for their suggestions, assistance and support.
I would like to thank DLWilliam Kolarik and School of Industrial Engineering and Management for providing with this research opportunity. I would also like to give special thanks and love to my parents for their support and encouragement.
Finally, I would once again thank School of Industrial Engineering and Management for supporting during these years of study.
111
TABLE OF CO TE TS
Chapter Page
1.
Introduction 1
2.
Literature Review 5
2.1.
Classification of Simulation Models 5
2.1.1.
Continuous-Time Simulation 6
2.1.2.
Discrete-Event Simulation 7
2.2.
Qualitative Simulation (QS) 8
2.3.
Qualitative Discrete-Event Simulation (QDES) 13
2.3.1.
Qualitative Discrete-Event Simulation Framework 16
2.3.2.
Qualitative Discrete-Event Simulation Parameter Definitions 19
3.
Research Methodology ' 23
3.1.
Objective of Thesis 23
3.2.
Scope and Limitations 24
3.3.
Hypothesis " 24
3.4.
Thesis Phases " 25
4.
Depth-First Algorithm Review
..,
27
4.1.
Depth-First Methodology 27
4.2.
Output of Depth-First 30
4.3.
Depth-First Methodology Explained With Example 30
5.
Breadth-First Algorithm Design And Implementation 36
5.1.
Breadth-First Approach , 36
5.1.1.
Implementation Approach 37
5.1.2.
Designing Steps for Breadth-First Algorithm Approach 38
5.2.
Validating With An Existing Example 41
5.3.
Breadth-First Algorithm Implementation 41
5.4.
Explanation OfThe Breadth-First Algorithm With An Example , 52
5.5.
Validating The Output 58
IV
5.6.
Run-Tilne onlparison 58
5.7.
Additional dvantages Of Th Breadth-Fir t Igorithm 61
6.
Summary and Future Re earch 63
6.1.
Research Summary 63
6.2.
Future Research 64
References 66
Appendix A. Interval Math 68
Appendix B. PERT Network Example 69
v
LIST OF FIGURES Figure Page Figure 2.1: Event Graph With a Scheduling Edge and an Execution Condition (Ingalls, 1999) 16 Figure 2.2: Event Graph for Single Machine Example (Ingalls, 1999) 17 Figure 4.1: Execution Tree 31 Figure 5.1: Proced ures for Execution of QSGM Model. " .42 Figure 5.2: Flow chart for Breadth-First Algorithm 47-49 Figure 5.3: Run Time Function for Breadth-First Algorithm 60 Figure 8.1. PERT Network Event Graph '" 69
LIST OF TABLES Table Page Table 5.1: Simulation clock time and state variables at some point in simulation 56 Table 5.2: Partial output for single machine example using breadth-first algorithm ....... 57 Table 5.3: Run Time (Seconds) for Single Machine Example (E = 8) 60 Table 8.1: The Depth-First Algorithm Partial Output for PERT Network Example 70 Table B.2: The Breadth-First Algorithm Partial Output for PERT Network Example .... 71
VI
Chapter 1
Introduction
Simulation is the modeling of processes and operations of real-world systems over time. Simulation generates artificial data to predict the system's behavior without actually working with the real-world system. The system can be studied and analyzed using the data generated by simulation. "Simulation is the promotion of idea that process whose complete models are unknown can still be used as basis for computation," (Hocaoglu,2003).
Simulation models are a representation of the actual system. These models require infonnation about the parameters or variables of the system that are used to model the actual system. Traditional discrete-event simulation often uses probability distributions to describe these parameters. The probability distributions are based on certain a umptions by the modeler. Exact infonnation about model parameters, such as the type of tatistical distribution, is often not available. Although it is standard practice to make assumptions for these inputs in traditional discrete-event simulation, qualitative discrete-event simulation has created the constructs to define model parameters qualitatively. For example, if a customer arrives at a teller between 10:00 AM and 10:15 AM, then traditional discrete-event simulation cannot be used for modeling without making certain assumptions about the arrival time distribution for the customer. Traditional discreteevent simulation might assume that the value of time when the customer arrives at the teller is a random output from a unifonn distribution with parameters of 10:00 AM and 10: 15 AM. It is cl ar that the unifOlm di tribution for arri al ti me is an assumption. Th
output obtained may not r present the tru bebavi.or of th y t m if the w1iform distribution assumption do s not bold. This might lead to faulty analysis of the system. Qualitative Discrete-Event Simulation (QDES) can be used to create models with fewer modeling assumptions.
Simulation models are largely classified into two types depending on how time is incremented. The two types are discrete-event simulation (DES) and continuous simulation (CS). Discrete-event simulation is defmed as one in which the state variables change when an event occurs. Tn continuous simulation; the state variables change at defLOed time intervals. Continuous simulation models are described by using a set of differentia] or difference equations.
Qualitative Continuous Simulation (QCS) was first developed by Kuipers (1986). Kuipers described QCS models based on qualitative differential equations (QDE). According to Kuipers (1986), "Qualitative simulation systems produce the set of possible behaviors by generating and filtering the set of possible transitions from one qualitative state description to its successors. QCS is based on qualitative differ ntial equation model in which variables are continuously di fferentiable functions. The range of each variable is defined qualitatively and it is a finite set of values on the real number line." QCS models start with initial values for the parameters. Successive states are derived continuously until the simulation tenninates or all the possible behavior of the models are generated.
Qualitative Simulation Graph Mode.ls (QSGM) were developed by Ingalls (1999). QSGM is an alternative approach to the problem of Qualitative Discrete-Event Simulation (QDES). By combining discrete-event simulation with qualitative simulation,
2
QDES is able to model discrete ent systems where act infonnation is not available or
cannot be adequately quantified.
A QDES model uses imprecise specification of paramet rs such as the event occurrence time and the state variables. The event occurrence time is represented using an interval on the real-number line. When time is defined in real-valued intervals, it is normal for the order of events that are scheduled to be executed to be uncertain. For example, if the event occurrence time for one event is [3,5] and the event occurrence time for a second event is [4,6], the order ofexecution for these two events is uncertain. When this uncertainty exists, then the QDES creates a ''branch'' or a "thread" for each possibility. In the first thread, it is assumed that the event whose event occurrence time is [3,5] is executed first. In the second thread, it is assumed that the event whose event occurrence time is [4,6] is executed first. An individual thread is terminated when a specified condition is met or when no additional events are scheduled to occur. The simulation stops when all threads terminate.
The thread generation process generates a tree-like structure whose nodes are represented by events. An algorithm that uses depth-first traversal to generate all possible threads of the model has been developed by lngalJs (1999). The objective ofthis thesis is to develop a breadth-first traversal of the threads so that an active threads can be evaluated simultaneously.
in depth-first algorithms, the root node is determined first, then the child node of the root is determined, then the grandchild is determined, and so on. The generation of children continues on a single thread until the thread reaches the stopping condition. During the process, sibling nodes are placed in a stack to be executed later. In breadth3
fIrst traversal, all of the sibling nodes ar d tennined and plac d in a queue. Then each sibling is taken out of the queue and executed. When a sibling node is executed its children are placed in the queue. Roughly speaking the ex cution goes from one level of the tree to another. This thesis proposes a breadth-first algorithm whose execution queue is managed in such a way that the simulation clock time is nearly equal for all of the nodes in the queue.
This thesis is organized into 6 chapters. Chapter 2 gives an overview of literature ltl the field of qualitative simulation. Chapter 2 also introduces to the concept of qualitative discrete-event simulation that was developed' by Ingalls (1999). Chapter 2 concludes by defining the objective, purpose and scope of the thesis.
Chapter 3 describes the hypothesis and different phases of the thesis. Chapter 4 discusses the depth-first methodology developed by Ingalls (1999) and the breadth-first methodology that is proposed. Chapter 5 demonstrates the breadth-ftrst algorithm implementation and provides an in depth explanation of the newly developed algorithm with the validation of the output. Chapter 6 summarizes the thesis and provides an insight into future research that could be done in the field ofQSGM.
4
Chapter 2
Literature Review
Most real-world systems that change with time are so complex that they cannot be modeled mathematically. However most of these systems can be modeled using simulation. According to Banks (1998), simulation is used to describe and analyze the behavior of a system. Simulations models help analyze the design of reaL-world operations and processes without building actual systems. This allows an analyst to answer what-if questions about the real system. Simulation models also help determine constraints and problems that couLd be faced by real-world systems before the actual system is in place, thereby saving a considerable amount of time and money. Efforts can be directed to solve the problems and to overcome the constraint during the system design phase. Simulation studies or models can be built for both existing and non-existing systems. Simulation models are widely used in manufacturing systems, queuing ystem, scheduling, material handling systems, capital investments decision making, cash flow analysis and supply chain modeling. Numerous applications of simulation in different fields make it a powerful modeling tool.
2.1. Classification of Simulation Models
Cellier (1991) have defined three types of mathematical models, which are:
•
Continuous-time models
•
Discrete-time models
•
Discrete-event models
5
In continuous-time models, the state variabl s change their .alu s continuously
with time. Continuous-time models ar represent d lIsing a set of di fferential equations for the variables that are differentiable with time. oncepmally time is an analog variable and the simulation clock is advanced in sufficiently small st ps in such a way that continuous time is approximated.
Discrete-time models are represented through a set of difference equations. In discrete-time simulation, the time is divided into discrete time steps and simulation clock is advanced by a fixed clock increment that is sufficiently large to make it noteworthy.
Discrete-event models change the state variables values only when something significant has occurred. As in continuous-time models, time is a continuous variable. What differentiates discrete-event models from continuous time models is the assumption that nothing significant occurs between two events.
Similarly, simulation can also be classified In two broad categories based on above distinction of mathematical models, which are:
1.
Continuous-time simulation.
2.
Discrete-event simulation.
2.1.1. Continuous-Time Simulation In continuous-time models, the state of the simulation model is defined by dependent
variables that change their values continuously over time. In Banks (1998), the state variables of continuous-time simulation models are represented in one of the following three ways:
•
Functional form, in which the state variable is represented as a function of time and other system variable. For example, x=f(y, t).
6
•
Difference equations in which the state variable is represented as a difference
in values from one time unit, t to next time unit t+ 1. For example x,+/=a x, + by,.
•
Differential equations.For example, dx/dt = fry, t).
The state variables in a continuous-time simulation model are dependent on the time. In continuous-time models, time is typicaUy considered as an independent variable, which is represented as t in above examples. Neelamkavil (1987) states that the simulation of a continuous system generates one or more numerical solutions which satisfy the differential equations defining the model for given initial condition using standard numerical method. These solutions satisfy the differential equations that defme the model.. The initial values of the state variables are initialized at the starting point in time. These values are used as inputs to the differential equations which determine a new set of values when the simulation progresses to next point in time, that satisfy the set of equations, using numerical analysis procedure. Banks (1998) attributes the complexity in continuous time simulation models to following reasons:
•
Randomness involved in the variables used to define the equations.
•
Changes occurring in the equations used to define the models due to the continuous change ofthe equations coefficients.
2.1.2. Discrete-Event Simulation
In discrete-event simulation, variables change their values only when an event occurs. Discrete-event simulation models are both stochastic and dynamic in nature. Discreteevent simulation captures dynamic system behavior by evaluating how the entities and the activities in the simulation interact with each other. For example, in a single-server
7
system where a ser er 5 rv a custom r th entity is th custom r and one of the activities is the custom r bing served by th server. E ents occur at th beginning and completion of each activity. In our exampl an event occurs when the customer starts the service that is performed by the server. The next e ent occurs when the customer leaves the system when the service is compi teo The state of the customer remains unchanged between start and end of the customer service by the s rver. The simulation clock advances at each event. When service begins, the simulation time is set to the time when the service is scheduled to begin. When the service ends, the simulation time is advanced to the time when the service is scheduled to end.
In cases where good quantitative infotmation exists, quantitative analysis methods are most appropriate and efficient to study and analyze the models. However, if good quantitative information is not available or information is incomplete, then qualitative simulation may be a better methodology for modeling and analyzing the systems under study.
2.2. Qualitative Simulation (QS)
"Simulation solves problems executing their model on computers using numeric information, but QS uses simulation's model execution approach for rea oning task", (Hocaoglu, 2003). QS is a reasoning technique which solves problems by deriving useful inferences from models having considerably less information than is usually required to analytically solve the problem.
Hamscher et a!. (1995) uses "boiling of water on stove" as an example to explain the QS technique. To write a program that could predict the behavior of the "boiling water" system, one would write a computer program to solve a set of differential
8
equations that would explain the relationship beh een the temperature of water, volume
of water, specific heat ofwater, bU111er temperatuT heat trans fer coefficient, temperature of the air, height of pot above sea level, and other parameters. Traditional continuous simulation could have been used to analyze this model if the modeler could specify the exact form of functions explaining the relationship between the model parameters, the precise value of the parameters in those functions and the initial values of the variables. Traditional simulation would result in a solution that would explain the behavior of the system. However, there are times when the modeler does not know about the precise nature ofthe equations. Also, there is a question ofwhich parameters need to be included and which parameters can be excluded from the model. For example, the modeler may not want to include the altitude of the pot. Also, the exact values of the initial conditions such as the temperature of the air and the temperature of water may not be known. However, qualitative information about the parameters may be available. An example of qualitative information for the boiling water example is given below:
1.
The burner temperature is greater than boiling point of water.
2.
The initial temperature of water is between ooe and lOOoe and the temperature of water is increasing.
QS can be used to predict the behavior of such systems. The three different behaviors of this system would be water is heated to boiling point from time 0 to some time tl, water is boiling from time tl to time t2 and finally there is no water from time t] to infinity. The example does suggest some important properties of QS. First, it can work with less precise information. Second, it does not assume precise values of the variables to solve the model as compared to traditional simulation models.
9
One of the early pioneers of QS is Kuip r (1986). Most of his work is based on
the qualitative differential equation model (QD ). "QDE is an abstraction of an ordinary differential equation, consisting of a set of real-alued variables and flUlctional, algebraic and differential constraints among them. QDE model is qualitative because the values of variables are described in tenns of their ordinal relations with a fmite set of symbolic landmark values, rather than in terms real numbers and functional relations are described as increasing or decreasing over particular ranges, rather than specifying it in functional form." (Kuipers, 2001). The QS technique described by Kuipers (1986) is used to solve continuous time models and it is referred to as Qualitative Continuous Simulation (QCS) in this thesis.
QCS generates aU the possible behaviors of the system. This gives the decision maker the ability to choose from multiple options available to him for decision making. QCS described by Kuipers (2001) starts with a qualitative model and a qualitative description of the initial state. QCS uses an interval in the set of real numbers to defme qualitative state variables. Kuipers (1986) describes the following inputs to the QCS algorithm using the "boiling water example":
•
A set of functions in the system. For example, a function describing relationship between temperature of the water and the burner.
•
A set of constraints applied to the function variables. For example, "change in
water temperature" is a derivative of "change in burner temperature" over time.
10
•
An ordered set of symbols representing landmark values associated with each function. For example, temperature of water varies in the range of 0° C to infinite.
•
The initial conditions at time to for all functions and variables. For example initial temperature of water is intialized between 0° C and boil.ing point of water. The temperature of the water is also increasing.
With these input values, the possible direct successors of the current state descriptions can be predicted using the quaUtative description of the current state. The process is repeated to produce a graph that describes all of the qualitative states of the system. The result of the QCS is one or more qualitative behaviors for the functions and symbols. The qualitative behavior of the boiling water model consists ofthe following:
•
Sequences of distinguished time points of the systems behavior. For example, the temperature of water is increasing at to = 0, water starts boiling at time [1, and water evaporates completely at some time (2.
•
Qualitative state description of the system between adjacent time points for each function and variables. For example, between time t1 and £2, the temperature of water is increasing and is between boiling point of water and infinity.
The QSIM software is developed by Kuipers (1986) for executing QCS models represented using differential equations. Farquhar et al. (1994) has prepared the manual for the QSIM tool. The QSIM software for solving qualitative continuous time models uses all of the traits of the QCS algorithm developed by Kuipers (1986). The software also compares alternative approaches that are produced. The algorithm starts with a set of
1I
constraints abstracted from a t of diffi rential quations. Kuiper 19 6 prov d that the
QSIM algorithm produces a qualitati e behavior corresponding to any solution that would have been produced by the original set of differential equations. He also demonstrated that the qualitative simulaHon algorithm might produce spurious qualitative behaviors which do not correspond to any feasible output ofthe original set ofdifferential
equations. QSIM executes the QCS model by deriving d scendants of each qualitative state. The process of deriving descendants is repeated until all of the possible qualitative states are predicted. Kuipers (2001) suggested that the algorithm must ensure that all possible qualitative value transitions and their combinations are predicted. Also, combinations of qualitative values are deleted when they are inconsistent with the feasible output of the original set ofdifferential equations. Qualitative continuous simulation usmg qualitative differential equations for modeling physical systems has been dev loped and is practically appli d to modeling physical systems. Wyatt et a1. (1995) compared qualitative and quantitativ simulation using a case study model of the interactive markets for housing and mortgages. They showed that the data or information required for qualitative simulation is considerably less in comparison to the data required for the quantitativ simulation. Also, they claimed that quantitative simulation tends to hide some of the true behavior of the system by making invalid and impractical assumptions. One such assumption is about the interest rate. The interest rate for the mortgages is kept constant in the quantitative simulation model to keep model simple. This assumption in model will certainly affect the realism as the interest rate keeps on changing thereby hiding the true behavior ofthe system.
12
A combination of qualitati and quantitati simulation using numeric intervals
to represent incompLete quantitati e infoffilation i suggest d by Berelant et at. (1997). They demonstrated that the combination would overcome the shortcomings of qualitative simulation by using the strengths of both techniques. All these studies focused on continuous models and did not consider discrete-ev nt models.
2.3. Qualitative Discrete-Event Simulation (QDES) To solve and analyze discrete-event simulation models with qualitative parameters, another approach to QS was developed by Ingalls (1999) that combines QS with discrete-event simulation. Ingalls defines the Qualitative Simulation Graph Model (QSGM), which is implemented with Qualitative Event Graphs (QEGs). QSGM is an alternative approach to the problem of Qualitative Discrete-Event Simulation (QDES). Bulitko et al. (2003) presented an alternative methodology to support a qualitative simulation of temporal concurrent processes using Time Interval Petri ets. The methodology is similar to one defined by Ingalls (1999). It uses tim int rvals to represent uncertainty in inputs and outputs, simi lar to temporal intervals defined by Ingalls (1999). The next section briefly describes QD. S methodology. Ingalls (1999) extends the application of DES to systems for which accurate quantitative information is missing by introducing the qualitative description of time,
delays, and state variables. Event execution time is defined using intervals in set of real numbers called temporal intervals. Two types of temporal interval defined by Ingalls (1999) are:
13
Constant Intervals: "A constant interval is an interval whos valu must be the
•
same throughout the entire thread of the simulation i.e. it is asswlled that the actual values of the variable is a constant that lies somewhere in an intervaL. Uncertain Intervals: "An uncertain interval is an interval whose value could be
•
different every time that the interval is evaluated."
For example, in a "single server system," the arrival time and service time are described as any value in the range of some time tl and [2. These temporal intervals are modeled as uncertain intervals and their representation is [tl, t2]. During the execution of a traditional DES, a random sample would be taken that would be in this intervaL. The type of distribution defmed for representing the arrival time is based on the assumptions made by the modeler, which may include fitting a distribution to past data. The assumption of the statistical distribution on the interval is not necessary with QDES, which allows the modeler to model and analyze systems with fewer modeling assumptions.
QDES approach differs from the QS models defined by Kuipers (1986) U1 following ways:
•
Defmition of the model -QDES is implemented usmg the qualitative simulation graph methodology (QSGM) while QCS uses qualitative differential equations.
•
QDES is targeted to solve models that come under the umbrella of discreteevent models while QCS are used to solve physical models based on continuous-time models.
14
The execution approach followed by both QDE and Q models are similar as
both methodologies proceed by predicting possible direct successors of the current state.
The process is repeated to produce a graph that describes all qualitative states of the
system. Each path starting from the root gives all possible qualitative behaviors of the
system.
QSGM generates threads, which are also called envisionments that characterize all possible behaviors. "Coverage is an important advantage of the QDES approach because it does not miss outcomes that a sampling based approach like traditional DES might with a finite sample size." (Ingalls, 1999) The generation of threads increases exponentially with the complexity of the model being executed. This exponential explosion of threads creates a run-time issue with the algorithm on large models. This issue is considered a key research topic by Ingalls.
Ingalls (1999) implements thread generation using a depth-first algorithm that completely finishes one thread while putting additional threads on a stack to be executed at a later time. This approach is very efficient in the case where all threads need to be executed. However, Ingalls envisions situations where criteri.a could be included in a model that would differentiate threads by some objective. The depth-first generation of threads is not efficient in the case of an objective that requires a comparison of all active tbreads. In order to accomplish this goal, a breadth-first algorithm for thread generation and simulation execution would need to be developed.
The breadth-first algorithm described in this thesis provides an opportunity to evaluate the threads simultaneously and eliminate "unimportant" threads. Eliminating some threads may reduce the run time and thereby allow modelers to solve more complex
15
models. The breadth-first algorithm will enable res archers to sol e more r alistic and
complex models and help to furtb r develop QDES methodology.
2.3.1. Qualitative Discrete-Event Simulation Framework Modeling methodology based on combinati.on of Event Graphs and qualitative Simulation, caned the Qualitative Simulati.on Graph Methodology (QSGM), is used to implement qualitative discrete-event simulation. QSGM uses the event graph construct to
define QDES models. Figure 2.1 shows event graphs construct with a scheduling edge and an edge execution condition.
Figure 2.1: Event Graph with a scheduling edge and an execution edge condition,
(Ingalls, 1999).
Events A and B are represented as nodes and edge connecting nodes indicates the relationship between the two events. The event graph framework shown in Figure 2.1 illustrates that if event A occurs and scheduling condition (i) is true at that instant, then event B will be scheduled to occur t time units later. If edge ex cution condition 0) is true
t time units later then event B will be executed with the state variable array ;; set equal to values in array k (Ingalls, 1999).
As an example of a QSGM, consider the example of a single machine queuing system. In this example, when the job arrives at the machine, if the machine is idle then the machine starts processing the job immediately. Otherwise, the job joins the queue and waits for the machine to become available. When the machine becomes available, tbe job is delayed for the machining time. Upon completion of the job, the machine is made
16
available for another job. [n this xample th buffi r capacity i assumed to be infinite.
The event graph for single machine exampl is shown in Figur 2.2.
13,81
Q=O Q=Q+1 Q=Q-1 =1
E=E+1
5=1 E=O Figure 2.2: Event Graph for single machine example, Ingalls (1999).
The nodes RUN, ENTER, START and LEAVE are events which represent the
following: RUN -the starting event that starts the simulation. ENTER -the arrival ofthe job in single machine queue system. START -the job starts its processing at the machine. LEAVE -the job completes its processing and exits.
The state variables are defined as: Q -the number ofjobs in the queue waiting for processing at the machin, S -the number ofmachines available for serving customers. For a single machine system S can be equal to either 0, when the machine is busy, or I, when machine is idle,
E -the number ofjobs that have been processed and left the system.
For this example, all of the edge execution conditions are TRUE. The scheduling conditions are represented on the edge connecting two nodes. In Figure 2.2, the scheduling conditions are S > 0 and Q > O. When the ENTER event occurs, then it wi 1
17
schedule the START event without any delay if the scheduling condition > 0 is true. The condition 5 > 0 is true if at least one server is available. Similarly, the scheduling condition Q > 0 represents that the START event will be scheduled without any delay only if Q > 0 when LEAVE event occurs. The condition Q> 0 is tme if there are jobs in queue waiting for machine to become available.
Temporal intervals are used for the edge delay times. The interval [3 8] on the ENTER-ENTER edge represents the inter-arrival time between jobs. to this case, the inter-arrival time between two jobs can be anywhere between 3 and 8. Similarly, the interval [4,6] on the START-LEAVE edge indicates that thejob completes its processing on the machine after a delay of at least 4 and no more than 6.
Below each node is a set of equations that are used to evaluate the state change variables. When the RUN event occurs, then the state variables are initialized to Q=O, 5=1, and E=O. When an ENTER event occurs, then the number of jobs in the queue increases by 1 (Q=Q+ I). Similarly, when a new job starts its proce sing at the machin then the Q value is reduced by 1 (Q=Q-l) and the state of the machine is changed from idle (5=1) to busy (S=O). When the job leaves the system after being processed then the machine state is changed from busy to idle and the number of units that have exited the system is increased by 1 (E=E+ 1).
The QSGM framework helps define the real-world system using the above set of notations and modeling approach. The next section will discuss the execution of the QSGM model using the framework defined above.
18
2.3.2. Qualitative Discrete-Event Simulation Parameter Definitions
Banks (1998) explains that a discrete system mod I consist of orne or all of the
following:
1.
Model -Representing a real-world system.
2.
Event -Occurrence of an event that changes the state of the system.
3.
System State Variables -A collection of variables that r present or are used to define what is happening in the system.
4.
Entities -Entities represent objects that move through the system.
5.
Attributes -Entities may have some values associated with them called attributes.
6.
Resources -Entities are served by the resources.
7.
Current Event Calendar -A list that represents events that are scheduled to occur at the current time of the simulation.
8.
Future Event Calendar -A list that represents the events that are scheduled to occur at some time in future.
9.
Simulation Clock -Represents the current time of the simulation. The clock time is advanced to the future time when an event is scheduled and the state change of the system occurs.
Since QSGM is a derivation of the Simulation Graph Methodology (SGM) introduced by Yi.icesen and Schruben (1992), then QSGM does not have all of the constructs defined by Banks. In particular, QSGM does not have entities and resources. Also, attributes are defined as a list of values passed from one event to another.
Similar to traditional DES, the simulation clock time represents the current clock time of the simulation and is a real-valued variable. The future events calendar forms a
19
sorted list of tim -delay d events. The tim -d lay dents ill not become acti ltntil
some future simulated time is reached. The fIrst e ot on th future e nts Ii t is event
that will occur next. In QSGM, the simulation clock time is not repre ented as a real-alued variable, but as a temporal interval. The future events calendar us d in QSGM is a single list that stores event notices. An event notice stores relevant information about the event that is to be executed. The event notices are sorted by a mechanism that assures that the first event notice on the calendar can possibly be the first event to be executed on the current thread. (Ingalls, 1999) Each event notice has following set of values:
1.
The time when event is to be executed.
2.
The execution priority for event. (The priority of an event notice helps in breaking a tie when two event notices have equal execution time.)
3.
The node (event) to be executed.
4.
The edge that scheduled the event notice.
5.
The values of the edge attributes.
An example of an event notice is ({O,O]. 1, START. ENTER-START, TRUE). It states that START event is scheduled to occur at time [0, OJ and was scheduled by the ENTER-START edge. The edge execution condition for the event notic is TRUE. The START event is executed when this event notice is removed from the future events calendar.
As in DES, the QSGM future event calendar or list is also sorted in order of event occurrence time, but the rules used to sort the list are based on interval math (Appendix A). In QSGM, if the time for event notices I and 2 are defined as (t/-, t/] and [t2-, t/],
20
then the following conditions are evaluated in order to detennine if £, prced s ,_ in the
future events calendar:
+1.
tJ < tl
2. t,-< t2
In traditional discrete-event simulation, if there is more than one event on the current events calendar, then the order of execution is detennined arbitrarily based on the type of algorithm used. In the QSGM, if two or more event notices could possibly executed next, then QSGM generates a set of threads for all possible combinations of event sequences. For example, if the two events A and B, with equal priority, are to occur at time [ta-, t/] and [tb-, lbJ, and it is not possible to detennine if event A occurs first or event B occurs first then QDES will generate two threads. One will execute event A first and the other will execute event B first. Ingalls (1999) defined the situation where the execution order of multiple events is uncertain as a non-detenninistically ordered set (NOS). The members of the NOS are called non-deterministically ordered events (NOEs). Each NOE becomes the next event to be executed a new thread. These threads, which comprise all possible event orderings, allow QSGM to characterize all possible behaviors of the system, which is the essence ofQS.
QSGM execution is similar to traditional DES. A QSGM model is executed over time by the mechanism that moves the simulated time forward. Since a temporal interval is used to define time in a QDES model, interval math (Appendix A) is used to calculate event times for the event notices in the future events calendar.
21
Ingalls (1999) has also included the qualitati e sp ci fication 0 f state variables
such as the number of servers a ailable. For example if number of ervers a ailable in the system at any given time is between 2 and 5 then it is stat d as [2 5]. The qualitative specification of the state variables will not be considered in thi thesis for simplicity.
22
Chapter 3
Research Methodology
3.1. Objective of Thesis
The objective of this thesis is to make a contribution to the field of qualitative discrete-event simulation by developing a breadth-first algorithm for the Qualitative Simulation Graph Methodology. An algorithm for solving qualitative discrete-event models using breadth-first traversal methodology is implemented using the objectoriented programming language, C++. Different models are executed using the algorithm to check its validity and the output is verified with output generated by depth-flrst algorithm presented by Ingalls (1999) in his dissertation.
With QSGM, Ingalls (1999) developed a simulation tool for solving discreteevent models for which precise infonnation is not available. Howev r, the algorithm developed by Ingalls (1999) uses depth-flrst traversal for solving QSGM model. This thesis assumes that the model could also be solved using breadth-first traversal and utilizes the advantages of breadth-first traversal algorithms. The depth-first algorithm does not allow the modeler to analyze all the threads simultaneously as each thread is executed until it reaches the stopping condition criteria. At any time during simulation run, the depth-first algorithm can only depict the partial behavior of the system. This is so because only certain threads are completely executed while other threads are waiting on the stack or may\;tot even have been determined. The breadth-flrst algorithm provides a
solution to the above problem.
23
3.2. Scope and Limitations The breadth-fLrst algorithm developed will only consid rs uncertain int rvals for describing time delays in tbe system. Even though state variables can be defin d qualitatively, this thesis does not consider the qualitative definition of state variables. The
conceptual use of the breadth-first algorithm is discussed using hypothetical examples only.
3.3. Hypothesis As mentioned earlier, Ingalls (1999) developed the Qualitative Simulation Graph Methodology (QSGM), as modeling framework for QDES. Ingalls (1999) developed a depth-first algorithm for QDES execution that first executes the root node, then the children of the root node, followed by the grandchildren of the root node, and so on until the thread is complete. After the thread is executed, sibling nodes are executed until the thread that they created IS complete. Since the depth-first traversal of the nodes is possible, the hypothesis IS to show that breadth-first traversal of the node is also possible. Since QSGM is still in its very early stages, a set of algorithms and analysis techniques that would make QSGM a useable tool for modelers is still being developed. A breadth-first algorithm enhances QSGM so that it is more practical for modelers, especially in the area ofstrategic decision-making. The algorithm would allow modelers to inspect all threads that are active at a particular time in the simulation and depending on their states. It would be possible to
terminate the simulation of threads that are less meaningful to the decision maker. By removing less meaningful threads, the run-time of the algorithm can be reduced.
24
Developing the breadth-flr t algorithm will r quir a data lmcture to tore sibling
nodes which will be created dynamically. Thes dynamically created ibling nodes will represent all the possible nodes that can be ex cuted. Each node corresponds to one thread that is active in the simulation. Each node will be stored in this data structur and be sorted with respect to the event execution time. The sorting of this data structure will ensure that all of the threads in the data structure have their execution time very clos to
each other. The purpose of the newly developed breadth-first algorithm will be demonstrated using a hypothetical example. Arbitrary criteria will be used to eliminate threads using the breadth-first algorithm and the run time will be compared with the nm time for depthfirst
algorithm.
3.4. ThesisPbases The thesis is carried out in discrete phases with each phase making progress toward achieving the objective of the thesis. Phase I: To Study Qualitative Discrete-Event Simulation First phase of the thesis concentrates on understanding the concepts of QDE approach that was developed by Ingalls (1999). The study ofQDES methodology focuses on understanding the Qualitative Simulation Graph Methodology modeling approach that is used to describe models for QDES. The depth-first algorithm is used for solving or executing the simulation. Phase n: To Code the Depth-First Algorithm For QSGM
The depth-first algorithm developed by Ingalls (1999) is coded in Smalltalk. To make this thesis possible, the QSGM algorithm has to be fe-coded in C++. This phase is
25
necessary as it will help to compar the output obtained from lIsinl:) the depth-first
algorithm developed by Ingalls (1999) and proposed breadth-first algorithm. Phase III: To Develop the Breadth-First Algorithm Third phase focuses on developing the proposed breadth-first algorithm for solving or executing QDES models. The algorithm is coded in C++ using Visual Studio
6.0 environment. The developed code is tested with examples describ d by Ingalls (1999). Phase IV: To Validate the Breadth-First Algorithm
The output of the proposed algorithm is validated by comparing the output from depth-fust algorithm since the output from both the algorithms must yield the same results. Phase V: To Show the Purpose OfTbe Breadth-First Algorithm Using An Example
A hypothetical example is used to show the purpose of developing the breadthfirst algorithm. The example will limit the number of active threads in the breadth-fir t algorithm to a smaller number and reduce the run time for the algorithm.
26
Chapter 4
Depth-First Algorithm Review
The framework discussed in the Chapter 2 is based on the Qualitative Simulation Graph Methodology. With the framework and parameter definition, the depth-first approach for the QDES developed by Ingalls (1999) will be discussed using the "single machine system" example.
4.1. Depth-First Methodology
The execution of QSGM resembles traditional DES to some extent. lngalls (1999) developed the depth-first algorithm to execute QSGM models. The following defmitions of parameters are necessary to understand steps i.n the depth-first algorithm.
L -the future events calendar, which is an ordered set of event notices.
S -the set of state variables. In the single machine system example th state
variables are S (the number of available servers), Q(the number ofjobs waiting in
the queue), and E (the number ofjobs that have exited the system).
H -the set of saved states. A saved state consists of the global event calendar L
and the state variable array S. This set is used to recurse through all possible states
in the simulation. H is also known as the stack.
Nh -the non-deterministically ordered set (NOS). This set contains the event
notices that can possibly be executed.
h -the number of saved sets in H.
ni, -the variable to iterate through the N" set.
27
With the previously defined parameters the steps in depth-first algorithm develop d by
Ingalls (1999) are as follows:
1.
Initialize the saved state set aod counter H =0 and It = 1.
2.
Initialize the global simulation clock to time t = [00].
3.
Insert one or more event notices ioto the event calendar, L, that could be executed at time [0,0].
4.
Detennine the NOS N", the set of all event notices that could be executed next.
5.
lEthe number of events that can be executed next equals to 1 (IN"I= 1) then go to step 9 else go to step 6.
6.
Initialize the variable to loop through N , It" = I.
"
7.
Save the state of the simulation by saving the state variable infonnation S, and the future events calendar information, L, in the save-state stack, H,,= {S,L} and increase the sav -state counter, I. = It + 1.
8.
Set I =( N/I_ 1 )n._, and remove event notice I from the global event calendar L.
L=L\{III= (Nh_,)n }.Goto step 10.
• -1
9.
Remove the first event notice I from the global event calendar L. Since the global events calendar is sorted according to tbe event execution time, the first event notice on the calendar is one that would be executed next.
10.
If the execution edge condition evaluates to FALSE then go to step 16, else go to step 11.
11.
Determine the possible new simulation clock time. The new simulation time is calculated as follows. Suppose current simulation time is represented by [t',
e
28
tc and ent time by [te', t/] than ne, imulation dock tim t> \vould be
[max(te-te') min(l/ 'ifI EL )].
12.
Update the simulation clock bme t=t'.
13.
Assign attributes to appropriate tate ariables.
14.
Evaluate the state change.
15.
Schedule further events. Schedule all events that are connected to edges with the current event if the scheduling edge condition is TRUE. The scheduled events are the events that will occur after delay times that are represented by temporal intervals on top ofrespective edges. Assign all attribut values to the new event notice for the scheduled e ent with the event time calculated by adding delay time to the current simulation clock time using interval math (Appendix A).
16.
Stop simulation ofthe thread ifany ofthe following condition is true:
•
Simulation clock time exceeded simulation stop time defmed by the modeler, or
•
The simulation stopping condition defmed by the modeler is evaluated as TRUE, or
•
The global event calendar L is empty.
Ifthe saved state stack is empty, which is shown by II = J, then tenninate the
simulation.
17. Increment nh-l= n".l + 1. If nh-l :=;;INh-11 then go to step 8.
18. Restore the last saved system state values that have been stored in step 7. h= h -1, L = (L IL in set H,,), 5 = (5 I5 in set H,,). Go to step 8.
29 The algorithm developed by Ingalls (1999) is discllssed \I ith the help of the single machine system example. The stopping condition defined for tenninating the simulation is when number ofjobs that have left the system equals 5. Simulation stop time is set to infinity, since we do not want to stop the simulation un61 the number of ex.its equals 5.
4.2. Output of Depth-First
The partial output for the single machine system is presented in a graphical tree fonn in Figure 4.1. Complete output is shown from Ingalls (1999).
The oval shapes in Figure 4.1 represent the nodes. First Line of each node indicates the event executed and current simulation clock time. The lines following the first line inside the node show event notices in global events calendar. The event notices in Figure 4.1 represent the time when the event executes, its priority, the node that will be executed next, and value ofstate variables S, Q, and E. The edges that schedule the nodes are not shown in the output. The nodes are numbered arbitrarily and do not necessarily represent the sequence in which the nod s wiII be reached or executed.
4.3. Depth-First Methodology Explained With Example
The depth-first approach for the QSGM starts by initializing the model parameters or variables to initial values. Initially the saved state stack H is empty and the variable II
30
••
•
t
Figure 4.1: Execution Tree
31
is set equal to 1. In step 2, the simulation. clock time is set to [0 0]. The tirst event
scheduled to occur at time [0,0] is aRe ent which is inserted in th global events calendar L. In step 4, the OS Nil w.ill have only the R event notice as it is the only event that can be executed next. In step 5, since IN"I = 1 the execution mov s to st P 9. In step 9, the RUN event notice is removed from L. RUN event does not have any edge execution condition and is always evaluated as TRUE. The simulation clock time is detennined as [0,0] in step 10 and updated. The RUN event updates the list of state variables to values, S = 1, Q = 0, and E = o. The RUN event schedules an ENTER event because the edge scheduling condition is TRUE on the edge RUN-ENTER. Since the edge RUN-ENTER does not have any delay, the event execution time for ENTER is [0,0] and the variables are given the values S = 1. Q = 0, and E = o. The event notice inserted in the calendar is ([O,O], 9, ENTER, RUN-ENTER, TRUE). In step 16, simulation stopping condition evaluates to FALSE, since simulation clock time is less than stopping time, E "#. 5, and events calendar is not empty. Hence the stopping condition for this thread is false and simulation goes to step 4.
Since the ENTER event is the only event contained in the global event calendar, L, it forms the NOS and is the only event that can be executed next. The ENTER event notice is removed and the execution condition is evaluated as TR UE. The simulation clock time is updated to [0,0]. The state change is evaluated using the equation Q = Q+ 1 and state variables are updated to S = 1, Q = 1, and E = o. Two edges emanate from ENTER node and therefore two events are scheduled on the events calendar as ronows:
32
•
The TART event, which is scheduled v ithout any delay since tll scheduling
edge condition (S > 0) evaluates TR UE because S = 1. The event notice inserted in the calendar is ([0 OJ, 1, START, ENTER-START, TRUE).
•
The ENTER event (the edge ENTER-E TER does not have any scheduling condition), is scheduled after a delay of [3,8]. The event time is calculated using interval math, which adds the delay time of [3,8] to current simulation clock time of [0,0] resulting in an event time of [3,8]. The event notice inserted in the event calendar is ([3,8], 9, ENTER. ENTER-ENTER, TRUE).
In step 16, the stopping condition evaluates false and the execution moves back to step 4.
Next, the event START is executed, the simulation clock time t is updated to [00] and the state change is evaluated using equation Q = Q -1 and S = O. This changes state variables to S = 0, Q = 0 and E = O. The START event schedules a LEAVE event after a delay of [4,6]. The LEAVB event is scheduled to occur at time [4,6] and now the events calendar has two notices on it:
• ([3,8], 9, ENTER, ENTER-ENTER, TRUE)
• ([4,6], 9, LEAVE, START-LEAVE, TRUE) Step 16 evaluates stop condition to be false and a simulation execution goes to step 4.
At this point in step 4, it is impossible to determine the order of the events on the calendar because the execution times of the two event notices intersect with each other and the priorities of the two event notices are equal. The algorithm will create a thread for each event by executing each event first. Both events are in the set N" and IN"I= 2. Since IN"I is not equal to 1, the variable nit is set to 1 and the execution goes to step 7.
33
Simulation state IS saved In the sa ed-state stack HI = {S,L} and the count r " IS
incremented to 2.
First, event notice E TER is removed from the global events calendar L. The edge execution condition is TRUE and the new simulation time is calculated in step 11. Since the current simulation time is [0,0] and the execution time of the events are [3,8] and [4,6], the simulation clock time set to [max(3,0), mjn(8 6)] =[3,6]. Since the ENTER event occurs before the LEAVE event in trus particular thread, it is necessary that the ENTER event occurs in time [3,6] since it cannot occur after the LEAVE event. State changes are evaluated and state variables are updated to S = o. Q = I, and E = O. The ENTER event is scheduled to occur after a delay of [3 8]. The START event cannot be scheduled because the scheduling edge condition S > 0 is FALSE. The process continues until the stopping condition of E = 5 is TRUE for trus thread. As the thread executes, the saved state stack is adding events that will be taken off of the stack and executed as new threads at a later time. Following the steps in the algorithm, the execution will reach the node labeled £1 in Figure 4.1. The node labeled Elindicates end of thread ). At the end of thread 1, the values of the state variables are S = 1, Q = 2 and E = 5.
As thread 1 progresses, there are several more events placed on the stack, H, and h is incremented accordingly. At some time in the future, these events will be taken off of the stack and h will be decremented until it is again set to 2. At that time, the LEAVE event that was placed on the stack is ready to be taken off.
At that time, Step 17 increments ""-I by 1 and the value of"h-I = 2 is equal to INhl. Since the saved state stack is not empty at this point, the simulation state is restored in step 18. Now, the current simulation time is be [0,0], the state variables are S = 0, Q = 0
34
and E = O. The global events calendar L will hav the following e nt notices with the
LEAVE event to be executed first (since E TER event has alr ady executed fir t in the previous thread):
•
([3,8), 9, ENTER, ENTER-ENTER, TRUE)
•
([4,6], 9, LEAVE, START-LEAVE, TRUE)
Simulation moves to step 8 where the LEAVE event is removed from the events calendar and execution continues until the tenninating condition in step 16 is satisfied. At the end of the simulation an leaf nodes of the tree will have E = 5 and the saved state stack H will be empty.
This algorithm executes one thread until its stopping condition is reached and then the next thread is executed. The process goes on unt; I all possible threads of the system are generated. Hence this algorithm is termed the "depth-first" traversal methodology.
35
Chapter 5
Breadth-First Algorithm Design And Implementation
5.1. Breadth-First Approach
The QSGM algorithm can also be implemented using a breadth-first traversal of the simulation nodes. A breadth-first traversal examines all firsts of the sibling. trees before it examines any child tree (Weiss, 2000). Breadth-first traversal will cover aU of the same threads that the depth-first traversal covered. The problem with the breadth-first traversal is that it cannot be defined recursively. The recursive nature of the depth.-first: algorithm gives it a speed advantage over breadth-first if an threads are generated.:he breadth-first algorithm carries the overhead to continuously manage swapping in and out of nodes for all the active threads.
The depth-first algorithm is executed recursively until all of the thr ads are executed and the stopping condition is reached. In order to follow the breadth-first traversal, all the sibling nodes will be executed before traversing through the child nodes. This could help modelers to keep track of the each possible state and each possible option that is available. For example, in the single machine problem, the modeler may be interested in knowing the completion time of the first job under every possible thread or condition. In breadth-first algorithm, it will be possible to know the state of the simulation at each important landmark in all possible threads. This cannot be easily detennined in the depth-first traversal. In the depth-first algorithm, the state of all of the
36
threads at ceJ1ain point in simulation can only b det n11jn d only aft r the simulation has
completed.
S.l.I.lmplementation Approach
As with all recursive algorithms, the depth-first algorithm goes through two distinct phases. The rust phase is building up the stack. A stack is built in the memory when the function calls itself. All variables are stored in a stack. The second phase is unwinding the stack. The stored functions on the stack are removed last-in first-out and the stack eventually becomes empty.
In the breadth-first algorithm, we propose to use a queue structure that will contain the nodes (representing the threads of the simulation) that are to be executed. The first node on the queue will be removed and executed. The execution of the node will schedule new nodes. The newly created nodes will be inserted in the queue and sorted according to the event execution time. The execution will be stopped when the queue is empty.
The breadth-first algorithm will only consider uncertain intervals and not constant intervals. "A constant interval is an interval whose value must be the same throughout the entire thread of the simulation, i.e. it is assumed that the actual value of the variable is a constant that lies somewhere in an interval," (Lngalls, 1999). Ingalls defined an uncertain interval as an interval whose value could be different every time that interval is evaluated. In order to keep the algorithm simple, constant intervals and qualitative definitions for state variables will not be considered.
37
5.1.2. Designing Steps for Breadth-First Algorithm pproach
The depth-first approach algorithm s rves as a guideline for developing the logic for the breadth-first algorithm. Two more variabl s are d fin d for the breadth-frrst algorithm. These two variables are:
BreadthFirstNode -A set that consists of the vent notice to be executed next,
the state variable array, and the global events calendar to be used when the
event notice is executed.
BreadthFirstNodeQueue -The queue used to store BreadthFirstNodes.
Also, two variables changed their definition for the breadth-first algorithm. The change is needed because the H set is no longer needed in the breadth-first algorithm. Those two variables are:
N -the non-detemlinistically ordered set (NOS). This set contains the event
notices that can possibly be executed. Since H is no longer needed, there are
not multiple instances ofthis set.
n -the variable to iterate through the N set.
The steps based of the breadth-first algorithm are as follows:
1. Initialize the simulation clock to time t=[0,0]. Initialize the state variables to their initial values in the state variable array S. Initialize the global events calendar L to be empty.
2. Create an empty queue to store the BreadthFirstNodes; call it the BreadthFirstNodeQueue.
3. Insert one or more event notices into the global events calendar,. L, that could be executed at time [0,0].
38
4. Create a BreadthFir tNode whos m mb r ar first vent notic on the global
events calendar L, the current simulation time t, the set of state variables Sand the global events calendar L. Put it in tb BreadthFir tNodeQueue.
5, Assign the current simulation clock time t, to the simulation time stored in the first BreadthFirstNode, the state variables, S to the values of the state variables stored in the first BreadthFirstNode, and the global events calendar, L, the global events calendar stored in the first BreadthFir. tNode. Remove the first BreadthFirstNode from the BreadthFirstNodeQueue Note: This step is equivalent to the step 18 of·the depth-first algorithm where the state of the simulation is restored. In the breadth-first algorithm, the state of the simulation is restored every time a new node is removed from the BreadthFirstNodeQueue.
6. lfthe execution edge condition evaluates to FALSE then go to step 15, else go to step 7.
,
7.
Determine the new simulation dock time t. The n w simulation time is calculated as follows: if current simulation time is represented by [tc", 1/] and event time by [te', t/] then the new simulation clock time t' = [max(te'., tc"),
8.
Update the simulation clock time with the time calculated in step 7. 1= t'.
9.
Assign attributes to the parameters of the vertex.
10.
Evaluate the state change.
11.
Schedule further events. Schedule all events that are connected with edges to the Current event if the scheduling condition is TRUE. Assign any necessary
39
attribute values to the new ev nt Dotic . Assign th e ent execution time by adding the delay time to the Clm" nt simulation clock time t, using interval math. (Appendix A)
12.
Detennine the NOS N, the set of all ev nt notices that can be executed next from the global events calendar. Set 11 = 1.
13.
If It ~ IN1 is TRUE then for the event notice Nn, evaluate the simulation time t' when tl1e event wi II scheduled to occur. Suppose the current simulation time is represented by [tc", t/] and the event notice Nn event execution time by [tIl"' t"J, then the time which Nn is scheduled to occur is t' = [max(t,,", tc"), min(t/VI EL )J.
elseı go to step 15.ı
14.
Ifany of the following conditions are true:
•ˇ
The time which event N" is schedul to occur, t', has xceeded the simulation stopping time defined by modeler, or
•ˇ
The simulation stopping condition defined by the modeler is evaluated as TRUE, or
•
The global event calendar L is empty.ı then go to step 15,ı
Else Copy the global events calendar, L, to a temporary calendar, C. Remove event notice Nn from C. Create a BreadthFirstNode with reference to event notice Nn whose members are N,,, the time at which event Nil is
40ı
Run
fnitializ s model stmcture calendar and
random number generator. el'
stopping condition and define fir t
node or node to be e ecuted.
~
StartTime_StopTime
Sets tart time for simulation and iJl ert flTst node or nodes in the calendar.
~
BreadthFirstExecution
Executes the model using breadth-flfst aooroach.
Figure 5.1: Procedures for Execution of QSGM Model
Before executing the algorithm, the user has to defme the structure and the functions of the model. The structure consists of defining nodes and edges of the QSGM model and also the functions that are used when the events occur. The functions are responsible for updating state variables. The following variables have to be defined in order to describe the breadth-first algorithm.
globalCalendar -set of events that are scheduled to occur at some time in future. The globalCalendar is set to be the calendar for the thread that is being executed. event -the event notice being executed. Each event notice i.s a set whose elements are the time at which the event will occur, the priority of the event, the event that scheduled this event, the edge execution condition and the attributes that are passed to the event being executed. The variables used to define the set are:
event.time -temporal interval indicating time when the event i.s scheduled to
be executed.
event.toMethod -event scheduled at event.time.
42
eventpriority -priority ofthe e nt.
event.executionCondition -a conditional stat m nt that e aluat s either TRUE
or FALSE. Ifit is TRUE, then event is execut d.
event.attributes -attributes of the event.
globalCalendar.time -denotes current simulation time [f,t] for the current
thread.
stateVariableArray -array of all variables that represents state of the simulation.
In the single machine system example, the state variables are value of the server
(S), the queue (Q) and the exits (E).
startTimeValue -time interval representing start time of the simulation.
stopTimeValue -time interval representing the stop time of the simulation. The
simulation cannot go beyond stopTimeValue.
The time interval structure has variables start and stop representing the beginning
and ending of the time interval respectively. For exampl , startTim Value.start is the beginning of the startTimeValue interval.
The QSGM algorithm starts with the user initiating the execution of the model by calling the Run procedure. The Run procedure initializes model parameters and calls the StartTime_StopTime procedure that starts the execution of the simulation by inserting the first event or events into the calendar.
Procedure Run Initialize the random number generator if required Initialize the globalCalendar Set the stopping conditions
41
Define the first node or nodes to be cut d (can be ov rridden In model
initialization)
Call StartTime_StopTimeO End Procedure RUff
The Run procedure initializes the state variables of the model and defmes the structure of the simulation model for execution. Also, th g neral structure that is required for any qualitative discrete-event model, like the random number generator (only if required) for the model and the global events calendar, is initialized. It also defines and stores the first event or events that are to be executed at the start. of simulation. A call is made to procedure StartTime_StopTime that executes the QSGM algorithm.
Procedure StartTime_StopTime(startTimeValue, stopTime Value)
Set globalCalendar.time = startTimeValue
Insert first node or nodes to be executed into the globalCalendar
Call BreadthFirstExecution (first event on the calendar to be execut d,
startTimeValue) End Procedure StartTime_StopTime
The procedure StartTime_StopTime sets the globalCalendar.time to startTimeValue. The events that will be executed at the start of the simulation are inserted into the globalCalendar.
In the depth-first algorithm developed by Ingalls (1999), the saved state stack. is used to store the simulation state as new threads are created. The state stack stores current values of state variables array and the global events caLendar. In the breadth-first algorithm, threads are swapped in and out of execution so that the simulation clock time
44 of all of the threads is nearly equal. In order the manage the swapping of threads into and out of execution a structure that holds certain infomlation about acb active thread is required. The structure is called t1,e BreadthFirstNode structUf and for each thread it stores the global events calendar and the state variable array. BreadthFirstNodes are stored in the BreadthFirstNodeQueue. The elements of the BreadthFirstNode structure
are: The variables that are initialized to trace threads and events generated during the execution of models are as follows: eventNumber -represents the number ofevents that have occurred. spawningEvent -denotes the number of the event that spawned or created this thread. modelThread -number of the model thread. Each thread has a using unique number. The maximum value of mode/Thread represents the total number of threads in the model.
modelThreadEvents -denotes the number of events within a model thread. The variables for storing the information required to execute the simulation of the thread are:
eventToBeExecuted -represents the event in the calendar that is scheduled to be executed when this thread is executed next. If the NOS that generated this BreadthFirstNode has more than one event, then there will be different BreadthFirstNodes that represent the alternative sequences of execution. calendarAssociatedWithNode -represents the calendar that is associated with
this thread.
45
stateVariableArra -stores the values ofth tat ariable oftbe tllfead.
After initialization is complete, the proc dur BreadthFirstExecutioll that executes the QSGM model using breadth-first trav rsali called using two parameters first event on the calendar and startTimeValue. The following ariables are used in the breadth-first algorithm.
BreadthFirstNodeQueue -queue for storing nodes of type BreadthFirstNode. possibleEvents -array of events that fOrnJ non deterministically ordered set (NOS) of events that can be possibly executed next. nextTime -the time ofthe simulation if a given event is executed. Following functions are also used: event.node(event.attributes) -executes the function associated with particular event with parameter event.attributes if execution condition for the event is true. The function schedules events and updates state variables. executeEvent -boolean variable defined to store the result after valuating the execution condition of the edge. tempCalendar -copy of globalCalendar. index -temporary variable to keep count of the elements in possibleEvents array. firstNode -variable of type BreadthFirstNode for storing the first node on the BreadthFirstQueue queue. !sSubsetO/O, minO and maxO -interval math function defined in Appendix A.
The procedure BreadthFirstExeclltion is described using the flowchart shown in Figure
5.2.
46
Start Procedure BreadthFirstExecution
Set event=first event on g/obalCalendar
Remove event from a/aba/Calendar
Create firstNode of type BreadthFirstNode Set firstNode.eventNumber= 1 Set firstNode.spawningEvent=O Set firstNade.modeIThread= 1 Set firstNode.mode/ThreadEvent= 1 Set firstNode.eventToBeExecuted = event Set firstNode. ca/endarAssociatedWithNode = globa/Calendar Set firstNode.stateVariableArrav = stateVariableArrav
Set BreadthFirstNodeQueue = empty Queue
Add firstNode into BreadthFirstNodeOueue
No
Set firstNode=first member of the BreadthFirstQueue Remove firstNode from the BreadthFirstNodeQlIeue globaICa/endar=firstNode.calendarAssociatedWithNode event=firstNode. eventToBeExecuted stateVariab/eArray=firstNode.stateVariableArray
Set executeEvent=event. executlonCondition
No
Yes
Call event.node(event.attributes) which schedules new events in qloba/ca/endar
Initialize possibleEvents=empty array of events Set passibleEvents=set of events in globa/Clendar that could be executed next
Figure 5.2: Flow chart for Breadth-First Algorithm
47
9
No
If size of DossibleEvents = 1?
Yes
Set nextTime.start=max(possibleEvents{1]. time. start, globalCalendar. time. start) Set nextTime. stop=possibleEvents. time.stop
event = possibleEvents{l)
Remove event from alobalCalendar
No
Yes
Set globa/Calendar. time =nextTime
Create tempNode of type BreadthFirstNode
Set tempNode.eventNumber=firstNode.eventNumber + 1
Set tempNode.spawningEvent=firstNode.spawningEvent
Set tempNode.modeIThread= firstNode.modelThread
Set tempNode.modeIThreadEvent=firstNode.mode/ThreadEvent+1
Set tempNode.eventToBeExecuted=possibleEvents(l)
Set tempNode. calendarAssociatedWithNode = globa/Calendar
Set tempNode.stateVariab/eArray = stateVariableArray
Add tempNode to BreadthFirstNodeQueue sorted in ascending order of
eventToBeExecuted.time
Set index =1
c
Figure 5.2: Flow chart for Breadtb-First Algorithm (conti 8ued)
4S
No
Set tempCalendar=globalCalendar
Set nextTime.start=max(possibleEvents[index]. time. start,
globalCalendar. time. start)
Set nextTime.stop= min(all possibleEvents. time.stop in the array of possibleEvents)
event =possibleEvents[index] Remove event from tempCalendar Set tempCalendar. time = nextTime
Yes
Create tempNode of type BreadthFirstNode
Set temoNode.eventNumber=firstNode.eventNumber+index
No
Yes
Set tempNode.spawningEvent=firstNode. spawningEvent Set temDNode.modeIThread= firstNode.modeIThr; ad
Set tempNode.spawningEvent=firstNode.eventNumber Set temoNode. modelThread= firstNode.modeIThread+/ndex-t
Set tempNode.modeIThreadEvent=firstNode.modeIThreadEvent +1
Set tempNode.eventToBeExecuted=posslbleEvents[lndex]
Set tempNode. CalendarAssociatedWithNode = tempCalendar
Set tempNode.stateVariableArray = stateVariableArray
Add tempNode to BreadthFirstNodeQueue, sorted In ascending order of
pVAntTnRpF)(p.rIItprl.timp.
index=index+1
Figure 5.2: Flow chart for Breadth-First Algorithm (conti ed)
49
The the proc dure Br adthFir lEx CUIion algorithm is called aft r initialization.
Two parameters are passed to this proc dur and th p udo cod for th procedure are
discussed below.
Procedure BreadtlzFirstExecutioll (first event on global al ndar startTimeValue)
Start
Set event = first event on globalCalendar
Remove event from globalCalendar
II Create firstNode using parameters eventNumber spawningEvent, modelThread,
modelThreadEvent, eventToBeExecuted, globalCalendar stateVariableArray
CreatefirstNode 0 f type BreadthFirstNode
SetfirstNode.eventNumber =1
SetfirstNode.spawningEvent =0
SetfirstNode.l1wdelThread =I
SetfirstNode.modelThreadEvellt =1
SetfirstNode.eventToBeExecuted = event
SetfirstNocle.calendarAssociatedWithNode = globalCalendar
Set firstNocle.state VariableArray = stateVariableArray
IIAdd created node into the queue Set BreadthFirstNodeQueue = empty queue for storing set of BreadthFirstNode sorted in ascending order ofeventToBeExecutecl.lime Add firstNode into BreadthFirstNodeQueue sorted in asc nding order of eventToBeExecuted.time
While BreadthFirstNodeQueue is not empty
Remove firstNode from the BreadthFirslNocleQueue
Point globalCalendar to firstNocle. calenclarAssociatedWithNode
Point event to firstNode.eventToBeExecutecl
Set stateVariableArray = firstNocle.stateVariableArray
II Comment: Up to this point, the algorithm has removed the node from the BreadthFirstNodeQueue to be executed and all of the values are assigned to the global variables. This will execute the event using methods that are accessible by global variables only. The purpose of copying node values to global values is that multiple copies of the calendar have to be made while inserting new nodes into the BreadthFirstNodeQueue. Also the old node is to be deleted from the BreadthFirstNodeQueue.
Set executeEvent = event.executionCondilion
If executeEvent = TRUE Then
50
II omment: If th e ent can be cut d, then it ill all the proc dur that would contain the logic to a]uate the state change i.. changino til stat of the variable and/or sch dUling fUI1h r v nt that could OCCUI after thi ev ot. Events that are sch dul dar placed in the global alendar.
Call event.node(evenLattributes) Else Break out from While loop and check if there are nodes in queue. II (i.e. go back to start of "Wbile" loop.) End If
II Comment: New nodes have to be added into the BreadthFirstNodeQueue bas d on events that could be executed next using this calendar. For each possible vent that could be executed next a separate node has to be created and inserted in the queue. The first thing after this is to detennine events that are possible and could be executed next after this event.
Initialize possibleEvents = empty array ofevents Set possibleEvents = set of events in globalCalendar that could be executed next
II Comment: The next step is to determine the next time when the event could occur.
If (size ofpossibleEvents = 1) Then Set nextTime.start = max(possibleEvents[IJ.time.start, globalCalendar. time.start) Set nextTime.stop = possibleEvents.time. top
II Comment: If this new event occurs and the stopping condition valuates to false then add the node into the queue with this event as a value to the variable
eventToBeExecuted.
event = possibleEvents[l]
Remove event from globalCalendar
If (event. time < stopTime .AND. Stopping Condition = FAL E) Then
Set globalCalendar.time = nextTime Create tempNode of type BreadthFirstNode Set tempNode.eventNumber = flrstNode.eventNumber +1 Set tempNode.spawningEvent = firstNode.spawningEvent Set tempNode.modelThread = flrstNode.modelThread Set tempNode.modelThreadEvent = firstNode.modelThreadEvent +I Set tempNode.eventToBeExecuted = possibleEvents[IJ Set tempNode.calendarAssociatedWithNode = tempCalendar Set tempNode.stateVariableArray = stateVariableArray Add tempNode to BreadthFirstNodeQueue sorted in ascending order of tempNode.eventToBeExecuted.time
51 End If
Else
II Comment: Insert one node each for each e ent that could be possible to be executed next.
For (index =1 to size ofpossibleEvents) Set tempCalendar = globalCalendar Set nextTime.start = max(possibleEvents[index].time. tart,
globalCalendar. time.start) Set nextTime.stop = rnin(all possibleEvents.time.stop in the array of
possibleEvents) event = possibleEvents[index] Remove event from tempCalendar Set tempCalendar.time = nextTime If (tempCalendar.time < stopTime .AND. Stopping Condition = FALSE) Then
Create tempNode of type BreadthFirstNode Set tempNode.eventNumber =firstNode.eventNumber + index If (index =1) Then
Set tempNode.spawningEvent = firstNode. spawningEvent Set tempNode.modelThread =firstNode.modelThread
Else Set tempNode.spawningEvent = firstNode.eventNumber Set tempNode.modelThread =firstNode.modeIThread+index-l
End If Set tempNode.modelThreadEvent =firstNode.modelThreadEvent + 1 Set tempNode.eventToBeExecuted = possibleEvents[index] Set tempNode.calendarAssociatedWithNode = temp alendar Set tempNode.stateVariableArray = state VariableArray Add tempNode to BreadthFirstNodeQueue. sorted in ascending order oftempNode.eventToBeExecuted.time
End If
End For
End If
End While Loop
End Procedure BreadthFirstExecutioll
5.4. Explanation Of The Breadth-First Algorithm With An Example
Consider the single machine example in Chapter 2. The algorithm starts its
execution by calling the RUII procedure. The globalCalendar is initialized with no event
on this calendar. The globalCalendar.time is set to the time [0,0]. The stopping condition
52 is set to E = 5. The e ent graph for this xampl is shown in Figur 2.2 ho s that the first event execut d is the "Run e· ent. This node is tor d in a variable that is used to store the first event to be scheduled on the calendar. Then the e cution pas es to the procedure StartTime_StopTime.
The parameter, startTimeValue is equal to [00] and it indicates start time for the simulation, and stopTimeValue is assigned a sufficiently large value nearly equal to infinity and it indicates stop time for the simulation. These parameters are pass d to the StartTillle_StopTime procedure. The globalCalendar.time is set equal to startTimeValue = [0,0]. The RUN event is inserted in the global events calendar and the procedure BreadtltFirstExecution is called with two parameters a pointer to the RUN vent on the globalCalendar and the starting time ofthe simulation, startTimeValue
Procedure BreadthFirstExecutioll controls the creation and execution of threads. The first event is removed from the calendar and the variable event is assigned the value of the first event. The next step is to create the first BreadthFirstNod which i inserted in the BreadthFirstNodeQueue. The BreadthFirstNode lements will be initializ d to the following values:
eventNumber = 1, spawningEvent = 0, modelThread = 1, moclelThreadEvent = 1 eventToBeExecutecl = event, calendarAssociatedWithNode = globalCalendar, and stateVariableArray = stateVariableArray. The globalCalendar is now because its only entry, the RUN event, has been removed and is stored in the variable eventToBeExecuted. The stateVariableArray is assigned values of state variables Q, Sand E. At the start of the simulation these values are Q = O. S= J and E = O.
53
The newly created node is insert d into th BreadfhFirst ode II U. ow the
BreadthFirstNodeQueue queue has one member the node r pr senting th R e ent in
the first thread. ext, firstNode i assigned to the first m mb r of th
BreadthFirstNodeQueue. firstNode is the removed from the BreadthFir tNod Queue and
the globalCalendar IS assigned to the firstNode's calendar
(jirstNode.calendarAssociatedWithNode). At this time, global alendar is empty b cause
the RUN event has already been removed from the calendar. The fir t event notice, stored
in the variable eventToBeExecuted, is assigned to the global variable event. The state
variables are Q, S and E, and their values 0, 1 and 0, respectively are copied from
firstNode.state VariableArray. After all of the elements of fir tNode are copied to local variables, the event is executed if the edge execution condition evaluates to TR UE by calling the edge execution function that is associated with the node. There is no scheduling edge condition on the edge between the RUN node and the ENTER node shown in Figure 2.2, so the edge execution condition is always TRUE. The RUN event is executed by calling the function which handles scheduling of new events and updating the state variables array. Execution of RUN event schedules an ENTER event at time [0,0] and is represented as the root node of the execution tree in Figure 4.1. The event notice ([0, OJ, 9, ENTER, RUN-ENTER, TRUE) is inserted in the globalCalendar. A BreadthFirstNode node is created with the ENTER event as the event to be executed. The node is inserted in the BreadthFirstNodeQueue. The process continues and executes the ENTER event and START event (nodes 2 and 3 in Figure 4.1) with the same process as the RUN event. After the START event (node 3) is executed, there are two possible events that could be executed next, an
54 E TER event and a LEAVB nt. The ord r of the e cution of th e tw ents in
uncertain because the event OCCUIT ncetim oftb s nod s 0 erlap and they ha e the same priority. The E TER event is scheduled for time [3 8] and tb LE E event scheduled for time [4,6]. Because of this overlap, the algorithm creates two BreadthFirstNodes. The first node has E TER event as the eventToBeExecuted and the second node has the LEAVB event as the eventToBeExecuted. Both nod sarin erted in the BreadthFirstNodeQueue. These two nodes are represented as nodes 4 and 10, respectively, in Figure 4.1.
When both BreadthFirstNodes are in the BreadthFirstNodeQu.eue, the first node removed from the BreadthFirstNodeQueue bas the ENTER event as the eventToBeExecuted. When this event is executed, a node with the LEAVE event (node 5 in Figure 4.1) and a node with the E TER event (node 9 in Figure 4.1) will be added to the BreadthFirstNodeQueue. At this point, a total of 3 nodes are in the BreadthFirstNodeQueue, nodes 5, 9 and 10.
The next BreadFirstNode to be executed will be node lOb cause it has the earliest possible execution time and was in the BreadthFirstNodeQueue b for node 5. Therefore, the execution follows the path 1, 2, 3, 4, 10, 5, 9. 11, 6 and so on. A partial execution sequence of this model is given in Table 5.2. The sequence occurs because the BreadthFirstNodeQueue is ordered by the execution time ofthe nodes.
The BreadthFirstNodeQueue queue is always sorted in ascending order of the event execution time. This is done to keep the simulation clock time of each thread approximately the same. The simulation clock time and state variables in each of the thread at some point of time in simulation is shown in Table 5.1.
55
In Table 5.1, the BreadthFir lode Qu ue was xamjn d at a point in time in the
simulation run. It shows that the BreadlhFirsl oel Queu has 49 thr ads and that th
execution times of those threads intersect with each other. lthough a counter example
can be shown to prove that this inters ction does not always occur, it is expected that the
intersection of execution times will occur often.
Table 5.1: Simulation clock time and state variables at some point in simulation.
Model Model Thread Time S Q E Thread Time S QE 1 [16 24] 0 13 26 [16 18] 022 2 [16 26] 0 13 27 [15 181 022 3 [14 18] 0 22 28 [15 18] 022 4 [14 28] 00 3 29 [15 181 0 22 5 [14 26] 0 0 3 30 [16 30] 0 0 3 6 [14 18] 012 31 [16 281 0 0 3 7 [15 241 013 32 [16 26] 003 8 [14 201 022 33 [16 28] 003 9 [15 30] 003 34 {16 24] 003 10 [15 281 00 3 35 [16 261 003 11 [15 26] 00 3 36 [16 28] 00 3 12 [15 281 00 3 37 [16 261 0 03 13 [15 18] 022 38 [15 24] 0 13 14 [15 18] 022 39 [16 241 013 15 [15 241 0 13 40 [16 20] 022 16 [17 24] 013 41 [16 181 022 17 [16 201 022 42 [16 20] 022 18 [16 26] 0 13 43 f16 261 01 3 19 [17 201 0 03 44 [17 20] 0 o 3 20 [14 18] 022 45 [16 241 01 3 21 [14 20] 012 46 [17 20] 022 22 [14 181 012 47 [17 261 0 1 3 23 [14 22] 012 48 [17 24] 01 3 24 [1,4 201 0 12 49 [18 201 0o 3 25 [16 18] 022
56
Table 5.2: Partial output for single machine example using breadth-first algorithm
1-M d 1Thr ad 1I -Event umb r III -pav ning E ent T -Model Thread ents -Time 1-t cthod
-erver Q -Queue E-Value or xits
x-alendar
I II IIIIV V VI S0E X Start Time: 07/24/200304:14:09 1 1 0 1 1[.00000, .000001 beqin 1 0 0 Ir.000,.000I,enter,nil,999.,l. [.000,.000),start,nil,1. 12 a 2 1[.00000, .000001 enter 1 1 0 3.0000,8.001,enter,nil,999. [3.00,8.00),enter,nil,999. 130 3I LOOOOO, .000001 start 0 0 0 4.0000,6.001,leave:,-1,999. [4.00,6.00),leave:,-1.,999. 1 4 0 4 1[3.0000, 6.00001 enter 0 1 0 6.0000,14.0),enter,nil,999. 2 5 3 4 [4.0000, 6.00001 leave: 1 0 1 3.00,8'.00].enter,nil,999. [4.00,6.00),start,nil,1. 1 6 0 5 [4.0000, 6.00001 leave: 1 1 1 6.0000,14.01,enter,nil,999. [4.00,6.00],leave:,-1,999. 3 7 4 5 [6.0000, 6.00001 enter 0 2 0 9.0000,14.0J,enter,nil,999. [7.00,16.0],enter,nil,999. 2 8 3 5 [4.0000, 8.00001 enter 1 1 1 4.0000,8.00l,start,nil,1. [6.00,14.0],enter,nil,999. 1 9 0 6 [4.0000, 6.00001 start 0 0 1 8.0000,12.01,leave:,-1,999. [6.00,6.00],start,nil,1. 3 10 4 6 [6.0000, 6.00001 leave: 1 2 1 9.0000,14.0I.enter,nil,999. [7.00,16.0),enter,nil,999. 2 11 3 6 1[4.0000, 8.00001 start 0 0 1 8.0000,14.01,leave:,-1,999. [8.00,12.0],leave:,-1,999. 1 12 0 7 1[6.0000, 12.0001 enter 0 1 1 u9.0000,20.0J,enter,nil,999. 4 13 9 7 1[8.0000, 12.0001 leave: 1 0 2 Ir6.00,14.0J,enter,nil,999. [9.00,14.0],enter,nil,999. 3 14 4 7 [6.0000, 6.00001 start 0 1 1 10.000,12.0J,leave:,-1,999. .
[19.0,38.0].enter,nil,999. 1 561 0 17 [20.000, 30.0001 leave: 1 1 5 20.000,30.01,start,nil,1.
(36.0,36.0],start,nil,1. 893 2328 2174 23 1[36.000, 36.0001 leave: 1 7 5 39.000,44.01,enter,nil,999. [36.0,36.0),start,nil,1. 894 2329 2176 23 1[36.000, 36.0001 reave: 1 7 5 39.000,44.01,enter,nil,999. [36.0,36.0],start,nil,1. 895 2330 2178 23 1[36.000, 36.0001 leave: 1 7 5 39.000,44.0J,enter,nil,999. [36.0,36.0J,start,nil,1. 896 2331 2179 23 Ir36.000, 36.0001 leave: 1 7 5 39.000,44.0J,enter,nil,999. [37.0,38.0J,start,nil,1.897 2332 2182 23 1[37.000, 38.0001 leave: 1 7 5 40.000,46.01,enter,nil,999.
57
5.5. Validating The Output
Using the infonnation in Figure 4.1 and Table 5.2, it is shown that the br adthfirst algorithm works as expected. The output of the breadth-first algorithm should also match the output of the depth-first algorithm. The output was obtained for the singl machine system example shown in Figure 2.2 for both algorithms. Both algorithms generated 897 threads for this example, and that matched the number of threads obtained from a similar example used by Ingalls (1999). Also, the output from the breadth-first algorithm was compared event-by-event to the output of the depth-fLrst algorithm, and all of the events were included in both outputs.
5.6. Run-Time Comparison
Literature exists that claims that depth-first traversal algorithms are faster than breadth-first traversal algorithms. In the breadth-first algorithm, since all the nodes are stored in the memory at the same time, there are large memory requirements. (Weiss, 2000) The models that were run where U,e same exact output is given for both the d pthfirst and breadth-first algorithms showed that th depth-first algorithm is always faster. ill particular, for the single machine example discussed previously, the execution times on an Intel Pentium 4, 1.6 GHz for the depth-flrst and the breadth-first algorithms are 6 seconds and 13 seconds, respectively.
However, since the breadth-first algorithm traverses across the tree, the simulation model is able to track all active threads at any given point in time. Because of the availability of all active threads, the modeler could decide that some threads are "less valuable" than other threads. In that case, the breadth-first algorithm has the ability to
58 terminate these "less aluable" thr ads ithout running them to compl tion. The d cision
to terminate a thread early is based on using d cision criteria defmed by the modeler.
Additional coding IS needed to eliminate threads from the BreadthFirstNodeQueue. The elimination step is added after a node is added to the queue. If the number of nodes on the queue exceeds the desired number then the nodes on the queue are compared using the decision criteria and the node performs the worst against the decision criteria is removed from the queue. This step ensures that the number of nodes on a queue does not exceed the desired number, thereby limiting the number of active threads at any point in the simulation.
To show the speed advantage of being able to eliminate unwanted threads, the single machine server example is run with a change in the stopping condition for the simulation. In particular, the stopping condition is changed from E = 5 to E = 8, which means that an individual thread will be complete when the number of jobs processed is equal to 8. This experiment will be run for the depth-first simulation to completion. This experiment will also be run for the breadth-first simulation wh re the number of active threads is arbitrarily limited to 50, 100, 200, 400, and 1000. The experiment will show that, if the modeler is able to design a decision criteria that will eliminate threads, there are speed benefits to the breadth-first algorithm. Also., the output will be focused more on the areas in which the modeler is interested.
In the Table 5.3, the output from the experiment shows tremendous time savings.
59
Table 5.3: Run Time (Seconds) for Single Machine Example (E = 8)
Depth-First
Breadth-
Breadth-
Breadth-
Breadth-
Breadth-
First
First
First
First
First
99383
50 Active
100 Active
200 Active
400 Active
LOOO
Threads
Threads
Threads
Threads
Threads
Active
Max
Max
Max
Max.
Threads
Max
716
4
7
13
31
116
Run Time Function for Breadth-First Algorithm for Number of Active Threads
140 .---=-="""--~~--'.....,......~--~---~---.
~=1
100 -I-~
L----_1
80 +-------------~~------1
• Breadth-First Run Times -2nd Order Polynomial Fit
60 +--------.,;-----~--------_l
40 +--------~::.-----------_1
20 -I-----.,;...:.-----::"e.--------------~
O~:.--.....,;---..__--.....,..--~~--...,...--....."
o 200 400 600 800 1000 1200 Number of Active Threads
Figure 5.3: Run Time Function for Breadth-First Algorithm
Table 5.3 also shows a trend of the increase in runtime as the number of active threads increases. A chart of this run-time increase is shown in Figure 5.3. This chart also shows that a second-order polynomial perfectly fits the data in Table 5.3. With this
polynomial (O.00007x2 +0.0457x+1.5218), we can estimate the number of active threads that would have the same run-time as the depth-fLrst algorithm that generates all
60 of the threads. Based on the fit, the breadth-first run-tim \ ith 2 885 acti e thr ads
would be appro imately the same as th depth-first run-tim .
5.7. Additional Advantages Of The Breadth-First Igorithm
One of the issues with the depth-first algorithm is that model size is restricted due to the amount of memory needed to manage the stack. For single machine model, the depth-first algorithm with E = 10 as the stopping condition generated more than 1,000,000 threads which causes the recursion stack to overflow and stops the execution after nearly 3 hours. However, by using the breadth-first algorithm and restricting the number of nodes in the BreadthFirstNodeQueue to some number that would reduce the memory requirements of the model, the model could run and produce some results. The loss of information due to eliminated threads could be minimized by developing effective decision or thread elimination criteria.
Developing decision rules would be a challenge for a modeler. But it would be worth the effort because the information obtained using Q models is much more valuable when compared to traditional simulation models. This value would come from collecting information that is relevant, instead of random threads generated by the traditional simulation models. Also, eliminating unimportant threads would reduce the complexity in output analysis by allowing the modeler to concentrate on small number of important threads.
Ingalls (1999) has described the thread scoring technique for assigning scores to threads. He used thread scores to rank threads based on relative likelihood of their event execution sequence. He suggested using the thread scoring technique to eliminate threads that are less likely to occur thereby reducing the number of threads from the output of
61
QDES models. H also suggested that th tIlr ad plosion prabl m mak s it difficult to get meaningful information from th output and mak s output analy is difficult. The depth-first algorithm can be used for making a comparison of thread scor s only after th simulation has tenninated, while the br adth-first algorithm provide an opportunity to compare and eliminate low-scoring threads thereby reducing the nm time of the
algorithm. This thesis provides a mechanism for eliminating threads using decision criteria and thus reduces the run time for the algorithm.
62
Chapter 6
Summary and Future Research
6.1. Research Summary
The objective of the thesis is to develop the breadth-first algoritlun for solving Qualitative Simulation Graph Models (QSGM) models. The algorithm traverses the nodes across tbe tree before the nodes below the tree. The algorithm enhances the depthfirst algorithm developed by Ingalls (1999), by traversing the child nodes of the tree before the sibling nodes. The breadth-first algorithm developed is presented and explained in Chapter 5 using the pseudo code algorithm. QSGM, developed by Ingalls (1999), is used as modeling framework used for describing the models. The algorithm is coded in C++ using Visual C++ 6.0. The output obtained using the breadth-first algorithm is tested and compared with the output from the d pth-first algorithm. The comparison of the output obtained validates the breadth-first algorithm. The parameters defined to trace the events and threads in the output shows that the breadth-first algorithm traverses nodes across the tree before going in to the depth of the solution tree. An additional model is built to test the validity ofthe algorithm and the output obtained from both the algorithms is compared. The output obtained from both the algorithm is exactly same (Appendix B).
The breadth-first algorithm uses a queue structure to store the sibling nodes. Each and every thread in the simulation is executed in such a way that each thread's simulation clock time is nearly equal. The reason for this is that the queue is sorted in ascending
63
order of simulation clock time. This may be important to the mod I r in making d ClSlons during simulation. Also, the active th.reads can b aluated and compared to other threads in the simulation at any point in time, which is not possible with the depth-first algorithm. The comparison of the threads based on a certain set of decision rules at certain point in the simulation may help to eliminate threads that are unlikely to give any valuable information. One such example that uses arbitrary decision criteria for comparing and eliminating the threads is explained in Chapter 5. The example shows the importance of developing the breadth-first algorithm because it helps to improve the performance by reducing the run time using the thread elimination criteria. Also, the breadth-first algorithm reduces the complexity of the output by reducing the number of threads and allowing the modeler to concentrate threads that provide meaningful infomlation.
The thesis accomplishes its objective by developing the breadth-first algorithm for solving qualitative simulation graph mod Is. The algorithm provid s the capability to compare all the active threads at some point in th simulation and eliminat the "less valuable" threads using decision criteria. An example is used to show that elimination of the "less valuable" threads resulted in reduction of the run time of the algorithm.
6.2. Future Research
This thesis only considered the uncertain intervals for defining qualitative time in the simulation. It did not consider constant intervals whose value must be the same throughout an entire thread in the simulation. The breadth-first algorithm can be further
developed to include the logic for handling constant intervals.
64
Thjs th sis do s not define th state ariabl qualitati Iy. Th algorithm can b developed to allow definition of th stat ariabl s qualitati Iy. Trus may incr a e th number of threads and the run time of the algorithm, but it would provide flexibility in defining of the modeling parameters.
One of the major concerns of the qualitative simulation algorithms is execution time. Threads can explode exponentially and the execution time for the qualitative simulation can be very long. It is clear that one of the benefits ofbreadth-first simulation is the use of decision criteria to eliminate active threads. In future research, effective decision criteria can be designed which can be used to compare and evaluate the threads in qualitative simulation. With effective decision criteria, unimportant threads can be terminated thereby reducing the run time for the algorithm. Thread scoring techniques, such as those suggested by Ingalls (1999), can also be developed to elimjnate the unimportant threads. The breadth-first algoritJun provides the groundwork for such type of future research by providing a tool to solve QDE models. Algorithms that use parallel processors and multithreading can be developed to execute Q GM mod Is to reduce the run time of the models.
The QSGM methodology developed has not received much attention in practical applications. This thesis attempts to provide an alternative tool for solving QSGM models which might allow QSGM to be developed for practical applications.
65
References
Banks, J, 1998. Handbook ofSimulation, Engineering and Management Press.
Berleant, D., and Kuipers, B. J., 1997. Qualitative and Quantitative Simulation: Bridging The Gap, Artificial Intelligence, 95:215-255.
Bulitko, Y., and Wilkins, D. C., 2003. Qualitative Simulation of Temporal Concurrent Processes using Time Interval Petri Nets, Artificial Intelligence, 144:95-124.
Cellier, F. E., 1991. Qualitative Modeling And Simulation: Promise Or Il1usion, Proceedings ofthe 1991 Winter Simulation Conference, eds. Barry L. Nelson, W. David Kelton, and Gordon M. Clark, pp. 1086-1090.
Clancy, D. J., Brajnik, G., and Kay, H., 1997. Model Revision: Techniques and Tools For Analyzing Simulation Results and Revising Qualitative Models, 11th International Workshop on Qualitative Reasoning, Cortona, Siena Italy, June 1997.
Damerdji, H. And Nakayama, M. K., 1999. Two-Stage Multiple-Comparison Procedures For Steady-State Simulations, ACM Transactions on Modeling and Computer Simulation, 9(1):1-30.
Farquhar, A., Kuipers, B., Rickel, J., Throop, D. and The Qualitative Reasoning Group, 1994. QSIM: The Program and its Use, Department of Computer Science, University ofTexas at Austin, Austin, Texas, October 18, 1994. [Retriev don July 29, 2003] URL: htt ://www.s.utexas.cdu/uscrs/r/R-sortwar.html-sim.
Goldsman, D., Marshall, W. S., Seong-Hee Kim, and Nelson, B. L., 2000. "Ranking And Selection For Steady-State Simulation", Proceedings ofthe 2000 Winter Simulation Conference, eds. J. A. Joines, R. R. Barton, K. Kang, and P. A. Fishwick, pp. 544-553.
Hamscher, W., Kiyang, M. Y. and Lang, R., 1995. Qualitative Reasoning in Business, Finance, and Economics: Introduction, Decision Support Systems, 15(2):99-103.
Hao, W., Fujimoto, R. M. and Riley, G., 2001. Experiences Parallelizing A Commercial Network Simulator, Proceedings ofthe 2001 Winter Simulation Conference, eds.
B.A. Peters, l.S. Smith, DJ. Mederios, and M.W. Rohrer, pp. 1353-1360.
Hocaoglu, M.F., 2003. A Comparison between Qualitative Simulation and Traditional Simulation: Bridging the Conceptual Gap, Applied Modeling and Simulation Joint Research Group (AMSJRG), Infonnation Technologies Research Institute Tubitak-Marrnara Research Center, Turkey. Working Paper. [Retrieved on July 29,2003] URL: http://www.btae.mam.gov.tr/-hocaoglu/qscomparison.pdf.
66
Ingalls, R. G., 1999. Qualitative Simulation Graph Melhodoio and /mpl In nta/ion The niversity of Texas at Austin.
Kuipers, B., 1986. Qualitative Simulation, Artijiciallntelligenc 29:28 -238.
Kuipers, B., 2001. Qualitative Simulation, 2001. [Retrieved on July 22 2003] URL: http://,ww.cs.utexas.edu/users/gr/paprs/·ui!rs-epst-01.html.
McConnack, W. M., and Sargent, R. G., 1981. Analysis of future Event Set Algorithms for Discrete-event Simulation, Communications a/the A 'M 24(12):801-812.
Neelamkavi1, F., 1987. Computer Simulation and Modelling, John Wiley & Sons Ltd.
Preiss, B. R., 1999. Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, Inc. New York.
Schruben, L. W., 1983. Simulation Modeling with Event Graphs, Communications o/the ACM,26(11):957-963. .
Weiss, M. A., 2000. Data Structures And Problem Solving Using C++, Addison-Wesley. Reading, Massachusetts.
Wyatt, G. J.,. Leitch, R. R. and Steele, A.D., 1995. Qualitative and Quantitative Simulation of Interacting Markets, Decision Support Systems, 15(2):105-113.
Yticesan E. and L. W. Schruben. 1992. Structural and Behavioral Equivalence of Simulation Models. ACM Transactions on Modeling and Computer Simulation, 2(1): 82-103.
67
Appendix A. Interval Math
Function
a=b a+b a-b a*b a IsSubsetOfb max(a,b) min(a,b) a<b a equal to b Midpoint(a)
Result of the function
Assign (a-= b-) and (a+= b+)
Evaluates to [a-+b-, a++b+]
Evaluates to [a--bO, a+-b+]
Evaluates to [a-* b-, a+ * bJ
True if «a">b-) and (a+<bj) else False
Evaluates to [max(a-,bO),max(a+,b+)]
Evaluates to [min(a-,b-),min(a+,bYl
True if(a+<b-) else False
True if «a-= b-) and (a+= by) else False
Equals to «a-+a+)/2)
Source: Ingalls (1999) Page 25.
""-~----------------------Appendix B. PERT Network Example
The breadth-fLrst algorithm is also validated using the PERT (program E aluation and Review Technique) network problem in addition to the singl machin s rver example discussed in the thesis. The PERT example discussed here is a simple network with 7 nodes. The event graph representation of the PERT network is shown in Figure
B.1.
1"17 [6.7) ~r-::\
~
H,
H
H,-o
H,-o
H,-o
110-0
Figure B.l. PERT Network Event Graph The nodes are labeled from 0 to 7 and the scheduling edge conditions are represented on the edges. The state variables are defined as Hi , for i = I to6. Hi -the number oftimes node i has been hit. For example, when the edge between nodes I and 2 is scheduled, the number ofhits on node 2 will be equal to I. The partial output obtained using the depth-first algorithm is shown in table RI.
69
Table B.1: The Depth-First Algorithm Partial Output for PERT etwork E ample
1-Model Thr ad
II -E
nl
umb
r
111 -
pa
ning
vent
T -od] Thread E j[ -Tail Ev nt
ents
-Time In alendar
1
H ad
vent
I
II
III
IV
V
VI
VII
VIII
1
1
0
1
[.000,.000]
0
1
[2.0000,6.0000],node:,( 1 2 ),3,nil.
1 1 1 1 1 1
2 3 4 5 6 7
a 0 a 0 0 0
2 3 4 5 6 7
[2.00,6.00] [8.00,15.0] [8.00,15.0] [8.00,15.0] [8.00,15.0] [10.0,24.0]
1 2 3 2 2 3
2 3 4 4 5 5
[8.0000,20.000],node:,( 2 3 ),3,nil. [6.0000,16.000],node:,( 2 4 ),3.nil. f5.0000, 15.000J,node:,( 2 5 ),3,nil. [6.0000,16.000],node:,( 2 4 ),3,nil. [5.0000,15.000],node:,( 2 5 ),3,nil. [8.0000,15.000),node:,( 3 4 ),2,nil. f10.000,27.000],node:,( 3 5 ),3,nil. [6.0000, 16.000],node:,( 2 4 ),3,nil. [5.0000, 15.000],node:,( 2 5 ),3,nil. [1 0.000,27.0001.node:,( 3 5 ),3,nil. [5.0000, 15.000],node:,( 2 5 ),3,nil. [10.000,27.000],node:,( 3 5 ),3,nil. f11.000,24.0001,node:,( 4 6 ),3,nil. [10.000,27.000],node:,( 3 5 ),3,nil. f11.000,24.0001,node:,( 4 6 },3,nil. [11.000,24.000],node:,( 4 6 ),3,nil. [16.000,36.0001,node:,( 5 6 ),3,nil.
1
8
0
8
[11.0,24.0]
4
6
[16.000.36.000],node:,( 5 6 ),3,nil.
1
9
0
9
[16.0,36.0]
5
6
[22.000,43.000],node:,( 6 7 ),3,nil.
1
10
0
10
[22.0,43.0]
6
7
39
173
169
8
[16.0,29.0]
5
6
[11.000,29.000],node:,( 4 6 ),3,nil.
39
174
169
9
[16.0,29.0]
4
6
[22.000.36.000],node:,( 6 7 ),3,nil.
39
175
169
10
[22.0,36.0)
6
7
40
176
168
7
[11.0,29.0]
4
6
[10.000,32.000],node:,( 3 5 ),3,nil.
40 40
177 178
168 168
8 9
[11.0,32.0] [17.0,44.0]
3 5
5 6
[17.000,44.000],node:,( 5 6 ),3,nil. [23.000,51 ..o00],node:,( 6 7 ).3,nil.
I
40
179
168
10
[23.0,51.0]
6
7
70
The output shows threads 1, 39 and 40 only. The total numb r of threads for the PERT example represented by e ent graph in Figure B.l produc s 40 threads. The above model is also executed using the breadth-first algorithm and the output is shown in Table
B.2. It should be noted that the events in Table B.2 are not in the order that they were
executed. The order of execution is shown with the Event Number column.
Table B.2: The Breadth-First Algorithm Partial Output for PERT Network Example I-Model bread lJ -Ev nt limb r III -pawning ~vent IV-Model Thread Events V -Time VI -Head nt vn -Tail Event vnr -alendar
I II III IV V VI VII VIII
1
1
0
1
[.000,.000]
0
1
[2.0000,6.0000],node:,( 1 2 ),3,nil
[8.0000,20.000],node:,( 2 3 ),3,nil.
1
2
0
2
[2.00,6.00]
1
2
[6.0000,16.000],node:,( 2 4 ),3,nil.
[5.0000,15.000l,node:.( 2 5 ),3,nll.
[6.0000,16.000],node:,( 2 4 ),3,nil.
1
3
0
3
[8.00,15.0]
2
3
[5.0000,15.000].node:,( 2 5 ),3,nil. [8.0000,15.000],node:.( 3 4 ),2,nil.
[10.000,27.000].node:,( 3 5 ),3,nil.
[6.0000, 16.000],node:,( 2 4 ),3nll.
1
6
0
4
[8.00,15.0]
3
4
[5.0000, 15.000].node:,( 2 5 ),3,nil.
[10.000,27 .0001.node:,( 3 5 ),3.nil.
[5.0000,15.000].node:,.( 2 5 ),3,nil.
1
11
0
5
[8.00,15.0]
2
4
[10,000,27.000].node:,( 3 5 ),3,nil.
[11.000,24.0001.node:.( 4 6 ),3,nll.
1
18
0
6
[8.00,15.0]
2
5
[1 O.OOO,27.000],node:,( 3 5 ),3,nil. [11.000,24.0001.node:.( 4 6 ),3,nil.
1
32
0
7
[10.0,24.0]
3
5
[11.000,24.000],node:,( 4 6 ),3,nil. [16.000,36.0001,node:,( 5 6 ),3,nil.
1
60
0
8
[11.0,24.0]
4
6
[16.000,36.000],node:,( 5 6 ),3,nil.
1
100
0
9
[16.0,36.0]
5
6
[22.000,43.000],node:,( 6 7 ),3,nil.
1
140
0
10
[22.0,43.0]
6
7
25
53
28
7
[11.0,29.0]
4
6
I
(1 0.OOO,32.000j,node:,( 3 5 ),3,nil.
25
90
28
8
[11.0,32.0]
3
5
[17.000,44.000},node:,(56 ),3,nil.
25
130
28
9
[17.0,44.0]
5
6
[23.000,51.000],node:,.( 6 7 ),3,nil.
25
170
28
10
[23.0,51.0]
6
7
71
-~
40
98
58
8
[16.0,29.0]
5
6
[11.000,29.000],node:,( 4 6 ),3,nil.
40
138
58
9
[16.0,29.0]
4
6
[22.000,36.000],node:,( 6 7 ),3,nil.
40
178
58
10
[22.0,36.0]
6
7
Both the algorithms produce similar output which can be seen from Table B.1 and Tabl
B.2. Threads l, 39 and 40 of the depth-first algorithm are exactly same as threads 1 40 and 35 of the breadth-first algorithm. This further validates the accuracy of the breadthfirst algorithm.
72
VITA ®
Nitin Agrawal
Candidate for the Degree of
Master of Science
Thesis: BREADTH-FIRST ALGORITHM FOR QUALITATIVE DISCRETE-EVENT SIMULATION.
Major Field: Industrial Engineering and Management.
Biographical:
Personal Data: Born in Amravati, Maharashtra, India on April 8, 1977, son of Satyanarayan Agrawal and Usha Agrawal.
Education: Graduated from Brijlala Biyani Science College, Amravati, Maharashtra, India in May 1994; received Bachelor of Engineering degree in Production from V. J. T. 1., University of Mumbai, Mumbai in June 1998. Completed the requirements for the Master of Science degree with a major in Industrial Engineering and Management at Oklahoma State University in December 2003.
Experience: Employed as a graduate Teaching Assistant, School of Industrial Engineering and Management, Oklahoma State University, August 2003 to December 2003. Employed as a graduate Research Assistant, Oklahoma State Unjversity, School of Industrial Engineering and Management, January 2002 to May 2003. Employed as an Assistant Manager, Engine Assembly 3-Wheeler Division, Bajaj Auto Ltd., India, July 1998 to July 2001.
Professional Membership: Alpha Pi Mu and Kappa Phi Kappa.
~-----------......-----