Search

Job scheduling or operation scheduling is a typical problem frequently appearing within DEDS. The core of the problem consists in how to achieve an optimal distribution of jobs or operations among the processing units or servers available in the system under various criteria. In other words, the problem is the optimal allocation of the system resources (Frankovič and Budinská 1998). Typical environments in which a scheduling problem occurs are flexible manufacturing systems, distributed computer systems, database systems, and other. For example, flexible manufacturing systems (FMS) usually consist of product processing or machining units, measuring and testing equipments, transportation facilities, manipulators and robots, intermediate storages, input and output devices. Various methods have been developed for scheduling problems (Engell 1989; Li et al., 1995; Zhou and Venkatesh, 1998). It has been discussed earlier in this book that process control means control of the basic processes at the level responsible for direct control. It is the control level or layer closest to the system processes. A hierarchically higher level is the coordination level of the basic processes. Here, the co-ordination is considered as a selection of servers performing basic processing, if there are more options. For example, in flexible manufacturing systems it is a selection of production units if there are more options to realize a prescribed technological recipe. One of coordination aims is to accomplish the required jobs in the minimum time span. [ABSTRACT FROM AUTHOR]

The basic notion of discrete event dynamic systems (DEDS) was introduced in Chapter 1. Finite automata and Petri nets have been studied as powerful models of DEDS for their behavior modeling and control. It has been shown that the states and transitions are key features of both models. Consider an event-driven system being in its initial state. The complete behavior of the system is given by all possible event strings beginning in the initial state. The event strings are formally described by Equations (1.11) and (1.12). [ABSTRACT FROM AUTHOR]

Finite automata, Petri nets, Grafcet, statecharts, etc., are tools for DEDS specification and analysis. They represent a system as a whole or its chosen parts. The function of the control system to be designed requires specific extensions of the expression means in order to enable a reactive performance of the control in a feedback system structure. Generating a DEDS model is a highly creative process. There are many ways how to achieve this goal. However, precise and exhausting hints for it do not exist. Rather there are several supporting methodologies. One of useful practical ways is to first elaborate a model of the complete system as it appears to an observer with the control included. Second, a model of the system control is to be elaborated, which may serve for the control function analysis and writing control programs. [ABSTRACT FROM AUTHOR]

So far it could be observed how some shortcomings of finite automata used for DEDS modeling were overcome by Petri nets and Grafcet. This is mainly due to the latter's ability to specify the parallel activities of subsystem states and concurrency of events. However, a certain imperfection of both persists. Difficulties in visualizing large and complex DEDS require to apply a sort of hierarchical decomposition. Another tool for coping with this problem is statecharts (Havel 1987 and Fogel 1997, 1998). Statecharts use the same notions as the tools mentioned above, namely state and event, and are based on the basic transition system as well. They represent structure and dynamic behavior in a drawn graphical form. Their set-theoretic and functional description is possible, too. The next section introduces their concepts and Section 11.3 presents their applications to DEDS. [ABSTRACT FROM AUTHOR]

Petri nets in the standard form as considered until now are an effective tool for DEDS modeling and control design. They enable one to specify powerfully the system function. Analysis methods are used for testing Petri net model properties and hence to check the correct system function (Desel 2000). Very often quantitative properties of the system behavior are another point of interest. In other words, a kind of system function performance or system efficiency is dealt with. In order to make the performance analysis feasible, additional values, parameters, and variables are used within the Petri nets (Čapkovič 1993, 1994, 1998). Another reason for additional values to be built in the Petri nets is to make the Petri net models more transparent and understandable even for large and complex DEDS. Such extensions are often denoted as high level Petri nets (Struhar 2000) or generalized Petri nets (Juhás 2000). Standard Petri nets are not suitable for performance analysis. Undoubtedly, for performance analysis, an important system variable is time. Time enriches information by telling in what time or time interval a particular event occurs or should occur (Čapek and Hanzálek 2000). There are three ways to embed time into Petri nets. The first is to map the Petri net places into time intervals given as real or integer numbers; the second is to map them analogously into the Petri net transitions; and the last is to map into the arcs (Zhou and Venkatesh 1998). The options can be used separately or together. [ABSTRACT FROM AUTHOR]

Grafcet is designed as a specification tool for logic control to be implemented preferably on programmable logic controllers (PLC). It is a tool related closely to the binary safe Petri nets interpreted for control (Section 7.5). [ABSTRACT FROM AUTHOR]

Many important properties of Petri nets can be analyzed by means of Petri net reachability and coverability graphs. The reachability graph relates to the Petri net marking reachability. A frequently asked question is whether a given marking m is reachable by a transition firing sequence. First let us define the transition firing sequence. The starting marking is important in that question. [ABSTRACT FROM AUTHOR]

As described in Chapter 5, a finite automaton specifies a system by means of a set of states and a transition function. The arguments of the transition function are the state and event. We can speak about an actual state. The transition function assigns a state to an actual state. The assigned state is a next state while the actual state can be called the active present state. By repeating the assignments, a sequence of actual states is obtained. In the finite automaton there is always only one state active. A system can often be broken down into subsystems. If it is required to describe activities of subsystems and their mutual relations, a finite automaton model can be cumbrous because each combination of subsystem states needs a separate state of the finite automaton. Another model known as a Petri net removes that inadequacy. Petri nets are named after a German mathematician C. A. Petri who first proposed a model of that kind (C. A. Petri, 1962). With Petri nets the main idea is to represent states of subsystems separately. Then, the distributed activities of a system can be represented very effectively. Many properties of the DEDS, e.g., synchronization, concurrency, and choices can be well presented and analyzed using Petri nets. They can be used not only for the specification of the DEDS behavior but also the control design. However, Petri nets have various other uses. [ABSTRACT FROM AUTHOR]

Flow diagrams, sometimes called flow charts, are popular in programming. They are graphical tools for drawn-graphical visualization of algorithms to be programmed and executed by computers. Flow diagrams make final programming easier and help one minimize programming errors. Flow diagrams have been developed and used for decades for transformation programs dealt with in Section 4.2. A flow diagram prescribes a sequence of computer operations forced by computer instructions. There are four basic elementary building blocks used in flow diagrams: operational block (Fig. 6.1a), decision block (Fig. 6.1b), start and end block (Fig. 6.1c), and subprogram block (6.1d). The blocks are connected with arrows determining the next operation block. The decision block is equipped with one or more conditions. A continuation of a program depends on the conditions. A cyclic repetition of a same group of operations can be specified by means of a decision block, too. [ABSTRACT FROM AUTHOR]

Finite automata are a classical tool used for many years for DEDS modeling. A finite automaton incorporates both principal system features - system states and system transitions in an abstract form. The basic definition of a finite automaton is given in the sequel. [ABSTRACT FROM AUTHOR]

Consider the basic transition system Equation (1.19) by Manna and Pnueli described in Section 1.5 as a general model of a DEDS. As pointed out earlier, time is not explicitly considered in the model. The DEDS dynamics depends on events that appear in discrete time points. The events provoke changes of the system states. The relations and mutual influence of events and states with respect to control are studied in this chapter. [ABSTRACT FROM AUTHOR]

We will follow the way of reasoning developed in the preceding chapters. Consider an event set Σ ={e1,e2 ,...,en} given for a DEDS. Further consider it to be in an initial state q0. The system behavior can be defined by all possible sequences (strings or words) of events that can occur in it starting from q0. It is assumed that an event occurs in a discrete point of time. Further it is assumed that just one event occurs in one discrete time point. The set of all finite and infinite sequences, which can be created from the elements of Σ including the empty sequence ̃ε , is denoted as Σ*. The set that does not include ̃ε is denoted as Σ+ , i.e., Σ+=Σ*\̃ε where symbol "\" stands for the set subtraction. Usually only a part L of all possible sequences Σ* can occur in a given DEDS. Such a particular behavior of the DEDS is due to a subset L of sequences from Σ* , i.e., L ⊆ Σ*. L is supposed always to include the empty sequence (string, word) and is called a formal language. The formal language L defines the behavior of a DEDS. Our attention is aimed at formal languages with respect to the above-introduced interpretation related to DEDS. A formal definition is useful in order to exactly communicate the idea of a formal language. [ABSTRACT FROM AUTHOR]

The basic transition model and its derivatives can be very easily and transparently represented graphically. A platform for this representation is a mathematical graph. [ABSTRACT FROM AUTHOR]

People observe various phenomena of nature and endeavor to comprehend them. The first step in that is a reflection of the phenomena by imagination and description. The reflexive process is a process of abstraction. In this process, the notion of "system" is of basic importance. A system is defined to be a group of objects separated from the universe and having mutual relations. Different physical entities can constitute system objects. If time is included among the system objects, their temporal properties or the system dynamics can be considered. The system dynamics is given by the time behavior of the system objects. The behavior is called the process. A real physical system is represented by an ideal system created by human thinking and understanding. Mathematical representations of real systems are the most abstract and precise descriptions. Since the very beginning of its existence, mankind strives not only to know and to describe natural systems but also to govern and control them. Control of a system is based on knowledge about the particular system. This knowledge is developed via abstraction based on observation of the system. The observation is realized by measurements and if possible, by experimentation with the system. [ABSTRACT FROM AUTHOR]

Service choreography has become an emerging and promising technology to design and build complex cross-enterprise business applications. Dynamic composition of services on the fly requires mechanisms for ensuring that the component services in the composition are compatible with each other. Current service composition languages provide notations for describing the interactions among component services. However, they focus only on the compatibility at the syntax and semantic level in an informal way, yet ignoring the dynamic behavior within services. This paper emphasizes the importance of the behavior in the compatibility verification between services and utilizes the π-calculus to model the service behavior and the interaction in a formal way. Based on the formalization, it proposes a method based on the operational semantics of the π-calculus to automate the verification of compatibility between two services and presents an algorithm to measure the compatibility degree quantitatively. [ABSTRACT FROM AUTHOR]