This chapter presents a modelling technique for message passing in manufacturing systems. This modelling technique is a hybrid of object oriented paradigm, color timed Petri nets, and IDEF0.
First, the terminology of the object-oriented technique and color timed Petri nets, as used in this thesis, are defined. Next, a graphical representation based on object-oriented technique and color timed Petri nets is introduced. Finally, the integration of these modelling techniques is developed.
Currently, a variety of terminology for both object oriented techniques and Petri nets can be found in the literature [Rumbaugh et al 1991] [Coad and Yourdon 1991] [BOOCH 1991] [Snyder 1991] [OMG 1991] [Coad and Yourdon 1990]. This section defines the terminology for both the object-oriented concept and Petri nets that is used in this thesis.
The terms which apply to the object-oriented approach, as used in this thesis, are given below. These terms include both object semantics commonly used in the object-oriented paradigm and those specifically developed for the object-oriented connection model.
In order to faithfully represent the elements of a manufacturing cell in a model such that the message passing capability can be analyzed, it is necessary to find a way to represent the components of the manufacturing system. Depending on the level of detail required, or desired, the component may be a a machine tool, or just its controller, or just the communication part of the controller. Further, since each component may provide or request either information or service, i.e., some function such as "is switch A on", or "remove 0.1 inch of material", or both, it is necessary to find ways to represent these basic functions and to differentiate between when a component is a requestor of service and when it is a provider of service. In order to discuss these matters precisely the following definitions will be employed.
An object is a meaningful abstraction of an element of the manufacturing system; for example, a machine tool controller may be represented as an object. A set of objects which have common structure and a common behavior may form a class. For example, there may be similar machine tools in a manufacturing system. Each may be defined by comparing its structure and behavior with establish templates. If no match exists, a new template may be established. A cluster of objects which have same structure and behavior forms a class. An object is simply an instance of a class.
Each object has at least two features, the service(s) it can provide and the information it needs, contains, or supplies. An object requests services from another object by issuing a "request". An object which issues a request is called a client object. An object which receives a request from other objects is called a server object. These roles are dynamic, depending upon the system state. An object may be in either client or a server role, but not both, for each system state.
In order for it to perform the service, a client object may need to provide some information to the server object. A request which contains some information from the client object is called a "request with data". A request may simply want a service performed by the server object. This type of request is called a "request without data" and is sometimes called a "trigger" in the control of manufacturing systems.
A request may require a "reply" of the server object. A reply contains the answer to a request. A reply may be just the indication of a service completed. This type of reply will be called a "reply without data" and is sometimes known as an "acknowledgment" in the control of manufacturing systems. Alternatively, a reply may contain some information from the server object and will be called a "reply with data". Thus, the interactions between objects will be in the form of "request" and "request-reply". An interaction in the form of "request-reply" pairs will be called a "communication". A communication between one object and another object will be called "communication between objects" in later chapter. A communication is always initiated by a client, never by a server.
A request or a reply between a client object and a server object is called a message in this research. Therefore, message may refer to either a request or a reply. A message which passes from a client object to a server object represents a request for a service to be performed in the server object.
How the service is performed by the server object is called a method. A server object will invoke a method in response to the message it receives. In performing its service an object may access or modify its data and/or may in turn require services from other objects. There maybe more than one method that a server object can use to perform its service. The collection of methods in an object is called the behavior of this object.
More precise definitions for the terms, as used in this thesis, are listed below.
More precise definition of objects from the message passing perspective are given below. An object, o, is a 6-tuple, <MI, M, MO, SM, RM), where
Graphic symbols for representing an object and its corresponding types of requests are presented in this section. These graphic symbols will be used to construct a graphical model which will be described in a later chapter.
A basic Petri net is composed of: a) a set of places, a place is normally drawn as a circle, b) a set of transition, a transition is normally drawn as a box, c) arcs between places and transitions, and d) tokens.
An arc represents an input or output relationship between a place and a transition. A place which is connected to a transition is called a pre-place of that transition. A place which is connected from a transition is called a post-place of that transition. The representation of places, transitions and their connections represent the static structure of a basic Petri net.
A token normally drawn as a solid dot may reside in a place. The token(s) will be assigned to a place(s) in a basic petri net to represent the initial condition (or status) of this net at the beginning.
The dynamic operation of a basic Petri net is portrayed simply by the moving of tokens among places by an enable rule and a firing rule. Enable Rule: A transition is enabled if every pre-place of the transition has a token. Firing Rule: A transition is fired as soon as it is enabled. The firing action is represented by removing a token from every pre-place of the transition and by depositing a token to every post-place of the transition.
In this section, a color timed Petri net will be developed to model the behavior of objects. This color timed Petri nets integrates the time associated with transitions and color associated with tokens in basic Petri nets.
In basic Petri nets, a token is used to mark a place. One token is not distinguishable from another. The only significance of a token is its existence. In message passing, it is possible to use tokens interchangeably in a basic Petri net. It is also possible to use tokens to depict message flows. A token that is used to indicate message location must be differentiable from a token that is used to mark a place. Further, a token that is used to indicate the location of one message should be differentiable from another token representing another message. In advanced Petri nets, this is done by assigning different colors to different tokens. The same token color will be assigned to the same types of message. In order to indicate the types of tokens that are allowed to flow through from a place to a transition or from a transition to a place, a label is associated with each arc.
The use of color tokens alters the complexity of enableness conditions and firing rules. The pre-places and the tokens in these places together determine the pre-condition and enableness condition of a transition. A place may have more than one type of color tokens residing in it at different times. A transition expression is used to specify one firing operation in a transition. It determines which token is to be removed from every pre-place of the transition and which token is to be deposited to every post-place of the transition when the transition is fired. The collection of possible transition expressions for a transition will be called the transition firing operations. In order to avoid anomalies, each pre-condition of a transition expressions in a transition must be unique.
The transition expression can be used to represent different operations such as, transfer a token from one place to another, or convert a token to another token, or combine tokens into another token, or split a token into several tokens. When two tokens are combined to form a third, that 3rd token can be thought of as containing the two original tokens. A token which contains no other tokens is called a primitive token. A token which contains more than one token is called a container token. A container token can contain other container token(s) and/or primitive token(s). If the number of primitive tokens before a transition remains the same as the number of tokens after the transition, the transition is said to be token conservative. Token conservation is an important property of a transition.
In order to study time issues, it is necessary to represent time delays in Petri nets. Normally, a transition represents an action which requires time to complete. Therefore, a time delay function, D(t), is assigned to each transition in this thesis. D(t) can be a constant time or a stochastic time duration bounded by its minimum and maximum values. While D(t) is in the form of a duration, a transition may be fired anywhere between boundary values.
Basic Petri nets do not take time into consideration. Petri nets which associate a deterministic time with a transition are called "timed" Petri nets. Petri nets which do account for time duration are called "time" Petri nets. In this thesis, we need to differentiate tokens and need to account for time durations and therefore we need to use "color time Petri nets". However, in this research, we are only interested in the firing of a transition either at the minimum or at the maximum value of time duration. The two cases can be treated separately by two color timed Petri nets. Therefore, it is only necessary to define firing conditions for color timed Petri nets.
In the color timed Petri nets, a transition can be fired if the enable condition is still held after the time specified in the transition time function. The enable condition and firing of the color timed Petri nets will be defined.
More precise definitions of the color timed Petri net are given below. First, the notations and definitions used with color timed Petri nets are described. Next, the color timed Petri net graphic representation is given.
Notations used for the color timed Petri net are listed below.
A color timed Petri net, CTPN, is a 9-tuple, CTPN = (P,T, C, L, I-, I+, D, O, R) where:
The graphical symbols to represent the elements of the color timed Petri net are shown in Fig. 11.
The properties for basic Petri net have been well defined and accepted in the literature. However, in advanced Petri nets, the properties are defined for the convenience of the specific application domain. This is also the case in this research. In this section, the properties associated with basic Petri nets will be given first. Then, the definitions germane to message passing will be provided.
In a basic Petri net, a marking is defined as the pattern of token placements for a given state. Different marking patterns characterize different states of a net. In a Petri net with n places, a marking m is an n-vector, m = (m1, m2, ..., mn), where n=|P| and mi &OE; N, i = 1, ..., n, defines the number of tokens in each place [Peterson 1981]. Each element in the marking m(pi) represents the number of tokens in the place pi of the marking m and is called a marking element. Based on the definition of marking, boundedness and safeness and liveness will be defined.
A place is said to be k-bounded if the number of tokens in that place can not exceed an integer k. A basic Petri net is said to be k-bounded if every place of the net is k-bounded. Safeness is a special case of the boundedness property for k = 1. Boundedness can be used to check if a system has a finite number of states and to capture the capacity limitations of resources modeled as places.
The liveness property is defined based on the change of markings due to transitions. Assume m1 is the current marking and m2 is the marking after a transition tj is fired. In this case, m2 is said to be immediately reachable from m1. A reachable set R(C, m) of a basic Petri net C with marking m is defined as a set of all markings which are reachable from m. A transition tj of a basic Petri net C is potentially firable in a marking m if there exists a marking m' &OE; R(C, m) and tj is enabled in m'. A transition is live in a marking m if it is potentially firable in every marking in R(C, m). In CTPN, tokens are classified into colors to model different messages and system status. A transition tj is fired after a time delay. The above definitions of markings and liveness for the basic Petri net may not be suitable to define the properties of a color timed Petri net. Also, another dimension on boundedness with respect to the colors of tokens in a place may also be of interest and will be defined as color boundedness. In a color timed Petri net, a marking represents token assignment both in terms of numbers and colors in each place. Each element in the marking m(pi) in a CTPN defines the number of tokens for each color of tokens. A special case is when there is only one token in a place at any time. In this case, the representation of a marking element m(pi) may be reduced to be color of the token c. As it will be seen in the next chapter, the design of the CTPN for an object is safe in terms of number of tokens. Therefore, a marking definition which is useful to this thesis will be defined.
For a transition to be firable, the token type in pre-places must conform to some pre-condition of the transitions. Therefore, we introduce a new definition color-boundedness for CTPN. In essence, a place is said to be k-color-bounded with respect to a set of k token colors if that place can only be marked with tokens belonging to that token color set. A place in a color timed Petri net is said to be color-safe with respect to one specific token color if the place can only be marked by that type or color token. A reachable set R(CTPN, m) of a color timed Petri net CTPN with marking m is a collection of all markings which are reachable from the marking m. A transition tj of a color timed Petri net CTPN is potentially firable in a marking m if there exists a marking m' &OE; R(CTPN, m) and tj if enabled in m'. A transition is live in a marking m if it is potentially firable in every marking in (CTPN, m).
More precise definitions and assumptions are listed below.
This section will describe the integration of the object oriented technique and the color timed petri nets. In order to be more specific to the unified modelling technique, the general definitions of the previous section are further divided into sub-categories.
First, graphical representation of types of message will be described. Second, in order to keep consistent with the color timed Petri net representation, messages are transformed into a token representation. The transformation procedure is defined. Finally, a detailed communication representation between two objects is presented.
An object sends a message to another object to request a service. A request can be either synchronous or asynchronous. If a request is synchronous, the client object has to wait for the reply. On the other hand, if the request is asynchronous, the client object can continue its service without waiting for the reply even if a reply is required. The reply will be considered as another request from the server object to the client object. In order to represent the interaction patterns clearly, it is desirable to have a way to explicitly and graphically represent the "request-reply" pair. A "request-reply" pair may result in some time delay.
Based on the explanations in section 3.1.1, interactions between two objects may fall into following combinations: "request only" and "request-reply". Taking the type of request into consideration, "request only" can be further classified into: "request with data" and "request without data". The "request without data" can be used to model actions, triggers, and events [Champeaux 1991] [Wirfs-Brock 90] . Similarly, a reply can be further classified into: "reply with data" and "reply without data". A "reply without data" can be used to model an acknowledgment. In summary, the interactions between two objects may fall into one of the six possible combinations: "request without data", "request with data", "request without data/reply without data". "request without data/reply with data", "request with data/reply without data", and "request with data/reply with data". Since a message can represent a request or a reply, a combination of request and reply can be represented by two messages with opposite directions. In the following, a graphic representation for each of the six combinations will be described and will be called an "object connection".
In Fig. 10 of section 3.1.2, the arrow heads convey the request direction only. In order to differentiate request/reply combinations, different arrow representations are defined, as shown in Fig. 12. A request/reply is represented by a line with two arrow heads which connects the two objects. Note that in the definition of object box, a request always leaves from the right-hand side of a client object. The solid arrow head represents the "with data" situation. A line with one arrow means an asynchronous request, a request without reply. Since arrows are single directional to/from opposite sides of the object box, the request and reply will not cause confusion.
In Petri net modelling, message passing and state changes are represented by the movement of tokens. In object oriented modeling, an event occurs due to message passing among objects. In order to be consistent with Petri net conventions, tokens will be used to represent messages passing between objects. A message can be represented by an action token alone or by an action token with one or more data token(s). The message of a reply can also be represented by a confirmation token or data token(s). More precise definitions of action token and data token are given below.
Object connections depict message relationships between objects. However, an object is represented internally by a Petri net. A request enters the Petri net through one place and a reply exits the Petri net from another place. In order to associate a request and a reply with places explicitly, an object connection with two arrow heads must be split into two one way arrows, each of which will be referred to as a link. For example, a request without reply is represented by a link between these two objects. The link from a client object to a server object will be called a request link. When a reply is required, another link is used between these two objects. The link from a server object to a client object will be called a reply link. In other words, a request/reply is comprised of two links: a request link and a reply link. If there are more than one token on the link, the tokens are treated as a container token in color timed Petri net. A link is more precisely defined as follows.
A request without data which requires reply with data from a server object, shown and explained in section 3.2.1, can be represented by two links, shown in Fig. 13. The token on a request link will enter a place in the server object from a place in the client object. Conversely, a token on a reply link will leave from a place in the server object and enter a place in the client object. The four circles in Fig. 13 are used to represent four different places.
A request is sent by a method in a client object. A corresponding method in a server object will provide service to this request. When a reply is required, it leaves the method in a server object and enters the method in the client object. In a more detailed level, the links and their associated places defined in the previous section clearly define the interactions between method and message.
The graphic representation of this method/places is shown in Fig. 9. Links which enter the object from the left-hand side may be request links and/or reply links from other objects. For example, a request link and a reply link are connected to the method 2 from the left-hand side of the object box. Therefore, a request/reply pair will be separated in different sides of the object. The message reachability analysis in Chapter VI will be developed based on this object view.
The object definition from the message passing perspective is given below. An object is a 6-tuple, (LN-, RI, PI, M, LN+, P, SP, RP), where
Occasionally, it is necessary to combine Petri net representations of objects into a large net. In that case, a link may be represented as a transition and two directed arcs. For example, a link which connects two objects, o1 and o2, with token set, l, is represented as <o1, l, o2>. The label associated with each arc is l. The transition time is 0. The representation of a link in color timed Petri nets is shown in Fig. 15. Place, p1, is an output place of an object, o1. Place, p2, is an input place of another object, o2. The time delay, d, associated with transition t is 0.
