

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


INVESTIGATION OF A NEURAL NETWORK METHODOLOGY TO PREDICT TRANSIENT PERFORMANCE IN FMS By AUGUSTINE JONGIK KWON Bachelor of Science University of MissouriRolla Rolla, Missouri 1989 Master of Science University of MissouriRolla Rolla, Missouri 1991 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY May 2005 INVESTIGATION OF A NEURAL NETWORK METHODOLOGY TO PREDICT TRANSIENT PERFORMANCE IN FMS BY AUGUSTINE JONGIK KWON Thesis Approved: Dr. David B. Pratt __________________________________________________ Thesis Advisor Dr. Michael Branson _________________________________________________ Dr. Martin Hagan __________________________________________________ Dr. Manjunath Kamath __________________________________________________ Dr. Gordon Emslie __________________________________________________ Dean ofthe Graduate College ii ACKNOWLEGEMENTS I wish to express my sincere appreciation to my major advisor, Dr. David Pratt for his intelligent supervision, guidance, suggestions, and encouragement. My sincere appreciation extends to my other committee members, Dr. Michael Branson, Dr. Manjunath Kamath, and Dr. Martin Hagan, for their helpful comments, suggestions, and understanding during the course of this study. I also would like to thank Dr. John Nazemetz and the Industrial Engineering and Management Graduate Program for providing me with a research assistantship and their generous financial support during my stay in the program. I would like to express my deepest gratitude to my wife, Cindy, for her support, love, and understanding throughout the whole process. I thank my children, Katie and Megan, for their unconditional love and understanding despite being absent many times during last five years. Special thanks to my dear parents, God, and blessed Mary for the privilege and honor of obtaining the doctoral degree with the help of their unconditional love, encouragement, and inspiration. Finally, I would like to thank my boss, Sam Nusinow at Knowledge Base Engineering, Inc. and the School of Industrial Engineering and Management for supporting me to successfully complete this study. iii TABLE OF CONTENTS 1. Introduction ……...……..…...……………………………………………………… 1 1.1 Motivation of the Research……………………………………………...………...1 1.1.1 Growing Usage of FMS……………………………………………...……...3 1.1.2 Known Integration and Performance Modeling Issues with FMS ….....…....5 1.1.3 Importance of Performance Predictor in Online Controller………………..7 1.1.4 Simulation Modeling versus Metamodeling………………………………..9 1.1.5 Artificial Neural Network Based Metamodeling vs. Regression Based Metamodeling Approach……………………………………..……............11 1.2 Problem Statement…………………………………………………...…………..14 1.3 Scope of the Research……………...…………………………………………….16 1.4 Anticipated Contributions………...……………………………………………...18 1.5 Overview of the Dissertation……………………………………………………..20 2. Literature Review……...…………..……………………………………..…………22 2.1 Queueing Network Approaches…...……………………………………………..23 2.1.1 Summary of Major Developments……………...………………………….23 2.1.2 Conclusion………………………………………………………………….34 2.2 Markov Chain Models……………………………………………………………39 2.2.1 Summary of Major developments………………………………………….39 iv 2.2.2 Conclusion………………………………………………………………….47 2.3 Simulation Modeling……………………………………………………………..49 2.3.1 Summary of Major Developments………………………………………...49 2.3.2 Conclusion………………………………………………………………...61 2.4 Stochastic Petri Nets……………………………………………………………...63 2.4.1 Summary of Major Developments………………………………………...63 2.4.2 Conclusion………………………………………………………………...73 2.5 Summary…………………………………………………………………………75 3. Problem Settings and Systems Description………………………………………..79 3.1 FMS………………………………………………………………………………79 3.1.1 System Description………………………………………………………..79 3.1.2 Parts………………………………………………………………………..82 3.2 Time Series Analysis………………………………………………………..…….90 3.3 Artificial Neural Networks………………………………………………………121 3.3.1 Background………………………………………………………………121 3.3.2 Multilayer Neural Network Architecture and Training Methods………..130 3.3.3 Proposed Neural Network based metamodeling framework……..…….144 4. Statement of Research…………………………….……………………………….148 4.1 Research Goal………………………………………………………………….148 4.2 Research Objectives……………………………………………………………148 4.3 Assumptions and limitations…………………………………………………...153 v 4.4 Summary……………………………………………………………………….154 5. Research Methodology………..…………………………………………………...156 5.1 Research Tasks…………………………………………………………………156 5.2 Simulation Based Disruption Scenarios………………………………………..161 5.3 Summary……………………………………………………………………….167 6. Problem Development – Pilot Experiments…………………………………...….168 6.1 Development of a Computer Simulation Model……………………………….168 6.2 Initial Experiments and Findings………………………………………………171 6.3 Initial Simulation Experiment Sets and Data Processing Procedures………….181 6.4 Post Disruption Behavior Pattern Classification……………………………….187 6.5 Identification of Input and Output Vectors…………………………………….199 6.6 Summary……………………………………………………………………….214 7. Experimental Results………………….………………………………..…..……..215 7.1 Construction and training of Individual ANNs………………………………....215 7.2 Expansion of the Initial Experiment Size……………………………………....225 7.3 Performance Evaluation of Proposed Modeling Scheme……………………....228 7.4 Summary………………………………………………………………………..249 8. Summary and Conclusions......................................................................................250 8.1 Overview of Research Objectives and Accomplishments...................................250 vi 8.2 The major contributions of this research..............................................................253 8.3 The Strength and Weakness of the Proposed Modeling Approach......................257 8.4 Future Research Directions and Opportunities....................................................259 8.5 Summary..............................................................................................................260 Bibliography……………………………………………………………………..….…262 Appendix A…………………………………………………………………………….275 Extended Design of Experiments………………………………………………...….276 Appendix B………………………..…………………………………………………..287 B.1 MATLAB Source Code for Training Individual ANNs………………………288 B.2 Transient Behavior Prediction User Interface in MATLAB…………………..301 Appendix C……………………………………………………………………………306 C.1 Input Vectors for Postdisruption Type 1 ANNs, Net_2_1_1, Net_2_1_2, and Net_2_1_3, from the second level ……….…………………………………….307 C.2 Input Vectors for Postdisruption Type 2 ANNs, Net_2_2_1, Net_2_2_2, and Net_2_2_3, from the second level ……………………………………………..332 C.3 Input Vectors for Postdisruption Type 3 ANNs, Net_2_3_1 and Net_2_3_2, from the second level………..…………………………………………………345 C.4 Output Vectors for Net_1_1…………………………………………………….406 C.5 Output Vectors for Net_2_1_1………………………………………………….421 vii C.6 Output Vectors for Net_2_1_2………………………………………………….426 C.7 Output Vectors for Net_2_1_3………………………………………………….429 C.8 Output Vectors for Net_2_2_1…………………………………………………430 C.9 Output Vectors for Net_2_2_2…………………………………………………437 C.10 Output Vectors for Net_2_2_3………………………………………………..440 C.11 Output Vectors for Net_2_3_1………………………………………………..443 C.12 Output Vectors for Net_2_3_2………………………………………………..454 Appendix D……………………………………………………………………………467 Appendix E…………………………………………………………………………….477 Appendix F…………………………………………………………………………….487 viii LIST OF FIGURES Figure Page 1 Scenario for Interfacing Simulation with Physical System for Realtime Control……………………………………………………………. 57 2 Physical layout of the FMS under study………………………………. 81 3 A stationary time series showing shortterm correlation with its correlogram……………………………………………………………… 104 4 A nonstationary time series together with its correlograms……………. 105 5 A time series contains a periodic component ………………………….. 112 6 A spectrum with the corresponding normalized spectral distribution function…………………………………………………………………. 116 7 Anatomical illustration of biological neurons…………………………... 122 8 SingleInput Neuron…………………………………………………….. 123 9 Typical Transfer functions……………………………………………… 131 10 Threelayer network…………………………………………………….. 133 11 Proposed ANN based Metamodeling scheme…………………………... 146 12 Graphical Representation of Stable and Unstable Equilibrium…………. 165 13 Set Part Type Attribute Block ………………………………………….. 169 14 Part Routing and AGV Control Logic ………………………………….. 170 15 Single Resource Failure Scheduling and Control………….……………. 171 16 Row TIS Observations during First 500 Parts under the First Steady State Scenario with No Disruption……………………………………… 174 17 Moving Average Filtered TIS Observations under the First Steady State Scenario with No Disruption……………………………………………. 179 18 Moving Average Filtered TIS Observations under the First Steady State Scenario with Machine M6 Failure Took Place at 10000 ……………… 180 19 Preprocess Steps……………………………………………………….. 188 ix Figure Page 20 Type 0 (no change) Transient Behavior Pattern Class………………….. 190 21 Type 1 (an infinite linear growth) Transient Behavior Pattern Class…… 191 22 Type 2 (an infinite nonlinear growth) Transient Behavior Pattern Class……………………………………………………………………. 192 23 Type 3 (a finite growth to a new steady state) Transient Behavior Pattern Class…………………………………………………………… 193 24 Individual Moving Average Filtered TIS plots under Scenario No.19... 195 25 Moving Average Filtered Mean TIS Plots under Scenario No.19…….. 197 26 A Closeup View of Moving Average Filtered Mean TIS Plots under Scenario No.19………………………………………………………… 198 27 Proposed TwoLevel Deep Taxonomically Organized ANN Based Transient Performance Model…………………………………………. 211 28 Network Diagram of Net_1_1 in the Top Level………………………. 216 29 Individual Network Diagram of Type One Transient Behavior Approximation subANNs in the Second Level………………………. 217 30 Individual Network Diagram of Type Two Transient Behavior Approximation SubANNs in the Second Level………………………. 219 31 Individual Network Diagram of Type Three Transient Behavior Approximation subANNs in the Second Level………………………. 221 32 Performance Plots of the Top Level ANN Net_1_1 during Its Initial training with 90 Input and Output …………………………………….. 223 33 Comparative Performance plots of sub ANNs, Net_1_1 and Net_2_3_2, under Old and New Training, Test, and Validation Vector Sets…………………………………………………………………….. 227 34 RAW TIS and Moving Average Filtered (MA) TIS Plots of Exp No. 438 (Postdisruption Type 1 Behavior)………………………………... 232 35 Moving Average Filtered (MA) TIS vs. Approximations by a Quadratic Model for TISs during First 400 Postdisruption Observations…………………………………………………………… 233 x Figure Page 36 Moving Average Filtered (MA) TIS vs. Approximations by a Linear Regression Model for TISs from 4753rd to 8653rd Observation……... 234 37 Moving Average Filtered (MA) TIS vs. Approximations by the final Composite Regression Model for TISs from 4353rd to 8653rd Observation……………………………………………………………. 235 38 Trend Plot of Standard Deviation of Moving Average (w=500) Filtered TIS observations before and after the disruption and Comparative Plots of Standard Deviation Regression Models………... 236 39 Comparative Plots of Mean TIS Approximations by Various Regression Based Models for Exp438 (Type1)………………………. 238 40 Comparative Plots of Sigma Approximations by Various Regression Based Models for Exp438 (Type1)…………………………………… 239 41 Descriptive Statistics and Normality Test on RAW TIS data from Predisruption Period of Exp438………………………………………….. 243 42 Descriptive Statistics and Normality Test on MA TIS data from Predisruption Period of Exp438…………………………………………... 244 43 Open Queueing Network………………………………………………. 489 44 Example of graphical representation of a Petri net…………………….. 496 45 Reachability tree of the model in Figure 44………………………….. 499 46 GSPN model of Figure 44 with given exponential and immediate transition times………………………………………………………… 502 47 Finding an equivalent CTMC for GSPN model given in Figure 5 503 48 A conversion from an ordinary PN of the FCFS queueing discipline with two job classes to an equivalent CPN…………………………… 506 xi LIST OF TABLES Table Page 1 Major Developments in FMS Performance Study Using QN Analysis…………………………………………………………………. 35 2 Sample orders with four part types under a production plan……………. 82 3 Interarrival Time and Machining Process Requirements for Different Part Types……………………………………………………………….. 83 4 Presort Conveyor Belts and Possible Part Types………………………. 84 5 Relative Part Size for Different Part Types……………………………... 85 6 Part Groups and Machine Process Capability………………………… 87 7 Service Time Distributions for Individual Part Types……….…………. 88 8 Part Types and Possible Part Mix Change Scenarios…………………… 162 9 Possible Single Machine Failure Scenarios……………………………... 163 10 Possible Single AGV Failure Scenarios………………………………… 163 11 Possible Single Resource Failure Scenarios……………………………. 166 12 Four Steady State Scenarios and Their Warmup Periods……………… 173 13 Individual System Resource Utilization Rates under Four Steady State Scenarios………………………………………………………………… 177 14 Four Steady State Scenarios and Their Control Limits…………………. 178 15 Initial Experiment Set…………………………………………………… 182 16 Makeup for Four Transient Pattern Types………………………………. 194 17 Semantics of Common Input Vector p….……………….….…………. 201 18 Semantics of First Output Vector a1 from the Top Level ANN…………………………………………………………………….. 202 19 Semantics of Output Vector a2,1 from First Three ANNs in the Second Level ANNs to Approximate Transient Behavior Pattern Type No.1…………………………………………………………..………… 204 xii Table Page 20 Semantics of Output Vector a2,2 from Second Group of Three ANNs in the Second Level ANNs to Approximate Transient Behavior Pattern Type No. 2………………………………………………………………. 207 21 Semantics of Output Vector a2,3 from Third Group of Two ANNs in the Second Level ANNs to Approximate Transient Behavior Pattern Type No. 3…………………………………………………………………….. 210 22 Training and Testing Performance Indexes from Individual Neural Networks with 90 training and 45 Testing Input and Output Vectors (original experiment set)………………………………………………… 224 23 Training, Test, and Validation Performances from Individual SubANNs under New Extended Training, Test and Validation Vector Sets vs. Those under Old Training, Test, and Validation Vector Sets……….. 226 24 Major Event Start Times on MA TIS Observations from 18 Selected Experiment RAW Data………………………………………………….. 230 25 Major Event Start Times on Approximated TIS Observations Rendered by Regression Models Based on MA Scenario Average TIS Observations from 18 Selected Experiments…………………………… 230 26 Major Event Start Times on Approximated TIS Observations Rendered by ANN Generated Regression Models for 18 Selected Experiments….. 231 27 TIS Transient Behavior Prediction Performance Table for Selected Experiments under Three Postdisruption Behavior Types……………... 247 xiii 1 1. Introduction 1.1 Motivation of the Research In most scientific domains, it is a common practice to build physical or mathematical models to study a system of interest. These models are frequently defined to be a collection of entities (components). These entities act and interact together toward the accomplishment of some logical end [Schmidt and Taylor 1970]. Often, these physical or mathematical models are simplified forms (abstractions) of real systems because it is only necessary to consider those aspects of the system that affect the system behavior under investigation [Banks et al. 1996]. Studying a system model normally provides an opportunity to better understand the relationships among its components or to predict how the system will operate under new policies or new operational conditions [Law and Kelton 1991]. In practice, for many real world systems, building a physical model is often too costly and impractical due to complexity and lengthy development time. Especially when models for the system require a fullscale level of detail, the cost can be prohibitive based on the nature of the system. For this reason, mathematical models are often preferred in many fields to study characteristics or behaviors of the system under given conditions. 2 System models can be classified into two broad categories based on their use. The first type is an evaluative model. An evaluative model can be used to study a particular system behavior(s) under a set of given configurations and operational parameters. The second type is a generative model. Generative models are built to find a set of optimal decision parameters that can satisfy operational or design objective(s) for the system under given constraints. Evaluative models are designed to provide performance predictions that are essential during the design and operational stages of a system. On the other hand, generative models are extensively used for performance optimization in various operations research (OR) type studies. Reliable performance prediction for manufacturing systems has been the focus of many industrial and academic research communities. Reliable but easytodevelop and easytouse evaluative models for both design and operation are crucial for operational success. Most evaluative models have focused on longterm steadystate system behaviors rather than shortterm transitory behaviors. For this reason, it is not ideal to use them to forecast often volatile transitional shortterm behaviors following events that cause disruptions of the steadystate behavior of a system performance indicator. Examples of unexpected events that can cause system disruptions are machine failures, rush orders, and changes in product mix due to part or material shortages. With the advent of more powerful computer and information technologies, interest in industrial application of online decisionmaking has intensified in recent years. In the area of highly automated production and process controls, online decision3 making and its associated issues have become prominent research topics. Especially in the area of flexible manufacturing system control, conveying a realistic view of upcoming shortterm behavior of the system is vital to building effective control policies to minimize unwanted performance deviation following an unexpected system disruption(s). 1.1.1 Growing Usage of FMS The most common challenge faced by manufacturers around the world today is to adapt themselves to a rapidly changing operational environment. The demand for highly customized products is on the rise and today’s fierce competition in lowcost precision manufacturing is unprecedented. Among many strategies available to deal with these challenges, one approach is to adopt and implement various forms of flexible manufacturing systems (FMSs) as a part of a strategic plan. There are many definitions of FMS available. Even though they may have some difference in details, all seem to agree on common basic design fundamentals that can be found in the definition given by Groover [1987]. According to Groover [1987], an FMS is a fully automated system consisting of functionally similar or dissimilar automated workstations interconnected by means of an automated material handling system and storage system, and controlled by an integrated computer system. The workstations are considered automated cells of computer numerical control (CNC) machines. A similar term, flexible manufacturing cell (FMC), often used in place of FMS, can be defined as follows: a typical FMC comprises a few numerically control (NC) machines, tool 4 magazines, and one or more material handling robots [Narahari and Viswanadham 1989]. According to Groover [1987], a distinction between FMS and FMC can be made based on the number of NC or CNC machines comprised within. Therefore, an FMS can also be formed as a collection of several FMCs. FMSs have various documented and publicized merits such as high adaptability to changes, flexibility in configurations and operations, improved product quality, short leadtime, and high utilization with a relatively low WIP [Groover 1987], [Vollmann et al. 1997]. From a systems perspectives, finding an effective modeling tool for FMSs will likely make contributions to modeling other Discrete Event Dynamic Systems (DEDS) because the system dynamics observed in various FMSs are analogous to those that can be found in many DEDS. In general, DEDS are large scale interconnected systems, driven by the occurrence of discrete events, where their dynamic behavior involves state changes only at discrete points in time [Ho et al.1984]. Complex interactions are often present in the system behaviors of DEDS. Synchronization, concurrency, randomness, and contention for limited resources are common aspects of these interactions [Narahari and Viswanadham 1989]. DEDS can be found almost everywhere in today’s modern technological infrastructure. According to Ho et al. [1984], examples of such systems encountered today are communication networks, computer systems, production/assembly lines, traffic systems, and transportation networks. Therefore, an effective modeling methodology for FMS transient behaviors may be applicable to these systems with some modifications. 5 1.1.2 Known Integration and Performance Modeling Issues with FMS Despite many publicized FMS merits, there are four welldocumented limitations [Huang and Chen 1986] that keep FMSs from being more widely applied in industry. These limitations are: 1. high initial costs, 2. long implementation lead time, 3. uncertainty of a successful FMS interface with the current production system, and 4. control software customization issues based on uniqueness of each installation site. All of the above limitations except the third, uncertainty of a successful FMS integration, can be naturally resolved as time progresses with little commitment from those who actually operate FMSs on a daytoday basis. For example, the continuous market growth in FMS installation and ongoing technological innovation will lower the high cost of precision machine tool manufacturing. Thus, FMSs will eventually become an affordable form of automation even to manufacturers without great financial strength. To overcome the uncertainty of successful FMS interface with the current production system, tremendous effort is required from both FMS designers and operators no matter how advanced the supporting technology becomes in the future. Without these efforts, the full potential of FMS may not be realized. 6 The concept of FMSs can be used within the context of manufacturing cells. Individual cells consist of several workcenters that can carry out similar or dissimilar manufacturing functions. Lin and Chiu [1993] stress that understanding and being able to predict dynamic behavior as well as long term manufacturing cell performance is necessary to better coordinate production among cells. Therefore, knowledge of transient performance behavior as well as steadystate behavior of individual cells can be vital to overcoming the third limitation in adopting FMS. Another research effort points out that the studies done on interactions among FMS resources and impacts brought by random changes in operations are still insufficient [Basnet and Mize 1994]. Random changes during operation, such as resource breakdowns and rush orders, are normally responsible for unanticipated system interruptions. Traditional performance modeling approaches, such as analytical and simulation modeling, constantly rely on human intelligence and modeling skills to create and maintain effective evaluative power. On a busy shop floor, especially for a highly utilized FMS, the ability to make instantaneous decision to effectively handle a wide range of critical disruptions using an effective shortterm evaluative model can be highly beneficial. For example, evaluative models based on steadystate performance can help an operator select a proper operational strategy in order to reach an optimal production level based on a long term production schedule. On the other hand, an effective shortterm look head capability can help an operator choose a proper short term remedy to handle the daytoday operational problems without compromising the longterm7 performance goal. However, due to its dependency on human intelligence and expertise, occasional offline maintenance is required when there are significant changes to the system configurations and operation rules. For example, adding new part type, AGV or machine center to the existing system requires redefining its state space in a Markov chain model. Lacking selfmaintainable modeling capability in a highly dynamic operational environment can sometimes result in a costly impact to the rest of production line. Utilizing transient analysis to measure impacts on a performance indicator following one or more disruptions will provide an FMS operator the opportunity to assess the situation and help him/her make the best operational choice so that the impact to the other parts of the production line can be minimized. The proper balancing between shortterm and longterm performance lookahead capability through efficient evaluative models is one crucial key for seamless integration between FMSs and traditional production systems since the return on investment on an FMS is initially much lower than other forms of automation. This is necessary to avoid creating another costly “automated island”. As applications of FMSs continue to grow, successfully integrating FMSs with other types of production systems become more critical. 1.1.3 Importance of Performance Predictor in Online Controller The continuous improvement and new development of online as well as offline production flow optimization schemes under different planning time horizons for a 8 dynamic system has been a primary focus for many FMS researchers. These schemes are developed using various operations research, mathematical programming, and artificial intelligence (AI) techniques with a wellconstructed evaluative model. There are important distinctions between offline flow and online production flow optimization schemes in typical shop floor control environments. Offline schemes are typically used to perform planning, scheduling and routing functions through periodic interactions with a human supervisor. On the other hand, online schemes are used by automatic control devices such as PLCs to continuously optimize hardware performance and to perform schedule and route changes due to resource failures, rush orders, and major deviations in the original production plans. If the predetermined schedule is carried out as planned, online controllers are required only for the actual implementation of control procedures, such as downloading of CNC programs. In such cases, offline schemes are used at predetermined time intervals and the resulting schedules are implemented. However, a perfect adherence to predefined schedules is almost never realized in practice due to exceptions known as disruptions or unexpected events that cause deviations of the shop floor behavior from the manager’s expectation [Katz and Manivannan 1993]. Katz and Manivannan [1993] acknowledge a great need for architecture to analyze complex patterns of online events caused by possible production disruptions. Online simulation is proposed as one way to obtain information about foreseeable detailed behavior of the manufacturing system within a specified length of9 time in which a control decision has to be made (also known as the control horizon). For online FMS control, devising fast and reliable evaluation models in a disruption handling architecture is crucial because most decisionmaking regarding unexpected online events takes place within a matter of seconds or minutes. Lin and Cochran [1990] state, “For shop floor control in real time, not only long term steadystate performance is important, shortterm dynamic performance of the production line is of even greater interest, since many unexpected events can be vital.” The majority of analytical model developments for FMS operations are based on longterm system behaviors using steadystate analysis. However, in reality most of these systems never reach steady state because of their highly dynamic operational nature [Buzacott and Yao 1986]. For people who operate FMSs on shop floors as a means to meet daily production goals, a comprehensive system model to depict realistic transient behaviors accompanied by possible, but unscheduled, disruptions is more meaningful to make control decision within a small time horizon. 1.1.4 Simulation Modeling versus Metamodeling Simulation modeling is an evaluative technique to study a system of interest. Simulation is normally conducted by a digital computer numerically exercising a model for the inputs in question to see how they affect the output measures of performance [Law and Kelton 1991]. Often, a wellbuilt simulation model provides realistic views of 10 system behaviors of interest. Thus, one can extensively study behaviors of a real world system without modifying an actual system for different baseline characteristics. Although most simulation models are simpler than the real world system they model, it is still a complex way to study systems behaviors because building a valid simulation model takes a considerable amount of expertise, effort, and time. The time and effort to build and validate such models, especially under time pressure, often leads users to switch to other forms of evaluative models, such as analytical models, or to choose a hybrid model that combines analytical and simulation models to avoid lengthy computation time. Metamodeling is a supplementary way to map target system input to corresponding output in simpler manner using simulation experimental design and mathematical techniques like regression analysis or time series analysis. Wellbuilt metamodels often provide the speed of analytical models with the fidelity of a carefully executed simulation study. The usefulness of regressionbased metamodels has been investigated in several studies [Friedman 1989], [Friedman and Pressman 1988], [Kleijnen 1979]. Typical metamodels are approximation formulas that map different combinations of input values to associated output values normally obtained through a full execution of a simulation experimental design. In most cases, nonterminating simulation is used for each run in the experimental design. A terminating simulation is one for that runs for some duration of time, where ETE is a particular event (or set of events) which stops the simulation. On the contrary, nonterminating simulation is one for which there is no 11 particular event E to specify the length of a run. Typically, a performance measure for such a simulation is said to be a steadystate parameter if the output stochastic process of interest exhibits a steadystate (or near steadystate) distribution. L,,21YY Relying on the traditional terminating simulation method to investigate transitional behaviors of a manufacturing system can be expensive and often impractical for real time production control [Lin and Cochran 1990], [Lin and Cochran 1990], [Lin and Chiu 1993], [Lin et al. 1998]. Thus, constructing metamodels using stochastic discrete event simulation and mathematical formulation as an evaluative modeling tool to forecast possible transient behaviors of a complexmanufacturing system under various scenarios has been shown to be a highly effective and practical approach [Lin and Chiu 1993]. 1.1.5 Artificial Neural Network Based Metamodeling vs. Regression Based Metamodeling Approach Artificial neural networks are widely used in many fields as a prominent artificial intelligent tool when rapid computation, adaptability, and robustness are required [Padgett and Roppel 1992]. Typically, neural network applications require fewer assumptions and less accurate data to model unknown functions. Using artificial neural networks as a nonparametric approximation methodology has been shown to be highly effective in the area of metamodeling compared to traditional regression type approaches [Kilmer 1994]. This is especially true, when the system contains a significant amount of the “noise” which is often present in many stochastically transitional systems [Kilmer 12 1994]. The number of different types of artificial neural networks is almost unlimited based on different design architectures and their application areas. Alternative design architectures are discussed more fully in Chapter 3. Regression analysis is the part of statistics that deals with investigation of the relationship between two or more variables related in a nondeterministic fashion. Regression models can be grouped into linear and nonlinear regression models. Nonlinear regression functions can have many different forms. A polynomial regression function is one common possible form. If there is more than one independent variable related to dependent variables, the model is called a multiple regression model. In general, neural networks appear to perform better than ordinary regression techniques in statistical approximation of unknown functions [Kilmer 1994]. The implementation of most regression techniques depends on two critical statistical assumptions about the model errors. These assumptions are: 1. errors must be independent, and 2. errors must be normally distributed with a zero mean and a constant variance [Miller et al. 1990]. Nam and Schaefer [1995] identify three reasons to move away from a traditional regression approach in practical forecasting. First, even though the accuracy of regression models is not significantly compromised when there are small departures from these assumptions, the performance of the model can deteriorate when the assumptions are violated. Such deviations from the assumptions can generally only be detected after the 13 construction of the model. Second, past observations regarding the unknown function often contain complex patterns. Third, there is no way of being certain that the choice of a given regression technique provides the best result. Alternatively, neural networks can learn from experience, move to new generalizations from previous ones, and abstract essential characteristics from somewhat noisy and incomplete inputs [Wasserman 1989]. In addition, neural networks do not require the same assumptions about the underlying distribution, as do many regression techniques. Therefore, artificial neural networks can be an effective alternative to most regression type approaches. Lin and Cochran [1990] utilize time series regression analysis and stochastic simulation in their metamodels to predict transient behaviors of a flow shop system. Since their modeling scheme relies on the modeler’s ability to classify and synthesize various functional elements to make a proper time series model for a given unknown performance function, it is difficult to transform the scheme into an effective automated modeling framework. Based on the pattern of the transitional behavior following a disruption(s), building a prediction model through ad hoc combinations of time series analysis and a linear equation with a particular part arrival or departure rate can be cumbersome. Compared to the traditional regression method, properly configured artificial neural networks can learn and capture any unknown functions with almost no human intervention. It has also been shown that artificial neural networks can effectively approximate behaviors of many nonlinear dynamic systems with a relatively small error 14 [Narendra and Parthasarathy 1990]. Since the development of reliable and easytouse performance prediction tools for a control mechanism is essential for wide acceptance of FMS in industry, constructing metamodels using an efficient artificial neural network design will be a stepping stone to building a truly practical disruption handler in future FMS control environments. 1.2 Problem Statement Thorough understanding of possible dynamic transient behaviors of a typical FMS under preselected disruption scenarios utilizing an artificial neural networks (ANN) based metamodeling framework is the motivation behind this research. The need for this research is based on a proposition made by Buzacott and Yao [1986] who argue that in reality, most FMSs never reach steady state because of their highly dynamic nature. Most rapid analytical evaluative models for FMSs are based on their steadystate performance. This argument supports a need to develop robust, easy to construct, and transportable transientperformance evaluative models for FMSs. Thus, building hybrid type evaluative models (metamodels) using artificial neural networks and stochastic simulations, which can capture realistic but general transient behaviors of an FMS under a set of typical operational scenarios, will help shop floor managers to successfully manage daytoday FMS operations in a tightly integrated manner. The primary objective of this research is to define an artificial neural network 15 (ANN) based metamodeling methodology for FMS transient behavior prediction. The proposed ANN based metamodeling scheme consists of a hierarchical taxonomy of clustered ANNs. Each cluster of ANNs collectively represents a different system knowledge domain. This taxonomically structured arrangement of ANNs overcomes shortcomings often found in single ANN based metamodeling schemes. These shortcomings are generally related to the limited knowledge acquisition capability of these schemes. The advantage of neural network based prediction models lies in their capability to capture not only time based onetoone expected performance but also an overall dynamic behavioral pattern of a particular performance index during a transition caused by a disruption. The proposed ANN based transient performance model is designed to provide better knowledge for an automated disruption handler or FMS operator to discriminatorily react to controllable performance deteriorations. The captured dynamic behavioral pattern of interest may show gradual or sudden shifting of the average performance value over a given time horizon, as well as an expected duration of such behavior. This feature will provide a decisionmaker with the capability of conducting intelligent disruption diagnosis for a discriminatory remedial control action(s) based on unique postdisruption system behavior. This capability will enhance the adaptability of FMSs in a highly dynamic manufacturing environment with a minimal performance disruption by providing shop production control a “lookahead” capability in order to make eventdependent and timely control decisions. 16 Defining an effective modeling framework to intelligently activate corresponding metamodels based on the nature of the disruption event and characteristics of behavioral patterns will be another contribution that makes this study practical in terms of real world application. Identifying and selecting significant operational factors as system input as well as performance indicators as meaningful system output, is done before the actual model construction process starts. Modeling an FMS with a common configuration and testing it under realistic operational scenarios are important tasks. In return, these welldesigned simulation experiments should closely capture common dynamic characteristics for the majority of FMSs that this research intends to represent. This will assure that pursuing an ANN based transient metamodeling approach is a viable alternative to devise a shortterm performance forecasting feature in online disruption handlers for many industries that operate similar types of FMSs in volatile daytoday production environments. Needless to say, designing and conducting verifiable simulation experiments and proper post simulation analysis are essential for the success of this research effort. 1.3 Scope of the Research The goal of this research is to demonstrate that ANN based metamodel consisting of a hierarchical taxonomy of ANNs can be an effective modeling alternative to regression based metamodels to forecast FMS transient behaviors following a random 17 disruption event(s). This research is proposed under the partially verified hypothesis that artificial neural network based metamodels of stochastic simulations generally appear to perform better than regression based counterparts [Kilmer 1994]. In Kilmer’s study [Kilmer 1994], ANN based metamodels are built to approximate an unknown response surface given by a set of alternative input parameters. The procedure, often called response surface methods (RMS) [Box and Wilson 1951], is used to find the levels of the experimental factors that yield the best value of the response (or output) of a system. Such ANN based metamodels deal only with steadystate performance parameters of stochastic discrete event simulations. However, for this research, ANN based metamodels deal with transient performances depicted by nonterminating simulations with imposed resource failures because the focus is on transitional behaviors (deviations from steady state) after the disruption(s). Even though the ultimate use of these ANN based models is for online disruption control, FMS control is not the focus of this research. Therefore, any technical issues regarding the actual FMS control are beyond the scope of this study. This study is intended to develop a new methodology for forecasting shortterm transient performance in a timely manner. In contrast to typical ANN applications in time series modeling trained with actual data points, individual ANNs from the proposed modeling framework will be trained with selected time average resource utilizations and coefficients from selected polynomial regression models found on a limited number of data points generated from18 various simulation experiments. These nonterminating stochastic simulations will be carefully designed and chosen to represent various unique postdisruption behavior patterns. Therefore, independent experimental factors for FMS transient behaviors are carefully identified, screened, and structured for a valid design of experiments. Then a manageable subset is selected for experimentation. Although this study extensively uses simulation, it is not an intention of this study to extensively review traditional issues associated with simulation modeling, validation, verification, and poststatistical analysis processes. Finding justifiable reasons to choose particular artificial neural network design architecture over others is another crucial objective of this research. The choice of possible variations within a particular architecture and training method, for example, the number of nodes, the number of hidden layers, the type of transfer function, selection of training data set, training methods, and the length of training period etc., must be identified. Finally, a taxonomical arrangement of individual neural networks that are designed to capture and approximate various parts of the desired system knowledge domain is to be presented and examined. 1.4 Anticipated Contributions The primary contribution of this research is the conceptualization of a system modeling framework that can provide selforganizing and pattern based transient 19 behavior forecasting. The proposed system modeling framework maps various shortterm transient behavior patterns over the chosen performance indexes by utilizing taxonomically structured ANN based metamodeling. The transient behavior forecasting is based on both the initial reaction path following a disruption and a unique relationship to a corresponding disruption scenario. The majority of ANN based time series modeling approaches presented to date in the literature have focused on a single function realization. However, this study intends to provide a means to store more than one postdisruption system behavior function under various disruption scenarios and make them retrievable by providing a nonparametric relationship between a functional domain and a range of unknown postdisruption system behavior prediction functions. Because the proposed framework will be designed to capture unknown transient behavior prediction functions in a simple form using independent variables, spline modeling, using such techniques as polynomial regression analysis can be useful to extract the unique characteristics of many nonlinear transient behaviors. Secondly, since the proposed approach is aimed toward online application, the practicality of a proposed modeling approach as an online modeling scheme can be partially verified through limited controlled tests. Thirdly, the simulation study of a given FMS model will provide a better understanding of how other tightly coupled systems would react to a disruption under similar circumstances. This will also help to verify if there are signs of any overreactions or underreaction from recovery actions 20 taken by the control system, if not, how closely these reactions will follow a monotonic behavior patterns discussed in some studies [Suri 1985], [Shanthikumar and Yao 1987]. Furthermore, this study provides a chance to closely examine methods and issues involved in quantification of nonmonotonic system behaviors compared to typical monotonic transition behaviors. If there exist any nonmonotonic transient behaviors following a disruption, this study will provide a better knowledge of when these behaviors can be triggered and under which system conditions. Finally, the study will examine the overall effectiveness of the proposed systemmodeling framework as a “look ahead” tool. In other words, the study will examine if an automated system modeling approach such as the one in this study is practical and reliable enough to provide an effective lookahead function for a fully automated production control environment. 1.5 Overview of the Dissertation The remainder of this dissertation is presented in seven chapters plus five appendices and a bibliography. Chapter Two reviews the literature in several major evaluative modeling methods commonly used in both steadystate and transient FMS performance analysis. Topics such as artificial neural networks and time series analysis are discussed extensively in Chapter Three since they are closely related to the proposed 21 modeling methodology. Chapter Three presents the FMS under study and proposed modeling approach. This includes detailed descriptions of the hardware configuration, operational rules, operational scenarios, and system parameters relevant to the hypothetical FMS under study. The rest of Chapter Three is allocated to elaboration of the proposed modeling framework. Chapter Four presents the research goal, objectives, assumptions, and limitations. Chapter Five outlines the research tasks, research methodology, and execution plan. Chapter Six discusses the design of simulation experiments, results analysis, classification of primary transient behavior patterns, configuration of input and target vectors, and configuration of the proposed taxonomically organized ANN modeling scheme for this study. Chapter Seven covers the training and construction of individual ANNs and evaluates the performance of the proposed ANN based metamodeling approach. Chapter Eight summarizes findings, draws conclusions, presents concerning issues, and discusses future research directions and opportunities. 22 2. Literature Review The primary objective of this research is to explore artificial neural networks as a nonparametric and nonregression based technique to build metamodels for time series so that the model can effectively predict shortterm transient behavior of an FMS after a disruption(s). The literature review focuses on several major FMS evaluative modeling methods that are useful for transient performance analysis. These techniques have evolved from major steadystate based evaluative modeling approaches. Therefore, there is a need to briefly review what has been done in the area of FMS performance modeling. This literature review covers not only specific transient performance models but also the steadystate performance models on which these transient performance models are based. Major evaluative modeling approaches in FMS are queuing networks, Markov chain, metamodels, stochastic Petri nets, and simulation. Basic theoretical foundations of these modeling approaches used for both FMSs transient performance analysis and steadystate analysis are briefly discussed. Common modeling assumptions for both steady and transient performance analyses using a particular modeling approach are identified and discussed. Typical of these modeling assumptions are that a model’s theoretical foundation is based on a steadystate Markovian stochastic process, a common underlining probabilistic distribution for arrival and service processes, no resource failure, no blocking, and deterministic part routings. 23 Significant breakthroughs in each modeling approach are reviewed. If there are several variations in a particular modeling approach, they are identified and their merits, compared to the original modeling approaches, are briefly discussed. Finally, the potential for adapting the particular approach for transient analysis is discussed. If there are already established ways to conduct transient analysis through the particular modeling approach, the literature review introduces the concepts and addresses their usefulness and concerning issues. A brief review of major developments in artificial neural networks is provided in Chapter 3 in addition to the proposed design architecture for this research. 2.1 Queueing Network Approaches 2.1.1 Summary of Major Developments Queueing networks (QNs) are the most frequently used analytical form among various FMS evaluative modeling approaches. In general, queueing networks can be formed to study aggregate system behaviors of clustered interactive queues, often “a machine shop” consisting of several departments [Jackson 1957]. Each department is considered a multiserver or singleserver queueing system (or a node within a queueing network) with an exponential service time distribution(s) and a single waiting line. 24 There are two major types of queueing networks based upon whether or not the total number of parts or pallets circulating in the network remains the same at any point in time during a normal operating cycle. The first type is open queueing networks (OQNs), also called Jackson networks [Jackson 1957], do not maintain a fixed number of parts in the network at any given time. The second type of queueing networks, called closed queueing networks (CQNs) [Gorden and Newell 1967], always maintain a constant number of parts. Despite the fact that the majority of analytical evaluative models for FMSs are based on CQN [Buzacott and Yao 1986], both the CQN and the OQN approaches are equally perceived as an effective way to model steadystate performance for various FMSs. For example, Buzacott and Shanthikumar [1980] model an FMS as an OQN where the scope of the model is expanded to include the jobs waiting for release to the FMS in a dispatching area. This study demonstrates the benefits of balanced workload, diversity in job routings with adequate control of job release to the system, and the superiority of common storage over local storage at each machine. Yao and Buzacott [1985] develop an OQN model to evaluate the performance of an FMS with general service times and limited local buffers. The model demonstrates that the arrival process can be formulated in terms of blocking probability on each station using renewal approximation by Whitt [1982]. Since most FMSs with limited local buffers tend to maintain a fixed number of pallets or parts in the system in order to avoid blocking, CQNs were initially perceived as an ideal type of queueing network model to depict behaviors of such FMSs. Formation of a CQN analytic model can result in either a product form solution with a normalization 25 constant or nonproduct form solution for the equilibrium joint distribution of pallets or parts. If the FMS CQN has a small number of nodes (workstations), the product form final solution of the equilibrium joint distribution can be easily estimated through an algebraic approach to finding the normalization constant. Several basic assumptions have to be made in order to have a product form solution. 1. The balance equations of part arrival rate are based on steadystate behaviors of the system. 2. The system consists of interconnected stages of service. The number of parts (or pallets) remains constant throughout the entire operational life cycle. mn 3. The service time distributions on each server are exponentially distributed. 4. The routing can be determined according to a discrete time Markov chain. The advantage of the closed queueing network approach is the ability to approximate the joint probability distribution of parts (or pallets) in the system using a separation of variables technique. When the number of nodes (workstations or cells) in the network (FMS) gets large, finding the normalizing constant, which is essential for finding the equilibrium joint probability of pallets in the system, becomes computationally challenging due to its permutable nature. The technique has been further improved by a computational algorithm to calculate the normalizing constant in a recursive manner [Buzen 1973]. This enables analytic CQN analysis to be a practical approach for a real production environment, especially for complex systems that require prompt decisionmaking. 26 The first successful adaptation of product form CQN in FMS was with a convolution technique, which is called CANQ [Solberg 1977]. This model was initially developed to handle only singleparttype FMSs with a central server (typically a material handling system) that every part must pass through. Later, CANQ was extended by Stecke [1981] to handle multiple part type FMSs. The performance of this analytical model depends on the assumption that the processing times at each firstcomefirstserve (FCFS) station are independent of the part type. If the assumption is satisfied, the convolution algorithm can deliver the exact solution. Otherwise, only an approximation can be made. Additional study done on a similar model suggested that the model would not perform satisfactorily if all the servers use an FCFS queue discipline and nonexponential service time distributions [Chandy and Sauer 1978]. Dallery [1986] has also shown that the product form FMS CQN model with a single part type is not well suited for performance prediction of multipleparttype FMSs with universal pallets and prescribed production ratios. Despite its known limitations, CQNs have been widely used for preliminary design and studying some operational issues in production planning for FMSs because of the speed and accuracy with which they can be evaluated once a model is correctly built. In the area of FMS production planning the CANQ model is extensively used to study the effect of various operational strategies on system throughput. 27 The class of product form CQNs was substantially extended and presented in a unified fashion [Baskett et al. 1975]. This triggered a rapid growth of applying CQN analysis in various FMS analytic models so that CQN analysis grew to handle problems that were initially thought to be unsolvable due to their deviations from the original assumptions. Assumptions such as a single part type and exponential service time distributions are commonly used in Gordon and Newell type network analysis. To overcome limitations of one of these assumptions, CQN with nonexponential service times, an “exponentialization” approach was introduced. This allows a CQN with general service times to be solvable, substituting general service times with equivalent exponential times so that the final product form can be still maintained [Yao and Buzacott 1986]. In practice, QNs with exponential arrival and service time distributions are not robust enough to capture realistic behaviors of various forms of FMSs in which the machine times are often known quite accurately [Pratt 1992]. Most workstations in an FMS, except for those that are failure prone, behave almost in a deterministic manner with very small variance especially when the system is fed with preselected part types, tightly integrated, and controlled by a computer. In some cases, time duration for individual part movements on predetermined part routes as well as processing in individual workstations is highly consistent and has much smaller variation than those with exponential probability distributions. Similarly, modeling failureprone FMSs using QNs with an exponential time assumption, which usually have larger variance than those of exponential systems, can also be misleading. Thus, modeling such FMSs using QN 28 with G/G/c/N queues is a more realistic approach. Yao and Buzacott [1985] model a workstation of an FMS using diffusion approximation (a recursive algorithm) in which the queueing process is formulated as a G/G/c/N queue. They found that a C2/C2/c/N queue and Coxian phases are appropriate for modeling queueing processes that represent workstations of an FMS with interarrival service time distributions having squared coefficients of variation of less than 0.05. Kamath [1989] found that most behaviors of asynchronous automated assembly systems (AASs) do not satisfy the assumption of exponential processing times made by closed form QN analysis and often the analysis can be misleading by such an assumption. These asynchronous automated assembly systems are also known as flexible assembly systems and represent a large and important subset of FMSs. Thus, it is necessary to use a method that can handle general service time distributions at each server for such AAMs [Kamath 1989]. Whitt [1993] studies a deterministic multiclass singleserver OQN and has shown that feedback with classdependent service times, and FIFO discipline can dramatically increase a chance for sudden large fluctuations on the sample paths of the queuewaiting processes with some initial conditions, which is highly conceivable in some FMS models. Suri [1985] has shown that a homogeneous service time (HST) CQN with exponentially distributed service times exhibits monotonicity throughout their performance measures depending only on the number of jobs present in the system. A HST workstation implies that the service time distribution at the workstation remains consistent across different 29 numbers of jobs present in the system. However, the monotonicity property cannot be satisfied unless all service times are exponentially distributed. Therefore, it is less likely for any CQN or OQN with nonexponential service times to exhibit monotonic behavior after a sudden disruption. Yao and Buzacott [1986] use product form CQNs to study the performance of FMSs with unlimited local buffers compared to FMSs with limited local buffers under three possible operational scenarios. Three possible operational scenarios to deal with any blocking are fixed routing, fixed loading, and dynamic routing. They conclude that dynamic routing has clear advantage in increasing throughputs when local buffers have limited capacities. Other studies [Kimemia and Gershwin 1985], [ShalevOren et al. 1985] used nonproduct form CQNs as an evaluative tool to test their new operational policies such as loading/routing and scheduling schemes. Several researchers used a nonproduct form CQN framework to study common behaviors of FMSs under a different set of system constraints or variables such as workstation breakdowns and limited buffers on each node so even blocking can be considered. Other studies extended the scope of QN modeling for FMSs even to those that are traditionally considered FMS supporting systems such as maintenance float networks and control systems. Lin et al.[1994] used CQNs with Buzen’s recursive algorithm to model a maintenance float network problem for FMSs. 30 Based on the approach taken to solve the product form of the equilibrium probability distribution, CQN can be further broken down into several subclasses. According to Seidmann et al. [1987], there are three subclasses for CQN analytic models. These are mean value analysis (MVA), the convolution technique (an extension of Buzen’s [Buzen 1973] recursive algorithm), and approximate mean value analysis (PMVA). CANQ uses the convolution technique. But, most other models are solved by either MVA or approximate MVA depending on whether or not the model will have a final product form as its equilibrium probability distribution of parts or pallets over the network. If the analytic CQN model results in a nonproduct form, the approximate MVA is applied. On the contrary, if a product form solution is found, either the convolution technique or mean value analysis can be applied. Mean value analysis (MVA) is a simplified technique to solve a CQN for a limited set of quantities, such as mean queue sizes, mean waiting times, utilizations, and throughputs, in a recursive manner without calculating normalization constants and product form joint distributions. MVA reduces a significant amount of the computational burden associated with complex CQN problems. In reality, the joint equilibrium distribution often contains far more detail than is needed for practical analysis. As matters of fact, the computational burden of calculating the normalization constants can easily outpace the efficiency of CQN analysis as the system gets more complex. Thus, a simplified way to get the most common performance measures was needed for larger scale product form CQN problems without going through 31 the somewhat tedious computational steps in traditional CQN analysis [Reiser and Lavenberg 1980]. MVA is based on a relationship between the mean waiting time and the mean queue size of a system with one less job. This relationship is also called the arrival theorem. The distribution of the network state seen by a job arriving at any node in the network is the same as the distribution of the network state a random observer would see with () parts circulating in the network. 1−n Several assumptions must be initially made in order to apply MVA to analyze CQN type FMSs. Some of these assumptions are: (a) the processing time of a part at each workstation has an exponential distribution, (b) the routing of parts to the next machine is chosen probabilistically, and (c) all workstations choose their next part according to the FCFS queue discipline. In reality, these assumptions have to be relaxed somewhat because there are many different classes of FMSs in existence based on their configuration and operational characteristics. Three major classes of FMSs are identified based on their modeling constraints such as pallet type, queue discipline, and prescribed production ratios [Dallery 1986]. These classes are monoclass models, multiclass models with fixed queueing disciplines, and multiclass models with prescribed relative throughputs. Viswanadham and Narahari [1992] identify nine common characteristics of automated manufacturing systems that could lead an FMS CQN model to a nonproduct 32 form. These are: (1) nonexponential service time distributions, (2) scheduling discipline other than FCFS, (3) different processing priorities among multiple part types, (4) new production control policies such as a pull system, (5) assembly operations (joining of parts), (6) breakdowns, (7) dynamic routing such as shortest queue routing (SQR), (8) blocking, and (9) multiple resource holding such as a part seizing a fixture, a pallet, a machine, and a set of tools in order to be processed. For example, a nonproduct form solution would result from an FMS where the routing is predetermined and the processing times at some workstations are not exponentially distributed. Another nonproduct form characteristic that is quite common is for each workstation to have a queue discipline other than FCFS. For this reason, Cavaille and Dubois [1982] proposed a heuristic based on MVA, called the approximate MVA method, to model an FMS with near deterministic service times using MVA with an additional approximation term. The FMS model used in the Cavaille and Dubois’s study has FCFS servers where the various part types may require distinct service time and routing requirements. Approximate MVA methods have been extended to handle FMSs with priority scheduling disciplines [ShalevOren et al. 1985]. The first successful computerized MVA application in overall production planning and control problems includes two different decision categories [Hildebrant 1980]. The first category deals with resource decisions and the second category deals with temporal decisions. Resource decisions are concerned with choices among different resources and temporal decisions deal with job sequencing and scheduling issues. This 33 model was subsequently further improved to demonstrate its accuracy and robustness even on larger scale models [Suri and Hildebrant 1984]. Zhuang and Hindi [1990] developed an extended MVA approach that can handle multiple class queueing networks with limited queue capacities to model an FMS with a central material handling system (MHS) and exponential service time distributions including one by the MHS. Zhuang and Hindi also develop an approximate MVA to evaluate an FMS with a single cart MHS, the assumption of exponential service time distribution, and limited local buffers which leads to block and wait mechanisms. Tetzalff [1996] utilizes approximate MVA to evaluate the performance of a tool management system in an FMS. The part transportation system is modeled as a product form CQN and the tool delivery system is model as a nonproduct form CQN. As an indirect way to study transient behavior of FMSs using QN, Chance [1993] studies the relationships among various conjectured upper bounds on transient mean total waiting times in OQNs with some assumptions such as Poisson arrival process, exponential service time distribution, and multiserver queue nodes within the network. He concludes that after some small initial period, transient mean total waiting times in the Jackson network are bounded above by the weighted sum of expected waiting times in queues. The expected network waiting time can be found from simulation and the expected waiting times for queue can be estimated through the program described in Kelton and Law [1985]. These conjectured upper bounds provide the lower bounds on the time required for the transient mean to approach its steadystate value. However, this 34 method can be applied only to OQNs with exponential service times. Also there is a significant drawback that the author acknowledges. The gap between the conjectured upper bound and actual transient mean on total waiting time grows wider as the network gets larger, which implies that the method is not robust enough to be applied on large scale networks. The study done by Suri [1985] supports the position that any OQNs with exponential service time distribution and some specified initial conditions are most likely to behave in a monotonic way during their transient period. Conversely, this implies that there may be a chance for either a CQN or an OQN with nonexponential service time distribution to exhibit nonmonotonic behavior during the transient period after a disruption on its sample paths. Thus, a transient analysis approach by asymptotically connecting individual steadystate values approximated for the particular number of jobs that can be present in the system during the transition period may not always provide a realistic view of true system behavior during a short time window. This issue leaves an open question for further research investigation. 2.1.2 Conclusion Table 1 summarizes the previously discussed major developments in QN analysis of FMSs. Most works are focused on steadystate behavior of the system. 35 Table 1. Major Developments in FMS Performance Study Using QN Analysis Title of Method/ Study Author(s) Year Type of QN (Approx. Method) Limits /Restrictions Type of Analysis Focus of Study/ Findings CANQ Solberg 1977 CQN Single part with a central servers Necessary assumptions for a product form solution SteadyState Analysis To study effects of various operational strategies (production planning) on system throughput Models for understanding FMSs Buzacott, Shanthikumar 1980 OQN Basic OQN assumptions SteadyState Analysis To evaluate FMS with jobs waiting for release in the dispatching area MVA (earlier version of MVAQ) Hildebrant 1980 CQN (MVA) Exponential processing times Probabilistic routings FCFS queue discipline SteadyState Analysis To study production planning and control issues related to failure prone FMSs CANQ (extended) Stecke 1981 CQN Multiple part type Processing times at each FCFS station are independent of Part Type SteadyState Analysis Effect of various operational strategies on system throughput of FMS with multiple part type Heuristic methods based on MVA Cavaille Dubois 1982 CQN (Approximate MVA) FCFS servers various part types require distinct service time and routing requirements SteadyState Analysis To study the performance of FMS with predetermined part routings and nonexponential service times MVAQ Suri, Hildebrant 1984 CQN (MVA) Exponential Service times Probabilistic routings Multiple part type modeled Proven robustness on larger scale models SteadyState Analysis To use MVA for practical planning and control of an FMS The method of Coaxian Phases Yao, Buzacott, 1985 OQN General service times Limited local buffers SteadyState Analysis To evaluate the performance of an FMS with general service times and limited local buffers 36 Table 1 (continued). Major Developments in FMS Performance Study Using QN Analysis Title of Method/ Study Author(s) Year Type of QN (Approx. Method) Limits /Restrictions Type of Analysis Focus of Study/ Findings Diffusion approximation Yao Buzacott 1985 CQN Coefficients of variation of interarrival and service time distributions is less than 0.05 Steadystate Analysis To approximate the behavior of FMS with nonexponential workstations Approximate MVA (extended) ShalevOren, Seidmann, Schweitzer 1985 CQN (Approximate MVA) Similar to Cavaille and Dubois’s approximate MVA assumptions Steadystate Analysis To study impact of priority scheduling discipline Heuristic based approximation of MVA Kimemia, Gershwin 1985 CQN (Approximate MVA) Similar to Cavaille and Dubois’s approximate MVA assumptions Steadystate Analysis To optimize the flow of the operation Exponentialization Yao, Buzacott 1986 CQN Necessary assumptions for a product form solution except general service times Steadystate Analysis To evaluate the performance of FMS with general service times using a product form CQN analysis ON modeling FMSs using CQNs Dallery 1986 CQN(MVA) CQN(Approximate MVA) Necessary assumptions for product form CQN analysis, MVA, and approximate MVA Steadystate Analysis Identified three major classes of QN based FMS models Models of FMSs (with various configurations) with limited local buffers Yao, Buzacott 1986 CQN Various nonexponential service time vs. exponential service time distributions Dynamic routing vs. fixed one Unlimited vs. limited local buffers Steadystate Analysis FMS with small local buffers are robust to various nonexponential processing time distributions MVA (extended) Zhuang, Hindi 1990 CQN (MVA) Limited queue capacity exponential service times A central server (material handling system) multiple part types Steadystate Analysis To extended MVA approach to multiple part type FMS with finite queue capacity Approximate MVA Zhuang, Hindi 1991 CQN (approximate MVA) Exponential service times limited local buffers A single cart MHS (block and wait mechanisms) Steadystate Analysis To study behavior FMS with a single cart MHS 37 Table 1 (continued). Major Developments in FMS Performance Study Using QN Analysis Title of Method/ Study Author(s) Year Type of QN (Approx. Method) Limits /Restrictions Type of Analysis Focus of Study/ Findings Conjectured upper bounds on transient mean total waiting times in QNs Chance 1993 OQN Poisson arrival process Exponential service time multi server queues Size of the network Transient Analysis To find conjectured upper bound on the mean total waiting time in Jackson Networks (applicable to some FMS) A maintenance float network problem Lin, Madu, Kuei 1994 CQN Necessary assumptions for product form CQN analysis Steadystate Analysis To find the optimal capacity of redundant system for a failure prone FMS A QN model for FMSs with tool management Tetzalff 1996 CQN (approximate MVA) Product form CQN requirements for MHS Non product form CQN for the tool delivery system Steadystate Analysis To study the performance of a tool management system in an FMS The QN approach is generally not an effective way to study detailed behavior of the system within a short time horizon. Instead it provides an idealistic picture of longterm behavior if the system reaches steady state. The most critical role of transient study in an online decision making environment is not only to detect any possible disturbances in steadystate performance but also to investigate the detailed nature of the system reactions brought by such disturbances. The detailed nature of such system behavior consists of the duration of a transient state, the magnitude of any reaction, under or over reaction if any, and the value of the new steadystate mean. Using this knowledge the decisionmaker can proactively engage in any remedial action to minimize or prevent the negative impact caused by such a disturbance in steadystate sample paths. 38 Since queueing networks are an aggregated form to represent interactive neighboring queueing systems as a whole, the equilibrium conditions for the entire network must be satisfied in order to directly or indirectly estimate the network performance. Even transient analysis on OQNs such as the one proposed by Chance [1993] to conjecture the upper bounds for the sample paths of total mean waiting time of the network during a transient period, has many limitations as a robust means to facilitate online transient analysis. Therefore, we can conclude that instantaneous transient analysis through ordinary QN analysis is practically infeasible because any exact or approximated behaviors of an individual or aggregated queue(s) using QN analysis can be derived only under the steadystate assumption. However, QN’s speed, reliability, and intuitive details are appealing to many researchers and industry users who are primarily interested in steadystate performance of FMSs. The QN approach can be extensively used during planning and designing stages of an FMS. However, it appears ill suited for online based transient analysis. 39 2.2 Markov Chain Models 2.2.1 Summary of Major developments Markov chain modeling provides fundamental foundations to many analytical evaluative models. Markov models are based on a stochastic process called a Markov process that has a unique mathematical property in which any future state of the system depends on the past state of the system only through the present state. Markov chains can be effectively used to capture stochastic dynamics of many discrete event systems with a finite state space such as manufacturing systems. Despite their wellknown drawbacks as an analytical evaluative modeling tool, such as exponential growth in modeling complexity as the size of the state space (a collection of all possible system states) gets larger, Markov chain analysis can be an appropriate way to study many special cases of FMS operations. Each state in a Markov chain model usually represents a possible discrete state of the stochastic process during its life cycle. Markov chains can be grouped into either discrete time or continuous time processes. Between the two types of Markov chains, Continuous Time Markov chains (CTMC) have been extensively used to analyze dynamic behaviors of many automated manufacturing systems [Viswanadham and Narahari 1992]. For example, studying the overall impact of a certain control mechanism over the entire system and a machine repair system with a redundant resource backup 40 system are popular areas to apply CTMC analysis. CTMCs also provide theoretical grounds for birth and death processes and time reversible Markov chains. Time reversibility is a necessary condition for product form QN analysis. Several foreseeable computational issues in CTMC modeling as the complexity of the problem grows can be identified. These issues are size, ill conditioning, and stiffness. The size issue arises when there is an exponential growth in the size of the state space as the number of available resources increases in the given system. In other words, the computational burden to calculate the coefficient matrix will rise rapidly as the state space gains more possible states. The second issue, ill conditioning, is based on the fact that small changes in the coefficient matrix can lead to large changes in the solution vector. Stiffness is a consequence of having transition rates of significantly different orders of magnitude among states. For example, for a certain CTMC, for particular states the transition rates among them can be significantly higher than the rest of transition rates among other states, which implies faster transitions between those particular states compared to other states. This can create stiffness during the computation. There are two ways, namely uniformization and numerical ordinary differential equation (ODE) solution, to solve these types of differential equations. Reibman and Trivedi [1988] conducted a survey of three numerical methods for transient analysis, uniformization, RKF45, and TRBDF2. They found that two numerical approaches, ODE RKF45 and TRBDF2, work well only for certain types of problems. On the other hand, uniformization works well for typical problems with more accuracy and efficiency. 41 Gross and Miller [1984] extend the randomization technique to Markov processes with infinite state spaces. The randomization technique was originally proposed by Grassmann [1977] and is a general nonnumerical method based technique to compute transient probabilities of Markov processes with finite state spaces through a probabilistic interpretation. Gross and Miller [1984] present an approach called SERT utilizing a generalized randomization procedure in an algorithmic way to model a continuous parameter Markov processes. SERT stands for state space (S), event set (E), rate vectors (R), and target vectors (T) that can collectively describe a general class of Markov processes. Upon successful completion of the randomization, closed form formulas for expected time averages, first passage time distribution, and expected number of events of a certain type occurring for a time interval can be constructed. This approach promises substantial relief from the computational burden associated with traditional transient Markov processes whose state spaces are quite large. The part selection policy for a flexible manufacturing cell is studied to minimize the expected shortage penalty per unit time using a semiMarkovian process [Seidmann and Schweitzer 1984]. For an FMS with block and recirculate, the workstations with finite buffers are modeled as a Markov chain model and solved even though one with a central buffer becomes substantially complicated to model [Viswanadham and Narahari 1992]. 42 Another major achievement in the study of FMS transient behavior by a Markov chain based analytical modeling approach is performability analysis. The notion of performability was first used by Meyer [1980] in the study of a degradable computing system performance. Performability analysis is a combined form of performance and reliability analysis. Performability modeling is used to study the overall impact brought by constituent subsystem failures on a particular system performance index over a finite time horizon. Performability analysis was originally designed to investigate performancerelated reliability for faulttolerant computing systems. Later the same technique was applied to automated manufacturing systems (AMSs). Even though the majority of performability studies use continuous time Markov chains with the deterministic reward structure consisting of a number of transient states and a single absorbing state, discrete time Markov chains with random rewards were later introduced [Mallubhatla and Pattipati 1994]. The notion of a Markov reward often implies the cost or reward incurred from being in a particular state at a given time. The first application of performability modeling in manufacturing systems appears in a work by Viswanadham et al. [1991]. This modeling was focused on AMSs producing a single part type. A subsequent study [Viswanadham et al. 1993] was done on AMSs producing multiple part types using continuous time Markov reward models. 43 Most automated manufacturing systems consist of numerous constituent subsystems. In reality, even the most reliable and welldesigned AMSs are subject to unscheduled and unexpected subsystem failures due to many complex mechanical interactions and functional dependencies. Especially for an FMS, a proper functioning of individual resources within the system is highly critical to its operational success because the role of each resource is often uniquely defined and tightly integrated with others to complete any planned operations. Even if the frequency of these failures is very low, most of these AMSs are built with a certain degree of redundancy so that highly expensive systems like FMSs will not be sitting idle in case of any unscheduled subsystem failures. We call these types of manufacturing systems faulttolerant systems. They are built with a certain degree of flexibility in both operation and capacity to handle limited multiple resource failures simultaneously. Due to natural time scale differences in frequencies of failure, repairs, and reconfigurations and of the part processing events, a performability model is often hierarchically devised: a higher level (longertime scale) dependability model and a set of lower level (shortertime scale) performance models. The study done by Viswanandham et al. [1995] shows that the accumulated reward over a given time interval is a solution of a set of forward or adjoint multidimensional linear hyperbolic partial differential equations. They also proposed efficient numerical methods for computing the distribution of the cumulative operational time, and the mean and variance of the cumulative production over a given time interval. One of the common difficulties in this 44 approach lies in efficient numerical methods to solve the partial differential equations in order to find the distribution of accumulated production over. ] ,0[t After occurrences of these resource failures, the system often goes through a series of possible intermediate transient states during the recovery process. The complex dynamics of the state transitions can be captured via the structure state process (SSP). The SSP is to describe the system evolution as influenced only by failures, repairs, and reconfigurations. In each structure state, the system can be associated with a different performance measure such as lead time, throughput, and work in process. The formal definitions of a structure state process and performability can be given as follows. Definition: Let be the structure state of the manufacturing system at time . Then the family of random variables )(uZ0≥u{}0),(≥uuZ having state space is called the structure state process. {mS,,2,1,0K= } If we let be rewards in the individual structure states and be a random variable over an observed period mfff,,,10K)(sYt[]t,0 with initial structure state given as Ss∈, the performability can be given as imiitfsYτΣ==0)( where iτis the total sojourn time of the SSP during []t,0 in state i. 45 The SSP can be modeled using CTMC, queueing networks, or stochastic Petri Nets. Viswanadham and Ram [1994] use both CTMC and Pertri nets to model performability of a flexible manufacturing cell (FMC) and suggest techniques for computing statistical moments of certain cumulative performance measures. Three measures: performability distribution, steadystate performability, and interval performability, are focuses of interest in performability analysis. The structure state of the SSP is a vector whose components describe the status of its constituent subsystems. The SSP is a collection of all possible structure states in which the sequence of transitions among allpossible states can be logically captured to reflect the evolution of the system during a given time horizon. Any failure prone AMS can go through a series of individual structure states within a given length of time following a resource failure. This combines both the performance and the reliability aspects of the system. Typically a part of the vector representation of the components in each state contains the total number of available machines at any point during a given time period. The current structure state changes due to failures and repairs as time progresses. A wellillustrated SSP model for a degradable (nonrepairable) faulttolerant FMS with a central server and identical machines is provided by Viswanadham and Narahari [1992]. m Gershwin’s study [Gershwin 1992] argues that the estimation of variability of production is an important measure of interest to the manufacturer. Furthermore, his study shows that the coefficient of variation of production in an actual AMS can exceed 0.1, which is considered unacceptable since high variability can cause over and under 46 production by creating either unnecessary inventory or material shortage. Therefore, finding higher statistical moments for the performability distribution is highly critical. The performability distribution is a cumulative distribution function of the performability , i.e., )(sYt{}xsYPt≤)( for Rx∈. The performability distribution and its statistical moments are used to quantify the performance and reliability of the system. A closed form expression for the performability distribution and its moments and recursive formulas to compute the moments for an nprocess system are found using a sum of simple exponential terms and double LaplaceStieltjes transformations by Donatiello and Iyer [1987]. Typically when a system with nonhomogeneous components (e.g., different types of machines) is modeled using a Markov process, the number of states in the system is the product of the number of different type components. Hence the total number of structure states can be very large. Finding statistical moments for the performability distribution is a useful way to approximate the distribution especially when the time complexity for computing the coefficients of the distribution becomes too expensive as the number of structure states grows. The same framework to find an analytical solution for the distribution of performability can be applicable to nonrepairable systems as long as the transitions between states are modeled by an acyclic Markov chain. n47 A similar but improved modeling approach was proposed by Rupe and Kuo [2003] in order to lessen the complexity of the traditional performability model by separately modeling independent failure and repair processes of each system and combining the results at the conclusion. This approach is designed to provide an efficient general architecture to be applied to a wide variety of FMS configurations including spare part inventory to repair down machines. Despite their promising findings, the complexity of the model can still grow significantly if each machine type has different failure and repair processes. 2.2.2 Conclusion Markov chain models are based on either Markov or semiMarkov processes that are the two most important subclasses of stochastic processes. Markov processes provide underlying theoretical foundations for many queueing theory based analytical modeling approaches. Significant contributions in FMS transient analysis are made by Viswanadham et al. [1991], Viswanadham [1992], Viswanadham and Ram [1994], Gross and Miller [1984]. In general, Markov chain models are intuitive and easy to understand. However, there are a few major drawbacks as Narahari and Viswanadham [1989] point out. These drawbacks are: (1) when the size of the physical system grows, the number of states in the Markov chain grows exponentially and this makes Markov analysis computationally 48 expensive; (2) as the number and complexity of interactions increases, visualizing the Markov chain states and the transitions among states becomes difficult; (3) the existence of two or more time scales can cause tremendous computational difficulties. Solving ChapmanKolmogorov equations that correspond to first order linear differential equations with constant coefficients, provides closed form solutions to approximate individual transition probabilities or the state probabilities as functions of time. There are basically two ways to find the solution for these first order differential equations. The first method is a numerical method based technique and the second one is nonnumerical method based technique. With either technique, finding closed form solutions can become problematic as the size of the state space grows. Also, building a Markov chain model using a predefined state space, which often focuses on one aspect of the system performance, still requires intuitive and creative modeling efforts. Shifting focus from one to the other or changing configuration of the system often requires redefining of the state space which can result in rebuilding the entire model. This process requires a significant amount of human modeler’s analytical skills and modeling expertise. Hence, this cannot be easily transportable to a fully automated system with a noninteractive modeling environment. Unless the system configuration never changes, in other words, the state space (dynamics of the model) remain unchanged and only the associated transition probabilities (performance parameters) change, reconfiguration of model on the fly will be challenging for online transient analysis. Therefore, it can be concluded that constructing Markov chains is not a practical 49 approach to building a rapidly reconfigurable online evaluative model focusing on transient behavior of a dynamic system. 2.3 Simulation Modeling 2.3.1 Summary of Major Developments During the past several decades, computer simulation has been an indispensable tool for many system engineers to numerically study the behavior of complex discrete and nondiscrete (continuous) event systems. Since many improvements have been made in simulation technology, such as improved usability, modeling power, and speed, simulation analysis has received greater attention as an effective modeling tool. Despite the availability of many effective system modeling methods, simulation modeling frequently becomes a favorable choice over other evaluative tools because it gives invaluable understanding of how the system operates as opposed to how everybody thinks it does [Pegden et al.1990]. In general, simulation should be used whenever detailed results are needed such as in a transient behavior study. The price to be paid for being detailed is that simulation takes a relatively longer time to develop, usually requires more input data than other analytical evaluative modeling approaches and often requires a great deal of computation time [Suri and Hildebrant 1984]. In addition, a steadystate analysis of a system by the 50 simulation modeling approach requires a statistically valid output analysis to find true steadystate means if there exists a significant initial bias on its outputs due to the model’s startup conditions, often called a warmup period. Because of this time consuming modeling process and cumbersome output analysis, the simulation modeling approach has shown only limited application in online decision making schemes such as online production control systems. Nevertheless, a great deal of research and efforts have been put into the area of online simulation as a viable approach to predict the shortterm system behavior for untested operational scenarios in typical manufacturing control environments. Especially with the current pace of progress in parallel and distributed computation, processing speed of inexpensive CPUs, and various model simplification techniques, simulation modeling to study detailed behavior of a system within a given time window has a promising future as a practical online based system modeling approach. Traditionally, simulation modeling has been extensively used in design, planning, scheduling, and control of FMSs. These studies typically seek the optimal configuration for a hypothetical system or the best operational policy for an existing system. The modeling oriented languages, such as GPSS/H, SLAM II, SIMAN, SIMSCRIPT, and ARENA, etc., have been favored over general programming languages by many simulation practitioners. Most of these modeling oriented languages possess realistic abstraction capability for individual behavior and interactions among various modeling entities, automatic statistic collection features, extensive runtime error detection, many 51 builtin sophisticated event handling mechanisms, and powerful addin animation features. However, there is some modeling inefficiency associated with these general purpose simulation languages to model complex manufacturing systems like FMSs because they are designed to model a wide variety of discrete event systems as well as manufacturing systems using generic building blocks. As Rolston [1985] points out, modeling FMSs with a general purpose simulation language often requires highly trained programming skills to conceptualize the entire system in terms of entities, queues, servers, and resources. For this reason, dedicated simulation languages for various manufacturing systems were developed, such as MAP/1 [Rolston 1985], GPSS/H [Schriber 1985], XCELL+ [Conway et al. 1987], WITNESS [Gilman and Billingham 1989], and MAST [Lenz 1989]. Fixtures, conditional part routing, and conveyers often require special modeling elements to capture their unique behaviors. For example, a conveyor belt is a material handing system but often acts as a finite storage buffer. Also, based on the way of the conveyer belt is used in the system, securing consecutive spaces on the conveyor belt is crucial for undisrupted traffic of a particular group of parts. MAP/1 is a simulation language that has been developed to capture such unique behaviors of FMSs [Rolston 1985]. Similarly, a GPSS/H model is proposed to represent a hypothetical FMS using a modular design approach to explore the concept of a universally applicable simulation model with minimal modifications possible for various FMSs [Schriber 1985]. For the GPSS/H model, some simplifying assumptions have to be made. These assumptions are 52 no machine breakdowns, negligible part travel time between any two points in the system, and no traffic congestion. Because of the complexity of most simulation models, a formal scheme to convey the underlying logic of the system using common words is needed. An activity cycle diagram is a graphical presentation to describe the underlying logic of a discrete event system that can be easily understood by nonexperts. Despite this effective formalism to depict the dynamics of a complex manufacturing system such as an FMS, the influence of a particular simulation language used to construct the models based on the activity cycle diagram can be found. Hlupic and Paul [1994] build a conceptual FMS simulation model using activity cycles diagrams to conduct a comparative study to show the apparent influence of the simulation package used for the model construction. There are two ways for simulation to be used in production control and planning environment: the first is online based simulation analysis and the second is offline based. Most simulation modeling efforts in FMS operation management have concentrated on offline steadystate analysis. Simulation modeling has been extensively used as an evaluation tool to test whether a suggested dispatching rule or schedule really works better than other alternatives. The schedule or dispatching rule in an FMS normally determines which parts are introduced into the system at what time and which part to load next into a particular machine. Comprehensive literature reviews on FMS scheduling using offline simulation as an evaluative tool can be found in [Gupta et al. 1989; Hutchison 1991; Basnet and Mize 1994]. 53 The other prominent application area for offline based simulation study is FMS design. Abdin and Mohamed [1986] conduct a simulation study to examine FMS design issues regarding the maximum number of pallets for each part type and the optimal conveyor speed under two distinctive job sequencing rules, namely the LPT and PROB rules. LPT gives the job with longest processing time the highest priority while the PROB rule orders work pieces according to their highest content in the workinprocess. The study concludes that for that particular cell configuration LPT is favorable over PROB and allocating four pallets of each part type can ensure a smooth production against various changes. A significant number of recent research efforts using simulation applications in FMS production planning and control have shifted their focuses to online and realtime applications. M. Kim and Y. Kim [1994] propose simulationbased realtime scheduling for an FMS. In this study, they argue that the dynamic and uncertain nature of system states may make offline scheduling impractical for most FMSs. In general, FMSs are more sensitive to system disruptions than conventional manufacturing systems because of their tighter synchronization, system integration, and interdependencies among many automated system components. Hence, FMSs require an immediate response to changes in their system states, and this can be achieved through implementing online scheduling and control.54 Harmonosky [1993] addresses two key issues, the simulation run length issue and lookahead horizon assumptions, for using simulation for realtime production control. In this study, Harmonosky identifies the types of manufacturing systems suited to pursuing simulation as a realtime control aid: systems with longer average processing time, WIP performance measures, and high flow shop characteristics are believed to take smaller CPU time and fall into this category. The biggest obstacle for simulation to become a practical online evaluative tool in realtime decision making environments has been its lengthy execution time. In addition to a rapid improvement in the speed of inexpensive CPUs, there have been many ongoing research efforts to make simulation experimentation a more practical methodology for online use. In order to shorten the lengthy execution time of simulation without compromising statistical precision, the majority of online steadystate simulation analysis schemes have adopted a form of executiontime reduction techniques, such as concurrent simulation, distributed simulation, model simplification, and the reverse simulation method. Each of these are discussed more fully below. A concurrent simulation means that a separate, independent processor is dedicated to running a simulation under each set of input parameters. Concurrent simulation is proposed as a primary analysis tool to evaluate candidate schedules in online production control environment. It utilizes parallel computing techniques to mathematically decomposing a scheduling problem into a parallel hierarchy [Davis and Jones 1988]. The success of this conceptual scheduling algorithm lies in the integration and development of key technologies, such as compromise analysis, conflict resolution, and efficiency of 55 concurrent simulation techniques. Also, the authors acknowledge that the optimality of the found schedule cannot be guaranteed and the probability of exact implementation of the suggested schedule is close to zero due to the tradeoff between a guarantee of feasibility and operational efficiency. Different from concurrent simulation, distributed simulation uses a technique to partition a single simulation run into several independently executable small components (routines) using parallel computation techniques. Distributed simulation focuses more on a distributed simulation algorithm (software) using parallel computation techniques rather than employing multiple processors (hardware) to host multiple simulation runs. In other words, a sound simulation model of concurrency is more important than the multiprocessor hardware itself. Traditional discrete event simulation is designed to be executed by a single processor sequentially following an event calendar as the single stepping clock advances. On the contrary, for distributed simulation each simulation component is run concurrently and brought together to collectively present the overall behavior of the system. A distributed simulation system must explicitly coordinate the advance of time in order to maintain temporal consistency among its components. There are two distinct tasks to maintain time among distributed simulation components: the movement of time and the coordination of time movement. Based on methods to coordinate time advances between concurrent simulation components, distributed simulation algorithms can be classified into two classes. 56 The first class is ChandyMisra (CM) simulation, also called pessimistic simulation [Peacock et al. 1979; Chandy and Misra 1981]. The mechanism holds back processing because it assumes that components will communicate out of sequence. The CM algorithm does not prevent simulationinduced deadlock. Thus, CM works best in tightly coupled simulations where objects are highly synchronous. The second class is Time Warp (TW) simulation, sometimes referred to as optimistic simulation [Jefferson 1985; Jefferson and Sowizral 1985]. It relies on the ability of an object to rollback its present state to that of some previous time. Time Warp is good for loosely coupled, highly asynchronous systems but is inefficient when models have mixed time scales or diverse interaction behaviors. McAffer [1990] proposes the Unified Distributed Simulation (USD) algorithm as a compromising approach. This approach is loosely based on the Time Warp algorithm. By explicitly defining risk and aggressiveness parameters for each model, simulation models with different behaviors can be mixed within one simulation. Prassad and Deo [1991] propose a parallel algorithm for discrete event simulation on exclusiveread exclusivewrite parallel randomaccess machines (EREW PRAM). The proposed algorithm uses a parallel data structure as an event queue, called a parallel heap, which allows simultaneous insertions and deletions of messages maintaining priorities among messages in a reasonably small amount of time using multiple processors. Another way to use simulation for real time scheduling, control, and monitoring was proposed by Harmonosky [1990]. Instead of adopting a concurrent simulation 57 approach, she suggests interfacing simulation with the physical system to run two separate modes. Figure 1 depicts the structure for such an approach. The first mode is a monitoring mode. It is used when the model is directly linked to the physical system, continuously receiving status information from various system elements. The second mode is a decisionmaking mode and is used when the model evaluates different control decision options through traditional offline runs. The issues regarding this approach are how to balance the tradeoff between a long enough time horizon to obtain statistically valid results and a shorter response time required to make prompt decisions. A similar approach interfacing a SIMAN based simulation model to a realtime control database is proposed to evaluate work order release sequences based on measure of performance by Muller et al. [1990]. Unlike most simulation studies, the evaluation is based on the transient behavior of the system and not steadystate performance. The control system looks at the time window in which the work order is predicted to be completed in order to determine if a particular work order sequence meets due date requirements set in advance by the MRP system. Ten replications are made to construct the confidence intervals (CI) on the completion time for a work order in order to be compared with actual data. Surprisingly, results indicate that only 43.6% of actual completion times occur within these estimated CI. The authors attribute the occurrences of work orders outside the confidence interval mainly to the uncertainty at the finishing cell. 58 System Control ComputerSystem StatusDecisionNeeded?Update simulation w/Current System StatusSpecify OptionsSimulate OptionsAnalyze & SelectOptionYesNoOption 1Option 2Option n...Option 1Option 2...Option nSelected Option Figure 1. Scenario for Interfacing Simulation with Physical System for Realtime Control [Harmonosky 1990] Even though the study done by Sims [1997] does not directly discuss the application of realtime simulation, he argues that, for any scheduling problem with a shortterm goal, running simplified simulation models with deterministic values would provide a realistic view and a faster response. Reverse simulation is used when the desirable range of values of the performance measure are known and used as inputs to the model so that the steadystate mean for the performance measure can be reached at a faster rate with fewer samplings. Lee et al. [1997] propose a single run optimization method to take advantage of the reduced execution time using the reverse simulation technique and chaos theory. 59 As discussed in Chapter 1, simulation can be classified into two categories: terminating and nonterminating. Nonterminating simulations are sometimes called steadystate simulations. Terminating simulations are run only until some stopping criterion is met. The stopping criterion is normally set as a system event that is designed to end the simulation run based on the nature of system or the purpose of analysis. On the contrary, nonterminating simulations can conceptually run indefinitely after they reach a steadystate or stationary pattern of behavior. With use of a proper warmup period deletion technique, most nonterminating simulations can be stopped at the point where there are sufficient observations for statistical accuracy and the least significant amount of influence from the truncated initial bias, often called the warm up condition. Most simulation languages have some form of builtin statistical output analyzers. These builtin statistical output analyzers are often inaccurate and misleading because they tend to ignore common startup problems and autocorrelation among observations [Seila 1990]. A simulation experiment without a valid statistical output analysis is meaningless. There are clearly two different classes of output analysis that can be applied to find statistical means based on whether the simulation is terminating or nonterminating. Different types of output analysis are covered in detail in several works [Seila 1990; Law and Kelton 1991; Banks et al. 1996]. Typically, a steadystate simulation with particular input parameters can be carried out by a single but reasonably lengthy replication with an output analysis using a technique like the batch means method. These techniques find statistically valid steady60 state means from a stochastic process that represents a particular performance measure. On the other hand, the run length in a terminating simulation is dictated by the terminating event or condition and this event or condition often limits the number of observations that can be collected from a single replication for the statistical output analysis. For a statistically valid output analysis one cannot depend on a highly autocorrelated sequence of a limited number of observations from a single run. Therefore, repeating a single run a total ofRtimes is required for terminating simulation to have observations in each replication rnr so that it can have statistically independent and identically distributed Rsample means. Terminating simulation can be effectively used as a lookahead performance evaluator in an online production control environment. The chronologically captured behavior of a particular performance measure from a terminating simulation during the transition period following an unexpected disruption may provide realistic and meaningful information to online based decision making for automated disruption handling. Such attempts can be accomplished by adopting a hybrid modeling approach, often called metamodeling. Metamodeling maps simulation output to a corresponding mathematical model using techniques such as regression or time series analysis. Lin and Cochran [Lin and Cochran 1990; Lin and Cochran 1990; Lin et al. 1998] proposed a metamodeling approach using terminating simulation. They argue that relying on the traditional terminating simulation method to investigate transitional behaviors of a manufacturing system can be expensive and impractical for real time production control. 61 2.3.2 Conclusion Many researchers and systems engineers studying the detailed behavior of complex systems such as FMSs have favored discrete event simulation as their preferred modeling tool. However, its limitations as an evaluative modeling tool, such as lengthy model development time, detailed input data requirement, lengthy simulation execution time, and necessary but cumbersome statistical output analysis procedures have kept simulation from becoming a practical analysis tool for online decision making. Recent improvements in simulation usability, modeling power, and speed have started receiving increased attention from both the research community and industry. In addition to these improvements, there have been considerable ongoing research efforts to make a simulation run faster and shorter using techniques such as distributed simulation, concurrent simulation, model simplification, and reverse simulation. There are clear differences between terminating simulation and nonterminating (steady state) simulation analyses. Nonterminating simulation is often useful to predict shortterm effects of disruption(s) on a particular system behavior. The majority of simulation modeling approaches proposed and explored so far within a framework of online decisionmaking, including online production control systems, have focused only on steadystate simulation. Even for a dynamic production environment, such attempts tend to focus only on the newly shifted steadystate mean after the disruption rather than intermediate transitional behaviors. 62 Using terminating simulation in a traditional way is very costly and impractical as a part of an online production control system such as a disruption handler. Applying a hybrid method such as metamodeling proposed by Lin [1990] combining terminating simulation and mathematical modeling is one way to effectively apply terminating simulation in such an online decision making support system. The drawback of such approach is the difficulty encountered as an online based noninteractive model constructor to choose the right time series model to represent dynamic characteristics and the complexity of the system’s possible volatile behavior following the disruption. This can become a critical issue especially when a composite model, a linear combination of several mathematical models, has to be built. Thus, in order to effectively use Lin’s approach for the fully automated and selfcontained FMS online controller there is a need to adopt a nonparametric method to build the model, such as applying effective neural network architecture. 63 2.4 Stochastic Petri Nets 2.4.1 Summary of Major Developments This study presents a brief history of Petri net based approaches in systems modeling and focuses on their applications in FMS transient and steadystate performance analysis. First, we need to look at some elementary definitions in classical Petri nets and other subclasses such as Stochastic Petri nets (SPNs) before discussing major developments in this area. Petri nets (PNs), also known as placetransition nets (PTNs), were proposed to graphically model discrete event dynamic systems by Carl Adam Petri [1962]. Petri nets were designed to model systems with deterministic behaviors. Classical Petri nets are useful for investigating qualitative or logical properties of concurrent systems, such as mutual exclusion and presence or absence of deadlocks. Recently, PNs have emerged as a powerful performance modeling tool by incorporating stochastic time functions for analyzing asynchronous concurrent systems that exhibit nondeterministic behaviors. As Kamath and Viswanadham [1986] point out, Petri nets have some noticeable advantages over other system modeling approaches. These advantages are: (1) easy visualization of complex systems using a powerful graphical presentation scheme, (2) modeling capability for hierarchical decompositions, (3) relatively welldeveloped analysis techniques, (4) wellformulated schemes for system design and synthesis, and (5) dual 64 analysis capability for both quantitative (performance evaluation) and qualitative (deadlock detection) characteristics using timed Petri nets. Formally, a Petri net is a bipartie graph (a graph with two types of nodes) and can be presented by three types of objects, namely places, transitions, and directed arcs connecting places to transitions and transitions to places. Pictorially, places are depicted as circles, transitions are depicted as boxes or bars. A place is an input place if there exists a directed arc connecting the place to a transition. A place is an output place if there exists a directed arc connecting a transition to the place. Typically, places represent preconditions or postconditions and transitions represent events. The presence of a token (a black dot) inside a place often indicates that the condition is satisfied. For example, input places may represent the availability of particular resources, transitions represent their use, output places represent release of the resources. Over the years Petri nets have been enhanced to improve their somewhat limited initial modeling capability. For example, to overcome shortcoming of being unmanageably large and complex in modeling of a concurrent system using a placetransition net (PTN), colored Petri nets (CPNs) are introduced to maintain a manageable size of the net [Jensen 1981]. Representation of an equivalent model of a traditionally large and complex system using CPN is simpler and more concise in comparison to using a traditional PTN. In addition, CPNs are capable of capturing complex functional dependencies between the color of transition firing and colors of required tokens. 65 By changing the placement of tokens on possible subsets of places, which may reflect the occurrence of events or execution of operations, one can capture and investigate dynamic behavior of the modeled system. The flow of tokens is governed by both enabling rules and firing rules. There are several key structural properties that can be exhibited by a certain class of Petri nets. These structural properties for Petri nets are: pure, boundedness, safe, live, dead, deadlock, mutual exclusion, reversibility, home state, concurrency, conflict, asynchronous, nondeterminism, instantaneous, and union of Petri nets. The detailed definitions for such properties can be found in various articles [Peterson 1977; Agerwala 1979; Kamath and Viswanadham 1986; Zurawski and Zhou 1994]. Among these properties, pureness, boundness, and liveness are necessary properties to capture important qualitative characteristic such as presence of deadlock in a Petri net model of any asynchronous concurrent system. To conduct quantitative performance evaluation for a system during time evolution, the concept of time has been added to the definition of Petri nets. There are two ways to introduce the time elements to a Petri net: the first one is to attach time to transitions [Ramchandani 1973; Ramamoorthy and Ho 1980; Zuberek 1980; Molloy 1982]; second one is to associate time with places [Sifakis 1977; Bruno and Biglia 1985]. The choice of associating time with transitions is more popular in the literature than associating time with places [Viswanadham and Narahari 1992]. Petri nets with time functions are called timed Petri nets. There are two types of timed Petri nets based on the 66 nature of the time function: one is deterministic timed Petri nets; and the other is stochastic timed Petri nets. Early work related to timed Petri nets is mostly confined to deterministic timed Petri nets [Ramchandani 1973; Sifakis 1977]. Later, the concept has been expanded to include random time duration [Natkin 1980; Molloy 1981]. We call Petri nets with random time delay for their transitions Stochastic Petri nets (SPNs). When random variables representing time delay are of general distribution rather than exponential, the resulting net model can not be solved analytically as we have seen in similar queueing network models with nonexponential service times. Thus, simulation or approximation methods are required to analyze the model. However, when the time delay for each transition is assumed to be stochastic and exponential, the resulting net can be analytically solved. These Petri nets are called exponential timed Petri nets (ETPNs) [Viswanadham and Narahari 1992]. When ETPN models allow for immediate (zero time delay) transitions, we call these SPNs generalized SPNs (GSPNs). Studies individually done by Natkin [1980] and Molloy [1981] have shown that the marking process of an exponential (or geometric) timed Petri net is a continuous time Markov chain (CTMC). Thus, both ETPN and GSPN models, including extensions such as priority transitions, inhibitor arcs, and probabilistic arcs can be directly converted into their equivalent continuous time Markov chain (CTMC) models, and analyzed using a Markovian analysis method. As we discussed earlier in Section 2.2 Makov Chain Models, the CTMC modeling approach has its own inherent shortcomings as an effective onlinebased transient 67 performance analysis tool in addition to drawbacks typically associated with Markov chain models. These shortcomings are associated with solving Kolmogorov backward or forward differential equations in the form of first order linear differential equations to find a closed form solution to approximate individual transition probabilities or state probabilities as a function of time. As Molloy mentions [Molloy 1985], for quantitative analysis of system performance, stochastic Petri nets do not provide more modeling power than Markov chains, but they provide a better human interface. By using a GSPN representation on appropriate discrete event dynamic systems, Markov chains may be generated and solved automatically. The clear advantage of using GSPN over Markov chains lies in enabling the system designer to specify the system operation in a concise form that can be verified during the generation of the reachable tree. In comparison to product form queueing networks, GSPNs are more powerful because they can represent nonproduct form features [Narahari and Viswanadham 1989]. Despite its continuous expansion and enhancement in modeling capability and flexibility, the abstraction power of ordinary Petri nets is not sufficient to capture many complex industrial systems, such as manufacturing and communication systems which require the flow of different resources or messages within the system. One way to model such systems is to construct a model in such a way that the flow of each resource or message is confined within a dedicated subnet. In largescale 68 systems, a number of resources or messages often share the same system that can be modeled as a single subnet. When this subnet is duplicated to model the entire system for different resources and messages, the overall model that may contain multiple replications of the same subnet may result in unmanageable graphical complexity. To resolve this issue, several methods for tokens to have distinct identity are proposed and they are often referred to as highlevel Petri nets. In highlevel Petri nets, a token can be a compound object carrying data in forms of integers, reals, text strings, records, lists and tuples. Highlevel Petri nets typically include predicatetransition nets [Genrich and Lautenbach 1991], colored nets [Jensen 1981], objectoriented nets, and nets with individual tokens [Reisig 1983]. Colored Petri nets (CPNs) were introduced to represent a complex system in a compact and manageable manner by maintaining distinct token identity through associating different colors [Jensen 1981]. In CPNs, a set of colors is associated with each place and each transition. The set of colors associated with a place indicates the color of tokens that can be placed at the place. Similarly a transition can fire based on each of its assigned colors. When a transition is fired, corresponding colored tokens are removed and added at its appropriate input and output places respectively according to the functional dependency specified between the color of the transition firing and the colors of the involved tokens. Petri nets have gained popularity as a versatile modeling and analysis tool for addressing design issues related to FMSs [Silva and Valette 1990; Zhou 1995]. 69 Typically, most ordinary PTN models have been used in the area of control system design, validation, and implementation. However, as Kamath and Viswanadham [1986] point out, the number of related studies in FMS performance modeling using Petri nets has been somewhat limited due to the limited availability of proper performance evaluation techniques for various PTN classes. A predominant number of FMS performance modeling attempts using Petri nets are based on Stochastic Petri nets with Markov chain analysis. Since bounded SPN models with exponentially distributed transition rates are isomorphic to Markov process models with a state space consisting of possible markings, a direct conversion to an equivalent Markov model can be easily achieved if the model is not too complex. Moreover, analytically evaluating equivalent Markov chain models is not a computationally difficult task as long as the level of complexity is kept minimal. As previously discussed, studying transient behavior of the given Markov chain requires finding equilibrium distributions in terms of time . To find these distributions, solving ChapmanKolmogorov equations in the form of first order differential equations either in a backward or forward form is necessary. The complexity of solving these equations can vary based on the different types of mathematical techniques that are applied. kt A simple SPN can also be easily converted to a simulation model as a nonanalytical form of performance evaluation. A transition state analysis by simulation is a more feasible approach to understand quantitative behaviors of the net than Markov chain analysis especially when the complexity of the given net is no longer considered 70 moderate. For FMS performance modeling using PTNs, converting PTNs to valid simulation models is a better approach for online production control. However, technical difficulties in conducting a reliable and fast online simulation study can still be problematic as discussed in the previous section. The majority of PTN modeling in FMS performance evaluation is based on the steadystate behavior of the given FMS. An initial investigation of applications of timed PTNs in FMS realtime control and performance evaluation can be found in the work by Dubois and Stecke [1983]. The study has concluded that timed PTN is a useful means to assess the steadystate performance as well as to detect any sequence of events which can result in deadlock in FMS realtime control. However, in reality ordinary SPN models for FMSs can become highly complex due to the fact that most control logic or operational sequences in many FMSs consists of resources that have a high degree of interaction. This type of systems is viewed as a system composed of many replications of a few basic common components. In most cases, these common components behave in a similar manner. Different arrangements of these basic components can represent various system conditions (status) and subsequent events for the given FMS. Utilizing Colored Petri nets in conjunction with SPNs is proposed as a powerful tool to verify the control logic through investigating the presence of deadlock in an FMS [Kamath and Viswanadham 1986]. Kamath and Viswanadham [1986] have shown the feasibility of direct 71 transformation of CPNs to effective simulation models. Aside from the traditional linear algebraic methods, the fast and efficient way to compute invariants of a PTN model for an FMS is found by taking the union of invariants of smaller and simpler underlying PTNs [Narahari and Viswanadham 1984]. Another study [Micovsky et al. 1990] has demonstrated that a CPN approach to validate a deadlock free design for an FMS control system utilizing a dedicated objectoriented programming tool with an incorporated simulation method is a highly effective way to prototype a new control system. A similar study [Venkatesh and Ilyas 1995] is done for modeling, controlling, and evaluating local area networks in FMSs using realtime timed PNs (RTPNs). In an RTPN, the standard TPN is augmented with two extra tuples, namely input signal vector and output signal vector, to read inputs from the system and send outputs to the system in real time. Venkatesh, Zhou, and Kaighobadi et al. [1996] find that TPNs are effective tools to study optimal operational parameters for a flexible factory automated system (FFAS) under both ‘push’ and ‘pull’ paradigms. FFASs typically comprise a strategic arrangement of flexible manufacturing systems (FMSs) and flexible assembly systems (FASs) to meet dynamically changing orders. The study shows that the configuration can result in the minimum buffer sizes and maximum system utilization when output rate is considered as the optimal solution under each paradigm. The study also concludes that the “push” paradigm performs better than the “pull” one
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Investigation of a Neural Network Methodology to Predict Transient Performance in Fms 
Date  20050501 
Author  Kwon, Augustine Jongik 
Keywords  Flexible manufacturing, Artificial neural networks 
Department  Business Administration, Management 
Document Type  
Full Text Type  Open Access 
Abstract  Most rapid analytical evaluative models for Flexible Manufacturing Systems (FMSs) are based on the steadystate performance. There is a practical need to develop robust, easy to construct, and transportable transientstate evaluative models for FMSs. This study proposes an ANN based metamodeling framework that can capture various post disruption system behaviors of FMS. The proposed ANN based metamodeling scheme consists of a hierarchical taxonomy of multiple ANNs. Each set of ANNs collectively represents a different part of the underlying system modeling domain. The taxonomical arrangement of multiple ANNs overcomes shortcomings often found in single ANN based metamodeling schemes. These shortcomings are generally related to the limited knowledge acquisition capability of these schemes. The study uses an Extend based discrete simulation model that is built after an experimental FMS with a limited disruption trigger and handling capabilities. The simulation model is used to study various postdisruption behaviors by a given FMS and to study the feasibility of the proposed modeling scheme as a viable means to provide lookahead capability for a low level controller. The proposed ANN based metamodeling approach using multiple ANNs, in a taxonomically organized modeling structure, is an efficient way to capture multiple target performance index observation processes with a similar overall postdisruption behavior pattern. Despite its accuracy issues, this methodology was proven especially effective when it has to deal with noisy time series such as TIS at observation under a data rich environment. The study is to prove that the proposed methodology could be a viable means to model transient system behaviors. As long as individual observation processes of the selected performance index can keep their variances smaller among themselves, the accuracy of the overall model would be acceptable. This nonparametric performance modeling technique using hierarchically organized multiple ANNs, is worth further investigation. 
Note  Dissertation 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  INVESTIGATION OF A NEURAL NETWORK METHODOLOGY TO PREDICT TRANSIENT PERFORMANCE IN FMS By AUGUSTINE JONGIK KWON Bachelor of Science University of MissouriRolla Rolla, Missouri 1989 Master of Science University of MissouriRolla Rolla, Missouri 1991 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY May 2005 INVESTIGATION OF A NEURAL NETWORK METHODOLOGY TO PREDICT TRANSIENT PERFORMANCE IN FMS BY AUGUSTINE JONGIK KWON Thesis Approved: Dr. David B. Pratt __________________________________________________ Thesis Advisor Dr. Michael Branson _________________________________________________ Dr. Martin Hagan __________________________________________________ Dr. Manjunath Kamath __________________________________________________ Dr. Gordon Emslie __________________________________________________ Dean ofthe Graduate College ii ACKNOWLEGEMENTS I wish to express my sincere appreciation to my major advisor, Dr. David Pratt for his intelligent supervision, guidance, suggestions, and encouragement. My sincere appreciation extends to my other committee members, Dr. Michael Branson, Dr. Manjunath Kamath, and Dr. Martin Hagan, for their helpful comments, suggestions, and understanding during the course of this study. I also would like to thank Dr. John Nazemetz and the Industrial Engineering and Management Graduate Program for providing me with a research assistantship and their generous financial support during my stay in the program. I would like to express my deepest gratitude to my wife, Cindy, for her support, love, and understanding throughout the whole process. I thank my children, Katie and Megan, for their unconditional love and understanding despite being absent many times during last five years. Special thanks to my dear parents, God, and blessed Mary for the privilege and honor of obtaining the doctoral degree with the help of their unconditional love, encouragement, and inspiration. Finally, I would like to thank my boss, Sam Nusinow at Knowledge Base Engineering, Inc. and the School of Industrial Engineering and Management for supporting me to successfully complete this study. iii TABLE OF CONTENTS 1. Introduction ……...……..…...……………………………………………………… 1 1.1 Motivation of the Research……………………………………………...………...1 1.1.1 Growing Usage of FMS……………………………………………...……...3 1.1.2 Known Integration and Performance Modeling Issues with FMS ….....…....5 1.1.3 Importance of Performance Predictor in Online Controller………………..7 1.1.4 Simulation Modeling versus Metamodeling………………………………..9 1.1.5 Artificial Neural Network Based Metamodeling vs. Regression Based Metamodeling Approach……………………………………..……............11 1.2 Problem Statement…………………………………………………...…………..14 1.3 Scope of the Research……………...…………………………………………….16 1.4 Anticipated Contributions………...……………………………………………...18 1.5 Overview of the Dissertation……………………………………………………..20 2. Literature Review……...…………..……………………………………..…………22 2.1 Queueing Network Approaches…...……………………………………………..23 2.1.1 Summary of Major Developments……………...………………………….23 2.1.2 Conclusion………………………………………………………………….34 2.2 Markov Chain Models……………………………………………………………39 2.2.1 Summary of Major developments………………………………………….39 iv 2.2.2 Conclusion………………………………………………………………….47 2.3 Simulation Modeling……………………………………………………………..49 2.3.1 Summary of Major Developments………………………………………...49 2.3.2 Conclusion………………………………………………………………...61 2.4 Stochastic Petri Nets……………………………………………………………...63 2.4.1 Summary of Major Developments………………………………………...63 2.4.2 Conclusion………………………………………………………………...73 2.5 Summary…………………………………………………………………………75 3. Problem Settings and Systems Description………………………………………..79 3.1 FMS………………………………………………………………………………79 3.1.1 System Description………………………………………………………..79 3.1.2 Parts………………………………………………………………………..82 3.2 Time Series Analysis………………………………………………………..…….90 3.3 Artificial Neural Networks………………………………………………………121 3.3.1 Background………………………………………………………………121 3.3.2 Multilayer Neural Network Architecture and Training Methods………..130 3.3.3 Proposed Neural Network based metamodeling framework……..…….144 4. Statement of Research…………………………….……………………………….148 4.1 Research Goal………………………………………………………………….148 4.2 Research Objectives……………………………………………………………148 4.3 Assumptions and limitations…………………………………………………...153 v 4.4 Summary……………………………………………………………………….154 5. Research Methodology………..…………………………………………………...156 5.1 Research Tasks…………………………………………………………………156 5.2 Simulation Based Disruption Scenarios………………………………………..161 5.3 Summary……………………………………………………………………….167 6. Problem Development – Pilot Experiments…………………………………...….168 6.1 Development of a Computer Simulation Model……………………………….168 6.2 Initial Experiments and Findings………………………………………………171 6.3 Initial Simulation Experiment Sets and Data Processing Procedures………….181 6.4 Post Disruption Behavior Pattern Classification……………………………….187 6.5 Identification of Input and Output Vectors…………………………………….199 6.6 Summary……………………………………………………………………….214 7. Experimental Results………………….………………………………..…..……..215 7.1 Construction and training of Individual ANNs………………………………....215 7.2 Expansion of the Initial Experiment Size……………………………………....225 7.3 Performance Evaluation of Proposed Modeling Scheme……………………....228 7.4 Summary………………………………………………………………………..249 8. Summary and Conclusions......................................................................................250 8.1 Overview of Research Objectives and Accomplishments...................................250 vi 8.2 The major contributions of this research..............................................................253 8.3 The Strength and Weakness of the Proposed Modeling Approach......................257 8.4 Future Research Directions and Opportunities....................................................259 8.5 Summary..............................................................................................................260 Bibliography……………………………………………………………………..….…262 Appendix A…………………………………………………………………………….275 Extended Design of Experiments………………………………………………...….276 Appendix B………………………..…………………………………………………..287 B.1 MATLAB Source Code for Training Individual ANNs………………………288 B.2 Transient Behavior Prediction User Interface in MATLAB…………………..301 Appendix C……………………………………………………………………………306 C.1 Input Vectors for Postdisruption Type 1 ANNs, Net_2_1_1, Net_2_1_2, and Net_2_1_3, from the second level ……….…………………………………….307 C.2 Input Vectors for Postdisruption Type 2 ANNs, Net_2_2_1, Net_2_2_2, and Net_2_2_3, from the second level ……………………………………………..332 C.3 Input Vectors for Postdisruption Type 3 ANNs, Net_2_3_1 and Net_2_3_2, from the second level………..…………………………………………………345 C.4 Output Vectors for Net_1_1…………………………………………………….406 C.5 Output Vectors for Net_2_1_1………………………………………………….421 vii C.6 Output Vectors for Net_2_1_2………………………………………………….426 C.7 Output Vectors for Net_2_1_3………………………………………………….429 C.8 Output Vectors for Net_2_2_1…………………………………………………430 C.9 Output Vectors for Net_2_2_2…………………………………………………437 C.10 Output Vectors for Net_2_2_3………………………………………………..440 C.11 Output Vectors for Net_2_3_1………………………………………………..443 C.12 Output Vectors for Net_2_3_2………………………………………………..454 Appendix D……………………………………………………………………………467 Appendix E…………………………………………………………………………….477 Appendix F…………………………………………………………………………….487 viii LIST OF FIGURES Figure Page 1 Scenario for Interfacing Simulation with Physical System for Realtime Control……………………………………………………………. 57 2 Physical layout of the FMS under study………………………………. 81 3 A stationary time series showing shortterm correlation with its correlogram……………………………………………………………… 104 4 A nonstationary time series together with its correlograms……………. 105 5 A time series contains a periodic component ………………………….. 112 6 A spectrum with the corresponding normalized spectral distribution function…………………………………………………………………. 116 7 Anatomical illustration of biological neurons…………………………... 122 8 SingleInput Neuron…………………………………………………….. 123 9 Typical Transfer functions……………………………………………… 131 10 Threelayer network…………………………………………………….. 133 11 Proposed ANN based Metamodeling scheme…………………………... 146 12 Graphical Representation of Stable and Unstable Equilibrium…………. 165 13 Set Part Type Attribute Block ………………………………………….. 169 14 Part Routing and AGV Control Logic ………………………………….. 170 15 Single Resource Failure Scheduling and Control………….……………. 171 16 Row TIS Observations during First 500 Parts under the First Steady State Scenario with No Disruption……………………………………… 174 17 Moving Average Filtered TIS Observations under the First Steady State Scenario with No Disruption……………………………………………. 179 18 Moving Average Filtered TIS Observations under the First Steady State Scenario with Machine M6 Failure Took Place at 10000 ……………… 180 19 Preprocess Steps……………………………………………………….. 188 ix Figure Page 20 Type 0 (no change) Transient Behavior Pattern Class………………….. 190 21 Type 1 (an infinite linear growth) Transient Behavior Pattern Class…… 191 22 Type 2 (an infinite nonlinear growth) Transient Behavior Pattern Class……………………………………………………………………. 192 23 Type 3 (a finite growth to a new steady state) Transient Behavior Pattern Class…………………………………………………………… 193 24 Individual Moving Average Filtered TIS plots under Scenario No.19... 195 25 Moving Average Filtered Mean TIS Plots under Scenario No.19…….. 197 26 A Closeup View of Moving Average Filtered Mean TIS Plots under Scenario No.19………………………………………………………… 198 27 Proposed TwoLevel Deep Taxonomically Organized ANN Based Transient Performance Model…………………………………………. 211 28 Network Diagram of Net_1_1 in the Top Level………………………. 216 29 Individual Network Diagram of Type One Transient Behavior Approximation subANNs in the Second Level………………………. 217 30 Individual Network Diagram of Type Two Transient Behavior Approximation SubANNs in the Second Level………………………. 219 31 Individual Network Diagram of Type Three Transient Behavior Approximation subANNs in the Second Level………………………. 221 32 Performance Plots of the Top Level ANN Net_1_1 during Its Initial training with 90 Input and Output …………………………………….. 223 33 Comparative Performance plots of sub ANNs, Net_1_1 and Net_2_3_2, under Old and New Training, Test, and Validation Vector Sets…………………………………………………………………….. 227 34 RAW TIS and Moving Average Filtered (MA) TIS Plots of Exp No. 438 (Postdisruption Type 1 Behavior)………………………………... 232 35 Moving Average Filtered (MA) TIS vs. Approximations by a Quadratic Model for TISs during First 400 Postdisruption Observations…………………………………………………………… 233 x Figure Page 36 Moving Average Filtered (MA) TIS vs. Approximations by a Linear Regression Model for TISs from 4753rd to 8653rd Observation……... 234 37 Moving Average Filtered (MA) TIS vs. Approximations by the final Composite Regression Model for TISs from 4353rd to 8653rd Observation……………………………………………………………. 235 38 Trend Plot of Standard Deviation of Moving Average (w=500) Filtered TIS observations before and after the disruption and Comparative Plots of Standard Deviation Regression Models………... 236 39 Comparative Plots of Mean TIS Approximations by Various Regression Based Models for Exp438 (Type1)………………………. 238 40 Comparative Plots of Sigma Approximations by Various Regression Based Models for Exp438 (Type1)…………………………………… 239 41 Descriptive Statistics and Normality Test on RAW TIS data from Predisruption Period of Exp438………………………………………….. 243 42 Descriptive Statistics and Normality Test on MA TIS data from Predisruption Period of Exp438…………………………………………... 244 43 Open Queueing Network………………………………………………. 489 44 Example of graphical representation of a Petri net…………………….. 496 45 Reachability tree of the model in Figure 44………………………….. 499 46 GSPN model of Figure 44 with given exponential and immediate transition times………………………………………………………… 502 47 Finding an equivalent CTMC for GSPN model given in Figure 5 503 48 A conversion from an ordinary PN of the FCFS queueing discipline with two job classes to an equivalent CPN…………………………… 506 xi LIST OF TABLES Table Page 1 Major Developments in FMS Performance Study Using QN Analysis…………………………………………………………………. 35 2 Sample orders with four part types under a production plan……………. 82 3 Interarrival Time and Machining Process Requirements for Different Part Types……………………………………………………………….. 83 4 Presort Conveyor Belts and Possible Part Types………………………. 84 5 Relative Part Size for Different Part Types……………………………... 85 6 Part Groups and Machine Process Capability………………………… 87 7 Service Time Distributions for Individual Part Types……….…………. 88 8 Part Types and Possible Part Mix Change Scenarios…………………… 162 9 Possible Single Machine Failure Scenarios……………………………... 163 10 Possible Single AGV Failure Scenarios………………………………… 163 11 Possible Single Resource Failure Scenarios……………………………. 166 12 Four Steady State Scenarios and Their Warmup Periods……………… 173 13 Individual System Resource Utilization Rates under Four Steady State Scenarios………………………………………………………………… 177 14 Four Steady State Scenarios and Their Control Limits…………………. 178 15 Initial Experiment Set…………………………………………………… 182 16 Makeup for Four Transient Pattern Types………………………………. 194 17 Semantics of Common Input Vector p….……………….….…………. 201 18 Semantics of First Output Vector a1 from the Top Level ANN…………………………………………………………………….. 202 19 Semantics of Output Vector a2,1 from First Three ANNs in the Second Level ANNs to Approximate Transient Behavior Pattern Type No.1…………………………………………………………..………… 204 xii Table Page 20 Semantics of Output Vector a2,2 from Second Group of Three ANNs in the Second Level ANNs to Approximate Transient Behavior Pattern Type No. 2………………………………………………………………. 207 21 Semantics of Output Vector a2,3 from Third Group of Two ANNs in the Second Level ANNs to Approximate Transient Behavior Pattern Type No. 3…………………………………………………………………….. 210 22 Training and Testing Performance Indexes from Individual Neural Networks with 90 training and 45 Testing Input and Output Vectors (original experiment set)………………………………………………… 224 23 Training, Test, and Validation Performances from Individual SubANNs under New Extended Training, Test and Validation Vector Sets vs. Those under Old Training, Test, and Validation Vector Sets……….. 226 24 Major Event Start Times on MA TIS Observations from 18 Selected Experiment RAW Data………………………………………………….. 230 25 Major Event Start Times on Approximated TIS Observations Rendered by Regression Models Based on MA Scenario Average TIS Observations from 18 Selected Experiments…………………………… 230 26 Major Event Start Times on Approximated TIS Observations Rendered by ANN Generated Regression Models for 18 Selected Experiments….. 231 27 TIS Transient Behavior Prediction Performance Table for Selected Experiments under Three Postdisruption Behavior Types……………... 247 xiii 1 1. Introduction 1.1 Motivation of the Research In most scientific domains, it is a common practice to build physical or mathematical models to study a system of interest. These models are frequently defined to be a collection of entities (components). These entities act and interact together toward the accomplishment of some logical end [Schmidt and Taylor 1970]. Often, these physical or mathematical models are simplified forms (abstractions) of real systems because it is only necessary to consider those aspects of the system that affect the system behavior under investigation [Banks et al. 1996]. Studying a system model normally provides an opportunity to better understand the relationships among its components or to predict how the system will operate under new policies or new operational conditions [Law and Kelton 1991]. In practice, for many real world systems, building a physical model is often too costly and impractical due to complexity and lengthy development time. Especially when models for the system require a fullscale level of detail, the cost can be prohibitive based on the nature of the system. For this reason, mathematical models are often preferred in many fields to study characteristics or behaviors of the system under given conditions. 2 System models can be classified into two broad categories based on their use. The first type is an evaluative model. An evaluative model can be used to study a particular system behavior(s) under a set of given configurations and operational parameters. The second type is a generative model. Generative models are built to find a set of optimal decision parameters that can satisfy operational or design objective(s) for the system under given constraints. Evaluative models are designed to provide performance predictions that are essential during the design and operational stages of a system. On the other hand, generative models are extensively used for performance optimization in various operations research (OR) type studies. Reliable performance prediction for manufacturing systems has been the focus of many industrial and academic research communities. Reliable but easytodevelop and easytouse evaluative models for both design and operation are crucial for operational success. Most evaluative models have focused on longterm steadystate system behaviors rather than shortterm transitory behaviors. For this reason, it is not ideal to use them to forecast often volatile transitional shortterm behaviors following events that cause disruptions of the steadystate behavior of a system performance indicator. Examples of unexpected events that can cause system disruptions are machine failures, rush orders, and changes in product mix due to part or material shortages. With the advent of more powerful computer and information technologies, interest in industrial application of online decisionmaking has intensified in recent years. In the area of highly automated production and process controls, online decision3 making and its associated issues have become prominent research topics. Especially in the area of flexible manufacturing system control, conveying a realistic view of upcoming shortterm behavior of the system is vital to building effective control policies to minimize unwanted performance deviation following an unexpected system disruption(s). 1.1.1 Growing Usage of FMS The most common challenge faced by manufacturers around the world today is to adapt themselves to a rapidly changing operational environment. The demand for highly customized products is on the rise and today’s fierce competition in lowcost precision manufacturing is unprecedented. Among many strategies available to deal with these challenges, one approach is to adopt and implement various forms of flexible manufacturing systems (FMSs) as a part of a strategic plan. There are many definitions of FMS available. Even though they may have some difference in details, all seem to agree on common basic design fundamentals that can be found in the definition given by Groover [1987]. According to Groover [1987], an FMS is a fully automated system consisting of functionally similar or dissimilar automated workstations interconnected by means of an automated material handling system and storage system, and controlled by an integrated computer system. The workstations are considered automated cells of computer numerical control (CNC) machines. A similar term, flexible manufacturing cell (FMC), often used in place of FMS, can be defined as follows: a typical FMC comprises a few numerically control (NC) machines, tool 4 magazines, and one or more material handling robots [Narahari and Viswanadham 1989]. According to Groover [1987], a distinction between FMS and FMC can be made based on the number of NC or CNC machines comprised within. Therefore, an FMS can also be formed as a collection of several FMCs. FMSs have various documented and publicized merits such as high adaptability to changes, flexibility in configurations and operations, improved product quality, short leadtime, and high utilization with a relatively low WIP [Groover 1987], [Vollmann et al. 1997]. From a systems perspectives, finding an effective modeling tool for FMSs will likely make contributions to modeling other Discrete Event Dynamic Systems (DEDS) because the system dynamics observed in various FMSs are analogous to those that can be found in many DEDS. In general, DEDS are large scale interconnected systems, driven by the occurrence of discrete events, where their dynamic behavior involves state changes only at discrete points in time [Ho et al.1984]. Complex interactions are often present in the system behaviors of DEDS. Synchronization, concurrency, randomness, and contention for limited resources are common aspects of these interactions [Narahari and Viswanadham 1989]. DEDS can be found almost everywhere in today’s modern technological infrastructure. According to Ho et al. [1984], examples of such systems encountered today are communication networks, computer systems, production/assembly lines, traffic systems, and transportation networks. Therefore, an effective modeling methodology for FMS transient behaviors may be applicable to these systems with some modifications. 5 1.1.2 Known Integration and Performance Modeling Issues with FMS Despite many publicized FMS merits, there are four welldocumented limitations [Huang and Chen 1986] that keep FMSs from being more widely applied in industry. These limitations are: 1. high initial costs, 2. long implementation lead time, 3. uncertainty of a successful FMS interface with the current production system, and 4. control software customization issues based on uniqueness of each installation site. All of the above limitations except the third, uncertainty of a successful FMS integration, can be naturally resolved as time progresses with little commitment from those who actually operate FMSs on a daytoday basis. For example, the continuous market growth in FMS installation and ongoing technological innovation will lower the high cost of precision machine tool manufacturing. Thus, FMSs will eventually become an affordable form of automation even to manufacturers without great financial strength. To overcome the uncertainty of successful FMS interface with the current production system, tremendous effort is required from both FMS designers and operators no matter how advanced the supporting technology becomes in the future. Without these efforts, the full potential of FMS may not be realized. 6 The concept of FMSs can be used within the context of manufacturing cells. Individual cells consist of several workcenters that can carry out similar or dissimilar manufacturing functions. Lin and Chiu [1993] stress that understanding and being able to predict dynamic behavior as well as long term manufacturing cell performance is necessary to better coordinate production among cells. Therefore, knowledge of transient performance behavior as well as steadystate behavior of individual cells can be vital to overcoming the third limitation in adopting FMS. Another research effort points out that the studies done on interactions among FMS resources and impacts brought by random changes in operations are still insufficient [Basnet and Mize 1994]. Random changes during operation, such as resource breakdowns and rush orders, are normally responsible for unanticipated system interruptions. Traditional performance modeling approaches, such as analytical and simulation modeling, constantly rely on human intelligence and modeling skills to create and maintain effective evaluative power. On a busy shop floor, especially for a highly utilized FMS, the ability to make instantaneous decision to effectively handle a wide range of critical disruptions using an effective shortterm evaluative model can be highly beneficial. For example, evaluative models based on steadystate performance can help an operator select a proper operational strategy in order to reach an optimal production level based on a long term production schedule. On the other hand, an effective shortterm look head capability can help an operator choose a proper short term remedy to handle the daytoday operational problems without compromising the longterm7 performance goal. However, due to its dependency on human intelligence and expertise, occasional offline maintenance is required when there are significant changes to the system configurations and operation rules. For example, adding new part type, AGV or machine center to the existing system requires redefining its state space in a Markov chain model. Lacking selfmaintainable modeling capability in a highly dynamic operational environment can sometimes result in a costly impact to the rest of production line. Utilizing transient analysis to measure impacts on a performance indicator following one or more disruptions will provide an FMS operator the opportunity to assess the situation and help him/her make the best operational choice so that the impact to the other parts of the production line can be minimized. The proper balancing between shortterm and longterm performance lookahead capability through efficient evaluative models is one crucial key for seamless integration between FMSs and traditional production systems since the return on investment on an FMS is initially much lower than other forms of automation. This is necessary to avoid creating another costly “automated island”. As applications of FMSs continue to grow, successfully integrating FMSs with other types of production systems become more critical. 1.1.3 Importance of Performance Predictor in Online Controller The continuous improvement and new development of online as well as offline production flow optimization schemes under different planning time horizons for a 8 dynamic system has been a primary focus for many FMS researchers. These schemes are developed using various operations research, mathematical programming, and artificial intelligence (AI) techniques with a wellconstructed evaluative model. There are important distinctions between offline flow and online production flow optimization schemes in typical shop floor control environments. Offline schemes are typically used to perform planning, scheduling and routing functions through periodic interactions with a human supervisor. On the other hand, online schemes are used by automatic control devices such as PLCs to continuously optimize hardware performance and to perform schedule and route changes due to resource failures, rush orders, and major deviations in the original production plans. If the predetermined schedule is carried out as planned, online controllers are required only for the actual implementation of control procedures, such as downloading of CNC programs. In such cases, offline schemes are used at predetermined time intervals and the resulting schedules are implemented. However, a perfect adherence to predefined schedules is almost never realized in practice due to exceptions known as disruptions or unexpected events that cause deviations of the shop floor behavior from the manager’s expectation [Katz and Manivannan 1993]. Katz and Manivannan [1993] acknowledge a great need for architecture to analyze complex patterns of online events caused by possible production disruptions. Online simulation is proposed as one way to obtain information about foreseeable detailed behavior of the manufacturing system within a specified length of9 time in which a control decision has to be made (also known as the control horizon). For online FMS control, devising fast and reliable evaluation models in a disruption handling architecture is crucial because most decisionmaking regarding unexpected online events takes place within a matter of seconds or minutes. Lin and Cochran [1990] state, “For shop floor control in real time, not only long term steadystate performance is important, shortterm dynamic performance of the production line is of even greater interest, since many unexpected events can be vital.” The majority of analytical model developments for FMS operations are based on longterm system behaviors using steadystate analysis. However, in reality most of these systems never reach steady state because of their highly dynamic operational nature [Buzacott and Yao 1986]. For people who operate FMSs on shop floors as a means to meet daily production goals, a comprehensive system model to depict realistic transient behaviors accompanied by possible, but unscheduled, disruptions is more meaningful to make control decision within a small time horizon. 1.1.4 Simulation Modeling versus Metamodeling Simulation modeling is an evaluative technique to study a system of interest. Simulation is normally conducted by a digital computer numerically exercising a model for the inputs in question to see how they affect the output measures of performance [Law and Kelton 1991]. Often, a wellbuilt simulation model provides realistic views of 10 system behaviors of interest. Thus, one can extensively study behaviors of a real world system without modifying an actual system for different baseline characteristics. Although most simulation models are simpler than the real world system they model, it is still a complex way to study systems behaviors because building a valid simulation model takes a considerable amount of expertise, effort, and time. The time and effort to build and validate such models, especially under time pressure, often leads users to switch to other forms of evaluative models, such as analytical models, or to choose a hybrid model that combines analytical and simulation models to avoid lengthy computation time. Metamodeling is a supplementary way to map target system input to corresponding output in simpler manner using simulation experimental design and mathematical techniques like regression analysis or time series analysis. Wellbuilt metamodels often provide the speed of analytical models with the fidelity of a carefully executed simulation study. The usefulness of regressionbased metamodels has been investigated in several studies [Friedman 1989], [Friedman and Pressman 1988], [Kleijnen 1979]. Typical metamodels are approximation formulas that map different combinations of input values to associated output values normally obtained through a full execution of a simulation experimental design. In most cases, nonterminating simulation is used for each run in the experimental design. A terminating simulation is one for that runs for some duration of time, where ETE is a particular event (or set of events) which stops the simulation. On the contrary, nonterminating simulation is one for which there is no 11 particular event E to specify the length of a run. Typically, a performance measure for such a simulation is said to be a steadystate parameter if the output stochastic process of interest exhibits a steadystate (or near steadystate) distribution. L,,21YY Relying on the traditional terminating simulation method to investigate transitional behaviors of a manufacturing system can be expensive and often impractical for real time production control [Lin and Cochran 1990], [Lin and Cochran 1990], [Lin and Chiu 1993], [Lin et al. 1998]. Thus, constructing metamodels using stochastic discrete event simulation and mathematical formulation as an evaluative modeling tool to forecast possible transient behaviors of a complexmanufacturing system under various scenarios has been shown to be a highly effective and practical approach [Lin and Chiu 1993]. 1.1.5 Artificial Neural Network Based Metamodeling vs. Regression Based Metamodeling Approach Artificial neural networks are widely used in many fields as a prominent artificial intelligent tool when rapid computation, adaptability, and robustness are required [Padgett and Roppel 1992]. Typically, neural network applications require fewer assumptions and less accurate data to model unknown functions. Using artificial neural networks as a nonparametric approximation methodology has been shown to be highly effective in the area of metamodeling compared to traditional regression type approaches [Kilmer 1994]. This is especially true, when the system contains a significant amount of the “noise” which is often present in many stochastically transitional systems [Kilmer 12 1994]. The number of different types of artificial neural networks is almost unlimited based on different design architectures and their application areas. Alternative design architectures are discussed more fully in Chapter 3. Regression analysis is the part of statistics that deals with investigation of the relationship between two or more variables related in a nondeterministic fashion. Regression models can be grouped into linear and nonlinear regression models. Nonlinear regression functions can have many different forms. A polynomial regression function is one common possible form. If there is more than one independent variable related to dependent variables, the model is called a multiple regression model. In general, neural networks appear to perform better than ordinary regression techniques in statistical approximation of unknown functions [Kilmer 1994]. The implementation of most regression techniques depends on two critical statistical assumptions about the model errors. These assumptions are: 1. errors must be independent, and 2. errors must be normally distributed with a zero mean and a constant variance [Miller et al. 1990]. Nam and Schaefer [1995] identify three reasons to move away from a traditional regression approach in practical forecasting. First, even though the accuracy of regression models is not significantly compromised when there are small departures from these assumptions, the performance of the model can deteriorate when the assumptions are violated. Such deviations from the assumptions can generally only be detected after the 13 construction of the model. Second, past observations regarding the unknown function often contain complex patterns. Third, there is no way of being certain that the choice of a given regression technique provides the best result. Alternatively, neural networks can learn from experience, move to new generalizations from previous ones, and abstract essential characteristics from somewhat noisy and incomplete inputs [Wasserman 1989]. In addition, neural networks do not require the same assumptions about the underlying distribution, as do many regression techniques. Therefore, artificial neural networks can be an effective alternative to most regression type approaches. Lin and Cochran [1990] utilize time series regression analysis and stochastic simulation in their metamodels to predict transient behaviors of a flow shop system. Since their modeling scheme relies on the modeler’s ability to classify and synthesize various functional elements to make a proper time series model for a given unknown performance function, it is difficult to transform the scheme into an effective automated modeling framework. Based on the pattern of the transitional behavior following a disruption(s), building a prediction model through ad hoc combinations of time series analysis and a linear equation with a particular part arrival or departure rate can be cumbersome. Compared to the traditional regression method, properly configured artificial neural networks can learn and capture any unknown functions with almost no human intervention. It has also been shown that artificial neural networks can effectively approximate behaviors of many nonlinear dynamic systems with a relatively small error 14 [Narendra and Parthasarathy 1990]. Since the development of reliable and easytouse performance prediction tools for a control mechanism is essential for wide acceptance of FMS in industry, constructing metamodels using an efficient artificial neural network design will be a stepping stone to building a truly practical disruption handler in future FMS control environments. 1.2 Problem Statement Thorough understanding of possible dynamic transient behaviors of a typical FMS under preselected disruption scenarios utilizing an artificial neural networks (ANN) based metamodeling framework is the motivation behind this research. The need for this research is based on a proposition made by Buzacott and Yao [1986] who argue that in reality, most FMSs never reach steady state because of their highly dynamic nature. Most rapid analytical evaluative models for FMSs are based on their steadystate performance. This argument supports a need to develop robust, easy to construct, and transportable transientperformance evaluative models for FMSs. Thus, building hybrid type evaluative models (metamodels) using artificial neural networks and stochastic simulations, which can capture realistic but general transient behaviors of an FMS under a set of typical operational scenarios, will help shop floor managers to successfully manage daytoday FMS operations in a tightly integrated manner. The primary objective of this research is to define an artificial neural network 15 (ANN) based metamodeling methodology for FMS transient behavior prediction. The proposed ANN based metamodeling scheme consists of a hierarchical taxonomy of clustered ANNs. Each cluster of ANNs collectively represents a different system knowledge domain. This taxonomically structured arrangement of ANNs overcomes shortcomings often found in single ANN based metamodeling schemes. These shortcomings are generally related to the limited knowledge acquisition capability of these schemes. The advantage of neural network based prediction models lies in their capability to capture not only time based onetoone expected performance but also an overall dynamic behavioral pattern of a particular performance index during a transition caused by a disruption. The proposed ANN based transient performance model is designed to provide better knowledge for an automated disruption handler or FMS operator to discriminatorily react to controllable performance deteriorations. The captured dynamic behavioral pattern of interest may show gradual or sudden shifting of the average performance value over a given time horizon, as well as an expected duration of such behavior. This feature will provide a decisionmaker with the capability of conducting intelligent disruption diagnosis for a discriminatory remedial control action(s) based on unique postdisruption system behavior. This capability will enhance the adaptability of FMSs in a highly dynamic manufacturing environment with a minimal performance disruption by providing shop production control a “lookahead” capability in order to make eventdependent and timely control decisions. 16 Defining an effective modeling framework to intelligently activate corresponding metamodels based on the nature of the disruption event and characteristics of behavioral patterns will be another contribution that makes this study practical in terms of real world application. Identifying and selecting significant operational factors as system input as well as performance indicators as meaningful system output, is done before the actual model construction process starts. Modeling an FMS with a common configuration and testing it under realistic operational scenarios are important tasks. In return, these welldesigned simulation experiments should closely capture common dynamic characteristics for the majority of FMSs that this research intends to represent. This will assure that pursuing an ANN based transient metamodeling approach is a viable alternative to devise a shortterm performance forecasting feature in online disruption handlers for many industries that operate similar types of FMSs in volatile daytoday production environments. Needless to say, designing and conducting verifiable simulation experiments and proper post simulation analysis are essential for the success of this research effort. 1.3 Scope of the Research The goal of this research is to demonstrate that ANN based metamodel consisting of a hierarchical taxonomy of ANNs can be an effective modeling alternative to regression based metamodels to forecast FMS transient behaviors following a random 17 disruption event(s). This research is proposed under the partially verified hypothesis that artificial neural network based metamodels of stochastic simulations generally appear to perform better than regression based counterparts [Kilmer 1994]. In Kilmer’s study [Kilmer 1994], ANN based metamodels are built to approximate an unknown response surface given by a set of alternative input parameters. The procedure, often called response surface methods (RMS) [Box and Wilson 1951], is used to find the levels of the experimental factors that yield the best value of the response (or output) of a system. Such ANN based metamodels deal only with steadystate performance parameters of stochastic discrete event simulations. However, for this research, ANN based metamodels deal with transient performances depicted by nonterminating simulations with imposed resource failures because the focus is on transitional behaviors (deviations from steady state) after the disruption(s). Even though the ultimate use of these ANN based models is for online disruption control, FMS control is not the focus of this research. Therefore, any technical issues regarding the actual FMS control are beyond the scope of this study. This study is intended to develop a new methodology for forecasting shortterm transient performance in a timely manner. In contrast to typical ANN applications in time series modeling trained with actual data points, individual ANNs from the proposed modeling framework will be trained with selected time average resource utilizations and coefficients from selected polynomial regression models found on a limited number of data points generated from18 various simulation experiments. These nonterminating stochastic simulations will be carefully designed and chosen to represent various unique postdisruption behavior patterns. Therefore, independent experimental factors for FMS transient behaviors are carefully identified, screened, and structured for a valid design of experiments. Then a manageable subset is selected for experimentation. Although this study extensively uses simulation, it is not an intention of this study to extensively review traditional issues associated with simulation modeling, validation, verification, and poststatistical analysis processes. Finding justifiable reasons to choose particular artificial neural network design architecture over others is another crucial objective of this research. The choice of possible variations within a particular architecture and training method, for example, the number of nodes, the number of hidden layers, the type of transfer function, selection of training data set, training methods, and the length of training period etc., must be identified. Finally, a taxonomical arrangement of individual neural networks that are designed to capture and approximate various parts of the desired system knowledge domain is to be presented and examined. 1.4 Anticipated Contributions The primary contribution of this research is the conceptualization of a system modeling framework that can provide selforganizing and pattern based transient 19 behavior forecasting. The proposed system modeling framework maps various shortterm transient behavior patterns over the chosen performance indexes by utilizing taxonomically structured ANN based metamodeling. The transient behavior forecasting is based on both the initial reaction path following a disruption and a unique relationship to a corresponding disruption scenario. The majority of ANN based time series modeling approaches presented to date in the literature have focused on a single function realization. However, this study intends to provide a means to store more than one postdisruption system behavior function under various disruption scenarios and make them retrievable by providing a nonparametric relationship between a functional domain and a range of unknown postdisruption system behavior prediction functions. Because the proposed framework will be designed to capture unknown transient behavior prediction functions in a simple form using independent variables, spline modeling, using such techniques as polynomial regression analysis can be useful to extract the unique characteristics of many nonlinear transient behaviors. Secondly, since the proposed approach is aimed toward online application, the practicality of a proposed modeling approach as an online modeling scheme can be partially verified through limited controlled tests. Thirdly, the simulation study of a given FMS model will provide a better understanding of how other tightly coupled systems would react to a disruption under similar circumstances. This will also help to verify if there are signs of any overreactions or underreaction from recovery actions 20 taken by the control system, if not, how closely these reactions will follow a monotonic behavior patterns discussed in some studies [Suri 1985], [Shanthikumar and Yao 1987]. Furthermore, this study provides a chance to closely examine methods and issues involved in quantification of nonmonotonic system behaviors compared to typical monotonic transition behaviors. If there exist any nonmonotonic transient behaviors following a disruption, this study will provide a better knowledge of when these behaviors can be triggered and under which system conditions. Finally, the study will examine the overall effectiveness of the proposed systemmodeling framework as a “look ahead” tool. In other words, the study will examine if an automated system modeling approach such as the one in this study is practical and reliable enough to provide an effective lookahead function for a fully automated production control environment. 1.5 Overview of the Dissertation The remainder of this dissertation is presented in seven chapters plus five appendices and a bibliography. Chapter Two reviews the literature in several major evaluative modeling methods commonly used in both steadystate and transient FMS performance analysis. Topics such as artificial neural networks and time series analysis are discussed extensively in Chapter Three since they are closely related to the proposed 21 modeling methodology. Chapter Three presents the FMS under study and proposed modeling approach. This includes detailed descriptions of the hardware configuration, operational rules, operational scenarios, and system parameters relevant to the hypothetical FMS under study. The rest of Chapter Three is allocated to elaboration of the proposed modeling framework. Chapter Four presents the research goal, objectives, assumptions, and limitations. Chapter Five outlines the research tasks, research methodology, and execution plan. Chapter Six discusses the design of simulation experiments, results analysis, classification of primary transient behavior patterns, configuration of input and target vectors, and configuration of the proposed taxonomically organized ANN modeling scheme for this study. Chapter Seven covers the training and construction of individual ANNs and evaluates the performance of the proposed ANN based metamodeling approach. Chapter Eight summarizes findings, draws conclusions, presents concerning issues, and discusses future research directions and opportunities. 22 2. Literature Review The primary objective of this research is to explore artificial neural networks as a nonparametric and nonregression based technique to build metamodels for time series so that the model can effectively predict shortterm transient behavior of an FMS after a disruption(s). The literature review focuses on several major FMS evaluative modeling methods that are useful for transient performance analysis. These techniques have evolved from major steadystate based evaluative modeling approaches. Therefore, there is a need to briefly review what has been done in the area of FMS performance modeling. This literature review covers not only specific transient performance models but also the steadystate performance models on which these transient performance models are based. Major evaluative modeling approaches in FMS are queuing networks, Markov chain, metamodels, stochastic Petri nets, and simulation. Basic theoretical foundations of these modeling approaches used for both FMSs transient performance analysis and steadystate analysis are briefly discussed. Common modeling assumptions for both steady and transient performance analyses using a particular modeling approach are identified and discussed. Typical of these modeling assumptions are that a model’s theoretical foundation is based on a steadystate Markovian stochastic process, a common underlining probabilistic distribution for arrival and service processes, no resource failure, no blocking, and deterministic part routings. 23 Significant breakthroughs in each modeling approach are reviewed. If there are several variations in a particular modeling approach, they are identified and their merits, compared to the original modeling approaches, are briefly discussed. Finally, the potential for adapting the particular approach for transient analysis is discussed. If there are already established ways to conduct transient analysis through the particular modeling approach, the literature review introduces the concepts and addresses their usefulness and concerning issues. A brief review of major developments in artificial neural networks is provided in Chapter 3 in addition to the proposed design architecture for this research. 2.1 Queueing Network Approaches 2.1.1 Summary of Major Developments Queueing networks (QNs) are the most frequently used analytical form among various FMS evaluative modeling approaches. In general, queueing networks can be formed to study aggregate system behaviors of clustered interactive queues, often “a machine shop” consisting of several departments [Jackson 1957]. Each department is considered a multiserver or singleserver queueing system (or a node within a queueing network) with an exponential service time distribution(s) and a single waiting line. 24 There are two major types of queueing networks based upon whether or not the total number of parts or pallets circulating in the network remains the same at any point in time during a normal operating cycle. The first type is open queueing networks (OQNs), also called Jackson networks [Jackson 1957], do not maintain a fixed number of parts in the network at any given time. The second type of queueing networks, called closed queueing networks (CQNs) [Gorden and Newell 1967], always maintain a constant number of parts. Despite the fact that the majority of analytical evaluative models for FMSs are based on CQN [Buzacott and Yao 1986], both the CQN and the OQN approaches are equally perceived as an effective way to model steadystate performance for various FMSs. For example, Buzacott and Shanthikumar [1980] model an FMS as an OQN where the scope of the model is expanded to include the jobs waiting for release to the FMS in a dispatching area. This study demonstrates the benefits of balanced workload, diversity in job routings with adequate control of job release to the system, and the superiority of common storage over local storage at each machine. Yao and Buzacott [1985] develop an OQN model to evaluate the performance of an FMS with general service times and limited local buffers. The model demonstrates that the arrival process can be formulated in terms of blocking probability on each station using renewal approximation by Whitt [1982]. Since most FMSs with limited local buffers tend to maintain a fixed number of pallets or parts in the system in order to avoid blocking, CQNs were initially perceived as an ideal type of queueing network model to depict behaviors of such FMSs. Formation of a CQN analytic model can result in either a product form solution with a normalization 25 constant or nonproduct form solution for the equilibrium joint distribution of pallets or parts. If the FMS CQN has a small number of nodes (workstations), the product form final solution of the equilibrium joint distribution can be easily estimated through an algebraic approach to finding the normalization constant. Several basic assumptions have to be made in order to have a product form solution. 1. The balance equations of part arrival rate are based on steadystate behaviors of the system. 2. The system consists of interconnected stages of service. The number of parts (or pallets) remains constant throughout the entire operational life cycle. mn 3. The service time distributions on each server are exponentially distributed. 4. The routing can be determined according to a discrete time Markov chain. The advantage of the closed queueing network approach is the ability to approximate the joint probability distribution of parts (or pallets) in the system using a separation of variables technique. When the number of nodes (workstations or cells) in the network (FMS) gets large, finding the normalizing constant, which is essential for finding the equilibrium joint probability of pallets in the system, becomes computationally challenging due to its permutable nature. The technique has been further improved by a computational algorithm to calculate the normalizing constant in a recursive manner [Buzen 1973]. This enables analytic CQN analysis to be a practical approach for a real production environment, especially for complex systems that require prompt decisionmaking. 26 The first successful adaptation of product form CQN in FMS was with a convolution technique, which is called CANQ [Solberg 1977]. This model was initially developed to handle only singleparttype FMSs with a central server (typically a material handling system) that every part must pass through. Later, CANQ was extended by Stecke [1981] to handle multiple part type FMSs. The performance of this analytical model depends on the assumption that the processing times at each firstcomefirstserve (FCFS) station are independent of the part type. If the assumption is satisfied, the convolution algorithm can deliver the exact solution. Otherwise, only an approximation can be made. Additional study done on a similar model suggested that the model would not perform satisfactorily if all the servers use an FCFS queue discipline and nonexponential service time distributions [Chandy and Sauer 1978]. Dallery [1986] has also shown that the product form FMS CQN model with a single part type is not well suited for performance prediction of multipleparttype FMSs with universal pallets and prescribed production ratios. Despite its known limitations, CQNs have been widely used for preliminary design and studying some operational issues in production planning for FMSs because of the speed and accuracy with which they can be evaluated once a model is correctly built. In the area of FMS production planning the CANQ model is extensively used to study the effect of various operational strategies on system throughput. 27 The class of product form CQNs was substantially extended and presented in a unified fashion [Baskett et al. 1975]. This triggered a rapid growth of applying CQN analysis in various FMS analytic models so that CQN analysis grew to handle problems that were initially thought to be unsolvable due to their deviations from the original assumptions. Assumptions such as a single part type and exponential service time distributions are commonly used in Gordon and Newell type network analysis. To overcome limitations of one of these assumptions, CQN with nonexponential service times, an “exponentialization” approach was introduced. This allows a CQN with general service times to be solvable, substituting general service times with equivalent exponential times so that the final product form can be still maintained [Yao and Buzacott 1986]. In practice, QNs with exponential arrival and service time distributions are not robust enough to capture realistic behaviors of various forms of FMSs in which the machine times are often known quite accurately [Pratt 1992]. Most workstations in an FMS, except for those that are failure prone, behave almost in a deterministic manner with very small variance especially when the system is fed with preselected part types, tightly integrated, and controlled by a computer. In some cases, time duration for individual part movements on predetermined part routes as well as processing in individual workstations is highly consistent and has much smaller variation than those with exponential probability distributions. Similarly, modeling failureprone FMSs using QNs with an exponential time assumption, which usually have larger variance than those of exponential systems, can also be misleading. Thus, modeling such FMSs using QN 28 with G/G/c/N queues is a more realistic approach. Yao and Buzacott [1985] model a workstation of an FMS using diffusion approximation (a recursive algorithm) in which the queueing process is formulated as a G/G/c/N queue. They found that a C2/C2/c/N queue and Coxian phases are appropriate for modeling queueing processes that represent workstations of an FMS with interarrival service time distributions having squared coefficients of variation of less than 0.05. Kamath [1989] found that most behaviors of asynchronous automated assembly systems (AASs) do not satisfy the assumption of exponential processing times made by closed form QN analysis and often the analysis can be misleading by such an assumption. These asynchronous automated assembly systems are also known as flexible assembly systems and represent a large and important subset of FMSs. Thus, it is necessary to use a method that can handle general service time distributions at each server for such AAMs [Kamath 1989]. Whitt [1993] studies a deterministic multiclass singleserver OQN and has shown that feedback with classdependent service times, and FIFO discipline can dramatically increase a chance for sudden large fluctuations on the sample paths of the queuewaiting processes with some initial conditions, which is highly conceivable in some FMS models. Suri [1985] has shown that a homogeneous service time (HST) CQN with exponentially distributed service times exhibits monotonicity throughout their performance measures depending only on the number of jobs present in the system. A HST workstation implies that the service time distribution at the workstation remains consistent across different 29 numbers of jobs present in the system. However, the monotonicity property cannot be satisfied unless all service times are exponentially distributed. Therefore, it is less likely for any CQN or OQN with nonexponential service times to exhibit monotonic behavior after a sudden disruption. Yao and Buzacott [1986] use product form CQNs to study the performance of FMSs with unlimited local buffers compared to FMSs with limited local buffers under three possible operational scenarios. Three possible operational scenarios to deal with any blocking are fixed routing, fixed loading, and dynamic routing. They conclude that dynamic routing has clear advantage in increasing throughputs when local buffers have limited capacities. Other studies [Kimemia and Gershwin 1985], [ShalevOren et al. 1985] used nonproduct form CQNs as an evaluative tool to test their new operational policies such as loading/routing and scheduling schemes. Several researchers used a nonproduct form CQN framework to study common behaviors of FMSs under a different set of system constraints or variables such as workstation breakdowns and limited buffers on each node so even blocking can be considered. Other studies extended the scope of QN modeling for FMSs even to those that are traditionally considered FMS supporting systems such as maintenance float networks and control systems. Lin et al.[1994] used CQNs with Buzen’s recursive algorithm to model a maintenance float network problem for FMSs. 30 Based on the approach taken to solve the product form of the equilibrium probability distribution, CQN can be further broken down into several subclasses. According to Seidmann et al. [1987], there are three subclasses for CQN analytic models. These are mean value analysis (MVA), the convolution technique (an extension of Buzen’s [Buzen 1973] recursive algorithm), and approximate mean value analysis (PMVA). CANQ uses the convolution technique. But, most other models are solved by either MVA or approximate MVA depending on whether or not the model will have a final product form as its equilibrium probability distribution of parts or pallets over the network. If the analytic CQN model results in a nonproduct form, the approximate MVA is applied. On the contrary, if a product form solution is found, either the convolution technique or mean value analysis can be applied. Mean value analysis (MVA) is a simplified technique to solve a CQN for a limited set of quantities, such as mean queue sizes, mean waiting times, utilizations, and throughputs, in a recursive manner without calculating normalization constants and product form joint distributions. MVA reduces a significant amount of the computational burden associated with complex CQN problems. In reality, the joint equilibrium distribution often contains far more detail than is needed for practical analysis. As matters of fact, the computational burden of calculating the normalization constants can easily outpace the efficiency of CQN analysis as the system gets more complex. Thus, a simplified way to get the most common performance measures was needed for larger scale product form CQN problems without going through 31 the somewhat tedious computational steps in traditional CQN analysis [Reiser and Lavenberg 1980]. MVA is based on a relationship between the mean waiting time and the mean queue size of a system with one less job. This relationship is also called the arrival theorem. The distribution of the network state seen by a job arriving at any node in the network is the same as the distribution of the network state a random observer would see with () parts circulating in the network. 1−n Several assumptions must be initially made in order to apply MVA to analyze CQN type FMSs. Some of these assumptions are: (a) the processing time of a part at each workstation has an exponential distribution, (b) the routing of parts to the next machine is chosen probabilistically, and (c) all workstations choose their next part according to the FCFS queue discipline. In reality, these assumptions have to be relaxed somewhat because there are many different classes of FMSs in existence based on their configuration and operational characteristics. Three major classes of FMSs are identified based on their modeling constraints such as pallet type, queue discipline, and prescribed production ratios [Dallery 1986]. These classes are monoclass models, multiclass models with fixed queueing disciplines, and multiclass models with prescribed relative throughputs. Viswanadham and Narahari [1992] identify nine common characteristics of automated manufacturing systems that could lead an FMS CQN model to a nonproduct 32 form. These are: (1) nonexponential service time distributions, (2) scheduling discipline other than FCFS, (3) different processing priorities among multiple part types, (4) new production control policies such as a pull system, (5) assembly operations (joining of parts), (6) breakdowns, (7) dynamic routing such as shortest queue routing (SQR), (8) blocking, and (9) multiple resource holding such as a part seizing a fixture, a pallet, a machine, and a set of tools in order to be processed. For example, a nonproduct form solution would result from an FMS where the routing is predetermined and the processing times at some workstations are not exponentially distributed. Another nonproduct form characteristic that is quite common is for each workstation to have a queue discipline other than FCFS. For this reason, Cavaille and Dubois [1982] proposed a heuristic based on MVA, called the approximate MVA method, to model an FMS with near deterministic service times using MVA with an additional approximation term. The FMS model used in the Cavaille and Dubois’s study has FCFS servers where the various part types may require distinct service time and routing requirements. Approximate MVA methods have been extended to handle FMSs with priority scheduling disciplines [ShalevOren et al. 1985]. The first successful computerized MVA application in overall production planning and control problems includes two different decision categories [Hildebrant 1980]. The first category deals with resource decisions and the second category deals with temporal decisions. Resource decisions are concerned with choices among different resources and temporal decisions deal with job sequencing and scheduling issues. This 33 model was subsequently further improved to demonstrate its accuracy and robustness even on larger scale models [Suri and Hildebrant 1984]. Zhuang and Hindi [1990] developed an extended MVA approach that can handle multiple class queueing networks with limited queue capacities to model an FMS with a central material handling system (MHS) and exponential service time distributions including one by the MHS. Zhuang and Hindi also develop an approximate MVA to evaluate an FMS with a single cart MHS, the assumption of exponential service time distribution, and limited local buffers which leads to block and wait mechanisms. Tetzalff [1996] utilizes approximate MVA to evaluate the performance of a tool management system in an FMS. The part transportation system is modeled as a product form CQN and the tool delivery system is model as a nonproduct form CQN. As an indirect way to study transient behavior of FMSs using QN, Chance [1993] studies the relationships among various conjectured upper bounds on transient mean total waiting times in OQNs with some assumptions such as Poisson arrival process, exponential service time distribution, and multiserver queue nodes within the network. He concludes that after some small initial period, transient mean total waiting times in the Jackson network are bounded above by the weighted sum of expected waiting times in queues. The expected network waiting time can be found from simulation and the expected waiting times for queue can be estimated through the program described in Kelton and Law [1985]. These conjectured upper bounds provide the lower bounds on the time required for the transient mean to approach its steadystate value. However, this 34 method can be applied only to OQNs with exponential service times. Also there is a significant drawback that the author acknowledges. The gap between the conjectured upper bound and actual transient mean on total waiting time grows wider as the network gets larger, which implies that the method is not robust enough to be applied on large scale networks. The study done by Suri [1985] supports the position that any OQNs with exponential service time distribution and some specified initial conditions are most likely to behave in a monotonic way during their transient period. Conversely, this implies that there may be a chance for either a CQN or an OQN with nonexponential service time distribution to exhibit nonmonotonic behavior during the transient period after a disruption on its sample paths. Thus, a transient analysis approach by asymptotically connecting individual steadystate values approximated for the particular number of jobs that can be present in the system during the transition period may not always provide a realistic view of true system behavior during a short time window. This issue leaves an open question for further research investigation. 2.1.2 Conclusion Table 1 summarizes the previously discussed major developments in QN analysis of FMSs. Most works are focused on steadystate behavior of the system. 35 Table 1. Major Developments in FMS Performance Study Using QN Analysis Title of Method/ Study Author(s) Year Type of QN (Approx. Method) Limits /Restrictions Type of Analysis Focus of Study/ Findings CANQ Solberg 1977 CQN Single part with a central servers Necessary assumptions for a product form solution SteadyState Analysis To study effects of various operational strategies (production planning) on system throughput Models for understanding FMSs Buzacott, Shanthikumar 1980 OQN Basic OQN assumptions SteadyState Analysis To evaluate FMS with jobs waiting for release in the dispatching area MVA (earlier version of MVAQ) Hildebrant 1980 CQN (MVA) Exponential processing times Probabilistic routings FCFS queue discipline SteadyState Analysis To study production planning and control issues related to failure prone FMSs CANQ (extended) Stecke 1981 CQN Multiple part type Processing times at each FCFS station are independent of Part Type SteadyState Analysis Effect of various operational strategies on system throughput of FMS with multiple part type Heuristic methods based on MVA Cavaille Dubois 1982 CQN (Approximate MVA) FCFS servers various part types require distinct service time and routing requirements SteadyState Analysis To study the performance of FMS with predetermined part routings and nonexponential service times MVAQ Suri, Hildebrant 1984 CQN (MVA) Exponential Service times Probabilistic routings Multiple part type modeled Proven robustness on larger scale models SteadyState Analysis To use MVA for practical planning and control of an FMS The method of Coaxian Phases Yao, Buzacott, 1985 OQN General service times Limited local buffers SteadyState Analysis To evaluate the performance of an FMS with general service times and limited local buffers 36 Table 1 (continued). Major Developments in FMS Performance Study Using QN Analysis Title of Method/ Study Author(s) Year Type of QN (Approx. Method) Limits /Restrictions Type of Analysis Focus of Study/ Findings Diffusion approximation Yao Buzacott 1985 CQN Coefficients of variation of interarrival and service time distributions is less than 0.05 Steadystate Analysis To approximate the behavior of FMS with nonexponential workstations Approximate MVA (extended) ShalevOren, Seidmann, Schweitzer 1985 CQN (Approximate MVA) Similar to Cavaille and Dubois’s approximate MVA assumptions Steadystate Analysis To study impact of priority scheduling discipline Heuristic based approximation of MVA Kimemia, Gershwin 1985 CQN (Approximate MVA) Similar to Cavaille and Dubois’s approximate MVA assumptions Steadystate Analysis To optimize the flow of the operation Exponentialization Yao, Buzacott 1986 CQN Necessary assumptions for a product form solution except general service times Steadystate Analysis To evaluate the performance of FMS with general service times using a product form CQN analysis ON modeling FMSs using CQNs Dallery 1986 CQN(MVA) CQN(Approximate MVA) Necessary assumptions for product form CQN analysis, MVA, and approximate MVA Steadystate Analysis Identified three major classes of QN based FMS models Models of FMSs (with various configurations) with limited local buffers Yao, Buzacott 1986 CQN Various nonexponential service time vs. exponential service time distributions Dynamic routing vs. fixed one Unlimited vs. limited local buffers Steadystate Analysis FMS with small local buffers are robust to various nonexponential processing time distributions MVA (extended) Zhuang, Hindi 1990 CQN (MVA) Limited queue capacity exponential service times A central server (material handling system) multiple part types Steadystate Analysis To extended MVA approach to multiple part type FMS with finite queue capacity Approximate MVA Zhuang, Hindi 1991 CQN (approximate MVA) Exponential service times limited local buffers A single cart MHS (block and wait mechanisms) Steadystate Analysis To study behavior FMS with a single cart MHS 37 Table 1 (continued). Major Developments in FMS Performance Study Using QN Analysis Title of Method/ Study Author(s) Year Type of QN (Approx. Method) Limits /Restrictions Type of Analysis Focus of Study/ Findings Conjectured upper bounds on transient mean total waiting times in QNs Chance 1993 OQN Poisson arrival process Exponential service time multi server queues Size of the network Transient Analysis To find conjectured upper bound on the mean total waiting time in Jackson Networks (applicable to some FMS) A maintenance float network problem Lin, Madu, Kuei 1994 CQN Necessary assumptions for product form CQN analysis Steadystate Analysis To find the optimal capacity of redundant system for a failure prone FMS A QN model for FMSs with tool management Tetzalff 1996 CQN (approximate MVA) Product form CQN requirements for MHS Non product form CQN for the tool delivery system Steadystate Analysis To study the performance of a tool management system in an FMS The QN approach is generally not an effective way to study detailed behavior of the system within a short time horizon. Instead it provides an idealistic picture of longterm behavior if the system reaches steady state. The most critical role of transient study in an online decision making environment is not only to detect any possible disturbances in steadystate performance but also to investigate the detailed nature of the system reactions brought by such disturbances. The detailed nature of such system behavior consists of the duration of a transient state, the magnitude of any reaction, under or over reaction if any, and the value of the new steadystate mean. Using this knowledge the decisionmaker can proactively engage in any remedial action to minimize or prevent the negative impact caused by such a disturbance in steadystate sample paths. 38 Since queueing networks are an aggregated form to represent interactive neighboring queueing systems as a whole, the equilibrium conditions for the entire network must be satisfied in order to directly or indirectly estimate the network performance. Even transient analysis on OQNs such as the one proposed by Chance [1993] to conjecture the upper bounds for the sample paths of total mean waiting time of the network during a transient period, has many limitations as a robust means to facilitate online transient analysis. Therefore, we can conclude that instantaneous transient analysis through ordinary QN analysis is practically infeasible because any exact or approximated behaviors of an individual or aggregated queue(s) using QN analysis can be derived only under the steadystate assumption. However, QN’s speed, reliability, and intuitive details are appealing to many researchers and industry users who are primarily interested in steadystate performance of FMSs. The QN approach can be extensively used during planning and designing stages of an FMS. However, it appears ill suited for online based transient analysis. 39 2.2 Markov Chain Models 2.2.1 Summary of Major developments Markov chain modeling provides fundamental foundations to many analytical evaluative models. Markov models are based on a stochastic process called a Markov process that has a unique mathematical property in which any future state of the system depends on the past state of the system only through the present state. Markov chains can be effectively used to capture stochastic dynamics of many discrete event systems with a finite state space such as manufacturing systems. Despite their wellknown drawbacks as an analytical evaluative modeling tool, such as exponential growth in modeling complexity as the size of the state space (a collection of all possible system states) gets larger, Markov chain analysis can be an appropriate way to study many special cases of FMS operations. Each state in a Markov chain model usually represents a possible discrete state of the stochastic process during its life cycle. Markov chains can be grouped into either discrete time or continuous time processes. Between the two types of Markov chains, Continuous Time Markov chains (CTMC) have been extensively used to analyze dynamic behaviors of many automated manufacturing systems [Viswanadham and Narahari 1992]. For example, studying the overall impact of a certain control mechanism over the entire system and a machine repair system with a redundant resource backup 40 system are popular areas to apply CTMC analysis. CTMCs also provide theoretical grounds for birth and death processes and time reversible Markov chains. Time reversibility is a necessary condition for product form QN analysis. Several foreseeable computational issues in CTMC modeling as the complexity of the problem grows can be identified. These issues are size, ill conditioning, and stiffness. The size issue arises when there is an exponential growth in the size of the state space as the number of available resources increases in the given system. In other words, the computational burden to calculate the coefficient matrix will rise rapidly as the state space gains more possible states. The second issue, ill conditioning, is based on the fact that small changes in the coefficient matrix can lead to large changes in the solution vector. Stiffness is a consequence of having transition rates of significantly different orders of magnitude among states. For example, for a certain CTMC, for particular states the transition rates among them can be significantly higher than the rest of transition rates among other states, which implies faster transitions between those particular states compared to other states. This can create stiffness during the computation. There are two ways, namely uniformization and numerical ordinary differential equation (ODE) solution, to solve these types of differential equations. Reibman and Trivedi [1988] conducted a survey of three numerical methods for transient analysis, uniformization, RKF45, and TRBDF2. They found that two numerical approaches, ODE RKF45 and TRBDF2, work well only for certain types of problems. On the other hand, uniformization works well for typical problems with more accuracy and efficiency. 41 Gross and Miller [1984] extend the randomization technique to Markov processes with infinite state spaces. The randomization technique was originally proposed by Grassmann [1977] and is a general nonnumerical method based technique to compute transient probabilities of Markov processes with finite state spaces through a probabilistic interpretation. Gross and Miller [1984] present an approach called SERT utilizing a generalized randomization procedure in an algorithmic way to model a continuous parameter Markov processes. SERT stands for state space (S), event set (E), rate vectors (R), and target vectors (T) that can collectively describe a general class of Markov processes. Upon successful completion of the randomization, closed form formulas for expected time averages, first passage time distribution, and expected number of events of a certain type occurring for a time interval can be constructed. This approach promises substantial relief from the computational burden associated with traditional transient Markov processes whose state spaces are quite large. The part selection policy for a flexible manufacturing cell is studied to minimize the expected shortage penalty per unit time using a semiMarkovian process [Seidmann and Schweitzer 1984]. For an FMS with block and recirculate, the workstations with finite buffers are modeled as a Markov chain model and solved even though one with a central buffer becomes substantially complicated to model [Viswanadham and Narahari 1992]. 42 Another major achievement in the study of FMS transient behavior by a Markov chain based analytical modeling approach is performability analysis. The notion of performability was first used by Meyer [1980] in the study of a degradable computing system performance. Performability analysis is a combined form of performance and reliability analysis. Performability modeling is used to study the overall impact brought by constituent subsystem failures on a particular system performance index over a finite time horizon. Performability analysis was originally designed to investigate performancerelated reliability for faulttolerant computing systems. Later the same technique was applied to automated manufacturing systems (AMSs). Even though the majority of performability studies use continuous time Markov chains with the deterministic reward structure consisting of a number of transient states and a single absorbing state, discrete time Markov chains with random rewards were later introduced [Mallubhatla and Pattipati 1994]. The notion of a Markov reward often implies the cost or reward incurred from being in a particular state at a given time. The first application of performability modeling in manufacturing systems appears in a work by Viswanadham et al. [1991]. This modeling was focused on AMSs producing a single part type. A subsequent study [Viswanadham et al. 1993] was done on AMSs producing multiple part types using continuous time Markov reward models. 43 Most automated manufacturing systems consist of numerous constituent subsystems. In reality, even the most reliable and welldesigned AMSs are subject to unscheduled and unexpected subsystem failures due to many complex mechanical interactions and functional dependencies. Especially for an FMS, a proper functioning of individual resources within the system is highly critical to its operational success because the role of each resource is often uniquely defined and tightly integrated with others to complete any planned operations. Even if the frequency of these failures is very low, most of these AMSs are built with a certain degree of redundancy so that highly expensive systems like FMSs will not be sitting idle in case of any unscheduled subsystem failures. We call these types of manufacturing systems faulttolerant systems. They are built with a certain degree of flexibility in both operation and capacity to handle limited multiple resource failures simultaneously. Due to natural time scale differences in frequencies of failure, repairs, and reconfigurations and of the part processing events, a performability model is often hierarchically devised: a higher level (longertime scale) dependability model and a set of lower level (shortertime scale) performance models. The study done by Viswanandham et al. [1995] shows that the accumulated reward over a given time interval is a solution of a set of forward or adjoint multidimensional linear hyperbolic partial differential equations. They also proposed efficient numerical methods for computing the distribution of the cumulative operational time, and the mean and variance of the cumulative production over a given time interval. One of the common difficulties in this 44 approach lies in efficient numerical methods to solve the partial differential equations in order to find the distribution of accumulated production over. ] ,0[t After occurrences of these resource failures, the system often goes through a series of possible intermediate transient states during the recovery process. The complex dynamics of the state transitions can be captured via the structure state process (SSP). The SSP is to describe the system evolution as influenced only by failures, repairs, and reconfigurations. In each structure state, the system can be associated with a different performance measure such as lead time, throughput, and work in process. The formal definitions of a structure state process and performability can be given as follows. Definition: Let be the structure state of the manufacturing system at time . Then the family of random variables )(uZ0≥u{}0),(≥uuZ having state space is called the structure state process. {mS,,2,1,0K= } If we let be rewards in the individual structure states and be a random variable over an observed period mfff,,,10K)(sYt[]t,0 with initial structure state given as Ss∈, the performability can be given as imiitfsYτΣ==0)( where iτis the total sojourn time of the SSP during []t,0 in state i. 45 The SSP can be modeled using CTMC, queueing networks, or stochastic Petri Nets. Viswanadham and Ram [1994] use both CTMC and Pertri nets to model performability of a flexible manufacturing cell (FMC) and suggest techniques for computing statistical moments of certain cumulative performance measures. Three measures: performability distribution, steadystate performability, and interval performability, are focuses of interest in performability analysis. The structure state of the SSP is a vector whose components describe the status of its constituent subsystems. The SSP is a collection of all possible structure states in which the sequence of transitions among allpossible states can be logically captured to reflect the evolution of the system during a given time horizon. Any failure prone AMS can go through a series of individual structure states within a given length of time following a resource failure. This combines both the performance and the reliability aspects of the system. Typically a part of the vector representation of the components in each state contains the total number of available machines at any point during a given time period. The current structure state changes due to failures and repairs as time progresses. A wellillustrated SSP model for a degradable (nonrepairable) faulttolerant FMS with a central server and identical machines is provided by Viswanadham and Narahari [1992]. m Gershwin’s study [Gershwin 1992] argues that the estimation of variability of production is an important measure of interest to the manufacturer. Furthermore, his study shows that the coefficient of variation of production in an actual AMS can exceed 0.1, which is considered unacceptable since high variability can cause over and under 46 production by creating either unnecessary inventory or material shortage. Therefore, finding higher statistical moments for the performability distribution is highly critical. The performability distribution is a cumulative distribution function of the performability , i.e., )(sYt{}xsYPt≤)( for Rx∈. The performability distribution and its statistical moments are used to quantify the performance and reliability of the system. A closed form expression for the performability distribution and its moments and recursive formulas to compute the moments for an nprocess system are found using a sum of simple exponential terms and double LaplaceStieltjes transformations by Donatiello and Iyer [1987]. Typically when a system with nonhomogeneous components (e.g., different types of machines) is modeled using a Markov process, the number of states in the system is the product of the number of different type components. Hence the total number of structure states can be very large. Finding statistical moments for the performability distribution is a useful way to approximate the distribution especially when the time complexity for computing the coefficients of the distribution becomes too expensive as the number of structure states grows. The same framework to find an analytical solution for the distribution of performability can be applicable to nonrepairable systems as long as the transitions between states are modeled by an acyclic Markov chain. n47 A similar but improved modeling approach was proposed by Rupe and Kuo [2003] in order to lessen the complexity of the traditional performability model by separately modeling independent failure and repair processes of each system and combining the results at the conclusion. This approach is designed to provide an efficient general architecture to be applied to a wide variety of FMS configurations including spare part inventory to repair down machines. Despite their promising findings, the complexity of the model can still grow significantly if each machine type has different failure and repair processes. 2.2.2 Conclusion Markov chain models are based on either Markov or semiMarkov processes that are the two most important subclasses of stochastic processes. Markov processes provide underlying theoretical foundations for many queueing theory based analytical modeling approaches. Significant contributions in FMS transient analysis are made by Viswanadham et al. [1991], Viswanadham [1992], Viswanadham and Ram [1994], Gross and Miller [1984]. In general, Markov chain models are intuitive and easy to understand. However, there are a few major drawbacks as Narahari and Viswanadham [1989] point out. These drawbacks are: (1) when the size of the physical system grows, the number of states in the Markov chain grows exponentially and this makes Markov analysis computationally 48 expensive; (2) as the number and complexity of interactions increases, visualizing the Markov chain states and the transitions among states becomes difficult; (3) the existence of two or more time scales can cause tremendous computational difficulties. Solving ChapmanKolmogorov equations that correspond to first order linear differential equations with constant coefficients, provides closed form solutions to approximate individual transition probabilities or the state probabilities as functions of time. There are basically two ways to find the solution for these first order differential equations. The first method is a numerical method based technique and the second one is nonnumerical method based technique. With either technique, finding closed form solutions can become problematic as the size of the state space grows. Also, building a Markov chain model using a predefined state space, which often focuses on one aspect of the system performance, still requires intuitive and creative modeling efforts. Shifting focus from one to the other or changing configuration of the system often requires redefining of the state space which can result in rebuilding the entire model. This process requires a significant amount of human modeler’s analytical skills and modeling expertise. Hence, this cannot be easily transportable to a fully automated system with a noninteractive modeling environment. Unless the system configuration never changes, in other words, the state space (dynamics of the model) remain unchanged and only the associated transition probabilities (performance parameters) change, reconfiguration of model on the fly will be challenging for online transient analysis. Therefore, it can be concluded that constructing Markov chains is not a practical 49 approach to building a rapidly reconfigurable online evaluative model focusing on transient behavior of a dynamic system. 2.3 Simulation Modeling 2.3.1 Summary of Major Developments During the past several decades, computer simulation has been an indispensable tool for many system engineers to numerically study the behavior of complex discrete and nondiscrete (continuous) event systems. Since many improvements have been made in simulation technology, such as improved usability, modeling power, and speed, simulation analysis has received greater attention as an effective modeling tool. Despite the availability of many effective system modeling methods, simulation modeling frequently becomes a favorable choice over other evaluative tools because it gives invaluable understanding of how the system operates as opposed to how everybody thinks it does [Pegden et al.1990]. In general, simulation should be used whenever detailed results are needed such as in a transient behavior study. The price to be paid for being detailed is that simulation takes a relatively longer time to develop, usually requires more input data than other analytical evaluative modeling approaches and often requires a great deal of computation time [Suri and Hildebrant 1984]. In addition, a steadystate analysis of a system by the 50 simulation modeling approach requires a statistically valid output analysis to find true steadystate means if there exists a significant initial bias on its outputs due to the model’s startup conditions, often called a warmup period. Because of this time consuming modeling process and cumbersome output analysis, the simulation modeling approach has shown only limited application in online decision making schemes such as online production control systems. Nevertheless, a great deal of research and efforts have been put into the area of online simulation as a viable approach to predict the shortterm system behavior for untested operational scenarios in typical manufacturing control environments. Especially with the current pace of progress in parallel and distributed computation, processing speed of inexpensive CPUs, and various model simplification techniques, simulation modeling to study detailed behavior of a system within a given time window has a promising future as a practical online based system modeling approach. Traditionally, simulation modeling has been extensively used in design, planning, scheduling, and control of FMSs. These studies typically seek the optimal configuration for a hypothetical system or the best operational policy for an existing system. The modeling oriented languages, such as GPSS/H, SLAM II, SIMAN, SIMSCRIPT, and ARENA, etc., have been favored over general programming languages by many simulation practitioners. Most of these modeling oriented languages possess realistic abstraction capability for individual behavior and interactions among various modeling entities, automatic statistic collection features, extensive runtime error detection, many 51 builtin sophisticated event handling mechanisms, and powerful addin animation features. However, there is some modeling inefficiency associated with these general purpose simulation languages to model complex manufacturing systems like FMSs because they are designed to model a wide variety of discrete event systems as well as manufacturing systems using generic building blocks. As Rolston [1985] points out, modeling FMSs with a general purpose simulation language often requires highly trained programming skills to conceptualize the entire system in terms of entities, queues, servers, and resources. For this reason, dedicated simulation languages for various manufacturing systems were developed, such as MAP/1 [Rolston 1985], GPSS/H [Schriber 1985], XCELL+ [Conway et al. 1987], WITNESS [Gilman and Billingham 1989], and MAST [Lenz 1989]. Fixtures, conditional part routing, and conveyers often require special modeling elements to capture their unique behaviors. For example, a conveyor belt is a material handing system but often acts as a finite storage buffer. Also, based on the way of the conveyer belt is used in the system, securing consecutive spaces on the conveyor belt is crucial for undisrupted traffic of a particular group of parts. MAP/1 is a simulation language that has been developed to capture such unique behaviors of FMSs [Rolston 1985]. Similarly, a GPSS/H model is proposed to represent a hypothetical FMS using a modular design approach to explore the concept of a universally applicable simulation model with minimal modifications possible for various FMSs [Schriber 1985]. For the GPSS/H model, some simplifying assumptions have to be made. These assumptions are 52 no machine breakdowns, negligible part travel time between any two points in the system, and no traffic congestion. Because of the complexity of most simulation models, a formal scheme to convey the underlying logic of the system using common words is needed. An activity cycle diagram is a graphical presentation to describe the underlying logic of a discrete event system that can be easily understood by nonexperts. Despite this effective formalism to depict the dynamics of a complex manufacturing system such as an FMS, the influence of a particular simulation language used to construct the models based on the activity cycle diagram can be found. Hlupic and Paul [1994] build a conceptual FMS simulation model using activity cycles diagrams to conduct a comparative study to show the apparent influence of the simulation package used for the model construction. There are two ways for simulation to be used in production control and planning environment: the first is online based simulation analysis and the second is offline based. Most simulation modeling efforts in FMS operation management have concentrated on offline steadystate analysis. Simulation modeling has been extensively used as an evaluation tool to test whether a suggested dispatching rule or schedule really works better than other alternatives. The schedule or dispatching rule in an FMS normally determines which parts are introduced into the system at what time and which part to load next into a particular machine. Comprehensive literature reviews on FMS scheduling using offline simulation as an evaluative tool can be found in [Gupta et al. 1989; Hutchison 1991; Basnet and Mize 1994]. 53 The other prominent application area for offline based simulation study is FMS design. Abdin and Mohamed [1986] conduct a simulation study to examine FMS design issues regarding the maximum number of pallets for each part type and the optimal conveyor speed under two distinctive job sequencing rules, namely the LPT and PROB rules. LPT gives the job with longest processing time the highest priority while the PROB rule orders work pieces according to their highest content in the workinprocess. The study concludes that for that particular cell configuration LPT is favorable over PROB and allocating four pallets of each part type can ensure a smooth production against various changes. A significant number of recent research efforts using simulation applications in FMS production planning and control have shifted their focuses to online and realtime applications. M. Kim and Y. Kim [1994] propose simulationbased realtime scheduling for an FMS. In this study, they argue that the dynamic and uncertain nature of system states may make offline scheduling impractical for most FMSs. In general, FMSs are more sensitive to system disruptions than conventional manufacturing systems because of their tighter synchronization, system integration, and interdependencies among many automated system components. Hence, FMSs require an immediate response to changes in their system states, and this can be achieved through implementing online scheduling and control.54 Harmonosky [1993] addresses two key issues, the simulation run length issue and lookahead horizon assumptions, for using simulation for realtime production control. In this study, Harmonosky identifies the types of manufacturing systems suited to pursuing simulation as a realtime control aid: systems with longer average processing time, WIP performance measures, and high flow shop characteristics are believed to take smaller CPU time and fall into this category. The biggest obstacle for simulation to become a practical online evaluative tool in realtime decision making environments has been its lengthy execution time. In addition to a rapid improvement in the speed of inexpensive CPUs, there have been many ongoing research efforts to make simulation experimentation a more practical methodology for online use. In order to shorten the lengthy execution time of simulation without compromising statistical precision, the majority of online steadystate simulation analysis schemes have adopted a form of executiontime reduction techniques, such as concurrent simulation, distributed simulation, model simplification, and the reverse simulation method. Each of these are discussed more fully below. A concurrent simulation means that a separate, independent processor is dedicated to running a simulation under each set of input parameters. Concurrent simulation is proposed as a primary analysis tool to evaluate candidate schedules in online production control environment. It utilizes parallel computing techniques to mathematically decomposing a scheduling problem into a parallel hierarchy [Davis and Jones 1988]. The success of this conceptual scheduling algorithm lies in the integration and development of key technologies, such as compromise analysis, conflict resolution, and efficiency of 55 concurrent simulation techniques. Also, the authors acknowledge that the optimality of the found schedule cannot be guaranteed and the probability of exact implementation of the suggested schedule is close to zero due to the tradeoff between a guarantee of feasibility and operational efficiency. Different from concurrent simulation, distributed simulation uses a technique to partition a single simulation run into several independently executable small components (routines) using parallel computation techniques. Distributed simulation focuses more on a distributed simulation algorithm (software) using parallel computation techniques rather than employing multiple processors (hardware) to host multiple simulation runs. In other words, a sound simulation model of concurrency is more important than the multiprocessor hardware itself. Traditional discrete event simulation is designed to be executed by a single processor sequentially following an event calendar as the single stepping clock advances. On the contrary, for distributed simulation each simulation component is run concurrently and brought together to collectively present the overall behavior of the system. A distributed simulation system must explicitly coordinate the advance of time in order to maintain temporal consistency among its components. There are two distinct tasks to maintain time among distributed simulation components: the movement of time and the coordination of time movement. Based on methods to coordinate time advances between concurrent simulation components, distributed simulation algorithms can be classified into two classes. 56 The first class is ChandyMisra (CM) simulation, also called pessimistic simulation [Peacock et al. 1979; Chandy and Misra 1981]. The mechanism holds back processing because it assumes that components will communicate out of sequence. The CM algorithm does not prevent simulationinduced deadlock. Thus, CM works best in tightly coupled simulations where objects are highly synchronous. The second class is Time Warp (TW) simulation, sometimes referred to as optimistic simulation [Jefferson 1985; Jefferson and Sowizral 1985]. It relies on the ability of an object to rollback its present state to that of some previous time. Time Warp is good for loosely coupled, highly asynchronous systems but is inefficient when models have mixed time scales or diverse interaction behaviors. McAffer [1990] proposes the Unified Distributed Simulation (USD) algorithm as a compromising approach. This approach is loosely based on the Time Warp algorithm. By explicitly defining risk and aggressiveness parameters for each model, simulation models with different behaviors can be mixed within one simulation. Prassad and Deo [1991] propose a parallel algorithm for discrete event simulation on exclusiveread exclusivewrite parallel randomaccess machines (EREW PRAM). The proposed algorithm uses a parallel data structure as an event queue, called a parallel heap, which allows simultaneous insertions and deletions of messages maintaining priorities among messages in a reasonably small amount of time using multiple processors. Another way to use simulation for real time scheduling, control, and monitoring was proposed by Harmonosky [1990]. Instead of adopting a concurrent simulation 57 approach, she suggests interfacing simulation with the physical system to run two separate modes. Figure 1 depicts the structure for such an approach. The first mode is a monitoring mode. It is used when the model is directly linked to the physical system, continuously receiving status information from various system elements. The second mode is a decisionmaking mode and is used when the model evaluates different control decision options through traditional offline runs. The issues regarding this approach are how to balance the tradeoff between a long enough time horizon to obtain statistically valid results and a shorter response time required to make prompt decisions. A similar approach interfacing a SIMAN based simulation model to a realtime control database is proposed to evaluate work order release sequences based on measure of performance by Muller et al. [1990]. Unlike most simulation studies, the evaluation is based on the transient behavior of the system and not steadystate performance. The control system looks at the time window in which the work order is predicted to be completed in order to determine if a particular work order sequence meets due date requirements set in advance by the MRP system. Ten replications are made to construct the confidence intervals (CI) on the completion time for a work order in order to be compared with actual data. Surprisingly, results indicate that only 43.6% of actual completion times occur within these estimated CI. The authors attribute the occurrences of work orders outside the confidence interval mainly to the uncertainty at the finishing cell. 58 System Control ComputerSystem StatusDecisionNeeded?Update simulation w/Current System StatusSpecify OptionsSimulate OptionsAnalyze & SelectOptionYesNoOption 1Option 2Option n...Option 1Option 2...Option nSelected Option Figure 1. Scenario for Interfacing Simulation with Physical System for Realtime Control [Harmonosky 1990] Even though the study done by Sims [1997] does not directly discuss the application of realtime simulation, he argues that, for any scheduling problem with a shortterm goal, running simplified simulation models with deterministic values would provide a realistic view and a faster response. Reverse simulation is used when the desirable range of values of the performance measure are known and used as inputs to the model so that the steadystate mean for the performance measure can be reached at a faster rate with fewer samplings. Lee et al. [1997] propose a single run optimization method to take advantage of the reduced execution time using the reverse simulation technique and chaos theory. 59 As discussed in Chapter 1, simulation can be classified into two categories: terminating and nonterminating. Nonterminating simulations are sometimes called steadystate simulations. Terminating simulations are run only until some stopping criterion is met. The stopping criterion is normally set as a system event that is designed to end the simulation run based on the nature of system or the purpose of analysis. On the contrary, nonterminating simulations can conceptually run indefinitely after they reach a steadystate or stationary pattern of behavior. With use of a proper warmup period deletion technique, most nonterminating simulations can be stopped at the point where there are sufficient observations for statistical accuracy and the least significant amount of influence from the truncated initial bias, often called the warm up condition. Most simulation languages have some form of builtin statistical output analyzers. These builtin statistical output analyzers are often inaccurate and misleading because they tend to ignore common startup problems and autocorrelation among observations [Seila 1990]. A simulation experiment without a valid statistical output analysis is meaningless. There are clearly two different classes of output analysis that can be applied to find statistical means based on whether the simulation is terminating or nonterminating. Different types of output analysis are covered in detail in several works [Seila 1990; Law and Kelton 1991; Banks et al. 1996]. Typically, a steadystate simulation with particular input parameters can be carried out by a single but reasonably lengthy replication with an output analysis using a technique like the batch means method. These techniques find statistically valid steady60 state means from a stochastic process that represents a particular performance measure. On the other hand, the run length in a terminating simulation is dictated by the terminating event or condition and this event or condition often limits the number of observations that can be collected from a single replication for the statistical output analysis. For a statistically valid output analysis one cannot depend on a highly autocorrelated sequence of a limited number of observations from a single run. Therefore, repeating a single run a total ofRtimes is required for terminating simulation to have observations in each replication rnr so that it can have statistically independent and identically distributed Rsample means. Terminating simulation can be effectively used as a lookahead performance evaluator in an online production control environment. The chronologically captured behavior of a particular performance measure from a terminating simulation during the transition period following an unexpected disruption may provide realistic and meaningful information to online based decision making for automated disruption handling. Such attempts can be accomplished by adopting a hybrid modeling approach, often called metamodeling. Metamodeling maps simulation output to a corresponding mathematical model using techniques such as regression or time series analysis. Lin and Cochran [Lin and Cochran 1990; Lin and Cochran 1990; Lin et al. 1998] proposed a metamodeling approach using terminating simulation. They argue that relying on the traditional terminating simulation method to investigate transitional behaviors of a manufacturing system can be expensive and impractical for real time production control. 61 2.3.2 Conclusion Many researchers and systems engineers studying the detailed behavior of complex systems such as FMSs have favored discrete event simulation as their preferred modeling tool. However, its limitations as an evaluative modeling tool, such as lengthy model development time, detailed input data requirement, lengthy simulation execution time, and necessary but cumbersome statistical output analysis procedures have kept simulation from becoming a practical analysis tool for online decision making. Recent improvements in simulation usability, modeling power, and speed have started receiving increased attention from both the research community and industry. In addition to these improvements, there have been considerable ongoing research efforts to make a simulation run faster and shorter using techniques such as distributed simulation, concurrent simulation, model simplification, and reverse simulation. There are clear differences between terminating simulation and nonterminating (steady state) simulation analyses. Nonterminating simulation is often useful to predict shortterm effects of disruption(s) on a particular system behavior. The majority of simulation modeling approaches proposed and explored so far within a framework of online decisionmaking, including online production control systems, have focused only on steadystate simulation. Even for a dynamic production environment, such attempts tend to focus only on the newly shifted steadystate mean after the disruption rather than intermediate transitional behaviors. 62 Using terminating simulation in a traditional way is very costly and impractical as a part of an online production control system such as a disruption handler. Applying a hybrid method such as metamodeling proposed by Lin [1990] combining terminating simulation and mathematical modeling is one way to effectively apply terminating simulation in such an online decision making support system. The drawback of such approach is the difficulty encountered as an online based noninteractive model constructor to choose the right time series model to represent dynamic characteristics and the complexity of the system’s possible volatile behavior following the disruption. This can become a critical issue especially when a composite model, a linear combination of several mathematical models, has to be built. Thus, in order to effectively use Lin’s approach for the fully automated and selfcontained FMS online controller there is a need to adopt a nonparametric method to build the model, such as applying effective neural network architecture. 63 2.4 Stochastic Petri Nets 2.4.1 Summary of Major Developments This study presents a brief history of Petri net based approaches in systems modeling and focuses on their applications in FMS transient and steadystate performance analysis. First, we need to look at some elementary definitions in classical Petri nets and other subclasses such as Stochastic Petri nets (SPNs) before discussing major developments in this area. Petri nets (PNs), also known as placetransition nets (PTNs), were proposed to graphically model discrete event dynamic systems by Carl Adam Petri [1962]. Petri nets were designed to model systems with deterministic behaviors. Classical Petri nets are useful for investigating qualitative or logical properties of concurrent systems, such as mutual exclusion and presence or absence of deadlocks. Recently, PNs have emerged as a powerful performance modeling tool by incorporating stochastic time functions for analyzing asynchronous concurrent systems that exhibit nondeterministic behaviors. As Kamath and Viswanadham [1986] point out, Petri nets have some noticeable advantages over other system modeling approaches. These advantages are: (1) easy visualization of complex systems using a powerful graphical presentation scheme, (2) modeling capability for hierarchical decompositions, (3) relatively welldeveloped analysis techniques, (4) wellformulated schemes for system design and synthesis, and (5) dual 64 analysis capability for both quantitative (performance evaluation) and qualitative (deadlock detection) characteristics using timed Petri nets. Formally, a Petri net is a bipartie graph (a graph with two types of nodes) and can be presented by three types of objects, namely places, transitions, and directed arcs connecting places to transitions and transitions to places. Pictorially, places are depicted as circles, transitions are depicted as boxes or bars. A place is an input place if there exists a directed arc connecting the place to a transition. A place is an output place if there exists a directed arc connecting a transition to the place. Typically, places represent preconditions or postconditions and transitions represent events. The presence of a token (a black dot) inside a place often indicates that the condition is satisfied. For example, input places may represent the availability of particular resources, transitions represent their use, output places represent release of the resources. Over the years Petri nets have been enhanced to improve their somewhat limited initial modeling capability. For example, to overcome shortcoming of being unmanageably large and complex in modeling of a concurrent system using a placetransition net (PTN), colored Petri nets (CPNs) are introduced to maintain a manageable size of the net [Jensen 1981]. Representation of an equivalent model of a traditionally large and complex system using CPN is simpler and more concise in comparison to using a traditional PTN. In addition, CPNs are capable of capturing complex functional dependencies between the color of transition firing and colors of required tokens. 65 By changing the placement of tokens on possible subsets of places, which may reflect the occurrence of events or execution of operations, one can capture and investigate dynamic behavior of the modeled system. The flow of tokens is governed by both enabling rules and firing rules. There are several key structural properties that can be exhibited by a certain class of Petri nets. These structural properties for Petri nets are: pure, boundedness, safe, live, dead, deadlock, mutual exclusion, reversibility, home state, concurrency, conflict, asynchronous, nondeterminism, instantaneous, and union of Petri nets. The detailed definitions for such properties can be found in various articles [Peterson 1977; Agerwala 1979; Kamath and Viswanadham 1986; Zurawski and Zhou 1994]. Among these properties, pureness, boundness, and liveness are necessary properties to capture important qualitative characteristic such as presence of deadlock in a Petri net model of any asynchronous concurrent system. To conduct quantitative performance evaluation for a system during time evolution, the concept of time has been added to the definition of Petri nets. There are two ways to introduce the time elements to a Petri net: the first one is to attach time to transitions [Ramchandani 1973; Ramamoorthy and Ho 1980; Zuberek 1980; Molloy 1982]; second one is to associate time with places [Sifakis 1977; Bruno and Biglia 1985]. The choice of associating time with transitions is more popular in the literature than associating time with places [Viswanadham and Narahari 1992]. Petri nets with time functions are called timed Petri nets. There are two types of timed Petri nets based on the 66 nature of the time function: one is deterministic timed Petri nets; and the other is stochastic timed Petri nets. Early work related to timed Petri nets is mostly confined to deterministic timed Petri nets [Ramchandani 1973; Sifakis 1977]. Later, the concept has been expanded to include random time duration [Natkin 1980; Molloy 1981]. We call Petri nets with random time delay for their transitions Stochastic Petri nets (SPNs). When random variables representing time delay are of general distribution rather than exponential, the resulting net model can not be solved analytically as we have seen in similar queueing network models with nonexponential service times. Thus, simulation or approximation methods are required to analyze the model. However, when the time delay for each transition is assumed to be stochastic and exponential, the resulting net can be analytically solved. These Petri nets are called exponential timed Petri nets (ETPNs) [Viswanadham and Narahari 1992]. When ETPN models allow for immediate (zero time delay) transitions, we call these SPNs generalized SPNs (GSPNs). Studies individually done by Natkin [1980] and Molloy [1981] have shown that the marking process of an exponential (or geometric) timed Petri net is a continuous time Markov chain (CTMC). Thus, both ETPN and GSPN models, including extensions such as priority transitions, inhibitor arcs, and probabilistic arcs can be directly converted into their equivalent continuous time Markov chain (CTMC) models, and analyzed using a Markovian analysis method. As we discussed earlier in Section 2.2 Makov Chain Models, the CTMC modeling approach has its own inherent shortcomings as an effective onlinebased transient 67 performance analysis tool in addition to drawbacks typically associated with Markov chain models. These shortcomings are associated with solving Kolmogorov backward or forward differential equations in the form of first order linear differential equations to find a closed form solution to approximate individual transition probabilities or state probabilities as a function of time. As Molloy mentions [Molloy 1985], for quantitative analysis of system performance, stochastic Petri nets do not provide more modeling power than Markov chains, but they provide a better human interface. By using a GSPN representation on appropriate discrete event dynamic systems, Markov chains may be generated and solved automatically. The clear advantage of using GSPN over Markov chains lies in enabling the system designer to specify the system operation in a concise form that can be verified during the generation of the reachable tree. In comparison to product form queueing networks, GSPNs are more powerful because they can represent nonproduct form features [Narahari and Viswanadham 1989]. Despite its continuous expansion and enhancement in modeling capability and flexibility, the abstraction power of ordinary Petri nets is not sufficient to capture many complex industrial systems, such as manufacturing and communication systems which require the flow of different resources or messages within the system. One way to model such systems is to construct a model in such a way that the flow of each resource or message is confined within a dedicated subnet. In largescale 68 systems, a number of resources or messages often share the same system that can be modeled as a single subnet. When this subnet is duplicated to model the entire system for different resources and messages, the overall model that may contain multiple replications of the same subnet may result in unmanageable graphical complexity. To resolve this issue, several methods for tokens to have distinct identity are proposed and they are often referred to as highlevel Petri nets. In highlevel Petri nets, a token can be a compound object carrying data in forms of integers, reals, text strings, records, lists and tuples. Highlevel Petri nets typically include predicatetransition nets [Genrich and Lautenbach 1991], colored nets [Jensen 1981], objectoriented nets, and nets with individual tokens [Reisig 1983]. Colored Petri nets (CPNs) were introduced to represent a complex system in a compact and manageable manner by maintaining distinct token identity through associating different colors [Jensen 1981]. In CPNs, a set of colors is associated with each place and each transition. The set of colors associated with a place indicates the color of tokens that can be placed at the place. Similarly a transition can fire based on each of its assigned colors. When a transition is fired, corresponding colored tokens are removed and added at its appropriate input and output places respectively according to the functional dependency specified between the color of the transition firing and the colors of the involved tokens. Petri nets have gained popularity as a versatile modeling and analysis tool for addressing design issues related to FMSs [Silva and Valette 1990; Zhou 1995]. 69 Typically, most ordinary PTN models have been used in the area of control system design, validation, and implementation. However, as Kamath and Viswanadham [1986] point out, the number of related studies in FMS performance modeling using Petri nets has been somewhat limited due to the limited availability of proper performance evaluation techniques for various PTN classes. A predominant number of FMS performance modeling attempts using Petri nets are based on Stochastic Petri nets with Markov chain analysis. Since bounded SPN models with exponentially distributed transition rates are isomorphic to Markov process models with a state space consisting of possible markings, a direct conversion to an equivalent Markov model can be easily achieved if the model is not too complex. Moreover, analytically evaluating equivalent Markov chain models is not a computationally difficult task as long as the level of complexity is kept minimal. As previously discussed, studying transient behavior of the given Markov chain requires finding equilibrium distributions in terms of time . To find these distributions, solving ChapmanKolmogorov equations in the form of first order differential equations either in a backward or forward form is necessary. The complexity of solving these equations can vary based on the different types of mathematical techniques that are applied. kt A simple SPN can also be easily converted to a simulation model as a nonanalytical form of performance evaluation. A transition state analysis by simulation is a more feasible approach to understand quantitative behaviors of the net than Markov chain analysis especially when the complexity of the given net is no longer considered 70 moderate. For FMS performance modeling using PTNs, converting PTNs to valid simulation models is a better approach for online production control. However, technical difficulties in conducting a reliable and fast online simulation study can still be problematic as discussed in the previous section. The majority of PTN modeling in FMS performance evaluation is based on the steadystate behavior of the given FMS. An initial investigation of applications of timed PTNs in FMS realtime control and performance evaluation can be found in the work by Dubois and Stecke [1983]. The study has concluded that timed PTN is a useful means to assess the steadystate performance as well as to detect any sequence of events which can result in deadlock in FMS realtime control. However, in reality ordinary SPN models for FMSs can become highly complex due to the fact that most control logic or operational sequences in many FMSs consists of resources that have a high degree of interaction. This type of systems is viewed as a system composed of many replications of a few basic common components. In most cases, these common components behave in a similar manner. Different arrangements of these basic components can represent various system conditions (status) and subsequent events for the given FMS. Utilizing Colored Petri nets in conjunction with SPNs is proposed as a powerful tool to verify the control logic through investigating the presence of deadlock in an FMS [Kamath and Viswanadham 1986]. Kamath and Viswanadham [1986] have shown the feasibility of direct 71 transformation of CPNs to effective simulation models. Aside from the traditional linear algebraic methods, the fast and efficient way to compute invariants of a PTN model for an FMS is found by taking the union of invariants of smaller and simpler underlying PTNs [Narahari and Viswanadham 1984]. Another study [Micovsky et al. 1990] has demonstrated that a CPN approach to validate a deadlock free design for an FMS control system utilizing a dedicated objectoriented programming tool with an incorporated simulation method is a highly effective way to prototype a new control system. A similar study [Venkatesh and Ilyas 1995] is done for modeling, controlling, and evaluating local area networks in FMSs using realtime timed PNs (RTPNs). In an RTPN, the standard TPN is augmented with two extra tuples, namely input signal vector and output signal vector, to read inputs from the system and send outputs to the system in real time. Venkatesh, Zhou, and Kaighobadi et al. [1996] find that TPNs are effective tools to study optimal operational parameters for a flexible factory automated system (FFAS) under both ‘push’ and ‘pull’ paradigms. FFASs typically comprise a strategic arrangement of flexible manufacturing systems (FMSs) and flexible assembly systems (FASs) to meet dynamically changing orders. The study shows that the configuration can result in the minimum buffer sizes and maximum system utilization when output rate is considered as the optimal solution under each paradigm. The study also concludes that the “push” paradigm performs better than the “pull” one 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


