Ayrık olay sistemlerinin incelenmesi

Abstract

Son yıllarda kullanılan teknolojinin gelişmesi ve her alanda geniş bir şekilde kullanılmaya başlanması, son derece karmaşık sistemlerin ortaya çıkmasına neden olmuştur. Bu yeni sistemlerde fiziksel zorluklar teknoloji sayesinde çözülmüştür, dolayısı ile sistemi oluşturan elemanların değişen koşullar ve değişen beklentiler karşısında her zaman uyumlu çalışmasını sağlamak en önemli sorun durumuna gelmiştir. Artık bu sistemlerde fiziksel kısıtlamalardan çok, insan-makine etkileşimi önem taşımaktadır. Bu tür sistemlere bilgisayar haberleşme şebekeleri, bilgisayar yönetimli üretim hatları örnek gösterilebilmektedir. Sonuç olarak bu sistemler daha değişik açılardan ele alınarak incelenmelidir. Bu çalışmada, yeni gelişmekte olan Ayrık Olay Sistemlerinin incelenmesi konusunda yapılan birçok çalışmadan biri tanıtılmaya çalışılacaktır. Çalışmanın birinci bölümünde Ayrık Olay Sistemleri genel olarak tanıtılmaktadır. İkinci bölümde ise Sistem Teorisinin bakış açısı tanıtılarak, Dinamik Sistemler ve Ayrık Olay Sistem Modeli tanı nü anmaktadır. Sistem Yönetimi ve bazı sorunları Üçüncü Bölümün ana konularını oluşturmaktadır. Dördüncü Bölümde Modüler Denetçi Tasarı mira içermektedir. Beşinci ve son bölümde çalışma sonuçları incelenmektedir.

Modern techology has increasingly created man-made dynamic systems which are not easily described by ordinary or partial differential equations. Examples of such systems are production or assembly lines, computer/commununication networks, traffic systems gn both the air and landside of an airport, military C I (Command + Control + Communication + Intelligence) systems, etc., where the evolution of the system in time, depends on the complex interactions of the timing of various disrete events, such as the arrival or the departure of a job or the initiation and completion of a task or message. The "state" of such dynamic systems changes only at this discrete instants of time instead of continously. Such man-made systems are called Discrete Event Dynamic Systems as opposed to the more familiar Continuous Variable Dynamic systems of the physical world that are described by differential equations. It is instructive to look a typical example trajectory of Discrete Event System, which is illustrative in Figure 1.3 in terms of a simple communication system. This is contrasted with a typical Continuous Variable Dynamic System trajectory in Figure 1.1, which consists of solutions of differential equations. For the discrete event system, the trajectory is piecewise constant and event driven. The sequence of piecewise constant segments represents the state sequence, and the duration is generally continuous. Thus a sequence of two numbers (state and state holding time) basically characterizes the trajectory. On the other hand, a CVDS trajectory is constantly changing with the state taking value in r'' and is generally driven with continuous inputs. The definition of state is also different in DES and CVDS. In the former, it is the "physical " state, e.g., the number of messages at each node in the communication network awaiting transmission, while in the latter,. it is the "mathematical" state in the sense of all the information at a given time other than external inputs that is required to uniquely specify the future evolution of the system. The mathematical definition of state includes the physical definition but not vice versa. -v-Compared with CVDS, DES is a relatively recent phenomena. It belongs in the domain of Operation Research (OR). Although a brief examination of any OR textbook tends to give the impression that OR represent a collection of useful techniques, such as decision analysis, mathematical programming, Markov chains, and queue ing theory, OR can and should be thought of as the science of operations and events of man-made systems. In this sense, DES is properly a subject of OR since it is represented primarily by man-made system governed by "rules of operations". However the development of DESs also received a large impetus from Control and System Theory. In particular, it is submitted that the concept of dynamics, such as time constants, time and frequency response, controllability and observability, have played and will continue to play important roles in the development of models and tools for DESs. Since DES is primarily man-made rather than a physical /natural.system, it tends to interact more with humans than with nature. A controlled but unmanned spacecraft to Mars is interacting mostly with nature (Newton's Law of motion and gravitation, the electromagnetic spectrum, etc. ). On the other hand, a Flexible Manufacturing system, even under computer control, is interacting more with human operators through terminals or actual materials handling. This has implications in the practical implemention of any DES theory in two respects. First, Artificial Intelligence (AI) interface and Natural Language processing ability may be much more important factor in DES than in CVDS. In manufacturing automation, for example, DES are required to interface with personnel of lower skill levels than those operating aerospace vehicles. Secondly, since DESs are totally man-made, there are no invariant physical laws to constraint system configurations other than natural limits of material and ergonomics. Combinatorial complexity can easily occur. Consequently, it is not possible to see the day when all solutions to all DES problems can be reduced to an algorithm. In summary, the DES research lies at the intersection os System & Control Theory, Operation Research and Artificial Intelligence. The importance of well established modeling framework such as the one found in CVDS using differential equations cannot be overemphasized, he models of DESs can be classsified in two sidşs :Untimed models and timed models. The former emphasize the "state sequence"of a DES and de-emphasize or omit -vi-entirely the "holding time" specifications for each state. Thus, in such models one primarily ask questions of qualitative or logical nature, e.g., "yes" or "no", "true" or "false". Timed models, on the other hand, incorporate "time" as an integral part of the model and more suited for answering performance related questions. In this work, an untimed model for DES is established. Main definitions used in this model will be given firstly. Events which can occur in DESs is represented by symbols and an alphabet Sis a finite nonempty set of symbols. A stringover the alphabet Z is a finite sequence of the elements of Z. Thus a string represents a sequence of events of a DES.The string consisting of zero symbols is denoted by I. AThe set of all finite string over Z is denoted by 2 A juxtaposition (or concatenation) of any two strings s and t, denoted as st, is also a string and s can be called as the prefix of st and t can be called as the suffixof st. The set of all admissible, i.e.,,. physically possible, strings is then a subset Lof Z. It is customary to call a subset of 2 a languageqver the alphabet Z A string for example u=& &..& <=Z, represents a partial event sample path. * A spring u is a prefix of a string veZ if for some weZ, v=uw. If v is an admissible sample path, then clearly so are aj,l the prefixes of v. If we define pref ixclosureof L £Zto the language * L = {u: uveL for some v«^- } the it is needed L=L. In this case L is said to be prefix closed. A DES is modeled as an automaton or a generator defined as 5-tuple: G = (Z, Q, 6, q0,Q)ri) where Q is the state set, 6:ZxQ - ? Q is state transition function, q is initial state and Q £Q is the marked state set of DES. Generator G can be interpreted as a device that starts in its initial state q and executes state transitions, i.e., generates a sequence of events following by its state transition graph. State transitions are occur spontaneously, asynchronously and insantaneously, and their occurence is signaled by the corresponding event -vi i -label cQ by defining '5(I,q)=q and &(w-y,q)=ö(0, 6(w,q)) whenever q=£(w,q) and £(w,g) are defined. The closed behaviour of G is defined to be prefix closed language L(G) = { w: w «Z and *(w,q ) is defined }. Marked behaviour of G (with respect to Q ) is defined as follows: L..(G) = { s: seL and 6 (s, qo )eQv.}. The language L.(G) is interpreteed as a distinguished subset of the generated sequences that could represents completed tasks (or sequences of tasks)carried out by the underlying DES thart G is intended to model. In order to control a DES it will be assumed that certain events of the system can be disabled (i.e. prevented from occuring) when desired. This provides to influence the evolution of the system by prohibiting the occurence of key events at certain times. So alphbet Z is partitioned into uncontrollable and control lab 1 e events : z = z u z. a c The events in Z_ can be disabled at any time, while those in Z model events over which the control agent u has no influence, e.g. machine breakdown in a manufacturing system, loss of a data packet in a communication channel. A control input for G consists of a subset r£Z satisfying S -=y. If o = (S,0) S = (I, X,?,x.X) is a deterministik automaton with state set X, input alphabet Z, transition (partial) function £ :Z*x - ? X, initial state x and marker subset X cX; while o m 0 : X - ? r is a total function that maps supervisor states x into control patterns y. In many applications it will be the case that X =X, i.e., the supervisor plays no auxilary marking role. -Yİİİ-It is needed to design as supervisor that select control inputs in such a way that the given DES G behaves in obedience to various constraints. Roughly, constraints can be viewed as requiring that certain undesirable sequences of events are not permitted to occur, while at the same time, certain other desirable sequences are permitted to occur. We introduced the main concept of control of DESs. The criteria is developed for the existence of a supervisor for which the corresponding closed-loop controlled system satisfied given linguistic requirements in the Chapter 3. Some special kind of supervisors such as proper, nonblocking and nonrejecting supervisor are introduced and projection (or simplification) of supervisors are defined. Modular approach to supervisor synthesis is formulated in Chapter 4, in order to reduce the complexity of supervisor synthesis. In this approach the control task is split into several subtasks, these are solved using the existing theory, and the resultant "subcontrollers" are combined to form a solution to the original problem. In addition to being more easily synthsized, a modular supervisor should be more easily modified, updated, and maintained. If one subtask is changed, then it is only necessary to redesign the corresponding subcontrol ler, rather than the entire supervisor. This work has provided an introduction of one trend in the development of a control theory for discrete event systems. Many problems has been solved in this model. But still there are lots of them.