STOCHASTIC MODELING AND CONTROL OF SOME PROBLEMS IN MANUFACTURING by Charles James Conrad A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Computer, Information and Control Engineering) in The University of Michigan 1986. Doctoral Committee: Professor N. Harris McClamroch, Chairman Professor Yoram Koren Professor Arch W. Naylor Assistant Professor Demosthenis Teneketzis Associate Professor A. Galip Ulsoy

it C'B OIN- z lj As

ABSTRACT STOCHASTIC MODELING AND CONTROL OF SOME PROBLEMS IN MANUFACTURING by Charles James Conrad Chairman: N. Harris McClamroch A control theoretic approach to some problems in manufacturing is examined. cussed. erated by underlying continuous processes. Four manufacturing problems are considered in which diffusion-threshold models are featured. The first problem considers the control of a machining process, specifically a simple drilling operation, with respect to economic criteria. Policies for scrap produ ction and the discrete nature of parts. A diffusion-threshold model for

tool wear/tool -life is utilized. Two types of policies are considered: age replacement policies in which the feedrate is constant and tool replacement is based upon age; and feedback policies in which tool wear measurements are occasionally available, the feedrate is allowed to vary, and tool replacement is based upon the wear measurements. Potential performance improvement (economic and otherwise) resulting from the additional information and control freedom present in the feedback policies is investigated. Cost per time and cost per part measures are developed for the age replacement case. A class of cost functionals, called one step costs, is introduced for the feedback case. The optimal policies for both cases are described. Comparative results are presented for a special case of interest, where tool life is assumed to obey a Taylor formula in the mean. The results from the first problem are used in the development of two additional problems. The second problem considers a machine with multiple tools. Age replacement and feedback policies are analyzed. The third problem considers decentralized control in serial transfer lines. Simulation results- for a two machine example are presented. The last problem uses a diffusion-threshold process to model work progress on a job. A supervisor is allowed to make occasional inspections of the job and re-assign resources. The scheduling of the inspections and the resource allocation are to be determined. An optimal control formulation of the problem results in a quasivariational inequality. The thesis offers new viewpoints of some contemporary manufacturing problems and demonstrates how new mathematical tools can be used to approach these problems.

Do mr tefal, frten4s, teahers, co-borekrs; each played no smal trole.

ACKNOWLEDGEMENTS One cannot hope to summarize in a few words the contributions made by so many over the years that mark the evolution from student to graduate. To those I neglect, please accept my apologies. My sincere thanks go to my advisor, Prof. Harris McClamroch, for the guidance he has given me as I wandered along the murky path that a student must take. Many thanks go to the members of my committee for the suggestions, criticisms, and insights they have offered. I am also appreciative of the assistance provided by the Robot Systems Division of the Center for Research on Integrated Manufacturing, and by the faculty and staff of CICE. I am forever grateful to Mictron, Inc. and Lamb Technicon, Inc. for the support they have given me that has made this possible. A very special thank you goes to Fran Leo for his unwavering encouragement and confidence in me. Much credit is deserved by my fellow students and especially my officemates for the contributions made through countless enlightening discussions. To each of them I say thank you. Finally, many thanks go to my family and friends for their support and understanding, and in particular to my wife, Wendy, who had to endure it all.

TABLE OF CONTENTS DEDICATION....................................................................... ii ACKNOWI LEDGEM:ENTS........................................ iii LIST OF FIGURES............................................................. vii LIST OF TABLES............................................................ rviii LIST OF APPENDICES............................................................ ix CHAPTER 1. INTRODUCTION.......................................................................... 1.1 Overview of the Research....................................2............... 2. A CONTROL THEORETIC APPROACH TO MANUFACTURING....9... 9 2.1 Introduction...................................... 9 2.2 Problems in Manufacturing....................................................... 10 2.3 Intelligent Manufacturing....................................... 11 2.4 The Control Theoretic Approach........................................ 14 2.5 Some Properties and Characteristics of Manufacturing Systems....................................... 16 2.6 A Brief Survey of Models of Manufacturing System................. 23 2.7 Discrete Event Processes Arising From Underlying Processes..................................................................................... 29 3. DESCRIPTION OF SOME MATNUFACTURING PROBLEMS....................................... 30 iv

3.1 Introduction..................................................... 30 3.2 Problem 1: The Drilling Problem............................................. 31 3.3 Problem 2: Multi-tooled Machines........................................... 35 3.4 Problem 3: Multi-machine Manufacturing Systems................. 36 3.5 Problem 4: The Supervisor's Problem...................................... 37 3.6 Summary of the Problems..................................................... 40 4. MATHEMATICAL THE ORY OF DIFFUSIONTHERESHOLD PROCESSES AND THEIR APPLICATION..................................................... 41 4.1 Introduction..................................................... 41 4.2 General Process Description..................................................... 43 4.3 Processes with Constant Coefficients......................................... 49 4.4 Processes with Measurement Feedback..................................... 58 4,5 Multi-dimensional Processes..................................................... 59 4.6 Application of Diffusion-Threshold Processes............................ 62 4.7 Relation to Other Work and Generalizations............................ 74 5. THE DRILLING PROBLEM..................................................... 78 5.1 Introduction..................................................... 78 5.2 Problem Description................................................................... 79 5.3 Survey of Related Work............................................................ 82 5.4 The Tool Wear Subproblem....................................... 83 5.5 Diffusion-Threshold Model of Tool Wear.................................. 85 5.6 Age Replacement Policies for the Drilling Problem................. 90

5.7 Feedback Policies for the Drilling Problem.............................. 100 6. POLICY COMPARISON FOR THE DRILLING PROBLEM: NUMERICAL EXAMPLES AND SIMULATIONS................................................. 112 6.1 Introduction.......................................................................... 112 6.2 Problem Description................................................... 113 6.3 Age Replacement Policy Analysis.............................................. 115 6.4 Feedback Policy Analysis................................................... 122 6.5 Simulation and Policy Comparison........................................... 128 6.6 Algorithms................................................................................. 142 7. APPLICATION OF DIFFUSION-THRESHOLD MODELS TO OTHER MANUFACTURING PROBLEMS..................................................................................... 149 7.1 Introduction.................................................... 149 7.2 Multi-tooled Machines................................................... 150 7.3 The Multi-Machine Problem: A Serial Transfer Line Example...................................................................................... 161 7.4 The Supervisor's Problem........................................ 169 8. SUMMARY AND CONCLUSIONS............................................ 176 APPENDICES................................................................................................. 180 REFERENCES..................................... 199 vi

LIST OF FIGURES Figure 4.2.4.1 Diffusion-Threshold Sample Path........................................ 48 4.3.1 Comparison of Density Functions............................................. 57 6.3.1.1 Expected Cost per Time under Age Replacement for G= 1................................................. 118 6.3.1.2 Expected Cost per Time under Age Replacement for G - 10............................................... 119 6.3.1.3 Expected Cost per Time under Age Replacement for G - 100......................... 120 6.3.1.4 Expected Cost per Part under Age Replacement for G -= 1..................................... 121 6.4.1.1 One Step Results for G =............................................... 125 6.4.1.2 One Step Results for G = 10................................................ 126 6.4.1.3 One Step Results for G = 100....................... 127 7.2.3.1 Expected Cost per Part for 2 Tools under Age Replacement for G = 1............................................................ 159 7.2.3.2 Expected Cost per Time for 2 Tools under Age Replacement for G 1................................................................................... 160 A. 1 Drill............................................................................................ 181 B.2.1 Example Curve Crossing Problem............................................. 192 vii

LIST OF TABLES Table 6.5.2.1 Policies for G 1............................................... 130 6.5.2.2 Policies for G = 10............................................... 131 6.5.2.3 Policies for G -- 100..................................................... 131 6.5.2.4 Production for 1 Week for G =-............................................. 132 6.5.2.5 Production of 1000 Parts for G - 1......................................... 133 6.5.2.6 Production for 1 Week for G = 10........................................... 134 6.5.2.7 Production of 1000 Parts for G = — 10................................... 135 6.5.2.8 Production for 1 Week for G -- 100.................................... 136 6.5.2.9 Production of 1000 Parts for G -- 100..................................... 137 7.3.2.1 Production in 2 Machine Serial Transfer Line of 1000 Parts for G 1................................................................................... 168 7.3.2.2 Production in 2 Machine Serial Transfer Line for 1 Week for G-= 1............................... 168 viii

LIST OF APPENDICES Appendix A. Drilling Terminology................................................... 181 B. Diffusion-Threshold Processes with Piecewise Constant Coefficients......................................................................................... 183 C. Properties of the One Step Cost Functional...................................... 193 ix

CHAPTER 1 INTRODUCTION A greater awareness of the importance of manufacturing, brought on by increasing global competition and the impact of a deteriorating manufacturing base, has resulted in a surge of activity in manufacturing research and development. Those new to the field are discovering what veteran workers and researchers have long known: manufacturing crosses many discipline boundaries and is rich in challenging problems. It might be expected that in any area as diverse as manufacturing there will be pockets of intense research activity and great unexplored problem frontiers. This is the case in manufacturing today. Although incremental improvements in the existing manufacturing knowledge base are important, the future probably lies in new approaches and methods. The intent of this work is to present one approach to some problems in manufacturing. The problems themselves are minuscule within the context of manufacturing. The approach, though, is believed to be far-reaching and thus of more general value to manufacturing. This approach is called control theoretic, since it draws heavily from control theory. More precisely, the approach recognizes the importance of information feedback in decision making. The concept of the control theoretic approach is to borrow from control theory the framework for approaching 1

2 the problem of utilizing information feedback in on-line control, and applying it to problems in manufacturing. The motivation for wanting to utilize information feedback and on-line decision making in manufacturing comes from the success of control theory in other areas. That is, the effective application of the ideas can potentially lead to improved performance and/or more desirable system characteristics. However, a concomitant caution must also be understood, because deterioration of performance is also possible. The effective use of information in decision making is a difficult problem. The control theoretic approach is beneficial in another way. The explicit allowance of information feedback and on-line control induces new views of old problems. This is particularly evident in the problems considered in this work. New viewpoints do not always lead to improved performance, but they usually contribute to increased understanding of the problems. This by itself is beneficial and useful. It is hoped that this work makes some contribution to the understanding of a class of manufacturing problems. 1.1. Overview of the Research The presentation continues in Chapter 2 with an expository chapter on manufacturing and the control theoretic approach. The concept of intelligent manufacturing is introduced. In an intelligent manufacturing system, the capability to acquire and process data in a timely way is assumed. This leads into the main theme of the work: How can information feedback be effectively used to improve the performance of manufacturing systems? This question is very general, but provides the motivation for most of this work. The question is explored through the examination of several example manufacturing problems.

3 The control theoretic approach is one methodology that can be used to address the main theme. The approach is not without difficulty, however. A discussion of problem issues confronting the control theoretic approach is presented. One particular source of difficulty is the modeling of manufacturing systems; more specifically, the development of models of manufacturing systems that capture the important features and maintain a compatibility with the control theoretic framework is difficult. Since modeling plays a key role in the control theoretic approach, a summary of the important features and characteristics of manufacturing systems is presented. The list is not exhaustive, but does include features not always captured in manufacturing models. These features include complexity, uncertainty, and available control mechanisms. The presence of both discrete event and continuous time phenomena in manufacturing systems is also discussed. A very brief survey of analysis methods available for manufacturing system study is given, accompanied by a comparison and critique of these methods. The chapter concludes with a discussion of an important sub-theme that transcends manufacturing: discrete events that arise from underlying continuous time processes. This view of discrete event systems is important because it allows the introduction of information feedback and control concepts into discrete event systems in a very natural way. Chapter 3 introduces four sample manufacturing problems. The first problem is called the drilling problem and is the most deeply studied problem in the thesis. Fundamentally, it is a machining economics problem, but placed in an intelligent manufacturing context. The drilling problem captures many important manufactur

4 ing features in a conceptually simple problem. The objective of the drilling problem is to determine machining parameters and make tool replacement decisions so as to achieve good system performance. The second problem is an extension to the drilling problem where multiple tools are considered. The third problem poses the question of how to control networks of machines where each machine is similar to that considered in the drilling problem. This problem is extremely challenging. Only a very simple example is considered in this work, resulting in what might best be called speculation. The fourth problem is called the supervisor's problem and is a radical departure from the first three problems. The supervisor's problem is a type of scheduling problem, but viewed in a very different way. In particular, an attempt is made to more accurately capture the dynamics of job progress and to recognize the role played by supervisory personnel in the manufacturing environment. The problem also serves as a reminder that people are an important part of manufacturing systems. Chapter 4 develops much of the mathematical framework that will be used to approach the posed problems. A class of stochastic processes called diffusionthreshold processes is introduced. The key features of these processes are a controlled diffusion process and a threshold boundary in the state space. When the diffusion first reaches the boundary, a significant event is considered to have occurred. This generally results in the re-initialization of the diffusion process and a new cycle of process evolution. The goal in studying diffusion-threshold processes is to derive a probabilistic description of the threshold hitting time in terms of the process parameters and the control policy used. The control policy may include diffusion measurement feedback.

The treatment of general diffusion-threshold processes is difficult and not considered in this work. Attention is instead restricted to simpler classes of processes where solutions are obtainable. Included are the cases of constant infinitesimal coefficients; coefficients constant between diffusion measurement feedback; and generalizations to multidimensional diffusions with independent components. The treatment of the piecewise constant coefficient case is considered in Appendix B. This development demonstrates the difficulty encountered when handling more general diffusion processes. The result for the piecewise constant coefficient case yields a partial solution to a Brownian motion curve crossing problem. This problem has appeared in the statistics literature. Application of diffusion-threshold processes to several categories of problems is discussed. Furthermore, diffusion-threshold processes play a central role in all the example problems discussed. An important feature of diffusion-threshold processes is that they combine discrete event and continuous time phenomena into a single process. This allows a different viewpoint of discrete event systems to be formed. The importance of this is believed to extend far beyond the specific problems considered in this work. Chapter 5 considers the drilling problem in detail. An important issue in the analysis of the drilling problem is the modeling of tool wear and tool life in a production environment. A brief history of this problem is presented. The model of tool wear and tool life must be compatible with the control theoretic approach in order to apply it to the drilling problem. A diffusion-threshold model is proposed which meets the requirements.

The introduction of the diffusion-threshold model allows the drilling problem to be placed in a stochastic control setting. Two classes of control policies are considered. First age replacement policies are examined. Age replacement policies assume fixed machining parameters and predetermined ages at which tools are replaced. These are the traditional policies assumed in machining economics problems. Procedures for the evaluation of two different performance measures under age replacement policies are derived. Next, feedback policies are considered in which tool wear measurements are occasionally available. The analysis and evaluation of general feedback policies for the drilling problem is very difficult. This motivates the development of a class of cost functionals called one step. One step cost functionals assess the costs and profits associated with producing the next part. They also enjoy the distinct advantage of being computable. The optimal policy for one step cost functionals is described. Implementation issues are discussed along with practical considerations that affect the control problem formulation. A limitation of the one step approach is that the long term performance of the manufacturing system cannot be easily evaluated in analytical terms. Chapter 6 addresses the problem of performance evaluation for one step policies, and the comparison of age replacement and feedback based policies. A specific problem is formulated based on drilling data and realistic economic assumptions. Age replacement analysis is carried out, and the optimal age replacement policies under two different criteria are determined. Next, one step costs are evaluated and the optimal one step policies are determined.

7 Performance assessment is done by simulation. Two different production situations are simulated with varying part worth. Age replacement and feedback policies are implemented based on the optimization results. Variations of these policies are also simulated. Economic performance and secondary performance characteristics are compared. Also given in this chapter are various algorithms used in the computation of the cost functionals and in the generation of random numbers for the simulations. The computational algorithms offer a significant speedup over numerical integration techniques. Chapter 7 discusses the other example manufacturing problems introduced in Chapter 3. The first two problems rely on the results obtained for the drilling problem. The multi-tool machine problem is shown to be a generally straightforward extension of the drilling problem. Results are obtained for age replacement and one step policies. The multi-machine problem is considerably more difficult. Attention is restricted to serial transfer lines with synchronous part transfer. A form of decentralized control based on local costs is proposed as one approach to the problem. Simulation is carried out for a two machine problem under decentralized age replacement and feedback policies. The performance of these policies is compared. A heuristic dynamic programming type of approach to the supervisor's problem is considered. The result is the derivation of a quasi-variational inequality that the optimal policy must satisfy. This result is similar to results obtained by other researchers working on different problems. However, the supervisor's problem has unique features. This development suggests a different approach to the analysis of

8 systems described by diffusion-threshold processes.

CHAPTER 2 A CONTROL THEORETIC APPROACH TO MANUFACTURING 2.1. Introduction Manufacturing presents to the researcher and practitioner an enormous variety of problems, covering diverse fields of knowledge and a spectrum of complexity. The scope of manufacturing is so broad that the development of an all encompassing, unified approach to manufacturing problems is quite unlikely. Nonetheless, there are significant classes of manufacturing problems where sufficient commonality is present such that some general approaches might be developed. This work will only consider discrete part manufacturing. The word batch will also be used to describe this type of manufacturing, with the understanding that the size of the batch can be arbitrarily large. Batch manufacturing is not a particularly restrictive classification; in general, the same breadth of variety and scope is still present. Consequently, batch manufacturing includes a diversity of products, technologies, techniques, machines, and skills. However, large segments of the batch manufacturing community are facing similar problems. Some of these problems will be considered here. 9

10 2.2. Problems in Manufacturing Perhaps the most pervasive problem today in batch manufacturing is the need to increase productivity. Productivity can be considered one important measure of manufacturing performance. Unfortunately, there is no universal definition of this measure, but it will be understood to subsume the production of a product in an economic and timely way, while achieving some level of acceptable quality. A summary of the preceding statement reveals three fundamental problems in batch manufacturing: cost, availability, and quality. The relative contribution of each of these factors and the presence of other factors in the productivity measure is specific to the particular manufacturing environment. Manufacturing problems can go far beyond operational issues. Such problems as product design and facility planning are clearly related to manufacturing. In order to try to further reduce the scope of manufacturing problems addressed here, only operational issues will be considered. Productivity will be considered a measure of operational performance. There are other operational concerns that may be factors in productivity. These concerns include: utilization of resources consumed in producing a product; utilization of production equipment; rate of production; speed of response to changes in the pro. duct; speed of response to changes in demand; capability of producing a variety of products; choice of production process; amount of work in process; inventory size; and required labor to produce a product. The intent here is only to provide a sampling of the types of concerns faced in manufacturing. An important motivation for research in manufacturing and in particular for this work is to address the problem of productivity improvement through improve

11 ment in one or more of the factors that may affect productivity. The question, then, is how to improve the productivity of a manufacturing system. One of the major deterrents to successfully answering the above question, and thus another important manufacturing issue, is a general lack of a scientific knowledge base in manufacturing. The "science of manufacturing" has not yet evolved. The result of this lack of fundamental knowledge is the proliferation of ad hoc techniques for dealing with manufacturing problems. It comes as no surprise that much of manufacturing is essentially trial and error, drawing heavily on experience and experiment. Without analytic tools and techniques to offer guidance, solution synthesis becomes difficult and problem insight may require long observation, if it is ever attained. The intention of this research is to find ways to improve the operational productivity of manufacturing systems through the use of analytic models and methods. The specific use of analytic methods will hopefully yield insight into the problems, result in solution synthesis techniques, and contribute to a scientific knowledge base for manufacturing. 2.3. Intelligent Manufacturing Although manufacturing suffers from the previously indicated problems, it has by no means stagnated. Advances in supporting technologies have had a tremendous impact on all aspects of manufacturing. Of particular importance are the great advances made in computer and communication technologies. These technological achievements have helped to make the use of such devices as robots and CNC machines economically feasible in many manufacturing environments. Plant floor communication networks are becoming a reality. The computer related technologies

12 are not alone in contributing to manufacturing. Major advances have also occurred in process technologies, material technologies, material handling, sensor technologies, and even in the basic structure of the manufacturing system: Flexible Machining and Flexible Assembly Systems (FMS/FAS). The advances in the supporting technologies have allowed for new approaches to the productivity problem. That is, a re-thinking of how manufacturing is done is now both appropriate and necessary. Since most of manufacturing has evolved by trial and error, the present solutions are specific to the manufacturing environments of the past. Changes in the environment dictate investigation of alternate structures and methods for manufacturing. However, this does not imply that the existing manufacturing structures are wrong and must be replaced by new structures. As an example, the assumption that all new machining systems must be flexible is unfounded and limiting. Underlying this type of assumption is the belief that traditional manufacturing systems have fully evolved. This belief has no basis. Consideration should be given as to how advancing technologies can be used in all types of manufacturing. An additional benefit of this consideration is the discovery that much of existing manufacturing is not really well understood. It should be clear that prior assumptions about the structure of advanced manufacturing systems will be avoided in this work. Instead, a more general and more powerful concept of manufacturing systems will be introduced. This concept will be called intelligent manufacturing. The concept of intelligent manufacturing is quite simple. Assume that there exists sufficient data collection, communication, processing, and storage facilities so that plant floor data can be used to aid in operational decision making. Furthermore, assume that the manipulation of the data can

13 be done in a timely way. Given this data collection and processing structure, how can the performance of the manufacturing system be improved. Intelligent manufacturing assumes the advanced technological support without making assumptions about the particular manufacturing structure. Given the availability of the requisite technology, the concept of intelligent manufacturing has a certain intuitive appeal. This appeal arises from the belief that an increase in the amount and quality of data available for decision making, and an increase in the speed at which it can be processed should result in better decisions, better performance, and greater productivity. This reasoning suffers from one flaw. The ability to efficiently handle data does not imply a knowledge of how to effectively use it. It is precisely a deficiency in the knowledge of how to use plant floor data effectively that has impeded greater advancement in intelligent manufacturing. The central theme of this research is conveyed by the following question: How can the feedback of information be used to improve the performance of the manufacturing system? The question presumes an intelligent manufacturing setting and the capability of influencing the system through on-line decision making. The methodology for approaching this question will be called control theoretic. Before explaining this methodology further, some motivation for the control theoretic approach will be given. Fundamental to control theory is the concept of feedback. Feedback of information is used in the determination of what actions should be taken so as to influence the behavior of a system in a desirable way. The similarity between this

14 point of view and the central theme motivates the control theoretic approach to manufacturing systems. 2.4. The Control Theoretic Approach The control theoretic approach has both advantages and disadvantages for approaching manufacturing problems. These relative merits and demerits are reveled by describing what constitutes the control theoretic view. As previously stated, fundamental to the control theoretic view is modification of system behavior. This modification can be accomplished by utilizing feedback of information regarding the condition of the system and exercising on-line strategies to influence the system behavior. The control theoretic view presumes the existence of means for exercising this influence. Clearly, the available means represent a limiting factor in influencing system behavior. Identification of the available means is an important modeling issue. The control theoretic view also recognizes some important issues regarding system performance modification. The first is that the effective use of information feedback is not trivial. The second issue is that information feedback can be detrimental as well as beneficial. Finally, the magnitude of performance improvement that can be achieved is limited. The control theoretic view represents an analytic orientation. The advantage of this orientation is the potential for gaining insight into classes of mathematical systems that can be used to model many physical systems. From this insight, analysis and synthesis methods for constructing and determining the performance of controllers can be derived. However, the control theoretic view still recognizes that the performance of the physical system is what actually matters. The analytic orientation helps to reduce considerably the amount of trial and error required in order to attain

15 the desired system performance. Unfortunately, there are some difficulties that arise in attempting to apply the control theoretic approach to manufacturing. The most important of these is mathematical incompatibility. The most powerful control theoretic results assume mathematical structures (finite dimensional, linear differential/difference equations) that are not readily applicable to most manufacturing problems. This means that either we accept poor system models that are familiar and fit the classical framework, or search for new models that are more appropriate but for which new analytic methods must be developed. The latter approach will be emphasized in this work. The problem of constructing compatible mathematical models for manufacturing systems is compounded by the relative lack of analytic models in manufacturing. Furthermore, those that do exist are generally not adequate for use with the control theoretic approach. Clearly, a major endeavor in using the control theoretic approach will be model construction. One of the main difficulties in applying control theory to manufacturing problems is that from some viewpoints, manufacturing systems appear as collections of discrete events. The problem here is that a branch of control theory dealing with discrete event systems has not yet evolved (except for certain special cases). See [Hol] for some recent approaches to the discrete event system problem. Also see [Brl] and [Cr11 for the special cases of controlled point processes and controlled queues. This fundamental inadequacy contributes greatly to the difficulty in applying control theory not only to manufacturing, but to many other classes of problems with similar attributes. One of the goals of this work is to present some ways of approaching certain types of systems that can be viewed as discrete event systems. Implicit in this

16 effort is the belief that this has value beyond specific manufacturing problems. Before attempting to construct suitable models of manufacturing systems, it is worthwhile reviewing some of the properties and characteristics of manufacturing. The following review is certainly not exhaustive, but it does present some features that are important. Some of these features are not often discussed in the literature. The reference [Gel] also presents a control perspective on manufacturing. There are many similarities but also some important differences between the viewpoint presented here and the one presented in that reference. See also [Whl]. 2.5. Some Properties and Characteristics of Manufacturing Systems Based on the previous discussion, it is apparent that modeling is a major issue if the control theoretic approach is to be used in manufacturing. The goals of this modeling effort are to characterize important features of manufacturing systems, identify the requirements of the control theoretic view, and to develop models that incorporate these features. In this section, the first two goals will be considered. The importance or relevancy of features will of course vary with the system being modeled. Nonetheless, the following provides a list of features shared by many manufacturing systems. 2.5.1. Complexity Manufacturing systems, when viewed in whole or even in part, can be enormously complex. A manufacturing system can easily involve many facilities located internationally and employing (hundreds of) thousands of people. Furthermore, these facilities may in turn depend on thousands of other suppliers and their respective facilities. Decision making may involve time intervals from sub-second to decades.

17 The processes and technologies involved can be extremely diverse. Even when the view in restricted to a single facility, the complexity of the system can be overwhelming. Hundreds of machines and thousands of people can be producing thousands of products. From a modeling standpoint, there are at least two approaches to the complexity problem. The first approach is to model the system using extensive aggregation and simplification. The second approach is to decompose the manufacturing system into simpler subsystems that are easier to model. 2.5.2. Decomposition Fortunately, most manufacturing systems can be decomposed into simpler subsystems that have less complexity. In general, several levels of decomposition are possible. As an example, consider a manufacturing system which has a machining line as a subsystem. The machining line can be decomposed into sets of related processes or operations; these can be further decomposed into distinct operations or workstations; these individual operations can be decomposed into sequences of steps that are necessary to do the operation. This example is only representative; subsystems involving human workers can be similarly decomposed. This decomposition of manufacturing systems is based on levels of detail. It is not a unique approach. Another approach is decomposition based on time scales ([Gel]). In this work, levels in the manufacturing system will refer to levels of detail and breadth of scope unless otherwise stated. The impact of decomposition on modeling must be considered. Although decomposition makes the modeling problem more tractable, it can also lead to certain views of the system that are incomplete or misleading. That is, depending upon the

18 level of decomposition chosen, there can be considerable aggregation, simplification, approximation, and omission of higher or lower level features. It is the author's opinion that this has resulted in the evolution of two disparate model classes for many types of manufacturing systems. More will be said about this later. 2.5.3. Uncertainty Manufacturing and manufacturing systems cannot be described in a completely deterministic way. Elements of uncertainty enter into all aspects and at all levels of the system. Some examples of uncertainty will help demonstrate its pervasiveness. At the operation level uncertainty manifests itself in the form of machine reliability and production quality. At higher levels, uncertainty is present in the aggregated performance of a facility and in the quality and availability of raw materials. At even higher levels, uncertainty is present in future product demand, capital availability, and economic conditions. Uncertainty is always present in the manufacturing system, but it is not necessarily independent of other factors. That is, uncertainty may affect the operation of a manufacturing system, but the operation decisions made and the actions taken can also affect the nature and magnitude of the uncertainty that arises. Consideration should be given to this potential coupling during the modeling effort. A very important form of uncertainty in manufacturing is production quality. Each part may deviate somewhat from what is intended. These deviations may be inconsequentially small, or so large that the part is unacceptable (scrap or rework required). There are many sources of these deviations: uncertainty in the raw parts, the machines, damage in handling, etc. The production of unacceptable parts is a manufacturing reality. These issues should be considered during model construction.

19 2.5.4. Deterministic Influences The presence of elements of uncertainty in the manufacturing system does not imply that the system is purely random. A manufacturing system is actually governed by an order or discipline imposed on it, and by natural physical principles. Deterministic influences are involved at all levels of the system. Examples of these influences at lower levels include selection of machining parameters, maintenance schedules for equipment, and the sequencing of processing steps. At even lower levels, the process evolution is presumed to obey physical principles, though they may not be well understood. At higher levels,' influences include production rate decisions and activity scheduling. Long term planning decisions can influence the evolution of the system over long time horizons. The inclusion of deterministic influences in manufacturing system models is particularly important when the control theoretic approach is used. This approach is naturally interested in identifying the means of influencing system behavior, and the effects of those influences. 2.5.5. Coupling Decomposition of the manufacturing system for the purposes of modeling does not in general produce a set of independent subsystems. As stated earlier, decomposition is generally only a simplification of the view of the system. Coupling generally exists between the subsystems, regardless of how the decomposition is carried out. Of course, the magnitude of coupling is quite variable, and in many cases nothing is lost in ignoring it. Manufacturing requires cooperation among the components and subsystems, so many elements of the system are interdependent. As an example, when a particular operation is isolated for the purposes of modeling, it is important

20 to remember that there are few stand alone operations in manufacturing and that the actual performance of the operation in a manufacturing context may be very different from its performance in isolation. The isolated characteristics may not be an adequate description of the operation's behavior. Generalizing, coupling may affect the performance of any subsystem. 2.5.8. Dynamical System Manufacturing systems are dynamical systems, not static. Their temporal evolution depends upon physical laws, deterministic and uncertain influences, and interaction with other systems. This is a key feature that provides a logical link between manufacturing and control theory. Whether or not the dynamics of the manufacturing system need to be modeled depends upon the level of the modeling viewpoint, the time scales of the features being modeled, and the time horizon for which the model is intended to hold. In some cases, static assumptions are reasonable approximations and are simpler to handle. However, static models fail to capture the true character of the system and thus are necessarily incomplete. Models that capture the dynamical character will in general be more complicated, though potentially more accurate. The dynamical character of the system to be modeled should be carefully considered so that the dynamics of the system with time scales relevant to the model intention are captured. 2.5.7. Control Theoretic Compatibility Manufacturing models that are to be used in conjunction with the control theoretic approach require a degree of compatibility with the basic assumptions of the approach. Therefore, the model needs to include explicit control mechanisms that

21 can be used to influence the system's evolution. Furthermore, in order to conform with the central theme of information feedback, those entities that can be measured or otherwise assessed also need to be identified. The identification of the control mechanisms is not sufficient. Also required are direct and indirect consequences of the manipulation of these mechanisms. This includes deterministic influences as well as influences on the system uncertainty. The model should also specify limits or constraints imposed on the influences, and limitations on the available measurements. Measurement limitations include both quality and availability. An example of a control input common to many manufacturing systems, but often overlooked in models, is the production rate or more generally the rate at which work is done. However, in order to use it effectively as a control input, the direct and indirect effects of production rate need to be understood and modeled. This particular control input will be used in this work. Control inputs can also be of a discrete nature. Some examples of this type include part routing decisions, pass/fail inspection, and on/off actuator inputs. Some control mechanisms are best modeled as discrete while others are best described as continuous. Since a typical manufacturing system has both types of control mechanisms the model may have to include both continuous and discrete valued control inputs. 2.5.8. Discrete Event vs. Continuous Process Viewpoint A popular modeling view of manufacturing systems is to model only the occurrence of specific events that are of some significance. This is the discrete event

22 representation of manufacturing systems. This modeling approach has the advantage of simplifying the representation of the manufacturing system and easing the burden of using the model in analysis, simulation, or design. [Gel] has several examples of this viewpoint. This viewpoint has also influenced manufacturing simulation language design. See [Pel] as an example. The discrete event viewpoint has the drawback of neglecting the underlying dynamics (typically continuous processes) that give rise to the discrete events. Consequently, many discrete event models neglect entirely the additional structure present in the actual system. This neglect can result in missed potential for system control and information feedback that may actually be available. Similarly, most models of continuous time processes fail to represent the occurrence of significant events (at discrete times) that impact system evolution. A rssible explanation for this is that most instances of models of manufacturing sys tems where continuous processes are used are at the lowest levels (e.g., process dynamics) where the discrete event view is not considered important. Similarly, the discrete event view can be regarded as a way to ignore process details that higher level views are not concerned with. An important modeling consideration, and one that will surface repeatedly in this work, is the possibility of hybrid models that capture important features of both continuous process and discrete event viewpoints. The advantage to be gained by this approach will include control compatibility while retaining the impact and importance of significant events.

23 2.8. A Brief Survey of Models of Manufacturing System The intention of this section is to provide a brief survey of classes of models of manufacturing systems, and to compare and critique these models with respect to the features previously described as desirable. Refer to [Gel] for a more complete bibliography and also to [Su2]. Prior to surveying the models, some remarks are in order concerning the use of models of manufacturing systems. In particular, there can be a distinction between models that are used for analysis and those that can be used for synthesis. Analysis refers to analysis of system behavior. Synthesis refers to producing candidate system designs. Systems design includes both structural issues (e.g., number and type of machines) and operational issues. Models that can be used for synthesis, and which include the previously specified features, are desirable but scarce. Much more common are analysis models, with synthesis performed by trial and error based upon the analysis results. The admittance by a manufacturing system of a decomposition based on levels of detail has been previously discussed. Detail based decomposition induces a hierarchy of views of the manufacturing system, ordered by the breadth of the view and the detail considered. The models discussed here can be considered as reflections of the view of the system considered important by the modeler. For descriptive convenience, a high-level view will correspond to breadth but lack of detail, and a lowlevel view will represent detail but lack of breadth. The models discussed here are restricted to system operational models. The first class of models considered is the queueing models. These models rely on the network of queues formulation. In these models, the manufacturing system is

24 composed of servers (work stations), queues (buffers), and routes (work paths through the system). These models have become popular for modeling flexible manufacturing systems. Queueing models seldom contain details of the processes involved, allowing for generality. As such, these models have a relatively high view among models of factory floor operations. See [Bull, [Crl], [Klll, [Sol], and [Whl]. The reference [Crl] is a bibliography of queueing research. Analytic results for queueing models are only proven under strong assumptions about service times and input processes. Recently there has been some work suggesting that these models are robust to deviations from these assumptions, indicating a more general usefulness ([Sul]). Variations of queueing analysis allow for determination of certain performance characteristics (e.g., expected queue length) quite rapidly. Several deficiencies of queueing models are evident. Probabilistic part routing and infinite queue capacitiesre often unrealistic assumptions. The probabilistic service time assumptions (exponential distributions) are also unrealistic for many systems. As an example, in machining the process times can be variable, but are certainly not exponentially distributed. Expanding on this criticism, queueing models are in some sense "too stochastic", and sacrifice lower level detail or knowledge that may be of use. When analytic tractability is sacrificed, representational accuracy may be improved, but the model is difficult to use for meaningful analysis of the system. A major drawback to the use of existing queueing models with the control theoretic approach is the lack of explicit control mechanisms, and identification of information that may be available for feedback. In fact, these models assume that the control policies are somehow "encoded" into the probabilistic descriptions and queue disciplines. This can be quite awkward to deal with. Queueing models do pro

25 vide a dynamical representation, however. The next class of models is the Markov chain or Markov process models. In both models the system is decomposed into machines and buffers. Each machine can assume one of two states: operational or under repair. The state of the system refers to the current inventory in the buffers and the state of each of the machines. In the discrete time version, production is usually viewed discretely, with parts produced at some multiple of the time quantum unit (usually one) ([Ge3]). In the continuous time model, production is usually modeled by a flow approximation ([Ge2], [Kil]). The transition of a machine from operational to under repair and vice versa is assumed to be a Markov process, and thus is exponentially or geometrically distributed. These models can allow for machine blockage and starvation. Closed form solutions are only available under very special circumstances. However, some approximation methods are known that can be more generally applied. These models do incorporate uncertainty through the failure/repair transitions. The binary state model is somewhat limiting, though, since it does not allow for machine deterioration due to aging. This comment applies to all models that assume exponential or geometric failure distributions. It is possible to incorporate production rate into some of these models. The failure mechanism is assumed to be independent of the production rate. These models do allow for some control theoretic approaches, since system state is assumed to be known to the controller ([Ge2], [Kil]). These models do incorporate many of the discussed features. Some assumptions are made that may not hold for many manufacturing systems, unfortunately. Some synthesis methods are available for some of these models. Typically, these are based on approximations.

26 Other classes of network models have been proposed as models of manufacturing systems. Most prevalent are the Petri net models, including the many variations and extensions of them ([Dull). [Kaml] discusses various Petri net type models. These models offer a graphical representation of concurrent, asynchronous processes, which are properties of manufacturing systems. The variations that have been proposed include timing information, classes of activities, and stochastic phenomena. Some of the properties and results that are known about Petri nets can be applied to manufacturing systems. These include liveness, safeness and boundedness. Petri net models have also been used as the foundation for simulation models and for the design of control logic. The Petri net viewpoint is decidedly discrete event. Concepts of state and control pertain to the components of the Petri net. Lower level details are generally omitted. The next category of models involves the sp*fic modelindividual processes. The focus here is at a lower level where process details become important but manufacturing aspects are often ignored. Detailed models of process behavior are constructed from physical principles or experimentation. Control mechanisms often enter naturally into these models. Generally these models are close to those types of models common in traditional control engineering: lumped parameter differential equations. References exist for many different manufacturing operations. Some specific references are [Dal], [Kanl], and [Kol]. Drawbacks to these types of models include viewpoint (often ignoring manufacturing concerns) and neglect of uncertainty. This latter feature could be included but typically is not. The absence of uncertainty tends to result in the modeling of nominal behavior only, ignoring the abnormal behavior that occurs in the manufacturing

27 environment. The significance of certain discrete events is usually ignored in these models. Models that respect some process characteristics while including more manufacturing oriented concerns are also available. Examples of these models are found in machining economics problems with multi-stage machining systems. See [Erl], [Hal], [Hil], [Iwl], [Kel], [Lel], [Le2], [Phl], [Shkll, [Takll, and [Tayl]. In these models, some low level details concerning tool wear, feedrate selection, and cutting constraints are used along with some high-level details such as profit and production rates. These models are used in conjunction with some optimization criteria to determine the (static) selection of certain parameters (e.g., feed speeds). These models are typically deterministic and static. Without a dynamical system viewpoint, many of the control theoretic concepts are not readily applied. In some formulations of theses models, uncertainty is included via probabilistic descriptions of the process variables and constraints. This does not change the static character, however. The intermediate view taken by these models is notable, as it includes a mixture of levels of detail. The next class of models is simulation models. Actually, simulation is best described as a technique for evaluation. However, since simulation does require that models for evaluation be constructed, it will be considered here. This is a varied class, and can take on essentially any viewpoint of the system desired. There is no explicit limit on the amount of detail that can be captured (although there are usually practical limits). Arbitrary degrees of complexity can be treated, but not without cost. As more detail is included, more effort is required in preparation, run time, and analysis. Also, more detail increases the chance of error. Simulation can

28 include all of the desirable features mentioned, though manufacturing simulations usually don't. Simulation is the single most common method of analyzing manufacturing system performance (other than experimentation with the actual system). See [Lal] as a general simulation reference and [Pell for a perspective on manufacturing simulation from a simulation language supplier. The generality of simulation makes it difficult to critically evaluate without specifying a particular problem. Usually, simulation is only used for evaluation though some techniques have recently appeared that can aid in synthesis ([Hol], [Ho2]). Simulation can represent a great deal of effort, and does not always result in useful insight into the behavior of the manufacturing system. As a side comment, it is worth noting that there exists some dichotomy in the simulation community between discrete event and continuous model simulations. Although many simulation languages support both types of systems, it is perhaps coincidental that the discrete event view prevails in manufacturing simulation ([Pel]). Again, this can lead to some restriction in the modeling approaches considered. With the exception of simulation (which will be excluded from the following discussion), none of the models discussed really captures all the desirable features and characteristics previously discussed. Clearly, each has some advantages and disadvantages. By extracting the appropriate features of each model type, it may be possible to develop models that satisfy the requirements. However, changes to each of these models can represent additional complexity not easily dealt with. Seemingly, modeling of manufacturing systems is still an open field.

29 2.7. Discrete Event Processes Arising From Underlying Processes Discrete event processes play a prominent role in many manufacturing system models. This prominent role can have the unfortunate consequence of obscuring the nature of discrete event processes. It is typically the case that discrete events are the result of underlying processes that give rise to these events. As an example, consider the machining of a part. The process of metal removal, which is occurring continuously in time gives rise to the discrete event of part completion. The discrete event viewpoint presents some compatibility problems with the control theoretic approach. First, the discrete event view can disguise the presence of underlying control mechanisms. Thus, available control inputs can be overlooked. Second, the potential utility of information feedback can be inhibited by the discrete event view, since the use of information concerning the underlying process is ignored. The explicit introduction of underlying processes giving rise to the discrete event provides a convenient link between the discrete event view and the control theoretic approach. Presuming that the underlying process has control mechanisms and measurable components, the utility of the control theoretic approach can be explored. It should be expected, however, that the use of underlying processes to describe discrete events, particularly stochastic events, may not be simple. This will be considered in some detail in this work, with particular attention to some discrete event processes arising in manufacturing. However, the author believes there is considerable potential for the application of this approach in areas outside of manufacturing.

CHAPTER 3 DESCRIPTION OF SOME MANUFACTURING PROBLEMS 3.1. Introduction In this chapter, several prototype manufacturing problems will be introduced and discussed. The problems are at once similar and dissimilar to problems typically discussed in manufacturing. These problems have been constructed with several intentions in mind. First, each problem embodies some important features or aspects of manufacturing. Second, the problems are not of the "black box" variety; rather, they represent realistic situations. This has been done in order to aid familiarization and problem visualization. That is, certain features are more clearly evident in a manufacturing setting that might otherwise be obscured in a purely mathematical setting. Third, the problems are set in an intelligent manufacturing context, with features that admit a control theoretic approach. These features are designed to be realistic or at least reasonable. However, the presence of these features results in a departure from typical related problem formulations. This will motivate a comparison between the traditional and the intelligent manufacturing problem formulations, and also help clarify the concept of the control theoretic approach. Fourth, each of the problems contains certain phenomena that can be modeled using a class of stochastic processes central to this work. This modeling relationship will be 30

31 explored in some detail for one of the prototype problems. The presentation of these prototype problems is not meant to imply that they embody all the important manufacturing problems, nor that they are the only problems to which the concepts developed in this work can be applied. However, each of the problems does have some importance in manufacturing. More importantly, each of the problems offers a viewpoint different than that which is usually presented. The author wishes to stress the importance of new viewpoints for manufacturing problems that more accurately convey the actual system or overcome limitations in past approaches. The primary objective in presenting these problems is to gain additional insight into some characteristics of manufacturing systems; insight that may ultimately yield productivity improvement. Finally, each of the problems provides a vehicle for exploring the control theoretic approach to manufacturing. A framework will be developed, with particular emphasis on one of the problems, that demonstrates the application of the control theoretic approach. Again, the intent is to provide examples, but the framework is not believed to be limited to the problems considered here. 3.2. Problem 1: The Drilling Problem The drilling problem represents a simple version of a problem found in metalremoval manufacturing operations, but with some new extensions. The heart of the problem is the question of how to operate a machining system in the best way subject to the limitations of uncertain physical phenomena. In this simplified version, only a single machine carrying out a single operation will be considered. It is important not to divorce the problem entirely from the surrounding manufacturing complex, however. That is, the problem formulation should represent at once aspects of

32 manufacturing and aspects of drilling. Assume there is a metal drilling manufacturing operation. The machine is a single tool drill, repetitively carrying out a single identical task. on parts as they arrive. The task involves the drilling of a single hole in each part. An unlimited supply of parts for drilling is available. When a part is completed, another part is immediately available for drilling. As holes are drilled, the tool wears and is susceptible to breakage. It is assumed that there is a limit to the wear beyond which the tool is unacceptable. A broken tool is considered unacceptable. Evolution of tool wear necessitates the occasional replacement of the tool. Replacement of the tool involves some costs for both time and material. The spindle speed and the feed speed of the drill are variable. The machining rate, i.e. the rate of metal removal, is proportional to the feed speed. The time required to complete an operation is inversely proportional to the machining rate. Assuming that the tool does not break, the time to complete a part is inversely proportional to the feed speed. See Appendix A for a description of relevant drilling terminology. The dynamics of tool wear are not completely understood. Experiments have been made from which empirical formulas for tool wear have been derived. These formulas are known to be only approximate, and considerable variation in tool life is evident. Furthermore, the material to be drilled has some uncertain characteristics that also affect tool wear. The empirical formulas for tool life suggest that under the assumption of a fixed feed (the ratio of feed speed to spindle speed), the tool wear rate is an increasing function of the cutting speed, and an increasing function of the

33 feed speed. The replacement of tools prior to breakage is feasible. If the tool breaks, it must be replaced before continuing. Furthermore, tool breakage may cause damage to the current part, possibly resulting in a scrap part or necessitating rework. Costs are therefore associated with tool breakage. Tool breakage is an unplanned event, so replacement of the tool due to breakage may take longer (and thus cost more) than planned replacement. The drilling problem is to determine the best policies for operating the drill. The required decisions are when to replace the tool, and the selection of spindle and feed speeds used to drill the parts. The criteria for ranking policies is a function of the various economic considerations. Any of several different criteria may be reasonable. The above description of the drilling problem is typical of problems of machining economics, and as such does not appreciably extend previous considerations of these problems. The on-line variability of the spindle and feed speeds is not usual, however. Similar problems can be found in many references, including [Erl], [Hal], [Hil], [Iwl], [Lel], [Le2], [Phl], [Shkl], [Takl], and [Tayl]. The problem will now be extended. Suppose that occasional measurements of the extent of tool wear are made. Continuous measurements cannot be made while the tool is engaged in the part however. Measurements may be made between parts, when the tool is disengaged. The method of wear measurement is not specified. This new information is to be incorporated into the decision policies. The essential features of the drilling problem are:

34 (1) Mechanical Aspects: The drill is used in a fixed operation carried out repetitively on parts. A fixed volume of material is removed from each part. As metal is removed from the parts, the tool wears. The tool wear mechanism is only known empirically, and variation in tool life is evident. As the tool wears, it eventually breaks or becomes unacceptable and must be replaced. Failure of the drill necessitates replacement, but can also cause damage to the part being machined. (2) Economic/Manufacturing Aspects: The production of parts results in profit, and the profit rate is related to the production rate. The profit rate is assumed to be an increasing function of the feed speed. Tool replacement is costly in terms of time and material. Tool breakage is in general more costly than simple replacement, due to possible part damage and the unplanned replacement that results. (3) Control Aspects: The objective is to determine policies for tool replacement and for feed speed selection. Tool replacement and changes in feed speed may only occur between parts, unless there is a tool breakage. (4) Information Feedback: Tool wear can be measured when the tool is disengaged from the part, but not during the machining. The specific use of a drilling operation in this problem is only to facilitate the presentation of the concepts and is not meant to imply a restriction of the ideas to that type of machining operation. There are several important features incorporated into the drilling problem that are common to many manufacturing systems. Since some treatments of manufacturing problems overlook these characteristics additional emphasis is warranted. First,

35 the discrete nature of parts is represented. This property imposes certain restrictions on the way manufacturing system analysis can be carried out, and definitely imposes restrictions on the control policies and availability of information. Second, the rate of production is specifically cited as a decision control variable in the sense that the local or instantaneous rate of metal removal can be controlled. Local means in the absence of other effects (tool failure, tool replacement, etc.). Although in actual manufacturing processes the production rate will necessarily be constrained by other physical considerations, its availability as a control input should not be overlooked. Third, production rate selection impacts the system in other ways. In the drilling problem, the production rate affects the rate of resource consumption (tool wear) and affects the likelihood of system failure. Production rate can not be made arbitrarily large without adversely affecting other aspects of the system's performance. Fourth, an instance of failure can result in the production of scrap. That is, not every piece produced is acceptable, and when certain limits are exceeded the risk of producing unacceptable parts increases. In the drilling problem, this effect is captured in a particularly simple way. It should be noted that in actual systems this effect may be far more subtle. 3.3. Problem 2: Multi-tooled Machines This problem is a simple but realistic extension of the drilling problem. It is not usually considered in the machining economics literature, although see [Shkl]. Suppose that the drill discussed in the drilling problem is actually multi-tooled. That is, suppose that several holes are drilled simultaneously. This type of machine is very common in high volume production systems. The tools are not independent and must be controlled as a group. Since all the tools are simultaneously engaged in

36 the same part, the failure of any one tool can damage the part. The problem now is to determine the group machining parameters and tool replacement policies so that good performance is achieved. Note that group replacement is not in general required (though it may be specified for convenience reasons). Assume all other conditions are as given in the drilling problem. This includes the availability of occasional wear measurements. 3.4. Problem 3: Multi-machine Manufacturing Systems Not many manufacturing systems consist of only one machine, as presented in the drilling problem. Typically, many machines are involved, with parts visiting several or all machines before their processing is completed. Although the machines can be multi-purpose, assume here that they are single purpose. Also assume that part routes are predetermined and fixed. This forces attention on operational issues other than scheduling and routing problems. In particular, the usual FMS problems are not being considered here. It is possible that buffers exist between some or all of the machinery, but it is not necessary. The problem is to determine the appropriate machining parameters; e.g., spindle speeds and feed speeds, and thus the production rate for each of the machines, as well as to specify tool replacement policies in order to achieve good system performance. Assume that each machine is conceptually the same as that considered in the drilling problem: on-line control of the machining parameters is possible and occasional tool wear measurements for each machine may be available. The status of machines in the system and current inventory in the buffers may also be available. Several important issues should be noted. For interconnected machines, tool failure, repair, and tool replacement decisions at one machine can affect other

37 machines through blockage and starvation. Furthermore, the costs for repair and tool replacement may be dependent upon the system status, and the availability of required workers or other resources. The worth of a part depends in general on how close it is to completion. The multi-machine system described here is representative of many manufacturing systems. However, it is possible that other types of machines are in the system as well, with different characteristics from those presented in the drilling problem. Consideration is restricted here to networks of machines that are conceptually similar to that described in the drilling problem. An additional issue arises in the multi-machine problem that does not appear in the single machine problem. The structure of the controller also needs to be specified. Consideration should be given to both centralized and decentralized controllers. Each structure has certain advantages and disadvantages that need to be examined as part of the problem. As an example, a centralized controller may be difficult to implement for a large system because of the amount of data that has to be handled and the computational burden. 3.5. Problem 4: The Supervisor's Problem A vital component in manufacturing is often omitted from problem formulations. That component is human workers. There are no manufacturing systems today that can operate for more than a few hours without human involvement. Many manufacturing systems are completely dependent upon humans. In order to bring recognition to the importance of human involvement, the next problem emphasizes human aspects of manufacturing and downplays the role of machines.

38 Consider a manufacturing facility (e.g., a- job shop) that employs a group of workers and a group supervisor. A job is scheduled for the facility. This job will be viewed as consisting of a single task. This task may be arbitrarily complicated, however. A group of workers (one or more) is to be assigned to the task. A supervisor is,responsible for overseeing the task and the workers. The task has associated with it various goals and economic considerations. Possible goals include minimizing costs/maximizing profits, meeting schedules (due dates), and minimizing time in shop. The task also has uncertainty associated with it. The sources of this uncertainty may include: how big the task is, how long the task will take, how fast the workers will work, mistakes in task specification, miscommunication between the workers and the supervisor and mistakes in carrying out the work. The supervisor's role is to assess the work requirements for the task and assign workers and other resources to the task. The supervisor is allowed to make occasional inspections to assess the work progress on the task. These assessments may be imprecise. Furthermore, these inspections are costly or otherwise constrained and thus constant inspection is impossible. As examples, work progress may be stopped during an inspection, or inspections might only be possible once a day. Based on the assessments, the supervisor is allowed to make adjustments to the manpower and resources assigned to the task in order to influence the work rate. These adjustments have some costs or constraints associated with them. The objective of the supervisor's problem is to develop policies the supervisor may use to determine when to inspect work progress and how, to assign resources based upon work progress assessments in order to optimize some performance functional.

39 When the supervisor is not present, the above problem is related to typical stochastic scheduling and assignment problems. This class of problems has been considered by many researchers, and a variety of techniques are available for approaching the problems (e.g., dynamic programming, other mathematical programming, search techniques, heuristics, etc.). Solutions are not necessarily simple, however. The usual solution to these types of problems is to produce essentially static assignments and schedules. The problem is that this solution fails to capture the role of the supervisor. In particular, manufacturing environments are dynamic, and the role of the supervisor is to react to the dynamics in order to keep the facility operating in a reasonable way. Fundamental to studying the supervisor's problem is the construction of a suitable model that incorporates the required features. Unfortunately, the traditional formulations of scheduling and assignment lack the mechanisms needed to capture the supervisor's role. A new model is needed. The supervisor's problem is an attempt to capture features common to manufacturing problems that are not typically represented in traditional formulations of related problems. The supervisor's problem recognizes the dynamic nature of the manufacturing environment and thus extends the formulation beyond the usual static assumptions. The dynamics of the problem are not deterministic; there is uncertainty associated with the system. Most importantly, the problem recognizes the role of the supervisor in the manufacturing environment as a decision maker. Thus, the concepts of on-line control and information feedback are represented in the supervisor's problem.

40 3.8. Summary of the Problems The prototype problems presented here are intended to convey aspects of manufacturing that are not typically considered in other problem formulations. As such, these problems depart from the traditional views of manufacturing found in the literature. The problems are also placed in an intelligent manufacturing setting, where the availability of information and the capability of influencing the system online is assumed. The control theoretic approach has been previously proposed as a method for handling intelligent manufacturing problems. However, in order to utilize this approach, there is a need for new models of manufacturing systems that incorporate certain desired features as well as adhere to the control compatibility requirements. The next chapter is devoted to the study of a class of stochastic processes that will be used to model the problems proposed here. These stochastic processes are fundamental to this work. After introducing and describing these processes, the first prototype problem (the drilling problem) will be studied in some detail.

CHAPTER 4 MATHEMATICAL THEORY OF DIFFUSION-THRESHOLD PROCESSES AND THEIR APPLICATION 4.1. Introduction In this chapter, a class of stochastic processes called diffusion-threshold processes will be introduced and discussed. The name diffusion-threshold is derived from the process construction. A diffusion process evolves in time until some boundary (called the threshold) is first achieved. The attainment of the threshold signifies an event, resulting in some discrete action being taken; e.g., re-initialization or suspension of the diffusion process. The time at which the threshold is first attained is a random variable called the threshold hitting time or threshold crossing time. The discussion will begin by considering only real scalar diffusions. These diffusions can be controlled, however. The thresholds will be constant real values. The objective is to obtain probabilistic descriptions of the threshold crossing time based on the diffusion and threshold parameters. In particular, the probability distribution function is to be determined, and the moments are to be computed. Solutions to this problem are difficult in the general case. This work will focus on the development of some special cases where analytical solutions can be obtained. The basic result assumes the case of constant infinitesimal coefficients. Some of the 41

42 properties of this special case will be developed and discussed. The result for constant coefficients is extended to the case of deterministic piece. wise constant coefficients in Appendix B. The results for this case are significantly more complicated than the constant coefficient case. The piecewise constant coefficient case represents an approximation to the more general problem of deterministic time-varying coefficients. The determination of the distribution function for this more general problem is unsolved. The incorporation of measurements of the diffusion process into the distribution function is next considered. These results show how process measurement feedback can be used to update the threshold crossing probability distribution function. Multi-dimensional extensions of the diffusion-threshold process are next considered. Higher dimensional problems are generally difficult, but one special class of problems will be isolated and developed. Although the class appears to be restrictive, it will be shown later to have application. A discussion of some reasons for using diffusion-threshold processes in modeling will follow. Emphasis is placed on the significance of discrete event generation by the diffusion-threshold process. Interpretations of the various parameters in the process will be given from a modeling viewpoint. Several categories of general application of diffusion-threshold models will help to clarify the potential usage of the process. The chapter will conclude with alternative solution techniques and a discussion of generalizations of the process and its relation to impulsive control.

43 4.2. General Process Description 4.2.1. Preliminary Definitions Let (fn,F,P) be a probability space. Define R- (-oo,oo), 5R + [O,oo), and'R +- [O,o]. A history on (fl,F) is an increasing family of a —algebras {Ft, t >0} such that for O<J <t, F, C Ft C F. Define F,,O V Ft, the smallest a-algebra containing t >0 the history. Note that F,, C F. Let { W(w,t), w E f, t E R +} be a standard Brownian motion, (i.e. a Wiener Process), separable and measurable with respect to F B', where B+ is the Borel aalgebra on JR +, and ~ denotes the smallest product a-algebra. A standard Brownian motion is a real valued scalar Gaussian process such that: P [ W(w,0)0 ] = 1 (4.2.1.1a) E[W(w,t)] = 0 for tER + (4.2.1.1b) E[W(w,a)W(w,t)] = min( s,t) for s,tER + (4.2.1.1c) Recall that for a Gaussian process, the random variables (W(,t1),..., W(,t,,)) are jointly Gaussian for every finite collection (t1,..., 4,) R +. Since W(,) is assumed separable, every sample path is continuous, P-a.s. Without loss of generality, assume W(w,.) to be continuous for all w.fl. (Note that some authors specifically define Brownian motion to have this property.) The explicit dependence of the process on w will be omitted when no confusion is created: W(t) and Wt & W(w,t). An important property of Brownian motion is that it has independent increments ([Lol], [Karl], [Wol]).

44 Let {FW,t E R +} be the history generated by { W, }. That is FW a a{ W,, O< < t} (4.2.1.2) the smallest a-algebra generated by the set of random variables { W,, 0<s < t }. Definition: A stopping time with respect to a history {Ft } is an extended random variable T fl -Ri+ such that {w: T(w)<t}) Ft for all t EjR+. See [Brl], [Lol], [Wol]. A stopping time T induces a a-algebra denoted FT and defined as FTr _ a{S E F: sn{w: T(w)< t} E F,, for all t ER +}(4.2.1.3) Remark: An important stopping time for Brownian motion is T<,, min{t >0: Wt ~ (a,b)} for a <0< b (4.2.1.4) Definition: A strong Markov process is a process that exhibits the Markov property through stopping times. See [Kar2], [Lol], [Wol]. Remark: Brownian motion is a strong Markov process. 4.2.2. Diffusion Processes Brownian motion can be thought of as the prototype for a class of stochastic processes called diffusion processes. Diffusion processes have continuous sample paths and the strong Markov property ([Kar2]). Define a real-valued stochastic process {X,, t ER +} by t t X, = Xo + f b (, X,)d + fo(r, X,)dW, (4.2.2.1) 0 0 The last integral is a stochastic integral and will in general be interpreted as an Ito integral, although other interpretations are also possible ([Fli], [Wol]). Then, under

45 appropriate technical conditions on the coefficients b and a, {Xt } is called a diffusion. Growth and Lipschitz conditions (called the Ito conditions) on the coefficients are sufficient to assure existence and uniqueness. These are not necessary conditions, however ([F1ll, [Wol]). The functions b(-,) and a(y,) will be called the infinitesimal coefficients of the diffusion, with b called the drift coefficient and a called the diffusion coefficient. The process X can be thought of as the solution to the stochastic differential equation dXt = b(t, X,)dt + a(t, Xt)dW, (4.2.2.2) although this is not precise except when defined in terms of the above integral equation. For more information on general diffusions, see [Fli], [Itl], [Kar2], [Wol]. There are other ways of defining or characterizing diffusions. The above stochastic integral equation will be the operational definition in this wo* Conceptually, though, a diffusion is a strong Markov process with continuous sample paths ([Kar2]). The important relation between the diffusion and its infinitesimal coefficients is given by the following: Theorem (4.2.2.1): Let b(.,-) and o(-,) be Borel measurable on iR + xR Assume there exist positive a0 and K such that I b(t, z) I < KVTl+ T2 (4.2.2.3a) o < a0 _< a(t, z) < Ki + z2 (4.2.2.3b) I b(t,z)-b(t, y) I < Kl z- (4.2.2.3c) I a(t,z )-a(t,y) I < K z - y ] (4.2.2.3d) (These are the Ito conditions.) Then the diffusion process X, satisfies

46 lim 1 E [Xt+ -X IXt = Z = b(t,z) (4.2.2.4a) lim -E[(Xt+,,-Xt)2 Xt -J =a2 (t,z) (4.2.2.4b) d-~o Te Proof: See [Wol]. Stopping times can be defined with respect to diffusions. A particular stopping time that will be used in this work is the following. Let A >0 be a real value. Define TA:fa-JR_ + TA = inf{t >0: Xt >A} (4.2.2.5) Then TA is a stopping time with respect to the history {Ftx}. Note that TA is well defined because of sample path continuity. Also { TA = o} = {w: Xt <A for all t >0} (4.2.2.6) which can be a non-null event. One property of Ito integrals with respect to stopping times that is used implicitly in this work is the following: Theorem (4.2.2.2): Let Xt be a diffusion satisfying the Ito conditions. Let T be a stopping time with respect to {FX}. Then the following holds: (tA T) t f a(r, X,.)dW, = f t, < T1l(r, Xr)dW,. (4.2.2.7) 0 0 where 1[AI is the indicator function for the event A. Proof: See [Ell]. This result is quite intuitive, but not trivial. 4.2.3. Controlled Diffusions The previous results can be generalized to controlled diffusions ([F11], [Kryl]). Define a real-valued stochastic process {X~, t E JR +} by

47 t t X, = Xo + f b (r, X,., u)dr + f + (r, X,, u.)dW, (4.2.3.1) 0 0 where u (j) is a function which takes values in U, where U is a Borel measurable subset of R Assume that ut(-) is measurable with respect to {Ftx}. Then with appropriate conditions placed on the infinitesimal coefficients, the process {Xt } is called a controlled diffusion. The diffusions discussed in this work will be controlled, but will have an especially simple structure. 4.2.4. Diffusion-Threshold Processes By combining diffusion processes with stopping times based on threshold crossings, a diffusion-threshold process is constructed. Without loss of generality assume that X0 = 0. Let A >0 denote a positive threshold value, and TA the stopping time generated by a controlled diffusion Xi: TA =inf{t >0: Xt>A } (4.2.2.5) At time TA a significant event will be considered to have occurred. This will give rise to the following effects. If TA occurs, the diffusion process will be re-initialized. That is, XTA+ = Xo0. The instance of the threshold crossing can be thought of as causing a jump in the state space (instantaneous return process [Kar2]). Alternatively, the threshold crossing can be thought of as causing a killing of the process, and the reinitialization as a new selection of w E f2, with a time shift of TA. In order for this to make sense, assume that b(,ut) and a(,ut) are functions of t - to only, where to is the last re-initialization time. In order to simplify this, assume that a re-initialization results in a resetting of the diffusion clock to zero. Each process segment consisting of re-initialization to threshold crossing will be called a cycle. Thus, the diffusionthreshold process generates a sequence of cycles. In this work, the control will be restricted so that these cycles are probabilistically independent, though this may not be

48 true in general. An example sample path for a diffusion-threshold process is shown in Fig. 4.2.4.1. An additional discrete control action may also be allowed. It may be possible to force a re-initialization of the diffusion process at particular times prior to the diffusion achieving the threshold. This forced re-initialization will otherwise have the same effect as a re-initialization resulting from a threshold crossing. The goal in studying diffusion-threshold processes is to obtain a probabilistic description of the threshold crossing time. That is, the goal is to determine the probability distribution function for the random variable TA as well as compute the moments. Actually, the problem is somewhat more complicated because the diffusion-threshold process is controlled, and the relationship between the control and the threshold crossing time is to be determined. That is, it is actually a family of distributions parameterized by the control that is to be determined. Similarly, in A t I t TA Fig. 4.2.4.1 Diffusion-Threshold Sample Path

49 order to accommodate measurement feedback a family of conditional distributions given the diffusion state is to be determined. The general problem of determining the distribution function is hard ([Bli], [Mel], [Krtl], [Sill). It is known that for sufficiently smooth infinitesimal coefficients, the solution is associated with a partial differential equation called the backward equation. Closed form solutions to the backward equation are seldom available. In this work, the general problem will not be considered. Instead, the focus will be on certain classes of diffusions where the distribution function can be analytically obtained. The reference [Bi1] is a survey of various level (threshold) crossing problems. 4.3. Processes with Constant Coefficients In this section, attention will be restricted to a particularly simple class of diffusions. This restriction will allow closed form computation of the probability density function and the moments of the threshold crossing time. Consider those diffusions where band a are independent of X and t and thus depend only on the control ut. Also assume that ut - u is constant. That is: i t Xt X + f bd + fdW,. (4.3.1) o o and b = b ( ), O< b < oo (4.3.2) = _a(u), O<'<0o (4.3.3) Also assume that X0 = O<A. Under these assumptions, {Xt} is a Brownian motion with drift. As before let TA be the threshold crossing time. Note that in this case the stochastic integral can be equivalently evaluated as an Ito, Stratonovich, or

50 Riemann-Stieltjes integral, though never as a Lebesgue-Stieltjes integral ([Ell], [Fll], [Wol]). For diffusions in the above class, it is possible to compute the density function for the threshold crossing time. A preliminary result is needed first concerning the probability of a threshold crossing occurring. The following establishes that under appropriate conditions a threshold crossing will occur almost surely. Lemma (4.3.1): Given Xt = bt + a W,, b >, O>0, A >O then P[TA <00] = 1 (4.3.4) Proof: It suffices to prove the result for b = 0, since {w: TA(w)<oo, b >0} D {w: TA(w)<oo, b =0} (4.3.5) For b - 0, {wc: TA(w)<~oo} D {w: supWt (w)> } D {w: limWt(w)> } D {W: 1im W,(w)=oo} (4.3.6) >_>O But P {w: limWt=O} =1 (4.3.7) t>o is a standard result for Brownian motion. See [Loll. Therefore P[TA <oo] = 1. This lemma asserts that under the assumed conditions P[TA = oo] = 0. Thus the distribution function for TA is not defective on JR + The main result can now be stated.

51 Theorem (4.3.1): Given Xi = bt + aWj, b(u)>O, a(u)>O, A >0 the probability density function for TA, denoted qA (t I 0; u) is given by: A exp -(A - bt) t>0 qA (t I 0;U ) -= /|+at2 (4.3.8) O tt<0 Remark: This is a previously known result ([B11]). However, a proof will be given here that the author has not previously seen in detail. This proof will allow the introduction of certain Laplace transforms that are useful for studying threshold crossing problems. See also [Mel], [Sil]. Proof: The process Xt is Gaussian with density function CfhX; > _, ) >A, o s- (at - bt)2 (4.3.9) Choose t >0, z >A, but otherwise arbitrary. By the strong Markov property fxt (; Ui) f= f Xx(Z I A; u)q ( I 0; u)dq (4.3.10) where f XI x,(z I y; u) = v{- (z - y -(t-) (4.3.11) is a conditional Gaussian density. The explanation of the integral equation (4.3.10) is the following ([Bll]). By the strong Markov property, what happens before the threshold crossing is independent of what happens after. Further, the time of threshold crossing can be thought of as partitioning the set of sample paths. Thus the density function for the process must equal the integral of the conditional densities for processes with crossing times at v weighted by the density of processes with crossing times in (ti,77+dq). Note that t and? appear only as a difference in the conditional

52 density function. Therefore the integral equation is a convolution and Laplace transform is a viable solution technique. Denote qA(d Io; U), f (8; Z,U), f (8; z A,u) as the Laplace transforms (in t) of the density functions. Then = (8; z,u) qA(s I u) = (; z,u) (4.3.12) f (8; z IA,u) Now f(a;Z,u)=L{ 1 x expz2} {Z e - 2t} 1 bxp 2}F(S - a) (4.3.13) where ([Abll) F(s) = L{ eXP { 2 } -- exp (4.3.14) and -a- 2 (4.3.15) Thus f (; z,u) = exp { 2(-} a exp - (8-)} (4.3.16) Similarly, f(a; z IA,u) = exp{-(z-A } { 2-a)} (4.3.17) 0.2 VIaT — s ~-a ~ a V/T8 where a is given by (4.3.15). Therefore q(J u)= { }ex 2b }s-a{) (4.3.18) Now

53 A } A 2 L4l{exp{ o } } 3 exp - 2Ar2t (4.3.19) from [Abl]. So qA(tO; U) A exp 2 ep A {-A2}{ bA2t} | 2 t exp x 2o" - 22t =Jet {A } 2 (4.3.8) O t<0 Remark: The result holds for b = 0. It does not hold for b <0, since in this case P[TA = ool > 0. That is, the distribution becomes defective. Remark: From the proof of Theorem 4.3.1, note that qA(t 0O; ) = t fx,(A; u) (4.3.20) This has been previously shown to be true for a class of processes by Borovkov. See [Bll] for remarks and references. Remark: From equation (4.3.8) it is easily seen that lim qA(t I 0; u) = 0, b >0, >0, A >0 (4.3.21) t — #0+ Theorem 4.3.1 generalizes to non-zero initial conditions, where X0 = x0 3 0. Corollary (4.3.1): Given Xt = z0o + bt + aWt, b(u)>_0, r(u)>O, A > zo the probability density function for TA, denoted qA (t I zs; u) is given by: A-z {-(A-zo-bt)2 3 ( 2, Zo; u) a2c t qA (t I zo; u) = r 2 (4.3.22) O t<0

54 Proof: Simple extension of the proof used in Theorem 4.3.1. Remark: The corollary follows, since the infinitesimal coefficients don't depend on the state. Therefore the state space is homogeneous to the diffusion. The same argument applies to the time variable as well. Note that qA(t I zo; u) - qo(t l0; u) (4.3.23) where a = A - z0. From the above, the distribution function for the threshold crossing time given u is immediate. Define the distribution function for the random variable TA by: QA(tIO;u) P{ TA < t I XO =O;u} A (A -b d2 = A A exp{ } (4.3.24) The moments of TA can be evaluated from the Laplace transform of the density for b > 0. However, b = 0 is a special case. Theorem (4.3.2): For b = 0, E[TA]. Proof: (See also [Roll) E[TA] = fqA(,71 i; u)dl7 = 2 A (4.3.25) 0 exp1 2_,_; d(4.3.25) Substituting A -A (4.3.26) dy =n(4.3.26) Y-'a d —- 2 into (4.3.25) gives E 2A Y2 22 0 2

55 2A 2 001 Y2 - ~ 2A2 (- i2 2'!2-0.o3 exp 2 dy = o (4.3.27) Although the threshold crossing will occur with certainty, it may take an arbitrarily long time to happen with significant probability. This is analogous to a nullrecurrent Markov chain. For b > 0, the moments of TA are finite and can be computed from the Laplace transform: da E [TA'] = -1 ( — A( 1 0; u),0, 1,2,... (4.3.28) The central moments follow easily. The first four central moments are: E[ TA ] A (4.3.29a) Ao2 ar[ TAI =- (4.3.29b) 3A a'4 s:3 = 5 (4.3.29c) 15A ar 3A 2o4 14 5 + (4.3.29d) +7 b6 where As3 and s4 are the third and fourth central moments. Remark: The mean of TA is simply the distance divided by the rate. The density function qA is known in the statistics literature as an inverse Gaussian density ([Chl], [Shrl], [Twl]). However, a different parameterization is usually used. Define the parameters A(U ) = A (4.3.30) (u) 2 (4.3.31)

58 Substitution into the formula for the density qA gives: qA (t 10; u) = {-p 2t (4.3.32) Other parameterizations are also possible. In this work, the original parameterization will be used in order to retain the explicit dependence on the diffusion coefficients and the threshold value. Remark: The inverse Gaussian density is not a version of any of the commonly known density functions. Properties of the inverse Gaussian distribution and density can be found in [Chl], [Shrl], [Twl]. However, in each of these works, the statistical viewpoint prevails and the origin of the distribution in terms of threshold crossings in not exploited. In the following graph (Fig. 4.3.1) a comparison is made of the inverse Gaussian density to some other common density functions. One particularly remarkable result is the relationship between the inverse Gaussian distribution and the normal distribution. Since this result is not well known but is used in this work, it is presented here parameterized to conform with this work. Theorem (4.3.3): Let'D(z) _ P[X < ] when X - N[0,1]. Then QA (t I1; ) [ -X + exp { +1} (4.3.33) Proof: See [Chl]. The utility of this equivalence is that it allows the use of many known results for the normal distribution to be used in the analysis of the inverse Gaussian distri

57 1.25 inverse gaussian.1.00 lognormal mean mean = 1 -xponential variance = 1 0.75 1 1\ | all functions 0.50 - i | normal 0.25 0.00 0.0 1.0 2.0 3.0 4.0 5.0 Fig. 4.3.1 Comparison of Density Functions bution. In particular, bounds, limiting properties, and computational procedures for the normal distribution can be utilized. It is possible to compute the threshold crossing probability for the case where the coefficients are piecewise constant. Since this is not used elsewhere in the thesis, the development is presented in Appendix B. However, the following theorem will be used. Theorem (4.3.4): Given Xt = bt + oaWt, b(u)>O, a(u))>0. Define Mt sup X, (4.3.34) E[ O,tj Then the joint density of (X~, M,) is given by: gX,,M, (a,L; t,u) =

58 2(2y- exp -(2 bt) exp - 2(v-)b for v>q, v>O, t >0 3 2oc2t a2 V2 ra3 tr~~~3ta~~- (4.3.35) 0 otherwise Proof: See Appendix B. 4.4. Processes with Measurement Feedback In the previous section, the availability of information feedback was not considered. Assume now that occasional measurements of the diffusion process are available. These measurements are to be used to update the threshold crossing probability. As will be seen, the threshold crossing distribution QA gives the updated probability as well. Theorem (4.4.1): Given, = fb(u (r))dr + fo'(u ())dWt (4.4.1) o o such that for t' >0 u () arbitrary, r< t' (4.4.2) u () = u' t' <r (4.4.3) b(u') = b' >0 (4.4.4) (u') = ad >0 (4.4.5) and Xt = z' < A >0 (4.4.6) Then Pit' < TA t IXt' X=z',TA >t' I QA(t-t'; u' ) (4.4.7)

59 Proof: From the Markov property P[t' < T,<t I tX,, = z', TA >'] = P[t' < TAS <t IX, = 2' =P[TA<t-t' IXO -=';u'] QA(t-t' zi';') (4.4.8) This theorem generalizes to the more, important case of feedback control where the control u(t) is FX measurable. This class of control laws preserves the Markov property so the result still applies. In particular, suppose that u1 is a Borel measurable function of the current state. That is u (r) = u (X), 0 < r < t' (4.4.9) u (r) = u (Xt.), constant for t' < r (4.4.10) Then P[t' <TA<t I Xt,', TA >t; u = QA(t-t' 1z'; u') (4.4.11) That is, measurement of the process decouples the past and future, making future behavior of the process independent of past control laws. Of course, the future control must be constant in order to apply the results previously developed (or piecewise constant to use the results of Appendix B). In this work, the future control will generally be constant up to the time of the next measurement. This can be thought of as a type of sample-hold control law. Remark: The result also holds when t' is a stopping time. 4.5. Multi-dimensional Processes The treatment of multi-dimensional diffusion-threshold processes is generally even more difficult than the scalar case. One class of processes for which the distribution function can be obtained will be treated here. Although the class might seem restrictive, it does in fact have application.

60 The general theory of multi-dimensional diffusions will not be discussed here. It suffices to say that most of the scalar concepts generalize to higher dimensions. The class of processes considered here is sufficiently simple that the general theory is not required. Consider the class of n-dimensional processes defined as follows. Let: w(t) (wN(t), * * *, W (t))T (4.5.1) be an n-dimensional standard Brownian motion with independent components where superscript T denotes transpose; WOuOt) ) _~ (bt(u~ )..,(t)),..., bn t ) )rW bi(uj)_>0, i=l,..., n (4.5.2) be an n-dimensional drift vector; i_(t) ) diag(al(u(t) ),..,(u,(t) ) ), a(u)>, i=l,,n (4.5.3) be an n X n diagonal diffusion matrix; A -(ul,*.*.*, u,,)r (4.5.4) be the control vector. Define the n-dimensional diffusion process t t a(t) = f(? (r) )d + f|_ (!) )d W(T) (4.5.5) 0 0 Next define a threshold in R" as the union of hyperplanes A U U{ Ei: zi=Ai, Ai >0 i=1,..., n (4.5.6) *=1 Let TA. be the time when the process X first hits the threshold A. T = inf{t >O: X; E A } (4.5.7) For fixed u the distribution function for the threshold crossing time T. can be computed.

S1 Theorem (4.5.1): Given X(t) and A as above, and fixed control u, then: P[T.<oo] = 1 (4.5.8) and the threshold crossing probability distribution function is given by Q&(t I1;.) )= 1- H[1 - QA(t 0I;,,)] (4.5.9) i=1 Proof: Note that under the assumptions the process X(t) has independent components. The first statement follows easily from Lemma 4.3.1 since T&< TA. where TA, is the threshold crossing time for component i and threshold Ai. To show the second part observe that T= min( T,,) (4.5.10) Thus P[TA>t] = P[mim(TA,)>t] = P[(T,A)>t, i1,..., n] = IP[(TA;)> t] i=1 II[1 - QA,(t I 0; u)] (4.5.11) il by independence. Therefore Q(t I0 = 1- l - QA(t 0; Ui) 1- - ( ] (4.5.9) i=1 Remark: This result also generalizes to allow the incorporation of measurement feedback, provided that all measurements are available at the same time. If this is not the case, the computation becomes more complicated.

62 4.S. Application of Diffusion-Threshold Processes In this section several modeling applications of diffusion-threshold processes will be discussed. As will be seen, diffusion-threshold processes can be used to model a variety of phenomena. The applications will not be specific problems, but general categories of problems. Some of the motivation for these applications comes from manufacturing related problems, but certainly the applications are not restricted to manufacturing. More specific applications will be described in following chapters. An important aspect of each application is that the use of the diffusion-threshold model allows the problem to be viewed in a broader context than is typically considered. The ideas of control and feedback enter the problem in a natural way, allowing the problems to be placed in a control theoretic framework. One of the most important characteristics of diffusion-threshold processes is the generation of discrete events by hitting the threshold. Assuming a threshold hit is followed by a process re-initialization, a sequence of discrete events is generated. If the cycles are independent, then the durations of the cycles are also independent random variables. The diffusion-threshold process can be thought of as a discrete event generator. What makes it more powerful than simply assuming a sequence of random variables is the presence of the underlying diffusion process. This underlying diffusion is a continuous process whose state represents the "progress" made toward the threshold. Furthermore, the presence of this underlying process allows control and measurement feedback to naturally enter the discrete event generation through the diffusion. Consider the following interpretation. Let the threshold value represent some critical value, such as the amount of work to do a job, or the extent of deterioration

83 prior to failure for some device. The diffusion state then represents the current amount of work done, or the current extent of deterioration. The drift coefficient takes on the interpretation of mean work rate or mean rate of deterioration. The diffusion coefficient represents the magnitude of the uncertainty in the rate of state evolution. Conceptually, the diffusion-threshold model overlays a deterministic model and a noisy model to describe the system evolution. When underlying processes are used to describe discrete events, the whole viewpoint towards control of discrete event systems can change. In particular, the essentially binary viewpoint traditionally taken (the event has or hasn't occurred) is replaced by a viewpoint that recognizes that the system evolution is in fact continuous. Feedback of progress measurement now makes sense. Furthermore, the memoryless feature commonly assumed is replaced by a system that definitely possesses memory. It is asserted that many physical systems have memory. The following application examples and discussions will hopefully clarify these points. 4.8.1. Failure and Reliability Model One branch of reliability theory is concerned with the following types of problems: How long will a component last until it fails? What is the lifetime of a component? What are appropriate models for the lifetime and time to failure of a component? Each of the above questions can be generalized by substituting "system" for "component". The approach usually taken is to consider such questions in a stochastic process setting. In this approach one describes the lifetime and time to failure of components by random variables. Reliability of components (and systems) becomes in part a problem of assignment of probability distributions and in part a problem of

84 analyzing various properties related to these distributions. The problem of assignment is a modeling issue. Sometimes a probability distribution can be selected on the basis of underlying physical properties, but often it will be selected on, an empirical basis. In this case a distribution is assigned that fits the observed data. This assignment problem is at least bilevel. First a distribution family is chosen, then the parameters of the distribution function are chosen (estimated). Reliability theory often places a special emphasis on the following problem. Given that a component has survived (gone without failure) for some period of time, what is the probability distribution of its remaining life, or time to failure? The conditional probability density that describes this conditioned behavior is called the hazard or failure rate function, and plays a prevalent role in the reliability literature. Formally, the failure rate function is the conditional density of the failure time, given that the failure time is greater than some value. There exists much work relating the failure rate function and the physical characteristics of the components being modeled. Also related to the characteristics of the failure rate function are the concepts of aging and memory. See [Mull. There are many devices, components, and systems for which the above formulation and description of reliability is a reasonable one. The claim made here is that there are other systems for which this formulation is neither adequate, nor entirely satisfying. Some of the deficiencies and limitations of this usual formulation of failure models will be examined. First of all, an empirical formulation is never entirely satisfactory. One would prefer a description that incorporates at least some features derived from or motivated by a physical basis. Sometimes this is not possible due to a lack of under

85 standing and then an empirical description has to suffice. This does not mean that an empirical formulation is not useful. The second issue is concerned with the use of a single distribution to describe failure. Some devices are adequately described by one mode of use or operation. This means that the device is utilized in an essentially uniform way, and thus can be described by a single failure distribution. Some devices and systems do not readily admit such a description. For these devices a range of modes of use is possible. Furthermore, the mode of use influences the rate of deterioration (wear) of the device, and thus affects the failure rate of the device. When a single distribution is used to describe the failure probability of such a device, the description is an aggregate one. A more specific characterization of device failure would be a parameterized family of distributions, with the parameter a function of the mode of usage. This would be particularly useful if the mode of usage can be measured and/or controlled. The third issue is the conditioning used in the failure rate approach. The information structure assumed by the usual formulation is that inspection of the device reveals only that the device has or has not failed. For many devices, it is reasonable to assume that this is indeed the only information readily available. Measurement of deterioration may be physically impossible, impractical, or perhaps the measurement process is destructive. Some devices, though, can be inspected, and the extent of deterioration and wear can be determined or at least approximated. For these devices, it would be desirable to use this additional information in determining the probability of failure in the future. These various ideas can be unified into a control theoretic view of reliability that extends the usual formulation of reliability models. Suppose that the mode of

86 use of a device is in fact a function of some control input. This usage will be interpreted as a rate of wear. This same control input also affects the performance of the system in some way. Examples might be speed of operation or time in use of a device or system. Assume that this rate of wear and performance are conflicting: higher or better performance necessitates a faster rate of wear. This rate of wear affects the probability of failure of the device or system. How can a good compromise between these two conflicts be determined? Suppose that occasional measurements of the extent of the wear of the device or system are available. This information (feedback) is to be used in the determination of a control value that achieves an appropriate (according to some criteria) balance between performance, rate of wear, and probability of failure, given some set of wear measurements. This is a controlled reliability system. 4.8.2. Diffusion-Threshold Model of Controlled Reliability System The diffusion-threshold process can be used as a model for the controlled reliability system. Let Xt represent the wear, or deterioration of the system at time t. Let the threshold level A correspond to the wear level at which failure or unacceptable performance is considered to have occurred. The drift coefficient corresponds to a mean local rate of wear, and as such will be assumed to be strictly positive. Assume that the drift coefficient is a function of some control variable u. The diffusion coefficient will also be assumed to be strictly positive and a function of the control. Reference [Krtl] also considers the reliability problem in a similar way. When the coefficients do not depend on the process X~, the deterministic component of the wear at time t is given by:

B7 fb ( u,)dr (4.8.2.1) 0 and the stochastic component of the wear at time t is given by: Xo + fo( u,)dW, (4.6.2.2) 0 A simplifying assumption would be X0 = 0 P-a.a. This is equivalent to saying that new components have the same wear, assigned the value zero. A special case of interest results when b and a depend only on u and u is a constant function. This generates a family of distributions for the random variables { TA}. The control u corresponds to the mode of usage and is assumed to remain constant over the lifetime of the component. In this case the parameterized family of conditional first crossing densities is given by Corollary 4.3.1. Similarly, a parameterized family of failure rate functions can also be calculated: I (t I Zo; u) qA (t I o; u),(t l2o;,L1) - t " Q1.- Q,(t I|o; d) (4.6.2.3) IqA(.1lzo;.u)d. The use of the inverse Gaussian density as a reliability model has been previously proposed. See [Chll, and [Shrl]. However, these references do not consider the underlying diffusion-threshold model, and instead focus on the use of the inverse Gaussian distribution as an empirical model. The concepts of control and feedback are not considered. Under the assumption of constant distribution parameters, estimators for the parameters are developed. See also [Twl] for estimator properties. In [Chl], the failure rate function associated with the inverse Gaussian distribution is examined. Important properties of this failure rate function are nonmonotonicity and nonzero asymptotic tail. Comparison is made to the lognormal distribution in particular. The authors in [Chl] conclude that the inverse Gaussian distribution is

88 a reasonable reliability model for many systems, including those with early failure where an increasing failure rate is not appropriate. In [Shrl], the inverse Gaussian distribution is considered for a tool life model. The authors show that this distribution gives a slightly better fit than the lognormal distribution for a specific tool life data set. In none of these references is the choice of the inverse Gaussian distribution strongly motivated by its relation to the diffusion-threshold model. The authors of [Chl] do mention this connection, however. In this work, the suitability of the inverse Gaussian or other threshold crossing distribution is regarded as arising from the underlying diffusion-threshold processes which generates them, and the natural connection between wear and these processes. 4.8.3. Server Models Queueing theory is concerned with the modeling of the interaction of servers and customers, and in particular the waiting of customers when services must be shared. In modeling this type of problem, queueing theory typically uses a probabilistic description of customer arrivals and service times. Queueing theory, formulated in this way, represents an important modeling technique for many types of systems: communication networks, computer systems, customer service facilities. See [Brll and [K11] for detailed discussions of queueing theory, and [Crl] for a controlled queueing bibliography. Sometimes queueing theory is extended into an area where it is not evident that the above formulation represents an appropriate system description. One of the deficiencies that arises is the service time description. The purely probabilistic description is devoid of underlying structure. That is, what are the dynamics of the

8g server that give rise to the service time distribution? If the probabilistic structure of the service time can be generated based on the dynamics of the server, it would allow the introduction of additional information, parameters, and controls regarding the server into the problem that are not usually considered. The use of a service time distribution to describe a server system results in the following viewpoint: either the service is or it is not complete. No significance is attached to a service that is partially completed. Knowledge of partially completed work does not normally enter the information structure of the problem. Therefore the conditional distributions of the service time given the amount of partially completed work are usually not considered. In many actual service situations, the rate at which work is done by the server is influenced by many factors. These factors may include effects associated with the queueing system such as type of service required, number of customers waiting for service, and the performance of other servers in the system. Some influences may be thought of as control inputs: speed control of a machine or influencing an employee's work rate through various motivational schemes. For many systems, the rate at which work is done is a natural input for influencing the system. This rate may have a deterministic or stochastic interpretation. The deterministic interpretation would be a true work rate; the stochastic interpretation would be a mean work rate. How can this be incorporated into a probabilistic description of the service time? One approach would be to parameterize the service time distribution, and let the parameter be some (possibly random) function. The problem with this approach is determining a reasonable distribution and a method of parameterizing it which preserves the intuitive sense of work rate.

70 In some systems, it is possible to measure or approximate the amount of work required for a particular service in advance. When such knowledge is available, it would be desirable to include it in the service time description. Furthermore, it may be possible to determine the amount of work remaining on a particular service, while the service is in progress. This should also be incorporated into the model. For some systems, it would be appropriate to extend the usual formulation of queueing problems so as to create a truly controlled queueing model. This model would include descriptions of the dynamics of the underlying service mechanisms. From these descriptions, the probabilistic structure for the service times would be determined. These models would also admit the concepts of partial work completion and the control of the rate of work. 4.8.4. Diffusion-Threshold Models of Servers The diffusion-threshold process is now proposed as one model of a service mechanism. The intention is to model the underlying dynamics of a server by a diffusion with threshold and show that this formulation allows for the inclusion of work progress feedback and rate of work as an input. Let the diffusion process Xf correspond to the work completed on the current service at time t. Let the threshold value A >0 correspond to the amount of work required to complete the service. Reaching A corresponds to completing the current service. At the completion of a service the process either resets or sojourns at A for an arbitrary time (until the next customer arrives). The coefficient b takes on the physical interpretation of being the (local) mean work rate. This is presumed to be a function of some control variable u. The coefficient M represents the magnitude of the uncertainty in the work rate, and the

71 magnitude of uncontrolled influences on the server. Suppose u is taken to be constant for the duration of each cycle of the diffusion-threshold process. This means that the rate of work for each service can be varied, but not in the middle of a service. Thus the service times are associated with the family of random variables { TA}. The distribution of TA is now parameterized by u and can be conditioned on the state of the current task Xt = z < A. This new model now admits the concept of a controlled queue as described before. The control input is a (mean, local) rate of work and information feedback may include the state of the current service which is the amount of work completed on the current service. Presumably, a controller could use this information and capability in order to achieve some level of performance, subject to some constraints. [Crl] includes a list of references where service control is considered. However, none of the listed works presents a viewpoint similar to the one given here. The service time distribution generated by the diffusion-threshold model can be compared to other distributions commonly used to describe service times, in particular exponentially distributed service times. For the diffusion-threshold model the probability of two events occurring "very close" (relative to the mean) in time is essentially zero. This is not so with the exponential distribution. For many physical systems, it is not likely that a service can take place arbitrarily fast. For these systems, then, the diffusion threshold model is a potentially more realistic model. Also, the diffusion-threshold model is not memoryless, and thus better describes service mechanisms with nearly deterministic service times. Many operations in manufacturing are of this type, particularly repetitive operations found in production and assembly systems.

72 4.8.5. System Failure Models This application represents an extension to the application discussed in Section 4.6.1. Consider the problem of trying to model the failure of systems, where attention is no longer restricted to individual components making up the system. In the spirit of Section 4.6.1, suppose also that the system admits a range of modes of usage or operation. Each mode of system usage causes each of the components to be subjected to some individual mode of usage. As before, the component's failure rate depends upon the mode of usage. Is it possible to formulate a failure model of the entire system that captures these features? Assume failure of the system to be indicative of the failure of any component which causes the system performance to degrade to an unacceptable level. Redundant systems or systems with intermediate degradation are not considered here. Two modeling approaches using diffusion-threshold processes are proposed. The first approach is to use a scalar diffusion-threshold model as a reduced order, aggregated failure model. The representation is essentially the same as before, although the physical significance of some parts of the model may now be obscured. Since a scalar random variable is being used to describe the aggregated wear of the system, there may no longer be a physically meaningful relationship between the diffusion state and the system. Of course, the threshold value suffers in a similar way: the assignment of the maximum aggregated wear is no longer a simple problem. There is a second approach that preserves some of the physical significance of the models in Section 4.6.2. Suppose the scalar diffusion assumption is removed by allowing the diffusion to be a vector process in IR" and the threshold to be a boun

73 dary in JR. Assume that each component of the diffusion represents an actual system component. In this case, the boundary might be a union of hyperplanes, as described by equation (4.5.6). Failure is indicated by the diffusion achieving any part of the threshold boundary. Since redundant components are not considered here, only those components whose failure will result in a system failure have an associated diffusion component and threshold hyperplane. Each component of the system has an associated component in the vector drift coefficient. The diffusion coefficient is now a matrix expressing the interaction of all the components of the system. Wear measurements consist of a vector of wear measurements, one for each component of the system. For the particularly simple case of full decoupling the probability distribution is given by Theorem 4.5.1. This corresponds to independent component wear in the system, but equal capability for causing system failure. 4.8.8. Project Models This category can be thought of as an extension to the service models discussed in Section 4.6.3. Consider a project or job requiring the cooperation of workers, and perhaps the coordination of equipment, resources, deliveries, etc. The completion of the project requires the completion of a certain amount of work. How can the progress of the work, the rate at which work is done, and the effect of uncontrolled or unanticipated influences on the project be modeled? A deterministic model is not generally correct; this is substantiated by practical experience and observation of the progress of several large projects, although some projects are less likely to have large variations in their schedules than others. What is required is the development of a model for the progress of projects that includes stochastic effects and the impact of work rate

74 influence, and from which the probabilistic descriptions for the completion time for the project conditioned on the current state of the project and the amount of resources committed can be computed. A diffusion-threshold process is again proposed as a model. Let the diffusion state X,, represent the work completed at time t, and the threshold A represent the amount of work necessary to complete the project. As an aggregated variable, the scalar random variable Xi may not have a simple physical interpretation. Let the control represent the amount of resources committed to the project, effectively controlling the work rate on the project. Thus the drift coefficient would normally be an increasing function of the control. The control may affect the diffusion coefficient as well, reflecting the coordination problem associated with large task forces. Projects with large suspected variance in their schedules can be accommodated by suitable selection of the diffusion coefficient. Projects with large diffusion coefficients correspond to risky projects. An interesting situation in this model is that Xt < 0, or locally decreasing Xt has a physical interpretation. Observe that errors or mistakes in the project cause a possible increase in the amount of work required to complete the project. This is no doubt familiar to the reader. 4.7. Relation to Other Work and Generalizations The diffusion-threshold processes discussed in this chapter admit several extensions, some of which have been considered by other authors. Furthermore, there are related problems which have also been previously proposed by other authors. This section will try to briefly summarize some of this existing work.

75 The use of Brownian motion and diffusions to model various physical phenomena is not new. In fact, Brownian motion was first an observed physical process and then later a mathematical process. The deep mathematical properties of these processes offer several advantages to the modeler looking for ways to capture certain types of uncertain, erratic, noisy, or chaotic behavior. Consequently, the list of applications that have been considered is far too long to attempt to list here. The concept of controlled diffusion processes is more recent. The references [KrylI and [F11] present many of the basic ideas of controlled diffusions. However, both of these references, and in fact most of the existing literature on controlled diffusions assume continuous perfect measurements of the process and continuously variable control. These assumptions may be overly restrictive for some applications. Unfortunately, departure from these assumptions can cause many complications. In this work, these assumptions will be relaxed. See also [Bell. Most references on Brownian motion and diffusions include discussions on stop. ping times, particularly exit times. The threshold crossing times considered in this work are exit times. [Kryl], [Fll] and [Bell discuss the relation between stopping times and controlled diffusions. Another class of problems that are related to this work are inspection problems (called surveillance problems by Savage). See [Anl], [An21, [Sal]. In these problems, the control is usually of the discrete type: decide when to observe the process; decide when to re-initialize the process. The stochastic process being observed is often Brownian motion (though not always) but is otherwise usually not influenced. These problems are just examples of the very large class of stopping time problems.

76 In most of the literature, incruding the references cited here ([Kryll, [Fill, [Bell) the controlled diffusion is placed in a stochastic optimal control setting. The solution techniques generally rely on solving non-linear partial differential equations that arise from dynamic programming methods. By taking this approach, more general diffusions than those considered in this work can be handled. However, solutions are extremely difficult to obtain. Part of the motivation for the work here is to explore reasonable alternatives to solving partial differential equations. There is an alternate method to solving PDE's, however, that still allows a fairly general class of diffusions. The method uses boundary layer methods to approximate the probabilistic descriptions of the threshold crossing times. See [Matll. The requirements for this approximation technique are that the diffusion coefcient be small enough. For many applications, this is in fact the case. This technique represents a good alternative to solving PDE's, and yet accommodates more general diffusion processes. An important extension to the diffusion-threshold process is the inclusion of arbitrary jumps in the state. The diffusion-threshold process allows for a reinitialization action. This can be generalized to arbitrary (and random) jumps under the category of Impulsive Control [Be2]. These authors consider many examples of processes where both coefficient influence and impulsive control actions are permitted. Some of the applications considered in their work are related to applications discussed here. However, these authors prefer to place the problems in a quasivariational setting. This necessitates the solution of a nonlinear partial differential inequality, which is very difficult. Furthermore, these authors generally assume continuous exact measurements and continuously variable controls. Nonetheless, [Be2l

77 has many common features with the work presented here. The quasi-variational approach will be used for one of the problems considered in this thesis.

CHAPTER 5 THE DRILLING PROBLEM 5.1. Introduction In this chapter, one manufacturing problem will be considered in some detail using the control theoretic approach. This problem is called the drilling problem, and has already been introduced in Chapter 3. Some simplifying assumptions will be made here in order to facilitate the presentation of the essential concepts. Crucial to the development of the drilling problem is the use of diffusion-threshold processes to model tool wear. The use of this modeling method allows the control theoretic approach to be taken. The drilling problem is properly a machining economics problem. However, the features of the problem and the modeling and control methodologies used in this work are considerably different than the usual machining economics approach. The control theoretic approach imparts a distinctively different viewpoint. Actually, two different approaches will be considered in this chapter. The first approach will use the diffusion-threshold model of tool wear, but will otherwise assume a traditional control policy and information structure. The second approach will explore the potential of additional control capability and the significance of tool wear measurement feedback. An example problem comparing both approaches will 78

79 be discussed in the next chapter. The drilling problem is intended as a prototype manufacturing problem. The specific use of a drilling operation in this problem is only to facilitate the presentation of the concepts and is not meant to imply a restriction of the ideas to that type of machining operation. The features of the problem have been designed to reflect important characteristics of manufacturing systems. In an actual system, some of these features may differ, typically resulting in a more complex problem. Further, there are important manufacturing issues that are not represented in the drilling problem. Nonetheless, the problem is an attempt to convey how the features of manufacturing problems affect the kinds of problem approaches that can be taken, and how new approaches can arise from the intelligent manufacturing setting. 5.2. Problem Description A description of the drilling problem has been previously presented in Chapter 3. Only a brief review of the problem, along with more detailed discussions concerning specific features and assumptions will be given here. A drill is used in a fixed operation carried out repetitively on parts. A fixed volume of material is removed from each part. As metal is removed from the parts, the tool wears. The tool wear mechanism is only known empirically, and variation in tool life is evident. As the tool wears, it eventually breaks or becomes unacceptable and must be replaced. Failure of the drill necessitates replacement, but can also cause damage to the part being machined. The production of parts results in profit and thus the profit earned is related to the production rate. However, there are other factors affecting the profit, such as tooling costs and scrapped parts. Tool replacement is costly in terms of time and

80 material. Tool breakage is in general more costly than simple replacement, due to possible part damage and the unplanned replacement that results. Tool wear measurements may be occasionally available. If they are available, these measurements are to be used in the determination of operational policies. If tool wear measurements are available, they are only available when the tool is disengaged from the part. Tool wear measurements are not available during the drilling operation. Certain features of the drilling problem are common to many manufacturing problems. These features will be briefly reviewed here. The discrete nature of parts is represented and imposes restrictions on the problem. The rate of production is specifically cited as a decision control variable. Tool failure affects the quality and quantity of the production output. Production rate and tool failure rate are not independent phenomena. The objective in the drilling problem is to determine policies for tool replacement and for feed speed selection to obtain a suitable tradeoff between production rate and tool failure rate. Appendix A has a description of the drilling terminology used in this work. Drilling is a machining process with two parameters: feed speed and spindle speed. For this work, the drilling problem will be reduced to a problem with one independent parameter. This parameter will be the feed speed. The spindle speed will be assumed to vary in proportion to the feed speed in order to maintain a constant ratio; i.e., the feed is assumed constant. This assumption simplifies the analysis, but does not represent a limitation of the model or the approaches used.

81 The term tool failure will mean breakage or wear past an unacceptable limit. Breakage and in particular early breakage of the tool is arguably a discontinuous process, and thus should be modeled by processes that can accommodate discontinuities. In this work, all tool failures will be aggregated with the understanding that early breakage (due to defective tools) is a relatively rare event. This is true of most production situations. Feed speed control, tool replacement decisions, and tool wear measurements will be constrained depending upon the control approach being taken. For the age replacement policies, the feed speed will be fixed and tool replacement will be based upon the number of parts drilled. For feedback policies with variable feed speed, tool wear measurements will be available prior to starting a part. At that time, the tool may be replaced, and/or the feed speed may be changed. The feed speed will remain constant throughout the operation on a part. In all cases, an instance of tool failure will cause the current part to be scrapped. Part repair will not be considered in this work. Furthermore, tool failure will be considered to be immediately detectable. This is not a hard assumption, but it simplifies the analysis. A tool replacement must occur after a tool failure before continuing. There are many possible performance measures that can be used for the drilling problem. In fact, even if a single performance measurement is specified, there are usually secondary considerations that are important but not represented in the primary measure. In this work, the primary performance measures will be economic. In particular, cost per time and cost per part will be used to evaluate control strategies. *However,

82 there are many secondary considerations that may be significant in a manufacturing setting. These include: amount of scrap produced, frequency of tool failures, frequency of tool changes, etc. The importance of these secondary considerations is due to the burden they may place on the manufacturing system through resource requirements, additional congestion, or disruption. As an example, frequent tool changes may necessitate greater tool handling capability and greater tool setup capability. This is over and above the pure cost of the tool and tool change. Although the economic issues are important, they are not the entire picture. Unfortunately, some of the existing literature in machining economics ignores this point. 5.3. Survey of Related Work Aspects of the drilling problem have been considered by many authors. The work of Taylor [Tayl] is generally considered the first extensive treatment of tool wear and machining economics. One result of his work is the Taylor tool life formula relating tool life to cutting speed. Much of the work after Taylor presumed that the tool life is deterministically related to the cutting speed and other machining parameters, using variations of the Taylor formula. Under the assumptions of a deterministic relation, simple calculus can be used to arrive at optimal machining parameters for any of several criteria. See also [Drl] and [Hil] for examples. Many refinements and extensions are possible, including the consideration of multiple machines, constraints on machining parameters due to finish and power requirements, and tool geometry. Usually these treatments assume that the tool is changed at the end of its life, as given by the tool life formula, and that tool breakage and scrap parts do not occur.

83 More recent work in the area has recognized the stochastic aspects of tool life and the impact that tool life uncertainty has on machining operation productivity. In these works, tool life is viewed as a random variable whose distribution is parameterized by cutting speed and other factors. Some researchers have assumed particular distributions, while a few have only specified moments of the tool life random variable. See [Dell, [Erl], [Kell, and [Shkl]. The machining economics problem, whatever the assumption about tool life, usually considers as performance measures production rate, cost, or time to produce a part. Various types of constraints have been proposed for inclusion in the problem. Several things are not usually considered, however. The concept of information feedback and on-line control of machine operation is almost never considered. As a result, most machining optimization problems have assumed constant machining parameters. On-line variability of machining parameters based on tool wear measurements and other information is not usually considered. Policies for tool change are invariably defined in terms of information such as the number of parts machined, or change upon failure. Costs due to scrap and damage, or the status of other machines in the manufacturing system are not considered in tool replacement policies. Most importantly, tool wear information is not incorporated into the policies. 5.4. The Tool Wear Subproblem The problem of tool wear is central to the drilling problem. Without an appropriate model that captures the essential features of tool wear, the drilling problem cannot be readily approached in a control theoretic way. Consequently, tool wear model development is very important. Some background material is presented in this section that summarizes existing approaches to the tool wear subproblem.

84 The tool wear problem has been the subject of much study, and an extensive body of literature reflects this. There are at least two views of the problem that can be taken. The first is to explain on a physical basis the mechanisms of tool wear. The attempts in this area often lead to very complicated formulations for tool wear as a function of several variables. See [Dal], [Kani] and [Kol] as examples. Unfortunately, these models are not complete, describing at best the normal evolution of some aspects of tool wear under restricted conditions. Since the manufacturing environment is uncertain, and the information requirements of these models can be considerable, their current utility in the machining economics problem is debatable. The second view is that usually taken in machining economics. Precise description of tool wear phenomena is forsaken for empirical formulas that are easier to use, and that capture the essential character of tool life as a function of machining conditions. The empirical formulation of tool wear can be considered either deterministically or stochastically. Deterministic formulations are prevalent in the earlier literature, but more recently the stochastic nature of tool life has been recognized. The stochastic formulations usually assume that the deterministic formulas properly represent mean values of tool life. References [Del], [Hi2], [Kel], and [Wal] give various viewpoints of the tool wear problem. Also, the references on machining economics usually give some tool wear model. The stochastic formulation brings with it another level of complexity. If tool life is a random variable, its distribution must be specified. Actually, a family of distributions parameterized by machining conditions must be specified. Many distributions have been proposed for tool life including exponential, normal, and lognormal. In general these distributions are arrived at from purely empirical considerations, and

85 not from any physical basis. This is not an entirely satisfying situation. It should be mentioned that some authors have avoided this problem by parameterizing only the moments of the tool life (usually the mean and variance) and not specifying a distribution. It is asserted that a new model of tool wear is required in order to accommodate the intelligent manufacturing approach. This new model must incorporate certain features. The stochastic behavior of tool life must be recognized. The influence of machining conditions must enter into the model in a clear way. The distributions should arise from physical considerations of the process. The results of the model should agree with observed behavior in a statistical sense. This leads to the development of a diffusion-threshold model for tool wear. 5.5. Diffusion-Threshold Model of Tool Wear 5.5.1. Model Formulation The diffusion-threshold process discussed in Chapter 4 is now proposed as a model for tool wear in the drilling problem. The following analogy is made. Let the diffusion process {X } represent an aggregated wear variable for the tool. It is understood that all of the categories of tool wear are somehow represented by a single variable, and Xt therefore represents the magnitude of wear at time t. The feed speed will be regarded as the control input ut, with the drift coefficient b ( ) being a positive increasing function of the feed speed. The drift denotes a local mean rate of wear. The diffusion coefficient is the square root of the local rate of change of the variance. Let the maximum allowable tool wear correspond to the threshold A. When the wear reaches the threshold, the tool is considered unacceptable and must be replaced by a

86 new tool. The new tool is assumed to have zero wear. This is the re-initialization action. Likewise, the decision to replace the tool results in a re-initialization prior to reaching the threshold. The decision times will take place between parts; i.e., just prior to the start of a new part. At these decision times, denoted {to}, information concerning drill wear may become available. In this work, assume that exact measurements of the drill wear, X,, become available if tool wear feedback is allowed. 5.5.2. Rapproachment with Taylor Tool Life Formula For the drilling problem and other tool wear problems, a comparison can be made between the diffusion-threshold model and other more usual models. A comparison to the (simple) Taylor tool life formula [Drl] will be considered. The Taylor formula, in use for many years, is a strictly empirical formula for calculating tool life. As is shown in Appendix A, for fixed feed the Taylor formula may be written as uT" = C1 (5.5.2.1) where: u the feed speed T a life of tool n= an empirical constant dependent upon the part material, tool type, and machine type Cl-an empirical constant dependent upon the part material, tool type, and machine type Assume that replacement is indicated by having reached a certain level of wear that is fixed for a given tool type. Let this level of wear be denoted by W and let the wear of the tool at time t be denoted w(t). Also, define the instantaneous feed speed

87 by u(t). If the tool life given by the Taylor equation is interpreted as a mean value, a diffusion threshold model with the same expectation can be constructed. Let the drift coefficient be given by W b (u ) = -j- u (5.5.2.2) so that t 1 E[w(t) =l f-1U(r)"dr (5.5.2.3) 0 - tool life can be computed as E[TI4W Cl 2 n (5.5.2.4) in agreement with the Taylor tool life formula. No restrictions are placed on the diffusion coefficient a by the Taylor formula. In this work, a will be assumed constant. Note however that this does not imply that the variance of the tool life is independent of the feed speed. 5.5.3. Explanation, Justification and Limitations of the Model Some explanation of the diffusion-threshold model of tool wear is required in order to justify its use. Further, the restrictions of the model need to be presented so that limitations on its use are understood. The diffusion-threshold model of tool wear is motivated by several issues. First, the difficulty associated with trying to model tool wear deterministically using physical laws. This difficulty arises from the nature of the tool wear process: it is complex and chaotic, and it takes place in an uncertain environment with unmeasurable con

88 ditions. These statements are particularly oriented toward the production environment. Second, there are observed differences in tool wear evolution under similar operating conditions. Third, the system has a hybrid characterization; that is, there is tool wear and there is tool failure. There are several goals that the modeling effort should try to achieve, if possible. First, the model should capture a suitable analytic description of system evolution. This requires presenting an appropriate view of the phenomena (macroscopic vs. microscopic) and that the level of detail incorporated into the model be compatible with the intended use of the model. Second, the model should use an established mathematical base, and the model should be in some way tractable to be of value. Third, the model should have a certain intuitive appeal, although this is hard to quantify. Fourth, the model must be appropriate for use with the control theoretic viewpoint. The important characteristics of the diffusion-threshold model are as follows. Brownian motion represents the prototype chaotic system or system driven by noise. Without deeper understanding of the problem, Brownian motion is often a reasonable first approximation for systems that exhibit chaotic or noisy behavior. Diffusions are then the natural generalizations of Brownian motion. Properties of diffusions that facilitate mathematical analysis include the strong Markov property and continuous sample paths. Furthermore, the diffusion-threshold model has a certain intuitive appeal: a system evolves in time until some limit is reached. Finally, there is some agreement between experimentally observed tool wear processes and the diffusionthreshold model. This is evident in the similarity between the inverse Gaussian density and densities that have been proposed for tool life without any physical basis;

89 e.g., lognormal. The diffusion-threshold model also invites extension to more general diffusions with more complex coefficients. This does introduce computational difficulties, however. The model is thus extensible as additional properties of tool wear are discovered or proposed. This extensibility is very important. The model is not without limitations, however. Brownian motion (the mathematical process) is an abstraction and not a true characterization of the phenomena at the tool/part interface. Brownian motion is too erratic (since sample paths have unbounded variation) to truly represent a physical system. The Markov property inherent in diffusions is probably not valid for tool wear. As an example, material properties can depend on past histories and not just on current conditions. Unfortunately, deviation from the Markov assumption is hard to handle mathematically. Negative excursions of the diffusion are possible, but this has no physical interpretation in terms of tool wear. However, the probability of sustained negative values will in general be very small. This is similar to assuming Gaussian distributions for random variables that in fact are constrained in magnitude. The lack of known properties for the diffusion coefficient is disturbing, but not really a model limitation. It is more a limitation of available data. Finally, it is not clear whether or not the model captures certain types of catastrophic failure correctly. Since the diffusion process is continuous, it cannot literally represent jump phenomena. However, it can be argued that small jumps are still accommodated in a probabilistic way. Whether or not large jumps are accommodated probabilistically depends upon the diffusion construction (the coefficient selection). Generally, the model will not be assumed to represent early tool failure due to defective tools or parts. It is possible

90go to extend the model to allow for random reinitializations. This extension may capture premature catastrophic phenomena. 5.8. Age Replacement Policies for the Drilling Problem In this section, traditional control policies for machining economics problems will be considered. Traditional policies assume a fixed feed speed and replacement of the tool after either a tool failure or a predetermined number of parts has been processed. In other words, replacement takes place after a fixed machining time; hence the name age replacement. The diffusion-threshold model of tool wear will be used in this section. Furthermore, the features of the drilling problem will remain as described. This results in a problem formulation and solution method that is different than typical machining economics problems. Therefore, even though traditional policies are studied in this section, new results are obtained. The section will begin with a discussion of age replacement policies for diffusion-threshold processes, and a discussion on renewal theory. The application of these ideas to the drilling problem specifically will follow. 5.8.1. Diffusion-Threshold Processes and Age Replacement Policies Under age replacement policies, the evolution of the diffusion-threshold process is influenced by selection of the variable u, and by allowing the process to be reinitialized after a certain age has been reached. In this section, all reinitializations will be to zero. A control policy ~r consists of a pair (u,t,) where u determines the infinitesimal coefficients in the diffusion and t, is the replacement age. If the current cycle reaches age t, without a threshold crossing, the cycle is terminated. If the threshold is reached prior to t, then that event terminates the cycle. This class of policies will be denoted age replacement, but the availability of the selection of u

91 generalizes the usual use of this term. In the analysis of the drilling problem under age replacement policies, it will become convenient to alter slightly the policy definition to an equivalent description. The reasons for doing this will become evident. The probabilistic structure of a cycle under an age replacement policy can be developed. Assume an age replacement policy ir = (u,t,). Let T be the random duration of one cycle under this policy. Then T = min(TA,t,) (5.6.1.1) where TA is the threshold crossing time and t, is the replacement age. The distribution function Fr is then given by: QA (t 10; if t>t, (5.6.1.2),(t) ift>t, where QA(t 1I; U)= f A {-(A - b1 )2 d (5.6.1.3) is just the threshold crossing probability distribution. Note in particular that P'[ T = t, 1= - QA(tr I 0; u) > 0 (5.6.1.4) so that T = t, with positive probability. The expected value of T can be computed from the above: o9 a~tr AT 4E'[ T ] = td(t) = ftdQA(t 0; u) + t,(i - QA (t, 10; u)) 0 0 o o A 1 exp -(A - b2 2 +A t exp B2 } 15 0Jz~-~nc2cO 232 o _ /-_2T'_i N_2-r a, 1 7:'i

92 5.8.2. Renewal Processes in the Drilling Problem The drilling problem, along with many other manufacturing processes, can be described in terms of a cyclic sequence of events. The nature and number of events as well as their temporal relationship in any given cycle may be random, however. Furthermore, more than one cycle of events may be present. In the drilling problem, two obvious event cycles are the part processing cycle and the tool cycle. Sometimes it is possible to identify a sequence of cycles that may be adequately modeled as probabilistically independent and with identically distributed duration. For the drilling problem under age replacement policies, tool cycles can be so modeled. When such a sequence is available, and is such that it can be used to describe the long term performance of the system, then a renewal theory approach is suggested. Placing the problem in a renewal setting has the great advantage of allowing the use of several powerful theoretical results. 5.6.3. Application of Renewal Theory In this section several key renewal theory results will be applied to the drilling problem. For a more complete treatment of renewal theory see [Fell, [Karl], [Rol]. Let {Ti } be the set of tool cycle durations. That is, the random variable Ti is the duration of the i" tool cycle. Assume that these random variables are independent and identically distributed with common probability distribution function FT(). Let E[ T, ] =A < oo (5.6.3.1) Define the set of random variables {S, } by So = o (5.6.3.2)

93 S, = T. (5.6.3.3) i= 1 The random variable S, then corresponds to the cumulative time of the first n tool cycles, or the time at which the n' tool cycle completes. The first cycle is understood to begin at t = 0. Define the counting process {Nt: t >0} by Nt = max{n>0: S5<t} (5.6.3.4) The random variable Nt is the number of complete tool cycles that have occurred up to time t. Note that the cycle on-going at time t is not counted unless t is its completion time. The process {Nf } is a renewal counting process. Define the function m:J + -- AR + by m(t)= E[ Nt ] (5.6.3.5) This function is the renewal function. The value of the renewal function at time t is the expected number of completed tool cycles that have occurred by time t. The advantage to be gained by placing the drilling problem in a renewal setting is that long term performance can be assessed using only statistics for a single tool cycle. Since the computation of single cycle statistics is generally easier (though not necessarily easy) than the computation of long term statistics, the attraction of the renewal setting is evident. The number of tool cycles per unit time satisfies the relation lim = L with probability 1 (5.6.3.6) t —oo t AT by the strong law of large numbers. The elementary renewal theorem [Rol] states that the expected number of tool cycles per unit time is similarly described:

94 lim m(t) _ (5..3.7) t —oo t AT Assume now that for each tool cycle, some cost is incurred. Assume that the cost incurred in one tool cycle is independent of all other cycles and their associated costs. A dependence between the duration of a tool cycle and the cost for that tool cycle is permitted. Under these circumstances, the expected long term cost per time can be computed on the basis of single tool cycle statistics. Let (cj } be the set of tool cycle costs, with cj the cost for the jyh tool cycle. Assume that these random variables are independent and identically distributed with E[ c= ]- < oo (5.6.3.8) Define the cumulative cost function Ct -- E (5.6.3.9) The random variable Ct is the cost incurred through the first Nt tool cycles. Then the long term cost per unit time is given by the following [Rol]: Ulimn with probability 1 (5.6.3.10) t —o t Cr and E[ CJ _ li t = (5.6.3.11) t-oo t AT That is, the expected long term average cost per time converges to a value that may be computed by considering only statistics for a single tool cycle. Remark: The above result holds even when the cost is not lump sum. That is, even if costs are distributed throughout the cycle, the results remain valid ([Karl], [Roll).

95 An extension is required in order to allow for a control structure in the problem. 5.6.4. Controlled Renewal Coat Processes The renewal theoretic view starts with the collection {Ti } of random times. It is reasonable to inquire into the nature of the physical processes that give rise to these random variables. If these physical processes can be influenced by external inputs, then a means exists for controlling probabilistically these random variables. This gives rise to the concept of a controlled renewal process. Assume that there are inputs available that affect the probability distribution of the random variables {T,}, and the associated costs {c,}. Then as long as the control policy preserves the renewal structure, the renewal results can be used to evaluate the performance of the policy. Of course, if the policy does not preserve the renewal structure, other evaluative means must be employed. It is sufficient to identify the controls available and their effect on the indicated random variables. This is sufficient, but not entirely satisfying because it lacks a sense of physical cause. Instead, consider a different approach. Suppose that an underlying process is identified that gives rise to the renewal cycles. That is, this underlying process is a model of the dynamics of the system with an explicit representation of how external inputs affect its evolution. If the underlying process is such that the probabilistic structure of the renewal can be computed, then the nature and effect of the control can be inferred instead of being hypothesized. This motivates the use of diffusion-threshold models to describe the underlying dynamics of renewal processes.

96 5.8.5. Analysis of the Drilling Problem under Age-Replacement Policies Assume a tool cycle begins with a new tool, and ends after the tool is replaced. During the tool cycle the following events can occur: parts are produced causing tool wear; the tool reaches the replacement age or else it fails; tool failure produces scrap; finally, a new tool is installed. Assume that the tools are independent, and tool wear is described by a diffusion-threshold process. Under age replacement policies, the tool cycles generate a renewal process. In order to preserve the interpretation of the variables under control, a slight alteration in the definition of a policy is required. The continuous variable under control is the feed speed u. The drift and diffusion coefficient are then functions of u. Using the Taylor tool life approximation, an appropriate form for the drift is b = u'. The diffusion coefficient a will be assumed constant. In order to conform with the drilling problem formulation, age will be expressed in terms of number of parts completed, denoted by n,. This also conforms with typical specifications in an actual manufacturing environment. Therefore, a policy will be defined as r = (u,n,) where u E (O,oo) and n, E {1,2,...,oo}. An implicit assumption is that n, >1; i.e., that at least one part can be completed by one tool on the average. The special case n, = oo will denote a failure replacement policy. Under a failure replacement policy, the tool is replaced only when it fails. The time of replacement is now a function of both u and n,. Let the processing time for one part be given by tf = V where V is the depth of the hole to be drilled. Then t, = n,.t = n, V. Associated with each tool cycle is a cost. This cost consists of any resources used (including time) minus any profit earned for completed parts. Define the following parameters:

97 G - profit earned per completed part R - cost of a tool replacement, including tool and time costs B A cost of a tool breakage, not including replacement cost K - overhead cost rate for machine in operation tR = replacement time tB = repair time Overhead costs incurred during tool replacement and repair are assumed to be included in R and B respectively. Note that a total cost of B+R is associated with a threshold crossing (breakage or unacceptable wear). In the following formulation it is assumed that all profit for the current part is lost when a breakage occurs. This conforms to the assumption that failed tools produce scrap. The replacement time tR will be a part of every cycle. The repair time t8 will be a part of those cycles with tool failure. It is convenient to introduce the random variable 1 as the number of parts produced in one tool cycle (not counting scrap parts). Let' denote the random duration of one tool cycle, and let T = min(TA,n, -). The random variable T is the duration of the total tool cycle, including repair and replacement time. The random variable T is the tool life. As stated earlier, the long term expected cost per unit time can be approximated by the expected cost per expected time for one tool cycle. The expected long term cost per time is given by: E cost/cycle E[ R + KT + Blr=rA - GP] (5.6.5.1) E[ duration of cycle ] Et[ ] Also of interest will be the expected long term cost per part:

98 r E't cost/cycle E[ R + KT + Bl[r=r- G 56.5.2) E'[ part/cycle i Es[ Y I Strictly speaking, there is an ambiguity that arises when TA = n,-K; since this occurs with probability 0, the assumption that the part is scrapped presents no difficulties. Also note that overhead costs for repair and replacement could have been explicitly included in the cost function. In order to compute the performance statistics of interest, the following expectations must be determined: E'[ r[, E'[rl, E'[] Note that E't[' ] Er[ T ] + E'[ tBlrrTAI ] E'[ t ]I _='[ T i]+ tg QA(nr,- I; u)+ tR (5.6.5.3) and Er[ T ] has been previously computed: ~,2 ( 2ao7 } wq+A 2 (AItL7)a }3 (5.6.5.4) The computation of E[ f ] is somewhat more complex. Observe that: = E T1[re(jI,(j i l)tfl I + nt, 1 it f < TAI (5.6.5.5) i= 0 Therefore, Is -1 E'r[( Ji = CP[ QA((i+1)tf 10; u)- QA,(jtt; u)] + n, 1- QA(n,?t 1; u)] j=0 = n,[ 1- QA(n,t 10; u) ] + [n, - 1][ QA(n,t 10; u) - QA((n,-l)tf Io; u) ] + + [ QA(2tf 10; Ou)- QA(t, IO; u) ]

99 n, - E QA,(jt fIo; ) (5.6.5.6) a -o j= 0 Using these expressions, the performance statistics J~t and Jr can be computed. Substituting into (5.6.5.1) and (5.6.5.2) yields R + KE"[ T ] + BQA(t, 0; u) - GE[] (5 7) i.. = (5.6.5.7) E'[ T] + tHQA(tr I 0; ) + tR Also of interest will be the expected long term cost per part: R + KEr[ T ] + BQA(t,; u) G (5.6.5.8) E'[ Pi with E'[ T ] given by (5.6.5.4) and E'[ 1i ] given by (5.6.5.6). In general, numerical integration can be used to compute these functions for a given policy ir. In Chapter 6, algorithms will be given that allow the evaluations to be carried out without numerical integration. This facilitates rapid evaluation of a policy's performance. 5.8.6. Optimal Age Replacement Policies Since the economic cost functionals for the drilling problem under age replacement policies can be evaluated, it is possible to consider optimal age replacement policies with respect to the cost functionals. An optimal policy r' consists of a pair (u,n,) such that J"t < J' for all admissible policies ir. Since the variable n, is an integer, the optimization procedure is a mixed integer programming problem and is not straightforward. There are several possible approaches. The first approach is to use one of the available optimization algorithms for handling mixed programs. Since the system is of low order, this is not unreasonable. A second approach is to assume that n, is a positive real number and simply roundoff the result. Although no statement of the reasonability of this scheme is presented here, some numerical examples suggest that it is not a bad approach. A third approach, and one that is used in a later chapter, is an explicit calculation of

100 the cost functionals for fixed age replacement to determine optimal costs for that age, followed by a search among the ages. This can be done graphically and has proven to be quite effective and very fast. This does rely on fast algorithms for evaluating the various f,!,nctions. These will be discussed in a later chapter. The optimal policy is very simple to describe. All drilling takes place at the optimal feed speed u*. A counter maintains the number of parts completed by the current tool. The tool is replaced when the tool fails or when the counter reaches n,, whichever occurs first. The replacement of the tool resets the counter. The simplicity of the pc!icy allows a variety of possible implementations. 5.7. Feedback Policies for the Drilling Problem In this section, the drilling problem will be examined in an intelligent manufacturing setting. In this setting, information and control assumptions will differ from the usual machining economics problem formulations. This will allow the exploration of a new class of decision policies. In the next chapter, a comparison between the two approaches (in Sections 5.6 and 5.7) will be made for an actual problem. Since tool wear measurements will be assumed available for the policies considered here, they will be called feedback policies. However, variability of the feed speed is also assumed. 5.7.1. An Optimal Control Problem: General Formulation Consider the drilling problem previously described. Assume that pieces are being machined, and that the time to complete each piece depends on the selected feed speed. Furthermore, assume that measurements of tool wear can be made at the completion of each piece. At each measurement time, a decision can be made to

101 adjust the feed speed, and/or change the drill. Each of these decisions has some cost associated with it. In addition, there is a penalty cost associated with breaking the drill. The optimization problem is to make these decisions in such a way as to minimize some cost functional. The formulation of cost functionals for feedback policies presents some difficulties. The cost functional used must capture the important manufacturing concerns and allow for the additional information and control capability indicated. Ideally, cost functionals similar to those introduced for age replacement policies would be used. These cost functionals capture the long term performance of the system. In order to use the renewal theory setting, it is necessary to restrict attention to feedback policies which preserve the renewal structure. This is not a serious restriction. A far more serious problem is the computational difficulties encountered when feedback policies are considered. The probability functions involved are extremely difficult to compute. An alternate approach might be to formulate a dynamic programming problem over one tool cycle (or an even shorter horizon). This again presents major complications because it involves programming over stopping times with incomplete information. Furthermore, the probability functions are again very difficult to compute. The difficulties associated with these approaches motivates the consideration of alternate cost functionals. An alternate formulation should yield good performance, but be computationally tractable. In particular, on-line computability would be desirable. This is because the actual manufacturing system and its parameters are stochastically varying in time. Long term optimality would be willingly sacrificed. These considerations have resulted in the formulation of a class of cost functionals

102 different than those introduced previously in Section 5.6. The class of cost functionals considered in this analysis are called one step. One step in this context means one part ahead. One step costs incorporate the profits earned and the costs incurred in producing the next part. The formulation of one step costs must be carefully considered. In particular they must be formulated so that behavior extremely detrimental to successive parts is not encouraged. For this problem, define a control vector u (uv) where uE (O,oo) is the feed speed and vE {0,1} is the replacement decision, where O corresponds to not replacing the tool and 1 corresponds to replacing the tool. Define the following economic parameters: R - cost of a tool replacement, including tool and time costs B - cost of a tool breakage, not including replacement cost K overhead cost rate for machine in operation and the functions: g(u) - profit rate for selected feed speed u T. (u) - processing time for a part corresponding to a constant feed speed u and the random variables: M[tr P,,] sup {X~} the maximum excursion of the process over [to,tl] h (X, + Tr,M[tk,,h+ rTl,k) - tool utilization cost for processing a part Overhead costs incurred during tool replacement are assumed to be included in R. Note that a total cost of B+R is associated with a threshold crossing (breakage or

103 unacceptable wear). A candidate function for h will be presented later. In the following formulation it is assumed that all profit for the current part is lost when a breakage occurs. A cost functional can now be formulated: Minimize J(u_,zk) = (l-v)-Jl(u,zk) + v'J2(,0) (5.7.1.1) where Jl(u,zk) = E[ -g(u)- T, 1t,+2Tf<-TAl + (B + R)-1(TrA <f+TrI + h(Xtk+r,,M[tk,T+rI,zk) + K (Tf A (TA-tk)) I X(tk)=zk ] (5.7.1.2a) is the expected one step cost if the tool is not replaced, and J2(U,0)= E[-g(u)-Tf 1.T <rzI + R + (B + R).1(TAI rfl + h(XTrfM, T1,O) + K (Tf A TA) I X(o)=0 ] (5.7.1.2b) is the expected one step cost if the tool is replaced. Note that (T/ A T2) - min(T, T2) and that zk is the measured wear. The explicit use of 0 in J2 is only a reminder of its conditioning on zero wear. Before examining a special case of this problem, there remains the question of the reasonability of this cost functional. In response to the earlier comment, this cost functional contains terms which discourage initial detrimental behavior (high feed speeds). In particular, high feed speeds may be discouraged through the tool utilization cost term, and by the increased probability of a threshold crossing. A threshold crossing causes a complete loss of profit for the current part, and incurs the additional costs of replacement due to breakage (R+-B).

104 5.7.2. Restricted Formulation A restricted formulation of interest can be obtained under the following assumptions. Without loss of generality, assume that tk =0. Let the threshold value A = W, the maximum tool wear. Let b(u) = Ium", where 3>0 and m >1 are constants. This form of the drift function is motivated by the Taylor tool life formula with mn = C=1 and T1 (u)=f where V>0 is the depth of the hole to be drilled in each part. In this case, g(u). T (u) = gV G, the profit earned per completed part. Let h = D(XT,-zo)l1Mrf < A + D-(A-z0)' 1[MrI >_ A (5.7.2.1) That is, the tool utilization is proportional to the amount of tool consumed, with a maximum tool utilization given by A-z0, the remaining tool utility. The constant D is the tool utilization cost rate. Further note the equivalence of the random variables: 1[MTf <Al = 1(Tf < TAI (5.7.2.2) Summarizing, the new economic parameters are: G - profit earned for a completed part D - tool utilization cost rate The restricted formulation becomes Minimize J(u.,z0)= (1-v)'J(u,zo0)+ v J2(u,0) (5.7.2.3) where J1(u,zo) = E[-G TL r,<r, + (B + R )1lrA <r, + D'(Xr,-Zo)1Tir,< Tr

105 + D.(A-zo)-1rA<Trl + K.(T1 A TA) X(O)=zo I (5.7.2.4a) and J2(u,O) = E[ -GlTfrf,<TrA + R + (B + R)'1[TArfI + D XTrf 1IT<rAJ + D A -1TAl<rl, + K-(Tf A TA) I X(0)=O ] (5.7.2.4b) and T1 (u) = - (5.7.2.5) U The term (Tf A TA) can be alternatively expressed as (T, A TA)= T'l{Tf <TAl + TA 1Il[rA<r (5.7.2.6) As a consequence of this restricted formulation, the following functions become relevant. 8A( I Zo)= E[ V I zo0 = P[ TAC_ I Zo0 (5.7.2.7) (TA < I U rA (u I Zo) = E[ (Xv -z0).i < r I Z0 (5.7.2.8) zA(u I 20)= E[ TA'r1TA <V I I0 ] (5.7.2.9) The function A (U I 2) is the conditional probability of hitting the threshold before part completion. The function rA (u z) is the conditional expected change in wear for the tool for those sample paths that do not have a threshold crossing prior to finishing the part, weighted by the probability of a threshold crossing not occurring. The function ZA(uI 1 ) is the expected time of the threshold crossing conditioned on sample paths that do have a threshold crossing prior to part completion, weighted by the probability of a threshold crossing occurring. The functions 8A, rA, and zA can each be expressed in integral forms using the results of Chapter 4. The functions 8A and rA follow easily from the threshold crossing density:

106 V V a (5.7.2.10) A (U I Z) = QA(- I; U) = qA ( I; u)d (5.7.2.10) V zA(u z )= f lqqA (7 z; u )d (5.7.2.11) o where a exp {( a - I) )=?T)a ( 0; ) (5.7.2.12) 2V~,7 2 and a -A - z, z < A. The function rA is somewhat more complicated to compute. Let t -V. Without loss of generality assume that z = 0. Then A(u Io) = E[X XV v I Xo = ] [ - <TAl 00o 00 = f f|IVC<AlgX, Mt (7,l)d,,dP 0 - f00 A V = f fgxxM Mt (7,I)dd (5.7.2.13) where g is the joint density function from Theorem 4.3.4. Equation (5.7.2.13) can be further simplified by splitting the integral into two parts 0 A A A f i f gx, mt (,,?)d vd vd + f I f gxt Mt (, ) d v d (5.7.2.14) and evaluating. The result is given by A A (u 10) = fIp (A,u,7,)d q (5.7.2.15) -00 where p (a, u, ) = _{-u( _ - L )} - exp {2u.a )} (5.7.2.16) When A > z ~ 0, the result is given by

107 A-s r,(u I)= f qp(A-z,u,q)dq (5.7.2.17) -00 Note that the function p is a Gaussian density times a weighting function. This is more easily seen by substituting t! = V into (5.7.2.16). The functions J1 and J2 can be expressed in terms of these functions as follows. Jl(u,0) = (B + R + D (A -o))SA (u I 20) + (K —v - G)'(1-6A (u I z0)) + D'rA ( I zo) + K'zA(u zo0) (5.7.2.18a) J2(u,0)= (B + R + D A).A (u 10) + R + (K- v - G)-(1-8A (u 10)) + DrA (u 10) + K'zA (u 0) (5.7.2.18b) U Clearly, the existence of minima is tied to the properties of the functions As, rA, ZA and to the choice of parameters in the cost functional. The following gives a sufficient condition for the existence of a minimum. Theorem (5.7.2.1): Assume m>1 and that B, R, D, K, V, G are all strictly positive. Suppose there exists u' such that Jl(u',zo) < 0 or J2(u',0) < O. Then J(uL, z0) has a minimum on (0,oo)x {0,1}. Proof: The proof of this theorem uses the following properties of the cost functionals: lim J1(u,zo) = B + R + D(A - z0) > 0 (5.7.2.19a) t — 00 lim J2(u,0) = B + 2R + DA > 0 (5.7.2.19b) lim Jl(u,20) = 0 (5.7.2.19c) lim J2(u,0) 00 (5.7.2.19d) The proof of these properties can be found in Appendix C. Note also that the func

108 tionals J1 and J2 are continuous in u for u i (O,oo). Suppose there exists u' such that Jl(u',z0) < 0. By the above properties, there exists an interval U _ [ul,u2] containing u' such that for u, U, J(u,zo) > 0. Now J1 has a minimum on U (compact set) and infJl(u,zo) < 0< infJ1(u,zo) (5.7.2.20) Either J1 is the active functional in J in which case the minimum is established or else there exists a" such that J2(",O) < infJl(us,z) < 0 (5.7.2.21) For this case, apply the first argument to establish a minimum for J2 and thus for J. The same proof applies when there exists u' such that J2(u',) < 0. Remark: The theorem says that if the operation can be performed profitably for a given wear value a minimum exists. Corollary (5.7.2.1): Assume that the feed speed is additionally constrained such that u E (0,u,,]. Then J(uz0o) has a minimum on (0,u,]x{0,1} for 0<zo<A. Proof: Using the limiting properties discussed in the previous theorem, there exists u1 such that for 0<u < u 1, v {0,1}, U _ [u,u,] J((u,v),z0) > min( Jl(u,,z0), J2(um,,) ) > inf J (iu,zo) (5.7.2.22) -ED, *E{0,1} and J has a minimum on U {0,1}. Remark: The corollary says that under practical constraints on the feed speed a minimum exists for all wear values in [0,A ). Other more complicated sufficient conditions are also available. In general, if the piece profit is sufficiently high or the overhead rate is sufficiently low, a minimum

109 exists. The assumption m >1 is used in Appendix C in the proofs of properties (5.7.2.19a) and (5.7.2.19b). This assumption is satisfied according to Taylor tool life data for metal machining with all commonly used tools. Reference [Macl] gives typical values for n in the Taylor tool life formula (5.5.2.1) in the range 0.1 to 0.4, resulting in 2.5 to 10.0 as a range of values for m. 5.7.3. Optimal Feedback Policies The simple way in which the control variable v enters the problem allows the optimal policy to be given in terms of the functions J1 and J2. The optimal one step policy is of the following form (assuming existence of all minima). Let z be the measured tool wear. Denote J' () )minJj(,Z) u 1(2) arg minl(uz) J2 minJ2(u,0) u2 arg minJ2(u,O) i.e., the minimizing values of J1(',z) and J2(',0) are u;(z) and u4 respectively. Let v'(z) be the optimal replacement decision. The optimal one step policy is given by: (i) if J;(z) < J4, do not replace the tool (v'(z)=0) and continue at feed speed UI (2). (ii) if J*(z) > J4, replace the tool (v'(z)=1) and continue at feed speed u;. (iii) if the tool breaks, replace the tool and continue at feed speed u'. The values u (z) and u' must be computed numerically even in the restricted formulation. There is no known closed form solution. Depending upon the parameters, J1(,2) and J2(l,O) may exhibit large fiat valleys, and so gradient methods may not always be appropriate. As will be seen in an example, reasonable suboptimal

110 policies may exist for an interval of feed speeds. Therefore, it may be possible to maintain constant feed speed for a range of wear measurement values with negligible degradation in performance. This will become evident later. Implementation of the policy may be carried out in the following way. J; and u2 are constants and may be computed in advance. Initially, assume that a new tool is in place. The feed speed for the first part is u'. For each part thereafter, a wear measurement z is made, and J'(z) and u'(z) must be computed numerically based on the wear measurement. A table lookup would be a reasonable alternative. Recall that under the assumption of fixed feed, each selection of the feed speed necessitates a corresponding selection of the spindle speed as well. The optimal policy given previously is now used to determine the proper action for the next part. The above implementation can be extended to the realistic situation of (stochastically) time-varying costs and profit rates. In this case, J!(z), J2, u;(z), and u2 must all be computed for each part on the basis of the current cost functional parameters and wear measurement. It is assumed that the cost functional parameters are supplied by some higher level control and/or authority. In this situation, the higher level authority could influence tool replacement and higher feed speeds through manipulation of the costs and profit rate. In particular, tool replacement could be vetoed, in which case the next part would be machined at feed speed uL(z). Also, tool replacement could be strongly encouraged by a sufficient reduction in the tool replacement cost. Rationale for manipulating tool replacement policies and feed speed selection could include tool availability, service availability, the status of other machines and components in the manufacturing system, part and supplies inventory levels and part demand. This manipulation represents an indirect feedback of other

111 information in the manufacturing system to the drill controller. In actual practice, the selected feed speed will necessarily be constrained by other considerations: surface finish, spindle and drive power, and machine, tool, and part characteristics. In summary, the optimal feedback policy can be implemented in a manufacturing setting, provided sufficient computational capability is present, and tool wear measurement feedback is available. By allowing time variable cost and profit parameters, indirect feedback of other information about the manufacturing system can be introduced into the policy. The controller might be implemented in a local processor at the machine site.

CHAPTER 6 POLICY COMnPARISON FOR THE DRILLING PROBLEM: NUMERICAL EXAMPLES AND SIMULATIONS 6.1. Introduction In this chapter the methods developed in Chapter 5 for the drilling problem are applied to an example problem. The example is based on an actual drilling problem found in [Macl]. Analyses of age replacement policies and feedback policies for this problem are carried out. The problem parameters are held fixed except for the part profit value. This parameter is allowed to vary in order to explore the ramifications of relatively more and less expensive parts. Simulations of the drilling problem under different operational policies are conducted in order to compare the performance of different policies. Both primary and secondary performance measures are considered in the comparison. Two different production scenarios are considered: a fixed batch size and a fixed time production run. Algorithms to support the analysis and the simulations are also discussed in this chapter. Included are computational methods for calculating the various functions in the cost functionals and random number generators for use in the simulations. In particular, a random number generator for inverse Gaussian random variables is presented. 112

113 6.2. Problem Description The drilling operation parameters for this problem have been taken from [Macl]. They are as follows: Part Material: 4340 Alloy Steel 341 BHN Drill: M2 HSS Twist Standard Point 0.25 in x 4.00 in 29' Helix 118' Point Angle 7' Lip Relief Operation: 0.5 in through hole heavy oil lubrication Feed: 0.002 in/rev Tool life: 0.015 in end point wear Tool life data is also given in [Macli for different cutting speeds for the feed indicated above. In terms of feed speed, the data was in the range u E [2.1, 3.01 in/min. It is assumed here that the tool life data represents mean values. However, the reference does not comment on this. The tool life is assumed to agree with the Taylor tool life formula in the mean over the data range. That is, the mean tool life and feed speed are assume to be related by (5.5.2.1): u T = C1 (5.5.2.1) A least square fit of the data resulted in coefficient values of C1= 3.966 (6.2.1) n 0.194 (6.2.2) Recall that these coefficients are derived under the assumption of constant feed. The spindle speed is presumed to vary in proportion to u so as to maintain constant feed.

114 The tool life is modeled by a diffusion-threshold process with drift coefficient b(u) =,u" and diffusion coefficient a(u). The drift coefficient parameter are easily computed from the Taylor tool life coefficients and are given by: m --- 5.2 (6.2.3),-W i 1.2 x 10-6 (6.2.4) These values were used in all the analyses and simulations. No information concerning the variance of the tool life is given in [Macl]. This necessitated estimation of the diffusion coefficient a based upon assumptions. First, assume that the diffusion coefficient is constant and independent of the control u. This assumption is motivated by the lack of information regarding alternative functional forms. Now assume a nominal feed speed of 2.6 in/min. This is approximately mid-range for the available tool life data. At this feed speed, the mean tool life is about 8.7 minutes. Suppose that the standard deviation for the tool life at this nominal speed is about 20% of the mean. This corresponds to a standard deviation of about 1.7 minutes. From (4.3.30b), the diffusion coefficient can be computed: a= [v ar(TA)2= 0.001 (6.2.5) It would be very desirable to have information concerning tool life variance. This information could be used to determine (empirical) functional forms for the diffusion coefficient. Note that the diffusion-threshold model for tool wear does allow an arbitrary dependence of variance on the feed speed by appropriate choice of the diffusion coefficient. Summarizing, the diffusion threshold parameters used for this problem are given by:

115 A = 0.015 /= 1.2 x 10m — 5.2 o ~= 0.001 The economic parameters used in the drilling problem are based upon the following assumptions. Let the overhead cost rate be 30.00 dollars/hour which equals 0.50 dollars/min. Let the cost of a drill be 1.00 dollar. Assume that the time to change a drill under normal conditions is 0.5 minutes and that an additional 0.5 minutes is required if a tool failure occurs. In order to determine the effect of part worth, let the piece profit take on the values 1.00, 10.00, and 100.00 dollars. Summarizing, the parameters are given by: K (overhead rate) = 0.50 doUars/min R (replacement cost) = 1.00 + 0.5 x 0.5 = 1.25 dollars B (repair cost) = 0.5 x 0.5 = 0.25 dollars G (piece profit) E {1, 10, 100} dollars Additional operation parameters are given by: V (depth of hole) = 0.5 in tR (tool replacement time) = 0.5 min tB (additional repair time) = 0.5 min 6.3. Age Replacement Policy Analysis 8.3.1. Evaluation of Age Replacement Policies The results of Section 5.6 can be applied to this problem in order to evaluate the performance of age replacement policies. From Section 5.6, two performance measures can be computed. The expected long term cost per time is given by E'[ R + KT + BllTr=Al - Go] (5.6.5.1) and the expected long term cost per part is given by

116 E'[ R + KT + B[r= - G] (5.6.5.2) JP~r A (5.6.5.2) where a policy Ir a (u,n,) and T 4 tool life ~ duration of one tool cycle I' 4number of parts produced in one tool cycle The expected values of these random variables were previously shown to be given by (5.6.5.3)- (5.6.5.6): E'[ T ] = fI,qA(,7 0; u )dq + n, t -(1 - QA (n, tt i0; u) (5.6.5.4) 0 E'[ ] = E'[ T ] + tX QA(n, t I0; u) + ta (5.6.5.3) Er[ i =, - E Q,(jtl 0o; u) (5.6.5.6) j= 0 with t,! V-. Evaluation of the performance of age replacement policies requires the evaluation of these expected values. In general, numerical integration techniques can be used. However, expeditious evaluation motivates the design of alternate algorithms for computing these functions. These will be discussed in Section 6.6. The expected long term cost per time is plotted in Figs. 6.3.1.1 - 6.3.1.3 against feed speed for several age replacement values, given in number of parts. Fig. 6.3.1.1 is for a piece profit of 1.00 dollars, Fig. 6.3.1.2 is for a piece profit of 10.00 dollars, and Fig. 6.3.1.3 is for a piece profit of 100.00 dollars. The expected long term cost per part is plotted in Fig. 6.3.1.4 for a piece profit of 1.00 dollar. Since the piece profit only enters this cost functional in an additive

117 way, the plots for different piece profit values are not shown. 6.3.2. Discussion of Age Replacement Policies Examination of the graphs (Figs. 6.3.1.1 - 6.3.1.4) reveals several interesting features of this drilling problem under age replacement policies. The first observation is that the two performance criteria, expected cost per time and expected cost per part, do not lead to the same optimal policies. In fact, the optimal policies are distinctly different. This result is somewhat surprising, even though there is no reason to expect different cost functionals to yield similar optimal policies. The surprise is perhaps due to the intuitive idea that cost per part and cost per time should be closely related measures. For this problem, it is seen that minimizing expected cost per time leads to higher feed speeds and earlier tool replacement ages than those obtained by minimizing expected cost per part. Closer examination of Fig. 6.3.1.4 reveals that minimizing expected cost per part is achieved by letting the age of replacement n, -- oo. This corresponds to a failure replacement policy. However, this conclusion may be problem specific and should not be generalized. As indicated earlier, the optimal policy for expected cost per part does not depend upon the piece profit. Note, though, that the class of policies considered to give good performance (relative to the optimum) will depend upon the piece profit. The optimal policy for expected cost per time does have some dependence on the piece profit. As the profit increases, the trend is towards more conservative tool replacement ages, but slightly faster feed speeds. Generally, there exists a range of policies that will give near optimal performance.

feed speed (in / min) 2.0 3.0 4.0 5.0 0.0 - C - 1.0 plots for different replacement ages (in number of parts) r 4 c. -2.0 E -3.0 - o -4.0 - -5.0 60 50 40 30 20 18 16 14 12 Fig. 6.3.1.1 Expected Cost per Time under Age Replacement for G = 1

feed speed (in / min) 2.0 3.0 4.0 5.0 0.0 2C - 10.0 - plots for different replacement ages E (in number of parts) _ii -20.0 o -40.0 -50.0 60 50 40 30 20 18 16 14 12 10 Fig. 6.3.1.2 Expected Cost per Time under Age Replacement for G = 10

feed speed (in / min) 2.0 3.0 4.0 5.0 0.0 - -100.0 plots for different replacement ages (in number of parts) -200.0 0 2 a) -300.0 t 4c E 4-'~~~~~~~~~~~~ 8 -400.0 -500.0 60 50 40 30 20 18 16 14 12 10 Fig. 6.3.1.3 Expected Cost per Time under Age Replacement for G = 100

feed speed (in / min) 2.0 3.0 4.0 5.0 0.0 2 ~ -0.2 plots for different replacement ages LA -0.4 (in number of parts) -5 cis -0.6 CL Cl) C.)8 -1.0 60 50 40 30 20 18 16 14 12 10 Fig. 6.3.1.4 Expected Cost per Part under Age Replacement for G = 1

122 6.4. Feedback Policy Analysis 6.4.1. Evaluation of Feedback Policies The direct calculation of expected cost per part and expected cost per time for feedback policies is very difficult. Consequently, the one step cost was proposed in Section 5.7 as an alternative performance measure for feedback policies. In this section, good one step policies will be determined. Performance of these policies will be considered in the simulation section. The results of Section 5.7 can be applied to this problem in order to compute one step costs as a function of tool wear, feed speed, and replacement decision. From Section 5.7.2, the equations J,(u,) = (B + R + D (A-zo))-sA (u I0) + (K'7 - G)(1-A (u I zo)) + D rA(u I zO) + K'ZA(u I xO) (5.7.2.18a) J2(u,0) - (B + R + D-A )SA (U 10) + R + (K'- - G)'(1-A (u I 0)) + D'rA (u I 0) + K zA(u I 0) (5.7.2.18b) need to be evaluated in order to determine the one step cost. First, though, there is an additional parameter in the cost functional that must be determined. This parameter is the tool utilization cost rate (D). For this problem, this parameter was determined on the basis of a normal tool replacement cost: D (tool utilization cost rate) = 1.25/0.015 = 83.33 dollar/in Calculation of the one step cost was done by discretizing both the feed speed and tool wear. The wear value was taken from the set { 0.0, 0.003, 0.006, 0.009, 0.012, 0.014, 0.0145, 0.0146, 0.0147 } inches The feed speed was discretized at intervals of 0.2 in/min.

123 Examination of the pair of equations (5.7.2.18a) and (5.7.2.18b) show that the functions'8, rA and ZA need to be computed in order to evaluate the cost functionals J1 and J2. For each fixed piece profit (G), the functions 8A, rA, and zA were computed for each feed speed, for each of the tool wear values. In general, numerical integration can be used to compute these values. However, this is slow computationally, and so algorithms were designed to speed up the procedure. These algorithms will be discussed in Section 6.6. Using the computed values for the functions 8A, rA, and ZA, the function J1(y,) can be calculated. For this problem, the family of functions Jl(',zo) was determined by linearly interpolating between discrete feed speed values. The wear value zO was allowed to take on values from the discrete set previously given. The function J2(,O) is easily determined from the zero wear J1(,O) function by adding the replacement cost. Using graphs of the family of functions J1(,zo) and J2(.,O), the optimal feed speed selection and tool replacement decision can be approximated for each tool wear value. In order to better understand the one step policy, a somewhat different approach to policy determination was taken. For each wear value, regions of feed speeds were determined, rather than just an optimal value. The regions were classified as near optimal (within 1% of optimal performance) and suboptimal (within 10% of optimal performance). These regions were plotted versus tool wear, with linear interpolation between wear points. The wear value threshold for tool replacement was also determined. At this wear value, a tool replacement is called for. Finally, critical boundaries were determined where possible. A critical boundary indicates the economic break even point where a crossover from

124 profitable to costly operation takes place. These results are presented in Figs. 6.4.1.1 - 6.4.1.3 for the different piece profit values. 6.4.2. Discussion of Feedback Policies Examination of the graphs reveals several interesting properties. When a tool has little or no wear, the near optimal operating regions are relatively wide, indicating a relatively large interval from which feed speed selection can be made with near optimal performance. As the tool wear increases to the high wear region, however, the near optimal region narrows appreciably. In general, it would seem that the choice of feed speed is more critical towards the end of the tool's life than it is for new and little worn tools. What is perhaps most surprising is the observation that in some cases constant feed speed can be used throughout the tool's life while maintaining near optimal performance. Two effects of piece profit (G) on the policy are readily apparent. First, as G increases the width of the near optimal region increases for most wear values. Furthermore, as G increases tool replacement becomes more conservative; i.e., replacement of the tool occurs at lower wear levels. In particular, for sufficiently profitable parts and cheap tools, one could argue for tool replacement after very little wear (i.e., every part). Conversely, for cheap tools and cheap parts, replacement is close to the wear threshold. This is reminiscent of a "run until it breaks" policy. However, the region of operation for small G is generally narrower, so even a run until breakage replacement policy must be coupled with carefully chosen feed speeds. This seems to agree with the observation that manufacturing products with low profit margins requires more careful control of the operation in order to maintain (reasonable) profitability.

7.5 tool replacement boundary critical boundary (no profit) 6.0 4.5 -D a)oe1 1099 suboptimal0, a) a). t~uo ia 0.0 0.0 0.003 0.006 0.009 0.012 0.015 wear (in) Fig. 6.4.1.1 One Step Results for G=I

7.5 7.5 btool replacement boundary _ _critical boundary (no profit) a) 0.0 0.0 0.003 0.006 0.009 0.0 3.0 wear (in) g 641.52 One Step Results forG = 10 0.0 0.0 0.003 0.006 0.009 0.012 0.015 wear (in) Fig. 6.4.1.2 OneStepResultsforG=10

7.5 7.5 ~~~~~~~~~~tool replacement boundary critical boundary (no profit) 6.0 -~~aj~L~ — — ~~ —-— _ 1I OIX uboptimal 60o -o r) 4.5 C,) CL 3.0 nb -o a) 1.5 3 0.0 0.0 0.003 0.006 0.009 0.012 0.015 wear (in) Fig. 6.4.1.3 One Step Results forG = 100

128 6.5. Simulation and Policy Comparison Simulations of the drilling problem were conducted in order to evaluate the performance of different policies in different production situations. Because long term performance of the one step policies cannot easily be determined analytically, simulation represents the most direct way of evaluating and comparing policies. Simulation allows secondary performance characteristics to be compared as well. Simulation also provides an environment that allows policy experimentation. Thus, policy tuning can be carried out in an effort to find policies that perform well and are easily implemented. 6.5.1. Simulation Description Simulation of the drilling problem is straightforward, with only the random number generation presenting technical difficulties. The simulation written uses a tool cycle as an outer event loop. Recall that a tool cycle begins with a new tool and concludes when the next tool is installed. Tool failure necessitates tool replacement, but a tool can be replaced voluntarily prior to failure. The simulation uses a part cycle as an inner event loop. When a part arrives, the subroutine responsible for implementing the control policy is given a set of information regarding the current situation. This set includes: length of time the current tool has been in use; number of parts drilled by the current tool; wear measurement of the current tool. The control subroutine responds with a tool replacement decision and a feed speed. If the tool is to be replaced, the current tool cycle statistics are updated, and a new tool cycle begins. The part cycle proceeds with the updated tool wear measurement and the selected feed speed. First, it is determined whether or not

129 a tool failure occurs in this part cycle. This is done by generating an inverse Gaussian random number and comparing it to the completion time for the part. If a tool failure occurs, the time of occurrence is noted, the tool cycle statistics are updated, and a new tool cycle begins. If a failure does not occur, the new tool wear measurement is determined. The current tool cycle statistics are updated and the next part cycle begins. Different production situations dictate different stopping criteria. In this work, two production situations are investigated. The first is a fixed time production run of 4800 minutes. This represents two 8 hour shifts running for 5 days. The second production situation calls for the production of 1000 good parts. This typifies a small or medium batch run. As will be seen, operational policies do not necessarily give comparable performance in both of these production situations. Statistics collected for a simulation run include: time duration of production run, number of good parts produced, number of scrapped parts (number of tool failures), and number of tool changes. From these statistics, various measures of policy performance are computed and recorded. Algorithms for the generation of the required random variables will be discussed in a Section 6.6. 6.5.2. Simulation Policy Descriptions and Results The policies used in the simulations are summarized in Tables 6.5.2.1 - 6.5.2.3. The key for policy type is AR age replacement FR wear feedback replacement FR/FS wear feedback replacement and feed speed selection

130 The results from the simulations are summarized in Tables 6.5.2.4 - 6.5.2.9. Policy Descriptions: G = 1 Policy Type Replacement Feed Speed a AR 20 parts 3.0 b AR 40 parts 2.6 c AR failure 2.5 d FR/FS 0.0147 11(Z) e FR/FS 0.0145 1 (z) f FR/FS 0.0140 l(z) g FR/FS 0.0135 1l(x) h FR/FS 0.0147 12(z) i FR/FS 0.0145 12(z) j FR/FS 0.01425 12(z) k FR/FS 0.0140 12(z) 1 FR 0.0147 2.25 m FR 0.0145 2.25 n FR 0.0147 2.6 o FR 0.0145 2.6 p FR 0.0147 3.0 q FR 0.0145 3.0 r FR 0.0140 3.0 s FR 0.0135 3.0 Table 5.5.2.1 Policies for G -- 1 where the policies 1, and 12 are given in terms of the wear measurement z by: 3.0 z < 0.012 (6.5.2.1) l 3.0 - 375(z - 0.012) z > 0.012 3.0 z < 0.012 12(z)= 3.0 - 400(z - 0.012) 0.012 < z < 0.0135 (6.5.2.2) 2.4 - 533(z - 0.0135) z > 0.0135

131 Policy Descriptions: G = 10 Policy Type Replacement Feed Speed a AR 14 parts 3.25 b AR 16 parts 2.6 c AR failure 2.5 d FR/FS 0.0140 13(z) e FR/FS 0.0135 13( ) f FR 0.0140 3.0 g FR 0.0135 3.0 h FR 0.0140 3.25 i FR 0.0135 3.25 Table 6.5.2.2 Policies for G — = 10 where the policy 13 is given in terms of the wear measurement z by: =3.25 z < 0.012 (6523) 13(z) =3.25 - 583.3(z - 0.012) z > 0.012 Policy Descriptions: G = 100 Policy Type Replacement Feed Speed a AR 14 parts 3.3 b AR 16 parts 3.2 c AR failure 2.5 d FR/FS 0.0125 14(z) e FR 0.0125 2.5 f FR 0.0125 3.0 g FR 0.0125 3.25 h FR 0.0125 3.5 Table 6.5.2.3 Policies for G = 100 where the policy 1, is given in terms of the wear measurement z by: (4.5 z < 0.009 14(z) =4.5 - 342.9(z - 0.009) 0.009 (6.5.2.4)

AR FR/FS FR/FS a b c d e f g h _ _ Parts Produced 24754 22853 21726 23098 23875 24888 25253 22889 23594 24411 Profit 21096 19867 18908 19877 20602 21528 21797 19696 20355 21112 Scrap Parts 91 181 414 494 279 52 0 478 292 113 Tools Used 1246 593 414 810 848 954 1045 784 829 889 Parts/Tool 19.87 38.49 52.45 28.52 28.12 26.11 24.17 29.20 28.48 27.47 Production Rate 5.157 4.761 4.526 4.812 4.971 5.185 5.261 4.769 4.915 5.086 FR FR FR k I m n o p q r _ Parts Produced 24803 20587 20760 22598 23011 23549 24182 25258 25478 ______ Profit 21448 17952 18125 19694 20098 20165 20774 21787 21960 Scrap Parts 51 151 83 323 181 650 443 98 7 Tools Used 945 252 256 506 517 970 999 1061 1104 Parts/Tool 26.26 81.72 81.34 44.63 44.49 24.27 24.20 23.82 23.08 Production Rate 5.167 4.289 4.325 4.708 4.794 4.906 5.038 5.262 5.308 Key: AR - age replacement FR - wear feedback replacement FR/FS - wear feedback replacement and feed speed selection Table 6.5.2.4 Production for 1 Week (4800 min) for G = 1

AR FR/FS FR/FS a b c d e f g h ___ Production Time 194 210 221 208 201 193 190 210 203 197 Profit 852 869 870 861 863 865 863 861 863 865 Scrap Parts 4 8 19 21 12 2 0 21 12 5 Tools Used 51 26 19 35 36 39 42 35 36 37 Parts/Tool 19.87 38.49 52.45 28.52 28.12 26.11 24.17 29.20 28.48 27.47 Production Rate 5.157 4.761 4.526 4.812 4.971 5.185 5.261 4.769 4.915 5.086 FR FR FR k I m n 0 p q r s Production Time 194 233 231 212 209 204 198 190 188 Profit 865 872 873 872 873 856 859 863 862 Scrap Parts 2 7 4 14 8 28 18 4 (0.3) Tools Used 38 13 13 23 23 42 42 42 44 Parts/Tool 26.26 81.72 81.34 44.63 44.49 24.27 24.20 23.82 23.08 Production Rate 5.167 4.289 4.325 4.708 4.794 4.906 5.038 5.262 5.308 Key: AR - age replacement FR - wear feedback replacement FR/FS - wear feedback replacement and feed speed selection Table 6.5.2.5 Production of 1000 Parts for G = 1

AR _ FR/FS _ FR _ FR a b c d e f g h i Parts Produced 25180 24942 21726 125104 25689 25260 25478 25506 26013 Profit 247570 245410 214550 247360 253020 248990 251130 251140 256130 Scrap Parts 45 292 414 50 0 98 7 202 22 1,-, Tools Used 1802 1587 414 1262 1444 11060 1104 1499 1570 1 _ Parts/Tool 13.97 15.72 52.45 19.89 17.78 23.82 23.08 17.01 16.57 Production Rate 5.246 5.196 4.526 5.230 5.352 5.262 5.308 5.314 5.419 Key: AR- age replacement FR - wear feedback replacement FR/FS - wear feedback replacement and feed speed selection Table 6.5.2.6 Production for 1 Week (4800 min) for G = 10

AR FR/FS. FR FR a b c d e f g h i Production Time 191 192 221 191 187 190 188 188 185 | Profit 9832 9839 9875 9853 9849 9857 9857 9846 9846' Scrap Parts 2 12 19 1 2 0. 4 (0.3) 8 1 ____ Tools Used 72 64 19 51 57 42 44 | 59 61.... Parts/Tool 13.97 15.72 52.45 19.89 17.78 23.82 23.08 17.01 16.57 Production Rate 5.246 5.196 4.526 5.230 5.352 5.262 5.308 5.314 5.419 Key: AR- age replacement FR - wear feedback replacement FR/FS - wear feedback replacement and feed speed selection - Table 6.5.2.7 Production of 1000 Parts for G = 10

AR FR/FS FR FR FR FR a b c d e f g h Parts Produced 25301 25189 21726 21233 22745 25274 25765 25703 Profit (1000's) 2525.8 2514.7 2171 2116.2 2272.6 2523 2572.3 2565.6 Scrap Parts 102 122 414 0 0 0 0 0 Tools Used 1817 1586 414 4600 498 1180 1674 2258 Parts/Tool 13.92 15.88 52.45 4.616 45.72 21.41 15.39 11.38 Production Rate 5.271 5.248 4.526 4.424 4.739 5.265 5.368 5.355 Key: AR - age replacement FR - wear feedback replacement FR/FS - wear feedback replacement and feed speed selection Table 6.5.2.8 Production for 1 Week (4800 min) for G = 100

AR FR/FS FR FR FR FR a b c d e f g h Production Time 190 191 221 226 211 190 186 187 Profit 99828 99834 99926 99667 99917 99827 99834 99820 Scrap Parts 4 5 19 0 0 0 0 0 Tools Used 72 63 19 217 22 47 65 88 Parts/Tool 13.92 15.88 52.45 4.616 45.72 21.41 15.39 11.38 Production Rate 5.271 5.248 4.526 4.424 4.739 5.265 5.368 5.355 Key: AR- age replacement FR - wear feedback replacement FR/FS - wear feedback replacement and feed speed selection Table 6.5.2.9 Production of 1000 Parts for G = 100

138 6.5.3. Discussion of the Simulation Results For each production situation, several different policies were tested. Included in the testing were policies based on age replacement, approximations to the feedback policies based on one step costs, and variations of these feedback policies. In all cases, the simulation results for age replacement policies were in good agreement with the previously computed analytic results. This provided some assurance that things were working correctly. The results are presented in tabular form in Tables 6.5.2.4 - 6.5.2.9. The different columns correspond to different policies used. The policies used are described separately. Time units are in minutes and monetary units are in dollars. The discussion here will focus mostly on the case where the piece profit (G) is 1.00 dollar (Tables 6.5.2.4, 6.5.2.5). This case is in some ways the most interesting. This is because the results from the feedback analysis indicate a fairly narrow region of near optimal performance. Furthermore, this case represents best the challenge of producing inexpensive parts profitably. However, many of the remarks also apply to the other cases. The age replacement policies are a, b, and c. The remaining policies use tool wear feedback, though some have fixed feed speed. Policy a is based on the expected cost per time results, and policies b and c are based on the expected cost per part analysis. Note that policy c is failure replacement. As might be expected, each does well in a particular production situation. Minimizing cost per part results in good batch performance, whereas minimizing cost per time yields good long time performance. A general comment on age replacement policies is that if they are properly chosen for the production situation they do very well from an economic standpoint.

139 However, there are secondary performance measures that must be compared as well. Also, although the age replacement policies shown here perform well in particular production situations, it is the author's experience that in most manufacturing systems the same policies are used regardless of the production situation and that these policies are often very conservative. The feedback policies show considerable variation in performance. The policies evaluated were constructed by approximating the true one step optimal policy by piecewise linear functions. That is, the feed speed was chosen to be a piecewise linear function of tool wear. Examination of the one step graphs (Figs. 6.4.1.1 - 6.4.1.3) shows that this should be a reasonable approximation. The policy closest to the true one step policy for the case G = 1 is policy h. As can be seen, it does not give a distinguished performance. In particular, the scrap count is too large. This observation gives some insight into the one step cost functional, and also into how some good policy variations can be constructed. The problem with the one step cost functional is that the cost of tool replacement is too high. This is especially true when the piece profit is relatively low as is the case when G = 1. By forcing one part to absorb all the replacement cost, replacement is avoided until it is typically too late. Note that for the case under consideration it is cheaper to scrap the part (1.00 dollar) than to replace the tool (1.25 dollars). Thus, replacement is generally avoided. It would be more desirable to pro rate the tool replacement cost so that the burden of replacement is more evenly distributed among the parts that benefit from replacement. The easiest way to effect this cost disburdenment is to lower the tool wear threshold for replacement. This is precisely what is done in the feedback policy variations. The policies d, e, f, g and h,

140 i, j, k represent policies with decreasing tool wear replacement thresholds. There are other possible policy variations as well. An important practical question is what is the contribution of variable feed speed? That is, does tool wear feedback used only for replacement coupled with constant feed speed give good performance? In an effort to address this issue, some of the feedback policies use constant feed speed. Note that the one step graphs (Figs. 6.4.1.1 - 6.4.1.3) suggest that this may in fact be reasonable. Polices I through a are of this type. Consider first the timed run production situation (1 week of production). For this case, the best age replacement policy is a (minimize cost per time). The feedback policies that will be examined closely are g (variable speed) and s (constant speed). Policy s gives the best economic performance, with an improvement of 4.1% over age replacement. However, policy g is probably the best choice. Although this policy only gives a 3.3% improvement over age replacement, it has much better characteristics. In particular, the drop in scrap production is very significant. Further note that the number of parts per tool increases and the total number of tool changes decreases. The effect of the variable feed speed appears to be to trade off production rate and pure economic gain for less scrap production and fewer tool changes. Policy g represents a good example of the potential performance of a modified one step policy. However, if variable feed speed is not practical, than policy s still gives good performance. Finally, note that the other age replacement policies give mediocre performance. Now consider the batch production situation (production of 1000 parts). In this situation, the best age replacement policies are b and c. These policies minimize cost per part. Although policy c (failure replacement) gives the best economic perfor

141 mance, policy b is probably the one of choice since it has better secondary characteristics. Also, some managers and engineers may find failure replacement distasteful. Also note that age replacement policy a now gives mediocre performance. As can be seen, the candidate feedback policy g is economically worse representing a 0.7%o decrease in profit. However, this policy still exhibits superior characteristics in terms of scrap production and production time. This would generally justify the slight economic loss. The reason for the slightly poorer performance is that policy g uses too many tools for this performance measure. None of the variable feed speed policies considered betters the age replacement policy economically. This motivates exploration of other feedback policies. Policies n and o were constructed by taking the feed speed used by the age replacement policy combined with tool wear feedback replacement. Policies I and m are similar with a slower feed speed, and policies p, q, r, and s use a faster feed speed. As can be seen, policies 1, m, n, and o are economically superior, although by less than 0.5%. Policy o is the one of choice, since it has equal scrap production, is slightly faster, and uses fewer tools than the age replacement policy. An important point is that the age replacement policies can do very well, but must be selected for the batch production environment. This suggests that a properly chosen age replacement policy can be a good choice for some production situations. It also suggests that other cost functionals should be considered for determining feedback policies in some batch production situations. Nonetheless, the merits of feedback policy g include good performance in both production situations. All of the preceding discussion is problem specific. Nonetheless, some important issues have been raised. First, age replacement policies can give good performance if properly chosen for the production situation. Second, the one step approach to feedback policies can yield improved performance. However, modification of the tool

142 replacement threshold may be required in order to reduce the burden of replacement. Third, the one step approach does not always yield improved performance over optimal age replacement. Fourth, policies with constant feed speed and tool wear based replacement can give good performance as well. Fifth, it is important to look at characteristics other than just economic performance when evaluating a policy. Sixth, performance can vary with the production situation. When the production situation is uncertain, a feedback policy may give good all around performance, but an age replacement policy may not. There is no reason to expect dramatic improvement by using feedback policies in the drilling problem. What has been seen is that modest improvements can be realized. This does not imply that feedback policies are not useful. Since a typical manufacturing system has many machines, small improvements in the operation of each machine may be collectively significant. 6.8. Algorithms Several algorithms have been used to carry out the analysis in this chapter. These algorithms will be summarized in this section. 6.8.1. Algorithms for Age Replacement Analysis The performance statistics for the drilling problem under age replacement policies can be expressed in terms of integrals involving the inverse Gaussian density as a kernel. In general, numerical integration could be used to evaluate each of the integrals. However, for problems with large age replacement values (n,), this requires evaluation of many integrals (n, + 2 integrals). This motivates the investigation of alternative methods for evaluating the integrals. As will be shown, it is possible to

143 transform the integrals and use approximations to avoid all numerical integration. The distribution function for the threshold crossing time QA(t I 0; u) = P[TA <t] has been previously given as QA(tlo; )= fqA(lo; u)d =f 3 exp -A d (4.3.24) It can be shown that QA (t I 0; ua) can be expressed in terms of the normal distribution [Chl]. Let 4(z)= P[X < z ] when X - N(0,1). That is (z) f exp 1 (6.6.1.1) Then QA,(t @; u) 0 4;AA t { } axp r 4-A +l (4.3.33) Using a procedure similar to that given in [Chl], it is possible to show that the truncated mean can also be expressed in terms of the normal distribution. Corollary (8.8.1.1): t f qA(v I0; u)d1 A= 0 {[V- - p -(- ]] AP { t A +2Ab1 (6.6.1.2) b La A i i2 a'' A The above transformations show that all integrals required for evaluating the performance statistics can be expressed in terms of the normal distribution function. Although there is no known non-integral closed form expression for the normal distribution, there are several known approximations that are relatively easy to compute.

144 For this paper, the following approximation is used [Abl]: Approximation (6.6.1.1): (z) = 1 - f (z)[at + a2t2 + a3t3] + e(z), for 0 < z < 0 (6.6.1.3) where f(z) = exp - (6.6.1.4) is the normal density function and t (6.6.1.5) 1 + aoz a= 0.3326700 (6.6.1.6a) a1- 0.4361836 (6.6.1.6b) a2 = -0.1201676 (6.6.1.6c) as = 0.9372980 (6.6.1.6d) Le(z)I < 1 x 106 (6.6.1.7) Using this approximation, the performance statistics can be computed without numerical integration. 6.8.2. Algorithms for Feedback Analysis The evaluation of the one step cost functional requires the evaluation of the three functions 8A, rA, ZA. Note that, ( I ) = QA(tf I; U) (6.6.2.1) and that t! ZA( I 2)-)= fqA( I z; u)dq (6.6.2.2) 0 Thus, the results from the previous section can be applied to evaluate these two functions without integration.

145 Numerical integration was required to evaluate the function rA. However, approximations are necessary in order to reduce the integration interval to one with finite endpoints. Smaller integration intervals also reduce the computational burden. This reduction was done in the following way. From (5.7.2.17) rA (u I ) =- I p (a,u,7)d (6.6.2.3) where a - A - z and p (a,u,7) = f (I; a,u )'w (q; a,u) (6.6.2.4) with f a Gaussian density and w a weighting function. Now lim w (7) = (6.6.2.5) — * - 00 for all admissible a and u. So, for 0 < e there exists 7 such that 1 -e < w(7) < 1, for v < 7 (6.6.2.6) Assume that - < a. Then 7 a rA (u I z) f= 7p (a~,u,q)d + f 7p (a,u,t)d (6.6.2.7) The second term must be computed numerically. The first term can be approximated, however. 1 7 f 7p(a,u,rq)d (1 - ) flf (qc;a,u)dq (6.6.2.8) -00 — 00 where f is a Gaussian density. The integral in (6.6.2.8) can be evaluated as follows. Substituting 17 - bt! ai — bt- (6.6.2.9) into (6.6.2.8) yields

146 7- &t! f =f (e;au )dw (atf + btf exp 7- bt 7- bt btf=L','e2 f exp 2If exp 2) bt ]'O a ~, (6.6.2.10) * can be computed using Approximation 6.6.1.1. In the case where 7 > a, no numerical integration is required. 6.8.3. Random Number Generation The simulations used to evaluate policy performance require the generation of random numbers. Two distribution families are involved. First, an inverse Gaussian random number (with variable parameters) is required. Second, a conditioned Gaussian random number is needed. In order to generate random numbers from these distribution families, two algorithms are required. 6.8.3a. Generation of Inverse Gaussian Random Numbers The basic idea of this algorithm is to use the acceptance-rejection method [Lal] on a transformed inverse Gaussian random variable. Let (A, b, a) be the parameters of the inverse Gaussian distribution from which a A A A2 random numbers are to be generated. Denote is = - X = -. Let Y be a random variable with density _ +2 exp 2' y E R y(L) =21 - v-)t2 2{ })' Y (6.6.3.1) Then

147 T= [(2+ Y) + Y x+2]= h(Y) (6.6.3.2) is inverse Gaussian with parameters (A, b, a) ([Chl]). Now acceptance-rejection can easily be used to generate Y because of its relationship to a Gaussian density: 9r(Y) < exp 2 2} y ER (6.6.3.3) Algorithm (6.8.3.1): Let Z - N(0,1) U -- U(0,1) be independent if U<~-1,,___ if 2 - (6.6.3.4) then Y = Z, else generate new (Z, U) and repeat. Then T = h(Y) is inverse Gaussian. In practice, acceptance-rejection methods can perform poorly since a random number of (Z,U) pairs must be generated for each random number. However, this algorithm performed well in the simulations. 6.8.3b. Generation of Conditional Gaussian Random Numbers Assuming that a tool failure does not occur, it is necessary to generate the new tool wear value. This is done by generating the conditional change in tool wear: Y (X1f - z0) given TA > t! (6.6.3.5) The random variable Y has a density function f y given by fYr(1)-= 1{_ QA(t I|O q; u) (6.6.3.6) o J > ax where the function p is given by (5.7.2.16). Now p is majorized everywhere by a Gaussian density with mean btf and variance a2t1. Thus acceptance-rejection with

148 Gaussian random numbers is possible. Algorithm (8.8.3.2): Let Z - N(bt, o2t! ) U - U(0,1) be independent if U < (,Z,) W( a,U) (6.6.3.7) then Y else generate new (Z; a,)nd repeat. then Y = Z, else generate new (Z,U) and repeat.

CHAPTER 7 APPLICATION OF DIFFUSION-THRESHOLD MODELS TO OTHER MANUFACTURING PROBLEMS 7.1. Introduction This chapter will consider the application of diffusion-threshold models and the control theoretic approach to other manufacturing problems. The problems that are considered here were introduced in Chapter 3. Each of these problems conveys a viewpoint different than that which is typically taken in manufacturing problems. The emphasis here will be on how these different viewpoints can be accommodated using the concepts developed earlier in this work. The problems considered in this chapter will not be discussed in as much detail as the drilling problem. The intention is to develop a framework for approaching certain types of manufacturing problems using diffusion-threshold models and control theoretic techniques. In so doing, it is hoped that the potential for new approaches to manufacturing problems is exemplified. The problems in this chapter do not have simple solutions. They are not simple problems. In the first problem, a solution is presented under restricted assumptions. In the second problem, a simulation based approach is described. In the third problem, a dynamic programming type of condition is derived. More than anything, these problems reveal the difficulty of manufacturing problems and the need for new 149

150 analytic methods for approaching manufacturing problems. 7.2. Multi-tooled Machines The multi-tooled machine version of the drilling problem has been previously described in Section 3.3. The reference [Shkl] also considers multi-tool problems. In this problem the machine is allowed to have multiple tools that simultaneously machine the part. As was previously stated, this is a common design for high volume special machines. The tools are generally not independently controllable. For this problem, some simplifying assumptions will be made. The independent control variable will again be the feed speed. The spindle speed of each tool will be assumed to vary so as to maintain constant feed. This is a more restrictive assumption for the multi-tooled machine than it was for the single tooled machine. There are practical examples that adhere to these assumptions, however. A multi-dimensional diffusion-threshold model of multiple tool wear and failure is proposed. Assume that each tool can be described by a diffusion-threshold model, and that the wear processes for each tool are independent. The wear processes of all tools can be thought of as an n dimensional diffusion, where n is the number of tools. The drift vector b and the diffusion matrix a are functions of the feed speed u, which is a scalar. The failure of each tool corresponds to a threshold crossing of the diffusion process component associated with that tool. Failure of the operation is considered to have occurred if there is a failure in any tool. Thus, a crossing of any component threshold corresponds to an operation failure. The parameters in each diffusion-threshold component may be different. This would be the case if the tools are different, as an example. However, the component

151 drift and diffusion coefficients are assumed to be strictly positive for all values of the control variable u. The component threshold values are assumed to be strictly positive as well. In this work, it will be assumed that all tools begin and end their operations at the same time. This is to simplify the calculations. The results of Section 4.5 can now be applied in order to determine the distribution function for an operation failure. Let X(t)- (Xl(t),...,X,(t))T 7.2.1) be an n-dimensional diffusion process given by it X(t)= fb (u () )d T+ f a (u) )dW(r) (4.5.5) o 0 where W(t) (W(t), JO W (t) (4.5.1) b(u(t) )(b&(u(t)),..., b,(u(t) ) )r, bj(u)>0, i= 1,.., n (4.5.2) ju(t) ) - diag(a(u (t) ) (u(t), ai(u)>O, i = 1,., n (4.5.3) and u the feed speed is a scalar. Let the threshold be given by a union of hyperplanes A =U = R: z- =Aij, Ai >0, i - 1,..., n (4.5.6) i=1 Then the threshold crossing probability distribution function is given by Q&(t i; u)=1- II[1- QA,(t; u)] (4.5.9) *=1 for zx < A4, i = 1,..., n. The density function q.(t i 2; u) is given by qA(t IA; u) = -dQ&(t Iz; u) = — E qA(t I Z; u) ii [1- QA(t; u) ]i (7.2.2) i~, IC-1~~~~~,.

152 The control analysis methods used in the drilling problem can now be extended to the multi-tool case. Age replacement and one step analyses will be separately considered. 7.2.1. Age Replacement Analysis Age replacement analysis for the multi-tooled drilling problem can be carried out under the assumption of block tool replacement. This means that all tools are replaced at the same time, whether the replacement is voluntary or necessitated by failure. The analysis is considerably more complicated when individual tool replacement is allowed because the renewal framework is then lost. This case will not be discussed here. Under the assumption of block tool replacement the renewal framework is preserved; thus the results of Section 5.6 can be used. Assume that a policy 7r consists of the pair (u,n,), u E R +, n, E {1,2,...} where u is the fixed feed speed and n, is the age in number of parts at which the block tool replacement is made. Proceeding as in Section 5.6, the distribution function for the tool life T under policy ir = (u,n,) is given by: {1Q~,r! (t 0;.if t<t, where t, = n V-. Here V is the depth to be drilled by the tools. The expected value of the tool life T is given by: oo to AT -E'[ T ] tdF r(t)- ftdQ&.(t; u) + t,(1 - Q&(t, 0; u)) (7.2.1.2) 0 0 Similarly, the expected duration of a tool cycle E [] and the expected number of completed parts in a tool cycle E[ft] are given by: E'[ J = E'[ T ] + tB Q.(nt tt J O; u) + tR (7.2.1.3)

153,i-1 E'[ PY] = n - E QA(jtf 10; u) (7.2.1.4) j= o Therefore, from (5.6.5.1) and (5.6.5.2), both the long term expected cost per time, and the long term expected cost per part can be computed under policy ir. Es[ R + KT + Brr - G] (7.2.1.5) Jt, = (7.2..5) E'[ R + KT + B1r,- G](7.2.1.6) JPr= A. (7.2.1.6) Although the assumption of block tool replacement is restrictive, it is a common policy in practice. Some exceptions may occur in the case of early tool failure, however. Analytically, the assumption greatly simplifies the problem. 7.2.2. Feedback Analysis Feedback analysis of the multi-tooled drilling problem using a one step cost functional is also possible. As in the age replacement case, block tool replacement will be assumed. Some modification to the one step cost functional will be required in order to accommodate n dimensional diffusions. Assume that wear measurements of all tools are available. Define a control u = (u,v), u ER, v E {0,1} where u is the feed speed and v is the block tool replacement decision. Let = (z,..., z, ) be the initial wear measurement vector, with xz < Ai, i - 1,..., n. Let the one step cost functional be defined as in Section 5.7 with the following changes. The replacement cost is now the cost of replacing all tools, and the repair cost is the cost of repair due to any failure. As can be seen by examining (5.7.2.4a) and (5.7.2.4b), the tool utilization cost term needs to be redefined. That is, equivalents for D(A - z0) and D (X,! - z0) are required.

154 Consider a normalized tool consumption for each tool: Y A X. (t) - (7.2.2.1) Ai with Ai - zi 0 < Y <_ A, I=, n.,n (7.2.2.2) Y, is the percent of tool i consumed during the operation. A suitable measure of tool utilization is the maximum percent consumption among all the tools. This is a measure of the worst case tool utilization, which is in fact what is wanted. Define Y max {Y.} (7.2.2.3) Then the tool utilization cost becomes R Y under this criteria. Note that this is based on a normal replacement cost, the same as in the single tool case. Similarly, the worst case tool consumption in the event of a tool failure is given by R'y=m,, where Ymua x,~,l.m...A- A, (7.2.2.4) The variable ymo corresponds to the worst case percent tool consumption resulting from a tool failure. Recall that a tool failure results in replacement of all tools under the block replacement assumption. The one step cost functional for the multi-tooled problem becomes: Minimize J(, ) = (l-v) J1(u, ~) + v'J2(u, 0) (7.2.2.5) where J(u, _) = E [-G6.Ti <,T] + (B + R).1lTA. fl + R Y.~i7f < Tl + <R'Y=,'lTlr + K A(Tf A To) I X(O)- z] (7.2.2.6a) and

155 J2(,, O) = E[ -G'ltr < Il + R + (B + R)'1T" T_< I + R'Yl[rlr < TrI + R Ymu.=xl[T<r r + K.(T1 A T) I X(O) =0 1 (7.2.2.6b) Similar to the scalar case, evaluation of the one step cost involves the computation of three functions: a(u I -)=E[ ie,v 1 I]=P[ T-]< I _] (7.2.2.7) rA(u 1-EI Y-1IV<T I |] (7.2.2.8) z&( iL) = E[ Tlz[T < I ~- ] (7.2.2.9) The functions sJ and zL can be computed since QA and q& are known. Thus, only the function rA needs to considered here. From the definition, rA(u 13.) f qldP(Y-q, tt < Tl.; u) (7.2.2.10) where dP(Y = y, tf < TAI2; u)=- P(Y < y, tt < T-Iz;u)dy (7.2.2.11) Now P(Y < Y, tf < TA. I; u)= P(Yi y, tt < TA,, i n I, Un:;u) P(Y. < y, M(tf) < Ai - s, i = 1,...,n 10; u) (7.2.2.12) where M, is the component maximum random variable. Since the components of the diffusion are independent, (7.2.2.12) can be expressed as IIP(Y, < y, M (t,) < A, - z; ut) (7.2.2.13) Each term of this product P(YDI < y, M{(t/) < A; - zi ~O; u), i Al,..., n (7.2.2.14) can be computed from the component joint density function, as given in Section 4.3.

158 For each i, VA; P(Y, < y, M (t! ) < Ai - zx 1 0; u ) = f p (ai,u,7,)d1 (7.2.2.15) -00 where p(ac,,u,) is given by (5.7.2.16) and a, = Ai - z,. Thus ayA 2rtf a 2a tf 1ti - Ai |f~~~~~~~~~ em tt}Q-xt it2Y)3(7.2.2.16) o fory > AAi So rf A - ( - t ) -2a (a - yAjf) ) rsuI)j=I -00 V/2tif exp 2atf 0L.?t This can be simplified somewhat by substituting 9 = yAj in the first term. Then the expression becomes: r&(u It)=E exp {,, t, }; - exp { a A_ AI xft [s 1 - ____-_; __, {_2abt }2 -2a, (ai - ) d d- (7.22. 18) ill- V2.... 0rexp,, d2a dOt This gives the expected maximum percent tool consumption. The expression is very complicated, but in principle computable. Thus the one step cost functional under block tool replacement can be computed. Suppose now that individual tool replacements are allowed. For the case of feedback policies, there are 2" possible replacement decisions. For each replacement

157 decision, there may be a different replacement cost. It is also possible that there are different repair costs for different tool failures. Consequently, the problem becomes enormously complex as n gets large. This will not be further discussed in this work. The multi-tooled drilling problem can be analyzed under both age replacement and feedback policies in a manner similar to the one tool case. In general, the computations become much more complicated, even under a block tool replacement assumption. 7.2.3. Numerical Example The ideas of the multi-tooled problem are demonstrated here in a two tool age replacement analysis. Assume that each tool is a drill identical to the one considered in Chapter 6. Thus, each of the two component diffusions has the same parameter values. In this case, the threshold crossing distribution and density functions are given in terms of the scalar functions by: Q4(t I 0; u)= QA(t I 0; u)[2 - QA(t 10; u)] (7.2.3.1) qA(t 10; u) =2qA(t 10; u)[1 - QA(t I 0; u) (7.2.3.2) The long term expected cost per part and long term expected cost per time were computed using the same economic parameter values used in Chapter 6. The piece profit (G) was chosen to be 1.00 dollar. The results are shown in Figs. 7.2.3.1 and 7.2.3.2 respectively. Comparison of these figures to those for a single tool (Figs. 6.3.1.1 and 6.3.1.4) with the same economic conditions reveals only small differences. The expected cost per part graphs (Figs. 6.3.1.4 and 7.2.3.1) indicate that the optimal policy for two tools uses a slightly slower feed speed than for the one tool case. The expected cost per time graphs (Figs. 6.3.1.1 and 7.2.3.2) indicate an earlier replacement age for the

158 two tool case: 16 - 18 parts vs. 18 - 20 parts. Generally, the optimal policies for the two tool case are somewhat more conservative than the comparable policies for the one tool case.

feed speed (in / min) 2.0 3.0 4.0 5.0 0.0 ~u -02.2 plots for different replacement ages -0 4 t (in number of parts) O 4 r vt -0.6 _ 6 o -0.8 C Fi.) o -1.0 1 60 50 40 30 20 18 16 14 12 10 Fig. 7.2.3.1 Expected Cost per Part for 2 Tools under Age Replacement for G = 1

feed speed (in / min) 2.0 3.0 4.0 5.0 0.0 -1.0 - plots for different replacement ages E - i~ (in number of parts) -2.0 - -- 00 0) -3.0 E 0 -4.0 -5.0 50 40 30 20 18 16 14 12 Fig. 7.2.3.2 Expected Cost per Time for 2 Tools under Age Replacement for G = 1

161 7.3. The Multi-Machine Problem: A Serial Transfer Line Example Manufacturing systems are rarely as simple as the system considered in the drilling problem. Typical manufacturing systems involve many operations on many machines, with a variety of support equipment such as material handling and buffer storage. All of these factors make the analysis of realistic manufacturing systems much more complex than the analysis of a single machine. The intent here is to provide one framework for approaching more general manufacturing systems, using the concepts developed for the single machine case. The framework will be demonstrated through an example problem. The approach taken is strongly motivated by practical concerns for dealing with real manufacturing problems. That is, the concern is to develop techniques for controlling real systems in such a way as to improve the performance of the system. Optimality is not an issue here. The direction taken is very much an extension of the concepts laid down in the development of the drilling problem. However, the presentation is only one example of what the author believes is the true potential of the control theoretic approach to manufacturing. Consider a multi-machine manufacturing system, where each machine in the system exhibits properties similar to those present in the drilling problem. That is, each machine has tooling that wears with use and must be occasionally replaced. Tool failure can result in scrapped parts. Also, the operational speed of each machine is a controllable variable. The main difference between this problem and the single machine problem is that the machines are now interconnected. Thus, the performance of any one machine may affect the performance of the other machines and the performance of the overall system. The problem is to devise ways of operating the

162 system so as to obtain good overall performance. It is intended that the multi-machine problem be viewed in an intelligent manufacturing setting. That is, assume that information regarding the system (tool wear, buffer levels, etc.) is available. This information is to be incorporated into the operational decision process. There is another issue of great significance, however, that arises in this problem. The issue is the distribution of control and information in the manufacturing system. This issue is important both analytically and practically. The complexity and size of manufacturing systems makes the design and implementation of systems with centralized control and information difficult. Furthermore, the volume of information that can arise can easily overwhelm the capabilities of a communication system, especially if the information is required frequently for control purposes. Also, centralized control can impact system reliability and expandability. Finally, the design and implementation of such centralized systems is very complex and error prone. A more desirable situation might be attained with distributed control and information. This has many advantages in terms of design, implementation, expandability, and reliability. Unfortunately, distributed systems lead to decentralized control, and this can greatly complicate the problem analytically. Also, it is not immediately clear how the control and information should be distributed and organized. This issue distinguishes the single machine and multi-machine problems. The author believes that the practical advantages of distributed control and information far outweigh the analytical disadvantages. However, this position can only be supported if there are ways of eliciting good performance out of a distributed

163 system. The problem that will be considered here will have that as its goal. Returning now to the multi-machine problem, a diffusion-threshold model of each machine is proposed. This effectively gives rise to a network of diffusionthreshold processes, and possibly buffers and material handling equipment. This is still far too general a problem to deal with, so only a very special class of systems will be considered. This is the class of serial transfer lines. The serial transfer lines considered here consist of a sequence of machines that perform operations on the parts. It is assumed that there is no intermediate buffer storage between machines. The material handling system (the transfer system) is synchronous; all parts are transferred at the same time to the next machine in sequence. The machines themselves are independent, however. It should be noted that this is a common configuration for high volume production systems. The implications of restricting attention to this class of manufacturing systems are as follows. First, the production rate of the system can be no faster than the production rate of the slowest machine in the system. Second, a failure in any one machine results in a system stoppage until that machine is repaired. Consequently, each machine in the transfer line can strongly influence the total system. Analytic treatment of transfer lines under some restricted control policies (i.e., traditional) has been considered by other authors. That will not be the goal here. Rather, an approach that builds upon the results of the single machine problem while maintaining a distributed structure will be proposed. Since analytic treatment is not immediately available, simulation will be used to test the approach for one simple case.

164 Machining economics problems for serial transfer lines have been considered in the literature. Typically, these works have dealt with deterministic formulations of the problem. In these formulations, tool life usually obeys a Taylor type formula. The phenomena of tool failure is not generally represented. The policies proposed in these deterministic analyses are of the age replacement type. One method that has been suggested [Hil] is the following. The optimization procedure is algorithmic. Optimize each machine individually with respect to the overall system criteria. From this, determine the worst case (controlling) machine or machines. Call these the critical machines, since they determine the production rate. Now relax the operation speeds of the non-critical machines in order to improve their economic performance. Whether or not this is the best way to select machining parameters for serial transfer lines will not be discussed here. Rather, the intent here will be to implement policies in a related manner for purposes of comparison. That is, suppose that an essentially local optimization is carried out for each machine in the transfer line, and the optimal local policies are then implemented at each machine in a decentralized way. The local policy may be age replacement, or feedback, or something else. This concept gives rise to the following question. How do decentralized age replacement and decentralized feedback policies compare? Simulations have been carried out for an especially simple transfer line operating under decentralized age replacement and decentralized feedback policies. This will be described shortly. First, a few remarks are required. It might be expected that most serial transfer lines will have one or more machines that dominate the system performance. Similarly, there may be one or more machines that have a relatively weak influence on the overall line performance.

185 As an example, a 10 machine line with 4 critical failure prone machines and 6 unimportant reliable machines may behave in a manner similar to a line made up of just the 4 critical machines. This is not proven here, but seems intuitively plausible. In order to avoid this phenomenon, the simulated transfer line is composed of only 2 identical machines. This also keeps the simulation simple. 7.3.1. Simulation Description A 2 machine serial transfer line with identical machines is considered. Part transfer is synchronous. Each machine is similar to the one described in the drilling problem. That is, feed speed is considered a variable that affects the rate of operation and the rate of tool wear. Each tool is susceptible to failure which necessitates repair and causes the current part to be scrapped. There are a few differences from the single machine case, however. Repair and maintenance work takes place serially on a first request first served basis. This corresponds to a single worker/operator. If a tool failure occurs on a machine, the other machine may continue until part completion. At that time, a repair on the failed machine may commence. A repair may not begin while the other machine is still running. If both machines fail, repair begins after the second failure. If a failure occurs in the first machine, the part is scrapped and no part will be transferred to the second machine. That is, a hole appears in the part stream. If a failure occurs at the second machine, the part is simply scrapped. The first machine has an unlimited supply of parts, and so holes never appear there. A machine does not cycle if no part is present and hence no tool wear occurs. A part is completed and credited toward production only if it makes it through both machines successfully. Without loss of generality, the part transfer is assumed to take no time.

186 The control policies for the two machines are completely decentralized and share no information. Although the second machine knows when a failure occurs in the first machine because of the hole, this information is not used in decision making. The tool wear/tool life models for each machine are identical to the one considered in Chapter 6. That is, each tool is modeled by a diffusion-threshold process with coefficients as determined in Section 6.2. The economic parameters are identical to those in Chapter 6 with a piece profit (G) value of 1.00 dollar. No partial credit for a part is allowed. 7.3.2. Simulation Results Simulations were run for two production situations under three control policies. In all cases, both machines used identical policies. The three policies were taken from the results in Chapter 6 for the case of a piece profit of 1.00 dollar. It was found there that age replacement policy a worked best for the long term production situation and age replacement policy b was recommended for the batch production situation. Feedback policy g was recommended for overall performance. The results of the simulations of a two machine serial transfer line are shown in Tables 7.3.2.1 and 7.3.2.2. For the batch production situation (Table 7.3.2.1), policy b continues to give the best economic performance. As before, this performance is gained at the expense of scrap production and production time. Feedback policy g results in less profit, but has much better scrap characteristics and is 17 minutes faster. Policy a gives the worst economic performance. The long term (4800 minutes) production situation (Table 7.3.2.2) shows policy g to be clearly better in all characteristics except number of tools used. Note that

187 policy b now gives better economic performance than policy a. This is an unexpected result. In the single machine case policy g resulted in a 3.3% improvement over policy a. Here, though, a 6.8% improvement is realized. Policy g also gives a 4.5% improvement over policy b as well as producing over 1500 more parts. Based on the above results, it appears that the decentralized approach to implementing feedback policies has some merit. In particular, for longer term production runs, the results here indicate that this approach yields appreciable improvement over the recommended age replacement policy. Furthermore, the improvement is relatively greater than that seen in the single machine case. This is encouraging. Of course, neither the age replacement nor the feedback policies considered here are optimal, but they do represent a reasonable engineering compromise between complexity, good performance, and practical concerns. Clearly, this approach warrants further investigation in the future.

188 AR FR/FS' a b g Production Time 222 230 213 Profit 788 834 810 Scrap Parts 7 16 0 Tools Used 101 52 83 Parts/Tool 9.917 19.17 11.99 Production Rate 4.509 4.356 4.685 Table 7.3.2.1 Production in 2 Machine Serial Transfer Line of 1000 Parts for G = 1 AR FR/FS a b g Parts Produced 21641 20911 22488 Profit 17049 17428 18205 Scrap Parts 158 337 O Tools Used 2182 1 091 1 876 Parts/Tool 9.917 1 9.1 7 1 1.99 Production Rate 4.509 4.356 4.685 Table 7.3.2.2 Production in 2 Machine Serial Transfer Line for 1 Week (4800 min) for G = 1

169 7.4. The Supervisor's Problem The supervisor's problem was introduced in Chapter 3. The gist of the problem is the determination of when to inspect and how to assign resources to a project. The problem formulation allows for the possibility of occasional progress assessment (i.e., feedback) and re-assignment of resources (control). The supervisor's problem is at once dissimilar and similar to the other manufacturing problems considered. The dissimilarity is perhaps most apparent. People have replaced machines; reliability and failure are no longer central to the problem; the time to complete a task is now stochastic. However, the problems do have some similarity. All represent problem situations that arise in manufacturing. All of the problems capture viewpoints different than those present in usual problem formulations. Finally, all of the problems admit a diffusion-threshold model allowing each problem to be placed in a stochastic control theoretic setting. The supervisor's problem attempts to capture the true role of the supervisor in scheduling problems. That is, most scheduling problems fail to include the underlying dynamics of the system being scheduled. The supervisor's problem extracts these hidden dynamics and brings them to the front. 7.4.1. Diffusion-Threshold Model of the Supervisor's Problem A model of use in the supervisor's problem using diffusion-threshold processes was introduced in Section 4.6.6. The idea is to model the progress on a project as a diffusion process, with the threshold representing the required amount of work for project completion. The infinitesimal coefficients are functions of the amount of resources committed to the project.

170 Project assessment can now be represented as occasional measurement of the diffusion process. The supervisor has the role of a controller. Based upon measurement feedback of project progress, resources are re-assigned to the project. However, the supervisor has the additional duty of scheduling the next assessment. Thus, the interval between measurements is in general random. Some simplifying assumptions will be made. Assume that the amount of resources committed to the project is constant between assessments. Thus, the coefficients of the diffusion are piecewise constant. Assume that project assessment can be done perfectly. Assume also that project assessment and resource assignment can be done in negligible time. 7.4.2. Optimal Control Formulation The supervisor's problem can be placed in a stochastic optimal control formulation. The goal will be to complete the project at minimal cost. Define the following given constants td project due date h _ cost rate for overdue project g _ cost of an inspection the given function f (-) a cost rate function for resources the random stopping time TA = project completion time

171 and the control variable u = resources assigned to project Let U be the set of available resources. Assume here that the set U is finite and that h, g, and f are positive. Let a policy ir & (r, u) where r = (ro, r,..., rN) is an inspection time sequence, u = (uts, uI,..., UI) is a control sequence and N is a ranX,. X-r dom integer. The stopping time ri is F'i- measurable and ui is F' measurable, with r0 = 0 and X0 = 0. Let I be the set of admissible policies. As before, the diffusion process is given by: St X = f b(u(?))dn + f'(u(,))dWq (7.4.2.1) 0 0 where u(v) = Uk, <rk_<rk+l (7.4.2.2) The project completion time TA is a threshold crossing time defined as before. TA = inf{t >0: Xt >A } (4.2.2.5) The threshold level A corresponds to the amount of work required to complete the task. Define a cost functional rA 0o JY= E[f f (u(q7))dq + E g'l[,'<rAI + h'(TA - td)+ ] (7.4.2.3) 0 F —0 Then the objective is to minimize JO for ir E 1. Assume here that there exists r E II such that J'<oo. The cost functional J1 captures the cost of resource usage, the cost of inspection, and the cost of lateness associated with a policy vr. Of course, there are other candidate cost functionals that could be used as well.

172 The objective here will be to develop a heuristic dynamic programming approach to the supervisor's problem. The result is quite similar to results obtained in [Anl], [An2], [Bell, [Be2l. However, there are some differences that make the supervisor's problem somewhat unique. Rigorous justification in a more technical setting of the dynamic programming approach can be found in the indicated references. Some solution techniques can also be found there. The intent here is only to show how the supervisor's problem can be placed in a mathematical setting. Define J"(t, a, z, u) as the cost to go under policy r at current time t if the last inspection was at time s and resulted in a progress measurement of z and a control u. This is just the standard embedding technique used in dynamic programming. Now define an optimal cost to go as V(t, 8, z, u)- inf J"(t, a, z IU) (7.4.2.4) This function represents the best that can be done from now on given the current state. Given the current state (t, 8, z, u), there are only two available choices: continue as is, or inspect and possibly change the control u. Consider each choice in turn. Suppose that continuation is chosen for some additional time At. Assume that t<TA. Then t+At V(t, a, z, Iu) < E('"")[ f (u)1[q< rldq + V(t+At, 8, z, ) ] (7.4.2.5) if t + At< t. If t>td then V(t, 8,, i,) <

173 t+At E(',")[ f f (u)1f[,<rAJd + h'(At A(TA-t)) + V(t+At, s, z, u)] (7.4.2.8) Consider first the case t+At <td. Note that if t < td such a At can always be found. t+Ot t + t V(t, a, z, U) < f (Us) f E(e.s~)[1(,,<TA]dl + E(`,'"')[V(t+At, a, z, u t +At = (u) I P [<_ TA I T> t, X. =., u]d. + V(t+at, 8, z, )P[TA >_t+t I T >t, X, =, u] (7.4.2.7) Define the function XarjA)4 qA(rjIX; U) X(r | Z; U) 1 QA (r I z; U) (7.4.2.8) Then P[t<TA<t+dtlTA>tX, z, u] X(t -lz;u)dt (7.4.2.9) and P[TA >t+dt ( TA >t, X, = z, I I] 1 - X(t - a 2; I )dt (7.4.2.10) Note that X( I z; u) is just the failure rate function associated with the random variable TA given the initial condition z and control u. Now for small At, P[TA __t+at TA >t, X, = X, u] = 1 - X(t - s 1 2; u)At (7.4.2.11) and t+tf PX, =At (74212) r P [I< TA TA >t, X, = =, u ]d,; Z At (7.4.2.12) So for small At, the inequality is approximately V(t, 8, z, u) < f (u)at + V(t+at,, z, 2,) - V(t+At, 8, z, u)'X(t - s I; u)At (7.4.2.13) Dividing by At and taking the limit as At- 0O results in

174 - V(t, SJ Z. U)+ V(t, a,, U).X(t - 8 IZ; U)- f (u) < 0 (7.4.2.14) In the case where t > td a similar inequality can be obtained: -a a V(t,, S, u) + V(t, a, ), u)X(t - 8 Z; u) - f (u)- h(1- X(t - s I z; u)) < 0 (7.4.2.15) A combined statement of (7.4.2.14) and (7.4.2.15) is -a at V(t, a, z, u) + V(t,, z, u)X(t - i |; u) - f (s) - hl lttl(l - X(t - I z; u)) < 0 (7.4.2.16) Suppose now that an inspection is made. Then V(t, a, z, u) < mm E(~'""')[ g + V(t, t, X,, u')] (7.4.2.17) SI E U (7.4.2.17) Since one of these two choices must be made, the function V must satisfy - o V(t, a, z, u) + V(t, a, z, u).X(t - I xz; u) - f (u) - h ltt>d1(1 - X(t - s I z; u)) V(t, a, z, u) - mn E(#'s")[ g + V(t, t, X,, u' ) ] = 0 (7.4.2.18) and V(t,s, z,u)=0 forz > A (7.4.2.19) This extremely complicated set of equations ( (7.4.2.16), (7.4.2.17), (7.4.2.18), (7.4.2.19) ) is a form of a so called quasi-variational inequality ([AnlJ], [An2], [Bel], [Be2J) and has been studied by these and other authors. Closed form solution is generally impossible, but numerical solution techniques have been discussed. Characterization of the solutions for some types of quasi-variational problems has also been discussed. Needless to say, much work is still needed in the area. As stated earlier, the goal was not to solve the problem explicitly, so no further attempt to resolve the supervisor's problem will be given here. The example shows how a problem arising in manufacturing might be approached by diffusion-threshold

175 modeling and control theoretic techniques.

CHAPTER 8 SUMMARY AND CONCLUSIONS The pressing need for improvement that confronts manufacturing today has inspired the composition of the central theme of this work: How can the feedback of information be effectively used to improve the manufacturing system? A control theoretic approach has been proposed as a methodology for addressing this problem. Unfortunately, the application of control theory concepts to manufacturing problems is not immediate. Several obstacles must be overcome in order to effect the application. Of particular concern in this work has been the question of modeling manufacturing problems in such a way so as to capture the important features while maintaining a compatibility with the control theory framework. The control theoretic approach has been conveyed through four example manufacturing problems. These problems have been formulated to capture important manufacturing features and to show viewpoints different from existing manufacturing problems. The problem of modeling has led to the development of a class of stochastic processes called diffusion-threshold processes. The objective in the study of diffusion-threshold processes is to obtain a probabilistic description of the stopping time associated with a threshold crossing by a diffusion. Although generally difficult, 178

177 several cases of interest have been developed where a distribution function can be computed. An important feature of diffusion-threshold processes is that they combine continuous and discrete phenomena into a single process. This allows diffusion-threshold processes to be used in the modeling of discrete events generated by underlying continuous processes. The implication of viewing discrete event systems this way is that information feedback and control can now be incorporated into the system naturally through the continuous process. Several examples of the application of diffusion-threshold processes to general classes of problems have been given. Diffusion-threshold processes are central to the study of the example manufacturing problems as well. The most developed example problem is the drilling problem. The problem is to determine feed speeds and make tool replacement decisions for a drilling operation. A stochastic model for tool wear, based on a diffusion-threshold process, has been introduced. This model allows the drilling problem to be formulated as a stochastic optimal control problem. The general control problem is difficult, so attention has been focused on two types of policies: age replacement and one step. Age replacement policies are open loop whereas one step policies use tool wear feedback. A comparison of age replacement and one step policies has been carried out through simulation. Two production situations have been considered: a batch run of 1000 parts and a longer term run of two shifts a day for a week. Various age replacement and feedback policies have been compared in terms of economic performance and secondary characteristics.

178 Two important conclusions can be drawn from this simulation study. The first is that age replacement policies can perform very well, provided that they are chosen (tuned) for the particular production situation. The second conclusion is that feedback policies based on the one step cost functional can give good performance in different production situations. However, some tuning of the policy may be required. For the problems simulated in this work, the importance of feedback in making tool replacement decisions seems to outweigh the importance of feedback in feed speed selection. In many cases, constant feed speed performs very well. Policies based on one step cost functionals performed better in the longer term production situation than in the batch situation. For one case considered, economic improvement in the longer term production situation over optimal age replacement policies was in the 3% - 4% range. These results are problem specific, but dramatic improvement cannot really be expected. Modest economic improvement and improvement in secondary characteristics is more likely. The concepts developed in the drilling problem have been extended to the case where multiple tools are used. The computations become more complicated, however. Results have been obtained under a block tool replacement assumption. An example age replacement problem with two tools has been worked out and the results show a somewhat more conservative policy as compared to the one tool problem. The multiple machine problem remains open. For the case of serial transfer lines, some simulation evidence suggests that decentralized policies based on local one step cost functionals perform better than local age replacement policies. The latter have been proposed by previous authors for transfer lines. The most encouraging observation is that for the two machine case, the percent improvement of one step

179 policies over age replacement policies more than doubled compared to the single machine case. This is clearly an area that deserves further future investigation. Finally, a different application of diffusion-threshold processes has been considered in the supervisor's problem. The problem attempts to capture the role of a supervisor in overseeing jobs. A heuristic dynamic programming argument leads to a quasi-variational inequality that the optimal cost function must satisfy. This development demonstrates both an alternative interpretation of diffusion-threshold models and a different analytic approach. This work is only an introduction to the control theoretic approach to manufacturing. Clearly there is a need for much more research. It is hoped that this work contributes to the understanding of how control theoretic ideas can be applied to manufacturing problems, and motivates others to pursue problems in this area.

APPENDICES 180

181 APPENDIX A DRILLING TERMINOLOGY This appendix summarizes relevant terms used in drilling and in this work. These terms are typical of what is found in machining data handbooks. U.S. customary units and typical metric units are indicated. U Fig. A.1 Drill d _ drill diameter (in or mm) w spindle speed (rpm) u = feed speed (or feedrate) (in/min or mm/min) V cutting speed - the tool/material relative velocity at the outer tool edge (surface feet per minute (sfm) or m/min) f = feed - the amount of linear travel of the tool per revolution (in/rev or

182 mm/rev) In U.S. customary units the cutting speed is given by V=;d2 (sfm) (A.1) 12 The feed is given by =-' (A.2) Note that V =12 (A.3) so that only two of the variables u, f, and V are independent. Machining data guides (e.g., [Macl]) often give recommended values for f and V. The simple Taylor tool life formula for fixed feed is given by [Drlj: VT' -- C (A.4) which can be expressed as (5.5.2.1): uT" 12fC = C, (A.5) Ird

183 APPENDIX B DIFFUSION-THRESHOLD PROCESSES WITH PIECEWISE CONSTANT COEFFICIENTS In this appendix, the class of diffusion processes is extended to allow for piecewise constant coefficients. This class of processes has not been previously discussed in the literature (to the author's knowledge). The diffusion-threshold problem is related to a problem in statistics concerned with Brownian motion crossing a curve. Based on the results for piecewise constant coefficients, a partial solution to the Brownian motion curve crossing problem is obtained. B.1 Calculation of Distribution Function Consider those diffusions where band a depend only on u and where u and thus b and a are piecewise constant, i.e. there exists a set of times 0= t<ti<''' <t, such that U- = uk, tk <r< th+1 for k = O,1,...,n - (B.i.1) U,-= U,,, t,,<T (B.1.2) b (u) = bh >O (B.1.3) O(uk) =- ak >0 (B.1.4) for k = O,1,...,n. Under these assumptions, {Xt} is a Brownian motion with piecewise constant drift and piecewise linear variance. In order to develop the threshold crossing distribution for this process, a result is needed that pertains to the constant coefficient case of Section 4.3.

184 Theorem (4.3.4): Given Xt = bt + aWf, b(u)>0, o(u)>0. Define Mt su XI (B.1.5) and for O<to< t1 MItoel=l sup X, (B.1.6) M' el,Ptill Then the joint density of (Xt, Mt) is given by: g9xu,s (,v,; t,u) = 2(2:Y-rl exp - (2Y-qi-bt)2 exp -2()b fr>7,> I 3 { 2a t }127 V2 3 — - (B.1.7) 0o otherwise Proof: The proof of this result uses a technique due to Levy in his study of driftless Brownian motion, as reported in [Itl]. Define the random variable Xt(a,,3) = llx,<,,>pL I for ca<_, P>0, t >0 (B.1.8) Then E [x, (a,)1 = P [Xt <a, Mt >3 ] (B.1.9) Now xt (a,) = Xllxt'l <l[t > I -= (a). dt (I) (B.1. 10) so that fexp{-st }E [Xt (a,)] dt = E [fexp{-,t }t (Xa), (1)dt] 0 0 = E[fexp{-,t }t (a)dtl lTs

185 00 = E [exp{-JT}fexp{-st }t+r (a)dt (B.1.1 ) 0 where T, is the B-threshold crossing time. By using the smoothing property, (B.1.11) can be written as E[exp{-aT$} E[fexp{-st},+r,((a)dt Fr I (B.1.12) 0 where FrT is the a-algebra induced by To. Using the strong Markov property and time shift (B.1.12) becomes E[exp{-, T,}E[f exp{-at}It(a)dt I Xo=- i i 0 = E[exp{-,T0}] E[fexp{-at}6,(a)dt I Xo= ] (B.1.13) 0 again using the strong Markov property to decouple past and future of Xt by XT- =. But (B.1.13) is just 00 qs(8 10; u)-E[fexp{-at }t (a)dt I Xo= ] (B.1.14) 0 where the first term is the Laplace transform of the threshold crossing density. The second term can be evaluated as follows. E[fexp{-est }t(a)dt | XO_ J = fexp{-8t}E[f (a) I Xo=O ]dt 0 0 00 a fexp{-8t }J fx, l Xo(. )d dt o — o a 00 -- f fexp{-at}/flxo(n I9)dt dq (B.1.15) -0o 0 where f is a conditional Gaussian density. But fexp{-at }fx, i x,( I l )dt (B.1.16) is just the Laplace transform of a conditional Gaussian density and is given by

186 exp{ (<) exp,I.x... where a -r2 (B.1.18) Now substitute (B.1.17) into (B.1.14) and differentiate with respect to a and, and negate to obtain the Laplace transform of the joint density J~exP~fW)}p fo' |1 2 "xp ~exp{ ( ) V2~(s-a)} for za (B.I.i9) -o-.~ ~ for K<a Taking the inverse transform and simplifying gives the desired result: _, ex - (2_-a-bt)2 exp - 2(0-a)b for >a, 0 O, t >o 3 2't - 2 [] -/2ra 3t 2 (B.1.20) 0 otherwise Remark: As before, the result holds for b = 0 (studied by Levy) but does not hold for b <0. The result easily generalizes to the case of nonzero initial condition X0 = O, with v > zo as given in the next corollary Corollary (B.1.1): Given Xi = zo + bt + oW,, b(u)>O, a(u)>O. Then the joint density of (Xt, Mt) is given by: X,,M,(qv I Zo; t,U) {gx,t (ru-z~ov-zo;,u) for > 7, >z, t>O (B.1.21) otherwise

187 Remark: The result extends to non-zero initial time as well. It is possible to verify that the marginal densities from the above joint density agree with the known results. Verifying the density for Xt is straightforward, but verifying the density for Mt is more difficult. Using the joint density for the maximum and final value of the process, the piecewise constant coefficient threshold crossing distribution can be developed. The term multi-step will be used synonymously with piecewise constant. Theorem (B.1.2): (Multi-step Threshold Crossing Distribution) Let t t Xt f b (u(r) )dr + f j(u(r) )dW, (B.1.22) o o where u(r) = Uk, tk, T< t,+1 for k = 0,1,...,n-1 (B.1.23) u (r) = U, t, <r (B.1.24) isn - (0o,...,,,) (B.1.25) b (u,) - bk >0 (B.1.26) u(us) = a, >0 (B.1.27) 0 = to<tl< <t, (B.1.28) and let A >0 be a threshold value. Then the threshold crossing probability distribution is given by: Q(t Io; u)= P{ TA < t I Xo=O; }= QAr-l(t I 0; uA-) for 0< t < t, 4 A. (B.1.29) Q-1(t" I 0; u"-) + f QA(t-t I,;u. )Go 1( t.; u I-l)dx for t_ <t z-00 where

188 QA(t I1~; U) -- QA (t [0; U) (B.1.30) and A GA (Z,t,+; u') = f GA-V_,(z-y,t,+l-t,; u,)G l(yt,; -)d(B.1.31) A G(~,t,; U)= r g(O,,;,,U)dV (B.1.32) Remark: The distribution for n steps (changes in u) can be calculated recursively from the distribution for n-I steps, assuming the same control sequence (u0o,., tU,,-l) and time of changes (t0,. tl). Remark: GA(zgt,+,; un) =.P[X < z, Mt 1<A] (B.1.33) Proof: Let -L = (0,..,,un1) (B.1.34) u (u-,u,),) (B.1.35) O - to<tl<.. < t,'_ < t, (B.1.36) Then for t < t,, the processes under u"'- and u" are identical. Therefore QZ(t O0;,U')= Q'-l(t O; U"-') for 0<_t < tn (B.1.37) and it suffices to prove the update part of the formula. Let t, < t. Then P[T, <t]= P[TAE[0,t,]] + P[TAE(t,,t] ] - A Q-(t, 10;'"'l)+ P[TAE(t,nt] ] (B.1.38) Now A P[TE(tt] ] = fP[TAE(t, I t. = ZI Mt <A [x, =,AS <A0I — Co

189 A - P [TA E(t,,t] I Xt=s ZdP [Xt, =, Mt, <A — o00 A = Q, (t,-t I z; u,)dP [X, =z, Mt<A] (B.1.39) -00 Denote P [Xt < z, Mt, <A] = GA-'x(z t,; u-) (B.1.40) and this is the first part of the result. Next, the update formula for GA must be determined. Let n =1. Then Go(,tl; v) - AZP[Xt1<zS Mt <A] A s - -(O)f f g(q,"; tl,uo)di1 dv'o0\r) -oo - f g(x,v; t1,uo)dv (B.1.41) (oVS) where g(-,; tl,u0) is the joint density function from Theorem 4.3.4. For n >1 G(Z,t.+l; u )= P [Xtl<, Mt <A A = d p[Xt l< itX Xt =y Mt <A, M(t, ) n+ A] dy x-00 -00 = d P[Xt, $- M(tf tI<A Xt M<=Y, t,<A,,,,]<A]dy - a P [Xtf+ <z M(t,,, 11<A I Xt=y I Gs'(y,t,; u, <-)dy -00 A --- f G~_,(z - ytl-,; u,,)G-r'(y,t,n; u"')dy (B.1.42) -00 which is the required update formula. Remark: The formula assumes a deterministic sequence ({u0,u, ~..,,u } for the control. That is, this is the threshold crossing distribution for open loop

190 finite control sequences. A similar formula for closed loop Markov control sequences is considerably more complicated. B.2 Curve Crossing Problems for Brownian motion A problem of some interest in the statistics literature is the following. Given a Brownian motion and an arbitrary curve -:R + —LRas a function of time determine the distribution and moments for the time of first crossing of the curve by a Brownian motion. See [Brel], [Ledl], [Robl]. As will be shown, the curve crossing problem for Brownian motion is related to the multi-step problem previously considered. Based on the results for the multi-step case, a partial solution to the curve crossing problem is given. In the general formulation of the curve crossing problem, discontinuous curves are allowed provided that the discontinuities are points of increase. Only continuous curves will be considered here. Let -S:R + — (B.2.1) be a continuous function. Let W1 be a standard Brownian motion. Define T- inf{t >_0: Wt > a(t)} (B.2.2) T7 is the time at which the Brownian motion first hits the curve -, and is a stopping time. The problem is to find the distribution function for T7. This is an essentially unsolved problem, except for the case where - is a decreasing straight line with positive initial value.

191 Definition: Let C' be the class of decreasing concave piecewise linear curves such that for E C": BR + — R (B.2.3) = (t )-A - f b (r)d r (B.2.4) 0 where A >0 (B.2.5) b(r)- bk > 0, tk <Tr< tk+ for k = 0,1,...,n-1 (B.2.6) b(r) = b, > 0, t <r (B.2.7) = to<.. <t, (B.2.8) Theorem (B.2.1): Let 7 E C". Then P[T,<oo] = 1 (B.2.9) and P[T,7<t] = Q"(t 0; u") (B.2.10) where b(uh) = bk (B.2.11) O(uk,) = 1 (B.2.12) Proof: Let X= f b (r)dr + W (B.2.13) 0 Then X, >A Nr W>A - f b (r)dr (B.2.14) 0 so the results of the multi-step threshold crossing problem apply immediately. Thus the first statement follows from Lemma 4.3.1. For the second statement, observe

192 that {w: T7<t} = {w: W >A - fb(j)dr} 0 - {: X >A} = {w: TA <t} (B.2.15) where TA is the threshold crossing time for the process X,. Therefore P[T7_<t] = P[TA <t] = QA(t 10; u) (B.2.16) Remark: Clearly there exist curves not in C" such that P [T. = ool >0. Remark: The curves considered here (e C") are reasonable approximations to the class of decreasing concave asymptotic curves. The following example (Fig. B.2.1) illustrates this: Fig. B.2.1 Example Curve Crossing Problem

193 APPENDIX C PROPERTIES OF THE ONE STEP COST FUNCTIONAL In this appendix, properties of the one step cost functional used in Theorem 5.7.2.1 will be proven. It is sufficient to consider the limiting properties of the functions A, rA, and ZA. V Assume b(u) = — u", a > 0 is constant, a = A - zo > 0, and t! = -. Without loss of generality, it is sufficient to consider the functions sa I 10), r,,( 1 ), and z,,( I 0). Lemma (C.1): nm I.(U o0) = 1 (C.1) Proof: Note that 8,(u 0) is bounded o < a,(U I 0) (C.2) because s(u 10) = P[Ta< tf; ul (C.3) Now of o0 a(Ut) o)= fqo(,7O0; u)d,=7- f1I<,lqo(,j0; u)d, (C.4) 0 0 By Fatou's lemma lim s,(u O) = lim I 1l<t, 1q(nl; u)ddq m 0 0+ is —*0 0 00 >f lim l,1<-flqo(7o; u)d 0 u- 0+

194 00 ='qo(IO; O)d = 1 (C.5) 0 Since s, is bounded above by 1, the result follows. Remark: This result is true for m >O. Lemma (C.2): For m > 1 Ur 8C,(u 10) = 1 (C.6) Proof: This is most easily seen by using the normal form transformation for the inverse Gaussian distribution given in Section 4.3. 8(U 1 0)= ) < <1 - 1 + exp {2 4~ Z a +1 (C.7) Then lim a,(u Io0) -- 00 0 00 LQ V V o aV a 1 a J > 1+ im exp ( 2au }[ / V (C08) The result follows since s, is bounded. Remark: It is relatively easy to show that UM" exp { 2a/ +1 ] ] = ~ (C.9) 0 1* 00 01 V a

195 Remark: The result in not true for m <1. It can be shown that for m = 1 1 <1 vg lim a,(U I0)= -- = 1 (C.10) 00 + Q) 2 VR 0 va >1 and for 0 < m < lim srn(U ~0) 0 (C.11) Lemma (C.3): lim z,(u 1)= oo (C.12) -- 0* Proof: By Fatou's lemma, 0o+ es-* 0+ 0 00 > | l 1l[,<t], qo(,10; u )d, co = fIqo( I o0; u)d, = oo (c.13) where the last result is from Theorem 4.3.2. Lemma (C.4): lim Z,(u 10) = (C.14) -' 00 Proof: lim z,(u 10) = lim flij,<,fl7qa(j I 0; u)d7 %-I* 00 S — + 00 0 < lim fqqa(/ O; U)dq w — 00

19i lg O lim -- 0 (C.15),, oo0,u m But zo(u 10) > 0 for all u E R +. Therefore the result follows. Lemma (C.5): lim ra(u 10) = -- (C.16) —.* 0+ Proof: Recall that r.(u I 0) = E [Xf,f < r;] (C.17) Now E [Xf] =E [X,f 1t, < rI] + E [X9f 11f > r 1] (C.18) So lim E[XZ] = lim E[Xt, 1[,f<ra]i + lim E[Xt, 1, ral] (C.19) -_-. 0' fS,- * 0 0+ assuming this is well defined. Since X, -- N(#Vu"'-, o2t ),m E[X,,] = lim Vum- (C.20) a 0+ m..-,. 0' for m >1. Therefore Jim r,(u 10)= limn E[Xtflf>raj] (C.21) - O' m —+ 0'* -- By the smoothing property for strong Markov processes E [Xtt l[t, > T] = E [ E [Xt,, lf > ra I To = t] ] = fE[Xtflt>l, a To = t]qa(t IO; u)dt if itf = caf q(t 10; u)dt + u " f (tf - t)q.(t 10; u)dt (C.22) o o using the fact that E[XFIlff,>T I To = t] = a+ fu"m (tt - t) (C.23) Taking the limit of each term in (C.22) gives

197 t! lir af q(t I; u)dt a lim s,(u 10)- a (C.24).-. O 0 0*O+ Urm pum f(t, - t)q(t IO; U)dt < im ou tf q.(t I; u)dt 3pu|f(tf - t)q0(t ~0; u)dt > o (C.26) 0 Thus the limit of this term is 0. The result now follows. Remark: Note that lim ( ro(U I 0)+ aao(U 0) )=0 (C.27) -" 0+ Lemma (C.8): lim r,(u 1 0)= 0 (C.28) Proof: lim ra(u ) 2 - l I E [X,, lft, < T,] 2 m —-* 00 0of < lim E [Xt ] E [if < T]= lm E[X ]P[tf < T, = lim (2u 2(m"-l) + -)(1 - Q(tf 0 u)) S _+ 00 u - lim 2y2V 2(m-').(1- Qo(tf 10; u)) -im/02V2U2("-I) -* 00 00 01- iI a2 cr vg1.1 -- x < limSv2 N= r (oVC2 0.29)2L U v CO ] (.9

198 Now for z > 0 ([Abl]): exp {-. } (C.30) Using (C.30) in (C.29) it can be shown that nim p2V2U2(^-Q)42 [- OjtTz. V.. =0 (C.31) VL —-* cV a The result then follows. Using these properties of the functions as, ra, and z0, the limits of the one step cost functional can be computed. The limits are stated in Theorem 5.7.2.1. lim J(u,0) = lim[(B + R)-.(u 0o)+ D(a~ a(u lO)+ r.(u 0o)) V + (K. - G)-(1-,(u 1 0)) + Kz,(u I 0) B +R +Da (C.32) lim J,(U,0) = im [(B + R)s.o(u 1) + D(a,(u I 0) + r.(u I0)) + (K-. - G).(1-,o(u I 0)) + K.z(u I 0) > lim K-z(U l0)= o (C.33) The results for follow similarly giving quations (5.7.2.19a) - (5.7.2.19). The results for J2 follow similarly giving equations (5.7.2.19a) - (5.7.2.19d).

REFERENCES 199

200 REFERENCES [Abl] Abramowitz, M. and Stegun, I.A., Handbook of Mathematical Functions, Dover, N.Y., 1965, 9th printing [Ani] Anderson, R.F. and Friedman, A., "Optimal Inspections in a Stochastic Control Problem with Costly Observations", Math. of Op. Res., Vol. 2, No. 2, May 1977, pp. 155-190 [An2] Anderson, R.F. and Friedman, A., "Optimal Inspections in a Stochastic Control Problem with Costly Observations, II", Math. of Op. Res., Vol. 3, No. 1, Feh. 1978, pp. 67-81 [Bel] Bensoussan, A. and Lions, J.-L., Applications of Variational Inequalities in Stochastic Control, North-Holland, 1982 (trans. from 1978 French ed.) [Be2] Bensoussan, A. and Lions, J.-L., Impulse Control and Quasi-Variational Inequalities, Bordas, Paris, 1984 (trans.) [Blll Blake, I.E. and Lindsey, W.C., "Level-Crossing Problems for Random Processes", IEEE Trans. Info. Theory, Vol. 19, May 1973, pp. 295-315 [Brel] Breiman, L., "Exit Times from a Square Root Boundary", in 5th Berkeley Symp. on Mathematical Statistics and Probability, Vol. 2, Pt. 2, 1966, pp. 9-16 [Brl] Bremaud, P., Point Processes and Queues, Springer-Verlag, New York, 1981 [Bul] Buzacott, J.A. and Shanthikumar, J.G., "Models for Understanding Flexible Manufacturing Systems", Trans. AIE, Vol. 12, No. 4, Dec. 1980, pp. 339-350 [Chl] Chhikara, R.S. and Folks, J.L., "The Inverse Gaussian Distribution as a Lifetime Model", Technometrics, Vol. 19, No. 4, Nov. 1977, pp. 461-468

201 [Crll Crabill, T.B., Gross, D., and Magazine, M.J., "A Classified Bibliography of Research on Optimal Design and Control of Queues", Operations Research, Vol. 25, No. 2, March-April 1977, pp. 219-232 [Dal] Danai, K. and Ulsoy, A.G., "A Dynamic State Model for Tool Wear Estimation in Turning", Sensors and Controls for Manufacturing, ASME Winter Conf., Nov. 1985, pp. 137-148 [Del] DeVor, R.E., Anderson, D.L., and Zdeblick, W.J., "Tool Life Variation and Its Influence on the Development of Tool Life Models", ASME Jour. Eng. Ind., Vol. 99, Aug. 1977, pp. 578-584 [Drl] Drozda, T.J. and Wick, C. (eds.), Tool and Manufacturing Engineers Handbook, Vol. I, Society of Manufacturing Engineers, Dearborn, Mi., 1983 [Dull Dubois, D. and Stecke, K., "Using Petri Nets to Represent Production Processes", Proc. 22nd CDC, Dec. 1983 [Ell] Elliot, R.J., Stochastic Calculus and Applications, Springer-Verlag, N.Y., 1982 [Erll] Ermer, D.S., "A Bayesian Model of Machining Economics for Optimization by Adaptive Control", ASME Jour. Eng. Ind. Vol. 92, Aug. 1970, pp. 628-632 [Fell Feller, W., An Introduction to Probability Theory and Its Applications, Vol. II, Wiley, New York, 1971 [Fll] Fleming, W.H. and Rishel, R.W., Deterministic and Stochastic Optimal Control, Springer-Verlag, New York, 1975 [Gel] Gershwin, S., Hildebrant, R., Suri, R., and Mitter, S., "A Control Theorist's Perspective on Recent Trends in Manufacturing Systems", Proc. 23rd CDC, Dec. 1984

202 [Ge2I Gershwin, S., Akella, R., and Choong, Y., "Short Term Production Scheduling of an Automated Manufacturing Facility", Proc. 23rd CDC, Dec. 1984 [Ge3] Gershwin, S., from Tutorial Notes: "Manufacturing Systems Modeling and Control", IEEE Conf. on Robotics and Automation, April, 1986 [Hal] Hati, S.K. and Rao, S.S., "Determination of Optimum Machining Conditions - Deterministic and Probabilistic Approaches", ASME Jour. Eng. Ind. Vol. 98, Feb. 1976, pp. 354-359 (Hil] Hitomi, K., "Optimization of Multistage Machining System: Analysis of Optimal Machining Conditions for the Flow-Type Machining System", ASME Jour. Eng. Ind. Vol. 93, May 1971, pp. 498-506 [Hi2] Hitomi, K., Nakamura, N., and Inoue, S., "Reliability Analysis of Cutting Tools", ASME Jour. Eng. Ind. Vol. 101, May 1979, pp. 185-190 [Hol] Ho, Y.C. and Cassandras, C., "A New Approach to the Analysis of Discrete Event Dynamic Systems", Automatica, Vol. 19, No. 2, 1983 [Ho2] Ho, Y.C., Suri, R., Cao, X.R., Diehl, G.W., Dille, J.W., and Zazanis, M., "Optimization of Large Multi-Class (Non-Product Form) Queueing Networks Using Perturbation Analysis", Large Scale Systems Journal, Vol. 7, No. 2/3, Dec. 1984, pp. 165-180 [Itl] Ito, K. and McKean, H.P., Diffusion Processes and Their Sample Paths, Springer-Verlag, N.Y., 1965 [Iwl] Iwata, K., Murotsu, Y., Iwatsubo, T., Fujii, S., "A Probabilistic Approach to the Determination of the Optimum Cutting Conditions", ASME Jour. Eng. Ind. Vol. 94, Nov. 1972, pp. 1099-1107

203 [Kaml] Kamath, M. and Viswanadham, N., "Applications of Petri Net Models in the Modelling and Analysis of Flexible Manufacturing Systems", Proc. IEEE Conf. on Robotics and Automation, April, 1986 [Kanl] Kannatey-Asibu, Jr., E., "The Metal Cutting Optimal Control Problem - A State Space Formulation", Control of Manufacturing Processes and Robotic Systems, Hardt, D.E. and Book, W.J. (eds.), ASME, New York, 1983 [Karl]Karlin, S. and Taylor, H., A First Course in Stochastic Processes, 2nd ed., Academic Press, New York, 1975 [Kar2]Karlin, S. and Taylor, H., A Second Course in Stochastic Processes, Academic Press, New York, 1981 [Kel] Kendall, L.A. and Sheikh, A.KC, "Coefficient of Variation: An Index of Tool Reliability and Its Significance in Automated Production", SME Proc. NAMRC, 1979, pp. 362-369 [Kill Kimemia, J. and Gershwin, S.B., "An Algorithm for the Computer Control of a Flexible Manufacturing System", IE Trans., Vol. 15, No. 4, Dec. 1983, pp. 353-362 [K1] Kleinrock, L., Queueing Systems Vol. I, Wiley, New York, 1975 [Kol] Koren, Y., "Flank Wear Model of Cutting Tools Using Control Theory", ASME Jour. Eng. Ind. Vol. 100, No. 1, Feb. 1978, pp. 103-109 [Krtl] Krtolica, R., "A Singular Perturbation Model of Reliability in Systems Control", Automatica, Vol. 20, No. 1, p. 51, 1984

204 [Kryl]Krylov, N.V., Controlled Diffusion Processes, Springer-Verlag, New York 1980 [Lal] Law, A.M. and Kelton, W.D., Simulation Modeling and Analysis, McGraw-Hill, N.Y., 1982 [Ledl] Leadbetter, M.R., "On Crossings of Levels and Curves by a Wide Class of Stochastic Processes", Ann. Math. Stat., Vol. 37, 1966, pp. 260-267 [Lel] Levi, R. and Rossetto, S., "Machining Economics and Tool Life Variation, Part 1", ASME Jour. Eng. Ind. Vol. 100, Nov. 1978, pp. 393-396 [Le2J Levi, R. and Rossetto, S., "Machining Economics and Tool Life Variation, Part 2", ASME Jour. Eng. Ind. Vol. 100, Nov. 1978, pp. 397-402 [Loll Loeve, M., Probability Theory I, II, 4th ed., Springer-Verlag, N.Y., 1978 [Macl] Machining Data Handbook, Second Ed., compiled by Machinability Data Center, Metcut Research Assoc., Inc., Cincinnati, Ohio, 1972 [Matl] Matkowsky, B.J. and Schuss, Z., "The Exit Time Problem for Randomly Perturbed Dynamical Systems", SIAM J. of Appl. Math., Vol. 33, 1977, pp. 365382 [Mel] Mehr, C.B. and McFadden, J.A., "Certain Properties of Gaussian Processes and their First-Passage Times", J. Royal Stat. Soc. (B), No. 3, 1965, pp. 505522 [Mull Muth, E.J., "Memory as a Property of Probability Distributions", IEEE Trans. Rel., Vol. 29, No. 2, June 1980, pp. 160-164

205 [Pel] Pegden, C.D., Introduction to SIMAN, Systems Modeling Corp., State College, PA, 1982 [Phl] Philipson, R.H. and Ravindran, A., "Application of Goal Programming to Machinability Data Optimization", ASME Jour. Eng. Ind. Vol. 100, April 1978, pp. 286-291 [Rob 11 Robbins, H. and Siegmund, D., "Boundary Crossing Probabilities for the Wiener Process and Sample Sums", Ann. Math. Stat., Vol. 41, 1970, pp. 14101429 [Rol] Ross, S., Stochastic Processes, Wiley, New York, 1983 [Sall Savage, R.I., "Surveillance Problems", Naval Research Logistics Quarterly, Vol. 9, 1962, pp. 187-209 [Shkl]Sheikh, A.K., Kendall, L.A., and Pandit, S.M., "Probabilistic Optimization of Multitool Machining Operations", ASME Jour. Eng. Ind. Vol. 102, Aug. 1980, pp. 239-246 [Shrl] Sherif, Y.S., and Smith, M.L., "First Passage Time Distribution of Brownian Motion as a Reliability Model" IEEE Trans. Rel., Vol. 29, No. 5, Dec. 1980, pp. 425-426 [Sil] Siegert, A., "On the First Passage Time Probability Problem", Phys. Review, Vol. 81, Feb. 1951, pp. 617-623 [Sol] Solberg, J., "Analytical Performance Evaluation for the Design of Flexible Manufacturing Systems", Proc. CDC, 1979

206 [Sul] Suri, R., "Robustness of Queueing Network Formulae", J. ACM, Vol. 30, No. 3, July, 1983, pp. 564-594 [Su2] Suri, R., "An Overview of Evaluative Models for Flexible Manufacturing Systems", Proc. First ORSA/TIMS Conf. on FMS, Aug., 1984 [Takl] Takahashi, N. and Kahng, C.H., "Stochastic Optimization of Production Speed", SME Proc. NAMRC, 1983, pp. 461-465 [Tayl] Taylor, F.W., "On the Art of Cutting Metals", Trans. ASME, Vol. 28, 1906, pp. 31-350 [Twl] Tweedie, M.C.K., "Statistical Properties of Inverse Gaussian Distributions I", Ann. Math. Stat., Vol. 28, 1957, pp. 362-377 [Wall Wager, J.G. and Barash, M.M., "Study of the Distribution of the Life of HSS Tools", ASME Jour. Eng. Ind. Vol. 93, Nov. 1971, pp. 1044-1050 [Whl] Whitney, C., "Control Problems in Flexible Manufacturing", Proc. 1984 ACC, San Diego, -1984 [Wol] Wong, E. and Hajek, B., Stochastic Processes in Engineering Systems, Springer-Verlag, New York, 1985

3 9015 0265:i 6433