Division of Research School of Business Administration March 1988 Revised, October 1989 DYNAMIC ANALYSIS OF REPETITIVE DECISION-FREE DISCRETE EVENT PROCESSES: THE ALGEBRA OF TIMED MARKED GRAPHS AND ALGORITHMIC ISSUES Working Paper #542-b Didier Dubois Universite Paul Sabatier Kathryn E. Stecke The University of Michigan The University of Michigan School of Business Administration Ann Arbor Michigan 48109

ABSTRACT A model to analyze certain classes of discrete event dynamic systems is presented. Previous research on timed marked graphs is reviewed and extended. This model is useful to analyze asynchronous and repetitive production processes. In particular, applications to certain classes of flexible manufacturing systems are provided in a companion paper. Here, an algebraic representation of timed marked graphs in terms of recurrence equations is provided. These equations are linear in a nonconventional algebra that is described here. Also, an algorithm to properly characterize the periodic behavior of repetitive production processes is described here. This model extends the concepts from PERT/CPM analysis to repetitive production processes.

i

1. INTRODUCTION Manufacturing automation applications are increasing in industry because of the new abilities to manufacture in low and medium volumes efficiently. The increase in the number of operating options with automation increases the complexity of system planning. These facts have motivated recent research dealing with the modeling, design, performance evaluation, simulation, planning, and control of flexible manufacturing systems. Many models have been suggested to help describe the behavior of these systems under various points of view and levels of detail and different sets of assumptions. Many of these models are reviewed in Bel and Dubois [1985] and Buzacott and Yao [1986]. This work concerns one of these models, one that views a manufacturing system as a deterministic, discrete-event, dynamic system (DEDS) that repetitively performs a set of tasks (or activities). This type of model has been introduced by Cunninghame-Green [1962, 1979] and also studied by Cohen et al. [1985a, 1985b, 1986]. An algebraic framework for this model exists in the theory of dioids (Gondran [1979] and Gondran and Minoux [1979]). These provide a linear formulation, similar to that of linear systems in control theory, under a state space approach. As a consequence, the behavior analysis of deterministic DEDS can be achieved by solving an eigenvalue problem. This class of systems turns out to be identical to a special class of timed Petri nets (Peterson [1981], Chretienne [1983], and Ajmone Marsan [1986]), called event graphs. Applications to automated manufacturing have been described in Dubois and Stecke [1983, 1989] and Cohen et al. [1985a]. This paper is a survey of the modeling, algorithmic, and theoretical issues associated with timed marked graphs. A companion paper (Dubois and Stecke [1989]) addresses some solution issues and provides applications of this model to some problems of certain classes of flexible manufacturing systems that exhibit periodic behavior. The plan of the paper is as follows. ~2 begins by reviewing definitions and concepts associated with timed marked graphs and timed Petri nets. We specify convenient

-2 - modeling conventions for timed marked graphs in ~2.2. ~2.3 reviews the concept of reachability and illustrates some issues with an example. The algebraic representation of timed marked graphs in terms of recurrence equations is provided in ~3. 1. These equations are linear in a particular algebra, where "maximum" represents "addition" and "addition" represents "product". This (max,+) algebra has been termed a path algebra (Carre [1971]) in the graph-theoretic literature. Various representation issues are also addressed in ~3, such as outside influences on the performance of repetitive systems represented by timed marked graphs. A convenient choice of state variables provides an efficient representation of the recurrence equations. There are two modes of system evolution. The earliest starting times of activities based on an initial system state can be determined (Primal Mode). Alternatively, the latest starting times of activities based on system final states, such as due dates, can be determined (Dual Mode). These are extensions of PERT/CPM ideas to repetitive production environments. These repetitive systems eventually reach steady state with periodic behavior in either mode (Cohen et al. [1985a]). The steady state is characterized by solving the recurrence equations in ~4. Some material concerning the periodicity of the system from Cohen et al. [1985a] is reviewed. This allows the Primal Mode to be characterized. Other previous results (CunninghameGreene [1976]) are used to characterize the Dual Mode. With these results, useful parameters such as dynamic analogues to slack times and critical paths of PERT/CPM are calculated. These marked graphs also model the evolution of limited nonconsumable resource usage. This algebraic analysis allows computation of critical resources, whose shortage limits potential system performance. Finally, ~5 addresses algorithmic issues in solving (max,+) equations. We show that the computation of eigenvalues and critical circuits consists of shortest path calculations. There is a low order of computational complexity. The eigenvalue is important to characterize the period of the system, i.e., the smallest time horizon such that the initial state is identical to the final state. Having characterized the behavior of the system over

-3 - such a time horizon by calculating earliest and latest starting times for all activities, many performance evaluation measures can be easily obtained. ~5.2 provides tools to quantify the influence of the number of resources (tokens in the marked graph) on the length of the period. ~6 indicates some research needs. 2. TIMED MARKED GRAPHS A timed marked graph can be translated into a system of linear equations in the sense of an algebra where the maximum and addition operations, respectively, represent addition and product operations, respectively, in the usual linear algebra. The approach builds on previous work (Cohen et al. [1985a, 1985b, 1986]) in the modeling and analysis of discrete-event systems in the field of manufacturing. It improves and extends earlier attempts by Ramchandani [1974] and Ramamoorthy and Ho [1980] by providing a systematic treatment of timed marked graphs. 2.1 A Refresher on Marked Graphs A marked graph is a directed graph G where some arcs are assigned a number of tokens. It is a special type of Petri net (Peterson [1981]), where each place has exactly one input and one output transition. Places in such Petri nets correspond to arcs of the marked graphs, while transitions correspond to vertices. In the following, we use the terms vertex or transition interchangably, as well as the terms place and arc. The firing of a vertex is enabled as soon as each input arc (place) of this vertex contains at least one token. Vertices without an input arc are enabled unconditionally. The firing consists of removing one token from each input arc and adding one token to each output arc of the vertex. The system evolves over time in this manner. The vector M = (r l,...,r) (where ra, a = 1,...,p, is the number of tokens on arc number a) is called a marking. Firing transitions when enabled produces sequences of markings. Marked graphs are useful to describe the behavior of concurrent, asynchronous, deterministic processes, such as computer configurations (Diaz [1982], Ajmone Marsan et

-4 - al. [1984], and Smigelski et al. [1985]), parallel computations (Reiter [1968]), and distributed algorithms (Peterson [1981]). Marked graphs do capture concurrency phenomena but are decision-free: decisions on how the system should evolve have been made in advance. The consequences of these decisions can then be evaluated. Let V be the set of vertices and A be the set of arcs. When an enabled vertex i fires, the marking M evolves into M' such that r' = r + 1, if a refers to (ij) for some j; r' = ra - 1, if a refers to (j,i) for some j; ra = ra' otherwise, where (i,j) is the arc from vertex i to vertex j, if it exists. M' is said to be immediately reachable from M by i. More generally, a marking M' is said to be reachable from M if there is a sequence of firings at vertices i,...,in and a sequence of markings Mo = M, M,...,M n1 Mn = M', such that Mjl is immediately reachable from M. by ij. The set of reachable markings from Mo is denoted R(G,Mo) and includes Mo. A marked graph is safe if VMsR(G,Mo) and VaeA, then ra < 1; if this condition is relaxed to allow ra < ba, where (b laE A) is a set of finite upper bounds on the number of tokens on each arc a, the marked graph is said to be bounded. A marked graph is live for a marking Mo if VieV, there exists MeR(G,Mo), such that M enables vertex i. Any vertex satisfying this condition is called a live vertex. A chain in G is a sequence of adjacent vertices. A path in G is a chain, il,.,in, where (i, i+l) e A, Vj = l,...,n-1. When i1 = in, it is a circuit. When all i are different except for i1 = in, the chain is called a simple circuit. G is said to be connected if there is a chain between any two vertices and strongly connected if there is a path between any two vertices. A graph containing no circuit is called acyclic. The following results are known for marked graphs that are strongly connected: 1. The number of tokens on a circuit does not change after a vertex fires.

-5 - 2. Liveness is equivalent to the existence of at least one token on every circuit. 3. Safeness holds if and only if each place belongs to a circuit containing only one token. 4. M is reachable from M' if and only if the number of tokens on the circuits is the same for M and M'. 2.2 Modeling Conventions for Timed Marked Graphs Marked graphs can capture the time dimension by assigning durations to arcs and/or vertices and are then more useful to model a class of discrete-event dynamic systems. These systems are described by a set of activities, each of which requires a set of resources in order to be performed. Any resource that is engaged in some activity cannot be simultaneously used for another. In a manufacturing environment for example, activities include the processing operations of parts on machines as well as transportation, storage, and machine set-up activities. Resources can be parts, pallets, carts, robots, machines, cutting tools, and the like. Each activity requires a certain amount of time during which some of the resources are captured. A decision-free, discrete-event system is one that: (i) for each resource, the set of activities in which it is involved is linearly ordered, so that when this resource is liberated by some activity, it is known which activity captures it next; (ii) for each activity, the set of resources it captures is also ordered, so that resources do not compete. In terms of Petri nets (i.e., see Peterson [1981]), activities can be viewed as transitions. The input places of each transition at times contain tokens, which model resources that are required to start the activity. Condition (i) specifies that no place is an input to more than one transition. Condition (ii) means that no place is an output place of more than one transition. Hence we have the structure of a marked graph. Note that condition (i) specifies a deterministic system after some chosen systematic rule (such as first-come, first-served) has been used to solve the conflicts between resources. Condition (ii) is also necessary to obtain the useful structure of a marked graph.

-6 - Conventions to assign durations to the activities of marked graphs are not unique. The marked graph representation of a system having the least number of vertices is obtained by the following technique: *Vertices represent activities that involve more than one resource. The duration, O., of activity i is assigned to the vertex. *Activities requiring only one resource are modeled by arcs which connect to other activities requiring more resources. The durations, t.., of single-resource activities are assigned to the corresponding arcs, (i,j). FoPother arcs, ti = 0. Our firing conventions are described as follows. *A token that arrives on some arc (ij) is available only at time t.. after the arrival date. J *A vertex i is fired as soon as it is enabled (i.e., it has one available token on each input arc), and becomes active during 0. after the firing starts; after a duration of i., the token move takes place. ~An active vertex can be fired again as soon as another set of available tokens appears on each of the input arcs. This convention prevents vertices from being considered as a special kind of resource. The third convention implies that a vertex can be fixed, while still active, by the arrival of new tokens. It is possible to construct graphs having time only on vertices. To see this, every timed arc can be transformed into a one input arc/one output arc vertex, and then the time is specified on the vertex. (In the terminology of PERT/CPM, this is analogous to the "activity-on-node" representation.) Similarly, it is possible to specify time only on arcs. To do this, set every 0i to zero and every tij to tij + 0ij. In this case, vertices model events (which are starting points of activities) and we have an "activity-on-arc" type of representation. For modeling purposes, the latter convention has the drawback of confusing resource-sharing activities and the simpler activities that might follow them. It is clearer to separate them. On the other hand, the activity-on-arc convention is more straightforward and efficient for further computation with the model.

-7 - 2.3 Reachability in Timed Marked Graphs Let G be a timed marked graph. When G is acyclic, then the dynamic analysis of G reduces to the critical path method. Given the earliest starting times on the activities without predecessors, earliest ending times on the activities without successors are calculated. Considering the latest of these ending times as a due date, latest starting times on other activities are thus obtained. Activities with no slack time are called critical and cannot be delayed. Critical paths of activities are thus obtained, and tokens on these paths are critical resources. The more interesting types of systems are those in which graph G contains circuits. Then some activities are performed repetitively. A systematic study of these types of decision-free, discrete-event systems is not readily available to date, although some authors have obtained some insight into such problems (see, e.g., Ramchandani [1974] and Ramamoorthy and Ho [1980]). Timed Petri nets have been studied in some detail (e.g., Chretienne [1983]). Note that the concept of reachability of markings is not adequate to specify a timed marked graph. Indeed, the reachability set R(G,Mo) consists of all possible markings that can potentially be reached from Mo, regardless of activity durations. From the previous Section, starting with a bounded initial marking Mo on a strongly connected graph G, it is clear that R(G,Mo) is finite. When several vertices, i, j, k,..., are enabled under marking Mo, then there is no information about which vertex should fire first, and all markings Mi, M, Mk,..., obtained by firing vertices i, j, k,..., are calculated and put into R(G,M ). With a timed marked graph, the vertices enabled by Mo are ordered by their firing dates, which depend upon the availability dates of tokens on input arcs. As a consequence, it is necessary to distinguish between R(G,Mo) and the set of markings which will eventually be obtained from M. o

-8 - Let T = (0., ieV) U (t i, (i,j) EA). Denote by R(G, T, Mo), the set of eventually reached markings from Mo, i.e., markings that are actually obtained at some point in time, given the graph structure G and the time allocation T. Clearly, V set T, R(G, M ) v R(G, T, M ). However, the inclusion may be strict, as the following example shows. EXAMPLE 1 In Figure 1, crosses are vertices, arrows are arcs, and dots on arrows are tokens. 2 I X X3 Figure 1. M = (1, 1, 0, 1, 0). The arcs are numbered lexicographically, i.e., if arc a = (ij) and a' = (i',j'), then a < a' means that either i < i' or i = i' and j < j'. Then from Figure 1, the initial marking is: Mo = (1,1,0,1,0). The set R(G,Mo) is pictured as Figure 2. The times that are associated withes the arcs are always positive. Arrows contain the names (numbers) of the vertices that are firing over time.

-9 - (0,1,1,2,0) = M2 (1,0,0,0,1) = M3 1 3 2 (0,0,1,1,1) = M23 Figure 2. R(G,Mo). Let tl2 > t13 > 0 and tij = 0, otherwise. In the initial state Mo, the tokens are allocated at time t = 0 and are not available yet. Then the sequence of firing vertices is 3, 2, 1, 3, 2, 1,..., i.e., R(G, T, Mo) = (Mo, M3, M23). If t12 < t13, then this firing sequence would be 2, 3, 1, 2, 3, 1,... and R(G, T', M ) = {Mo, M2, M23), where T' is the set of new time allocations. U Assume now that G is strongly connected and that R(G,Mo) is a directed graph whose nodes are markings and arcs express immediate reachability. Moreover, when G is live for Mo and Mo is bounded, this reachability graph contains circuits. R(G, T, Mo) is one path in R(G, M ). It contains a circuit if G is live for Mo, since the number of possible markings is finite and the system evolves forever. Indeed, the liveness of G for Mo prevents any blocking from occuring. However, R(G, Mo) contains enough markings so that for any T, and any set of live markings Mo, all vertices in G eventually fire: Proposition 1: If G is strongly connected and live for a bounded marking M, then VT and ViYV, there exists a marking MieR(G, T, M ) such that Mi fires i.

-10 - Proof: If vertex i never fires, then no token on any arc (j,i) shall ever cross i. Hence no vertex k such that (i,k) is an arc is eventually enabled. That is, no vertex in V is eventually enabled. Hence the immediate reachability relation of R(G, T, Mo) makes it a path with no circuit. Hence Mo is not live, which contradicts the assumption. U Note that strong connectedness is required to insure that all vertices in V are eventually enabled. In ~3, graphs G are considered in which every vertex has at least one input and one output arc. Graphs that contain vertices without input arcs (sources) are examined in ~3.3, as well as graphs having vertices with no output arcs (sinks). 3. ALGEBRAIC REPRESENTATION Given an initial marking Mo and a set of availability dates for tokens, it is easy to simulate the behavior of a decision-free, discrete-event system (viewed as a marked graph), by firing the vertices at the proper points in time. We now indicate how to represent this evolution algebraically. 3.1 Deriving Recurrence Equations Let xi(n) be the earliest firing date of transition i for the nth time. Let ak, P k = 1,...,R, where R = ~ ra, be the availability date of each token in the initial marking Mo. Let Mo be a live marking. Without loss of generality, we can assume that 0i = 0, Vi~V (by adopting the activity-on-arc convention). Let r-(i) = {j I (j,i) e A} be the set of predecessors of vertex i. Then the following inequality holds: xi(n) > xj(n-rji) + ti, n > r.. and for j E F-(i). - ii J i ii (1)

-11 - There are r.. tokens on arc (j,i). But transition i's firing for the nth time is ji conditioned only by the first availability of the nth token. This token corresponds to firing transition j for exactly (n - rji) times. Values xj(0, 1= l,...,rij are calculated from the knowledge of the availability dates of the r.i tokens in the initial marking M. The initial marking is used as a landmark for numbering the transition firings. From equation (1) for all transitions and noticing that no other constraint impacts the value of xi(n), we obtain the following result: Proposition 2: Vi e V, x(n)= max x.(n-r.) + t. (2) jeIP(i) J Ji J' We adopt the following notational conventions: *X(n) = (x1(n),...,XiVl(n)) is the vector of nth earliest firing dates of vertices. *Let @ and * be scalar operations, such that a b b = max {a,b) and a * b = a + b, Va,b e R. *o and * can be extended to square matrices A and B as: (A@B)i = max{A.., B..} and (A*B)ij = maxtAik + Bkj, where Aij is the (i,j)th entry of A. J We write AB instead of A*B. It is easy to see that the following are true: *o equips IR with a commutative semi-group structure; o* is an idempotent operation (a(Da=a); *the identity is -oo, denoted by e; **is distributive over @: [a*(bDc) = (a*b) S (a*c)]; *the identity of the commutative group (IR,*) is denoted e(=O); *e is an absorbing element for * [e*a==,Va]. (IR, 5, *) is an algebraic structure known as a dioid (Gondran [1979]). Note that most of these properties (except for the commutativity property of *) catrry over to the set of

-12 - real square matrices. The identity of * is then E, such that E.j = e, if i ~ j and Eii = e, Vi. The absorbing element is 0, such that 0. = E, V i and j. Let us introduce a sequence, F0, F1,...,FA, of IVI x IVI matrices defined by: tij, if there exists an arc (i,j) e A such that rij = r; (Fr)ij < ~j otherwise. With these conventions, equation (2) can be written as (Cohen et al. [1986]): X(n) = X(n)F0 S X(n-l)F1 D...D X(n-A)FA, Vn > A. (3) The vectors X(l),...,X(A) are easily calculated from the availability date of tokens in the initial marking. Some comments are needed to discuss this representation: i) A is the largest number of tokens initially on any arc. ii) The earliest firing date of a transition i for the first time is conditioned by the availability date of the tokens on arcs (j,i), i.e., xi(l) > ak for token k on arc (j,i) in the initial marking. iii) The decision to use the vertex firing dates as the state variables is justified by the fact that, in general, the number of vertices is smaller than the number of arcs. iv) The x.(n), i ~ V, n = 1,...A are generally not independent, so that equation (3) does not provide a minimal representation. 3.2 Evolution of the System In order to be able to simulate the evolution of the system over time, it is necessary to express X(n) in terms of X(n') for n' < n. That is, we need to solve equation (3) with the X(n) as unknowns and viewing (3) under the form X(n) = X(n)FO SD M. To do this, we introduce the directed graph G(A) associated with a square matrix A. The graph is defined by: *V(A) = the set of rows of A;

-13 - *A(A) = {(ij)lAij > e}; *A.. = the weight on arc (ij). Moreover, the weight of a path is the sum (in the usual sense, i.e., the "product" in the algebra) of the weights on the path's arcs. The length of the path is the number of its arcs. The following result is known (Gondran and Minoux [1979]): Proposition 3: Equation X = XA @ B has a solution if and only if no circuit of G(A) has a weight greater than e = 0. Then the unique solution is: X = BA*, where A* = E E A @ A2 S...@O An..., and A2 = AA, A3 = AAA,... The matrix A* may be generated by repeatedly squaring ESA until (after a finite number of squarings) convergence is observed. Other, more efficient methods exist (Carre [1971]). A* may also be generated by substituting XA@B for X infinitely many times into the right hand side of equation (3). In our context, the entries A.. are positive, since they are the durations associated with activities. Circuits in G(A) have positive weights, if any. In this case, the existence condition in Proposition 2 reduces to the nonexistence of circuits in G(A) (except for 0-weight ones). Moreover, only a finite number of computations is required to obtain A*, since A* can be obtained by any longest path algorithm, e.g., Floyd's algorithm [1962]. More precisely, it is enough to compute (An I n < I V(A) I), where IV(A)I is the number of rows in A. Now equation (3) can be written as: X(n) = X(n-l)F1(FO)* @...E X(n-A)FA(FO)*, (4) provided that G(FO) contains no circuit except 0-weight circuits. This can be seen once it is noticed that G(FO) is a subgraph of G obtained by deleting all arcs (ij) with rij > O0. Hence equation (4) holds, for example, when G is strongly connected and the'initial marking M0

-14 - is live. Then every circuit in G contains at least one token and every circuit is broken in G(FO). In general, G can be decomposed into strongly connected components. To do this, consider the equivalence relation C on V = iCj <==> there is a circuit containing i and j; the strongly connected components are the equivalence classes of C. They form a partial ordering and can include isolated vertices. Now equation (4) holds when the initial marking restricted to each strongly connected component is live for this strongly connected component, that is, when it is not an isolated node. Note that when G is strongly connected and ML is not live, there is something wrong in the system and it cannot be feasible. Indeed, there is a circuit y that does not contain a token. Because the number of tokens on each circuit always remains the same as the marking evolves, then no vertex on circuit y will ever be enabled, even if this circuit has 0-weight. Hence we must rule out the latter case, even though (F0)* still exists. 3.3 Communication Outside the System So far, only isolated marked graphs have been described. However, it is possible to also consider the case when some tokens are supplied from outside, and dually, when some tokens are released from within the system. Let U be the set of vertices without predecessors, which then act as token-sources. Let Y be the set of vertices without successors, which can act as token-sinks. Let ui(n) be the firing date of vertex i e U for the nth time. Let B be the IUI X IVI matrix describing the link between input vertices and interior vertices: ie, if arc (i,j) exists; B.. = J ~, otherwise. Then equation (3) now becomes:

-15 - A X(n)= X X(n-l)F. U(n)B, (5) j=O J where U(n) is the vector (ul(n), u2(n),...,ulU(n)). More generally, if there are tokens in the input arcs (i.e., (i,j) with i E U), equation (5) becomes (Cohen et al. [1986]): A k X(n) = I X(n-j)F. @ U(n-k)Bk, j=O J k=O where Bk pertains to input arcs containing k tokens in the initial marking, i.e., (Bk)ij = e, if (ij) exists and r.. = k; and = e, otherwise. Similarly, yi(n) denotes the firing date of vertex i e Y for the nth time. C is the IVI X IYI matrix expressing the links between V and Y, i.e., Cij = e, if (ij) exists and = e, otherwise. Then introducing Y(n) = (y (n), y2(n),...;yly(n)), the output map of the system is described by Y(n) = X(n)C, or more generally, L X(n)=, X(n-t)Cf, 6=0 e, if i=j and rij = C; cpij = d e, otherwise. The set U can be viewed as a set of control vertices and Y as a set of observation vertices. A timed, marked graph can be defined as controllable, if each transition of V can be sent tokens by some input i ~ U. More formally, for any j ~ V, there is an i ~ U such that a path exists from i to j. Otherwise, if no path exists from any i e U to some j ~ V and tokens only come from inputs, then vertex j is not live. Dually, a timed, marked graph is observable, if for any i e V, there is an output vertex j E Y such that a path exists from i to j. If there is some i e V that is linked to no j E Y by a path, the tokens in the input places of i are trapped in the system.

-16 - We note that controllability (or observability) can be equivalently defined by the existence of a path from some input (or each strongly connected component) to each strongly connected component (or some output) of G. One example of a controllable and observable marked graph is a graph that consists of sources, interior vertices, and sinks and is an acyclic graph. Another example is a graph G consisting of interior vertices that is strongly connected. Otherwise, the marked graph may fail to satisfy the controllability and observability properties. 3.4 The Choice of a State Space In order to be able to solve the recurrent equations, one possibility is to transform equation (4) into a first order system. To achieve this, the most straightforward technique is to increase the size of the state vector X(n), i.e., let X(n-l) = (X(n-l), X(n-2),..., X(n-A)). Then equation (4) becomes: X(n) = X(n-l)H, (6) where (%)* \ H ~ * E The problem with equation (6) is that the vector x is too large. However, many of its components are dependent. It would be interesting and useful to reduce the number of variables necessary to describe the behavior of the timed marked graph..

-17 - Assume G is strongly connected and that the initial marking Mo is live. Let AzA* be the set of marked arcs, I = (ieVl(i,j) ~ A), and F = (ieVl(j,i) e A*). I(F) is called the set of initial vertices (set of final vertices). Note that the matrix associated with Go = (V, A-A*) is F0. Two cases are now considered: Case a) For every arc (ij) e A*, (i,j) contains only one token. In this case, equation (4) reduces to: X(n) = X(n-1)F1(FO)*. (7) Using G and F as input and output vertices, respectively, associated with subA vectors X(n) and X(n) of X(n), we have: A X(n) = X(n) B(FO)*, (8) where B expresses the canonical injection of I in V, that is, 0, if X.(n) and X.(n) correspond to the same vertex in G; (B)i = -oo, otherwise. A Equation (8) says that only the knowledge of X(n) (components of X(n) from I) is required to reconstruct X(n). Similarly, we have: X(n) = X(n)C, where C is the matrix associated with the restriction of V to F. Hence from equation (8), we obtain: A X(n) = X(n) B(FO)*C. (9) Now the feedback equation is: A X(n) = X(n-l)K = X(n-l)CF1 B,

-18 - where K is a IFI X IGI matrix with K.. = t.i, if (i,j) ~ A*; and = -Wo, otherwise. K is built from F1 by selecting rows corresponding to F and columns corresponding to I. Using (9), we obtain the following reduced form of equation (7): A A X(n) = X(n-1)B(FO)*CK (10) or X(n) = X(n-1)KB(FO)*C. (11) Case b) Marked arcs may contain more than one token. If arc (ij) ~ A* contains r.. > 1 tokens, then we can add r.. -1 vertices to the graph G and r.. - 1 arcs that will bear one token each, as shown in Figure 3. i j i i i2 J X —~ ---->X < —> X --->X ---->X ---->X Figure 3. Arc (ij) of graph G containing 3 tokens. In particular, let il, i2,...,ik for k = rij - 1, be the new vertices, and (i,i1), (ill,i2),...,(ik 1 ik)' (ik, j) be the new arcs, each marked with exactly one token. (See Figure 3.) A* is then completed by adding these arcs and deleting arc (i,j). In addition, the new vertices il,...,ik are added to both F and I. To mathematically quantify Case b, we begin with: xj(n) = max {xi(n-ri) + tij, a), where a contains terms pertaining to other vertices preceding j. As we add vertices, we obtain: xj(n) = max (x. (n-l)+t., a) j i]J ij~~~'1

-19 - ik (n) X ik lik(n-l)+ t lik 'k ik-lk 1k-l'k x. (n)=x.. (n-1)+t, where t. ==t =.t 0 and t i = t... 1 1k i 1 J ik 'k-lik 1 ii In other words, we have introduced r.. - 1 new variables (the new vertices) into the algebraic representation. This technique enables matrices F2, F3,..., FA in equation (4) to vanish. They are transformed into new rows for matrix F1, by using these new variables. Then we are in the situation described by Case a. This method of transforming higher order delays into first order delays points out the fact that the number of independent state-variables is bounded from above by the number of tokens. It is then useful to consider as variables, the times when each token returns to its initial arc. Let 0 be the set of tokens and zi(n) be the time when token i E e is available again on its initial arc for the nth time. Using the technique of adding vertices, we can always assume without loss of generality that in the initial marking, each arc bears at most one token. In equation (10), let B (or C) become a 101 x IVI (or IVI x 101) matrix, where 00, if token i is on some input arc of vertex j; B.. = -Coo, otherwise. 0, if token i is on some output arc of vertex j; C. = J1 -o00, otherwise.

-20 - Let K be a diagonal matrix, with Kii.. = t., if token i is on arc (j,k). Then equation (10) becomes: Z(n) = Z(n -1) B(Fo)*CK. (12) Now each line or row of matrix B(Fo)*CK corresponds to a resource. This property will prove to be useful when we subsequently discuss performance evaluation issues. 3.5 An Illustrative Example An example is now provided to demonstrate the algebraic representations and manipulations. The Petri net (marked graph) of Figure 4 consists of 4 vertices, 7 arcs, and an initial marking Mo of 4 tokens distributed among the arcs. The arcs (ij) are labeled with the durations of the activities, ti. The algebraic representation of this graph, xi(n), i = 1,...,4, is provided by equation (2). ~X / \ a6 xl(n) = max(x2(n) + 4, x3(n) + 6) 3 r \ \2 x2(n) = xl(n-1) + 3 ~O7)X Q<~ x3(n) = max(xl(n-2)+ 2,x4(n-1) + 4) x4(n) = max{x2(n)+ 3, x3(n) + 5) 3 5 4 X Figure 4. Petri net example with algebraic representation. The equations of Figure 4 directly define the matrices F0, F1, and F2 as defined by equation (3):

-21 - ~ e ~ e 4 E e 3 6 8 E 5 E 8 E ~ (Fo)* is computed as: ~ 3 E e Fv -— ll8 ~ 4 8 e ~ ~ ~ 4 e ~ 3 (F )*= -- 6 ~ e 5 ~ ~ ~ e F = 2 ~ ~ 2 ~ ~ ~ ~ ~ 8 ~ ~ ~ 8 8 8 8 Arc (1,3) is the only arc containing two tokens. It is transformed into two arcs: 2 e With this transformation, the sets of initial and final vertices are: I = 2, 3, 5} and F= (1,4, 5}. The expanded matrices, (F0)* and F1, are:

-22 - (O)* = e ~ E~ ~ 4 e ~ 3 6 ~ e 5 ~ ~ E 8 e ~ ~ ~ E ~ e F = 1 8 3 E E 2 ~ ~E E E ~ 3 4 E ~ ~ ~ e E ~ Matrices B, C, and K are defined: E e ~ E ~ E E e E E ~E ~ ~ e e E ~ ~ e ~ e 8 8 E E E e 3 e 2 E 4 E e e Multiplying these matrices provides: 43 65e E.e B(Fo)*C = and B(F0)*CK = 77 6 998 e e e A With X(n) = (x2(n), x3(n), x5(n)), we obtain from equation (9): x2(n) = max {x2(n-1) + 7, x3(n-1) + 9} x(n) = max {x2(n-1) +7, x3(n-1) + 9, x(n-l)} x5(n) = max {x2(n-1) + 6, x3(n-1) + 8}. If we use the token space, tokens are numbered as follows:

-23 - No. 1 on arc (1,2) No. 2 on arc (1,5) No. 3 on arc (4,3) No. 4 on arc (5,3). These token markings define matrix B: E e E ~ e ~ ~ E E e E ~ e ~ ~ ~ ~ e E E e e S S ~ |~ | E ~ E ~ E ~ ~ e ~ ~ ~ E e 3 E E a 5 2 E ~ a E 4 S ~ | ~ e 3~~ ~2~ Multiplying these matrices provides: 4 4 3 e 7 6 7 e B(Fo)*C = e~ ~ 6 6 5 6 6 5 e ~ and B(Fo)*CK = e e e 989 ~ ~ 98 9 e Note that in the token space, B(FO)*CK has 2 rows and 2 columns which are identical, thus indicating the redundancy of the token comeback variables, zi(n), i.e., the token space does not provide minimal representation. The problem of finding the minimal representation is a topic for further research. We conjecture that it might be solved by finding minimal cuts in the graph. The reason is that one needs to find a minimal set of vertices that break all of the circuits in the marked graph. Moreover, the initial marking and the number of tokens must also affect the minimal representation. Then it seems to us that minimal cuts should play a role in finding the minimal representation.

-24 - 3.6 The Dual System Let vr denote the latest time that token r is available in G. In other words, we define a final marking Moo (due dates, for example) to be reached at time too, with v < too, r e 0. From this data, it is possible to simulate or evolve backwards to determine the behavior of the timed marked graph G and to calculate the latest firing times, qi, of vertices, which satisfy a final marking constraint. The following equality holds (Cunninghame-Green [1979] and Cohen et al. [1985a]): Vi, qi(n)= min {qj(n+rij)-tj. (13) je r+(i) j F i1J F+(i) = {jl(ij) sA and is the set of successors of vertex i. Equation (13) is the dual of equation (2). Denoting Qi(n) = -qi(n), equation (13) is transformed into: Vi, Q.(n)= min {Q.(n+rij)+tj). Qi(n) jE r+(i) J 1i i) We have returned to the {max,+) algebra. Dually of equation (3), we have: Q(n) = FoQ(n) S F1Q(n+1) S...S FAQ(n+A), (14) where A = max{ r. ) and Q(n) is a column vector containing the variables Qi(n). Matrix multiplication is now on the right because the successors of node i are used in equation (13). The backwards simulation from (14) requires first its solution in terms of Q(n) of: Q(n) = F0*F1Q(n+l) @...D (FO)*FAQ(n+A), (15) and then the knowledge of Q(n), Q(n-l),...,Q(n-A+l), for some n. Moreover, by introducing token variables r(n) that represent the opposite of the latest arrival date of token r on its final arc (as in the final marking), then it is possible to transform equation (15), when A=1, into the dual of (12):

-25 - g(n) = B(F0)*CK S(n+l), (16) where B is the token-to-vertex interface matrix, C is the vertex-to-token interface matrix, and K is a feedback matrix. When A > 1, it is possible to transform to equation (16) by adding a sufficient number of dummy vertices as in ~3.4, Case b). 4. SOLVING {max, +} RECURRENCE EQUATIONS ~3 provides a linear representation of timed marked graphs in a nonstandard algebra. The usefulness of this representation depends upon whether enough can be developed about this algebra to provide interesting results and analyses from the linear representation. This algebra has been studied by several researchers, such as Cunninghame-Green [1962, 1976], Gondran and Minoux [1979], and Cohen et al. [1985a]. Results on more general algebraic structures can be found in Zimmermann [1981] and Gondran and Minoux [1984]. In particular, Zimmermann discusses eigenvalue problems in ordered algebraic structures. Here we summarize and extend some of the results contained in the latter references concerning the study of (max,+) systems of recurrence equations. 4.1 Algebraic Setting Let M be a square m x m matrix and G(M) the associated graph as described in ~3.2. M is said to be irreducible if G(M) is strongly connected, which is assumed here. A study of recurrent equations of the form Z(n) = Z(n-l)M naturally leads to a study of eigenvalues and eigenvectors. An eigenvalue is a quantity X such that Z(n-1)M = XZ(n-l), where XZ(n-l) is obtained here by adding 2 to each component of Z(n-l). This behavior implies that Z(n) is obtained from Z(n-l) by a simple translation in time, without moving the relative location of events corresponding to the components of Z(n-l). Hence any real number X and vector X = (xi,...,xm) will be called an eigenvalue and eigenvector of M, respectively, on the left, if:

-26 - XX = XM. (17) It can be proven (see Cohen et al. [1985a]) that X > e and xi > e, Vi. Moreover, given M, X is unique and has a nice graph-theoretical interpretation. Namely X is the maximal average weight of circuits in G(M). The average weight W(y) of a circuit y in G(M) is defined as the ratio of the weight of the circuit by its length, (y): W(y) () (18) lly) In the notation of the algebra, where maximum represents addition and addition represents product, one would write equation (18) as W(y) = t) W(y) (see Ramchandani [1974]). The maximum of W(y) exists and is attainable, due to the finiteness of the graph G(M) (and Mi < + oo, Vi,j). It is easy to show that only simple circuits (with length iy) < m) need be considered. Let W* = max(W(y)(1y) < m} be the maximal average weight of Y circuits. We have W* = X, an eigenvalue of M. Any circuit y0 such that W(yO)= X is called a critical circuit. The graph Go(M) = (Vo(M), AO(M)), obtained as the union of all critical circuits, is called the critical graph associated with M. The set of eigenvectors of M has been characterized as follows (see Gordan and Minoux [1984] and Cohen et al. [1985a]): Let M+ = M.M* = MeM2 @...E Mn e.... M+, as M*, exists only if no positive weight circuit exists. In that case M*=E M M2... m-1. Hence M+ = M ~ M2 e...e Mm. Given M with eigenvalue X, define Mx such that (Mx)ij; = M.. - X, Vi,j, which can be written: Mx = 2A'M. Since X is the maximal average weight of circuits in G(M), the most weighted circuit in G(Mx) has weight 0 and (M)+ exists. It is proven in Cunninghame-Green [1979] (and also shown in Gondran and

-27 - Minoux [1984] and Cohen et al. [1985a]) that the set V0 of rows of (Mx)+, corresponding to vertices of the critical graph, are eigenvectors of M, and are enough to generate the eigenspace associated with M. That is, if y is an eigenvector of M, there is a set of real numbers (gili ~ VO) such that: y= X i(M)+ (19) i~Vo where the Z means a maximum and Mi denotes row i of M. Moreover, RLi = yi, Vi e V0. This is because any eigenvector of M is also an eigenvector of M+. The structure of the eigenspace depends upon the number of connected components C19,...,Ck of the critical graph Go(M). It is shown that (Cunninghame-Green [1979] and Cohen et al. [1985a]): *If i and j are vertices in V0 belonging to the same connected component, then (M) + and (Mx)t are collinear. That is, there exists a scalar p such that (MX). = (M)j. Hence choosing one vertex i. in each connected component Cf, we get a basis of k independent generators of the eigenspace; k is called the rank of matrix M. Note that the (max,+) algebra does not behave as a regular linear algebra with respect to independence. In particular, if V1,...,Vk are such that: k V= kVk' i= 1 then we cannot conclude that there exists al, a2,...,Xi- ai+l,...,ock, a, such that: k V= S a.V.i aV, j=l j.i Subspaces in the {max,+) algebra are more akin to convex polygons, where any n inner point x is a convex combination (, X.x.) of vertices x,...,x, where 2k. = 1 and all 1 nl 1

-28 - n.i > 0. When x = Y X.x., we cannot conclude that x. = ajx. + ax, because the X's 1 i=l 11 i J J must be positive. In the {max,+} algebra, all numbers are "positive" because "max" does not allow inverses. That is, there do not exist numbers "-a" such that max (a,"-a") = 8. The k basic vectors extracted from (Mx)+ play the role of the vertices of a convex polygon. The question of independence in the (max,+) algebra requires theoretical investigations which are beyond the scope of this paper. (See Cunninghame-Green [1979], Gondran [1979, 1984], and Cohen et al. [1985b], however.) The notion of a projector also exists in the algebra. A projector is a matrix P such that P2 = P. Given a matrix M, there is a projector PM such that for every V, VPM is an eigenvector of M as long as there exists an no e N such that: Vn > n, (MX)n = (M))nO (20) and PM = lin (M )n, a limit which is attained in a finite number of steps. In that case, M n —+oo VPMM = V lirm (M)n+l = XVPM. n —+oo 4.2 Periodicity More generally, a matrix M is said to be order-d-periodical if there are integers d and no such that: Vn> n0, (M)n+d = (M,)n (21) thus, generalizing equation (20). In the following, it is assumed that Vn, Mn is irreducible. This condition holds, for example, if G(M) contains a loop, i.e., there exists an i such that M1. > a. The following results are proven in Cohen et al. [1985a]. *If the critical graph is a circuit of length d, then M is order-d-periodical. *If the critical graph has only one connected component, then d is the g.c.d (greatest common divisor) of the lengths of the simple circuits (critical circuits) in Go(M). Then d is called the order of Go(M) and M is order-d-periodical.

-29 - *If G (M) has K connected components C., (=1,...,K, let d be the order of C. Then M is order-d-periodical with d = l.c.m. (least common multiple) of (d,...,dK). If M is order-d-periodical, the following quantities exist: Qi = lim (M)dn+i, i=O,...,d=l. 1 n —+oo Clearly, Qi = (M)i QO = Qo(M1)i. Q0 = PMd is the projector of Md. Q0 can be obtained from the knowledge of a basis of generators of the eigenspace on the left, (extracted from d + the rows of (Mx), as explained in ~4.1) and a basis of generators of the eigenspace on the d+ right, extracted the same way from the columns of (M ). More specifically, let V1...,V be a basis of left eigenvectors of Md, where k refers to strongly connected component number k of G0(Md), and let W,...,WK be a basis of right eigenvectors of Md, i. e., Vk d+ d+ = (M )k. and Wk = (M).k. The outer product Wk @ Vk produces an m x m matrix, where entry i,j contains the term: (Wk)i (Vk)j. It is proven in Cunninghame-Green [1979] and shown in Cohen et al. [1985a] that: K QO= Wk @ Vk k= We now demonstrate with an example. EXAMPLE 2 We have the following matrix M and its associated graph G(M). The weights of each arc are labeled accordingly. M=E 4 2; G(M)= 2 4 ^6 M = 4 G(M) = 4x /

-30 - By inspection, it is clear that the circuits (and their weights and lengths) are: 1-1 weight 4 length: 1 2-2 weight 4 length: 1 1-3-1 weight 5 length: 2 1-2-3-1 weight 9 length: 3 This implies that the eigenvalue = X = 4. Hence the critical graph consists of two components, C1 and C2, corresponding to loop 1-1 and loop 2-2. We have Mx: 0 2 0 0 2 0 M4= 0 - 0 -2 (M44)= -(M4)4 + - 2 =(4) 3 =(M)4). -3 e ~ -3 -1 -3 Hence (M4)+ = (M4)2. The eigenspace on the left of M is generated by the two row vectors (0,2,0) and (-5,0,-2) (rows 1 and 2 of (M4)+) So the eigenspace is: E = ((x,y,z)l there exist A1 and X2, where x = max{1, X2-5), y = max(X1 + 2,X2}, z = max{(l, X2-2 }. Notice that the third line of (M4)+ is collinear to the first row. C1 and C2 are of order 1. Therefore, M is order-l-periodical. Q0 is obtained from rows 1 and 2, and columns 1 and 2 of (M4)+: 0 2 0 2 0 Q0= -5 (0 2 0) 0 (-5 0 -2) -5 0 -2 (=(M4)+ here). -3 -1 -3 -1 -3 If (x,y,z) is any vector, then (x,y,z)Q0 = (max (x,y-5,z-3), max x+2,y,z-1), max x,y-2,z-3)), which belongs to E (Xl = max{x,z+3), X2 = y).

-31 - It is indeed an eigenvector. 4.3 Systems of Linear Equations The algebraic setting presented in ~3.1, and the concept of order-d-periodicity enable (max,+) recurrence equations to be solved. A basic result is now stated, from Cohen et al. [1985a]. Proposition 4: Let M be an irreducible order-d-periodical matrix with eigenvalue X. Let (X(n) }n>0' Q(n)}n<N be sequences of vectors which are solutions of the recurrent systems: X(n) = X(n-l)M X(O) = X (primal system) Q(n) = MQ(n+l) Q(N) = -Q (dual system) Then there exists no such that X(n+d)= XdX(n) Vn > n (22) Q(n) = xdQ(n+d) Vn < N-n0. (23) The duality between X(n) and Q(n) is acknowledged in the following identity: X(n)Q(n) = X(n')Q(n'), for 0 < n < N and 0 < n'< N. U The behavior of X(n) over the long term is more precisely described as follows: Case i) If the critical graph, G0(M), has only one connected component of order 1, (e.g., Go(M) is a loop), then 'Vn > n0, X(n) = nXQ0. QO is a rank 1 projector. If X and X' are two initial states, then XQo and X'Qo are collinear. In other words, VX, the sequence S(n) = X(n)X-n converges to XQ0. The steady state is unique.

-32 - Case ii) If the critical graph, GO(M), has only one connected component of order d (e.g., Go(M) is a circuit of length d), then Vn > n0, X(n) = XnXQi, if n-d(n:d)** = i, i=0,...,d-l. Q0 is a rank d projector. Case iii) If the critical graph, Go(M), has k connected components of order dk, k=l,..., K, then Vn > n0, X(n) = 2nXQi, if n-d(n:d) = i, i=O,...,d-l with d=l.c.m. (d,...,dk) and the rank Q0 = i di These results are very useful to understand the behavior of discrete-event systems (that can be described by timed marked graphs) in the long run, from the knowledge of their initial state. Such systems achieve a complex periodical behavior: the earliest and latest firing times of events repeated n and n + d times are the same up to a translation of amount Ad, Vn > n0. A limiting cycle of states of the system is eventually reached. This limiting cycle is unique in Case i), and it becomes stable. The period of the system is closely related to the eigenvalue of its associated matrix. The effective calculation of the time characteristics of the limiting cycle is easily obtained from the knowledge of the eigenvectors of the matrix. More specifically, the earliest starting times in steady-state are obtained asX = XQi I i=O,...,d-l), up to a translation. It is called the earliest steady state. To get the latest starting times in steady state, we must first recall a result obtained by Cunninghame-Green [1976] on solving (max,+) systems of equations of the form XM = V, (24) **The notation n:d is the Euclidian division and n-d(n:d) is the remainder of this division.

-33 - where V is some given vector of dates. The problem is to determine how to choose starting times contained in X to ensure that the next cycle is undertaken at preassigned times. Equation (24) can be relaxed to XM < V, (25) where < is the usual vector-ordering: V < V', <==> V. < Vi Vi. Equation (25) views V as a due date constraint. Now, the set of latest starting times is described by X satisfying A X= sup(XI XM < V}, A where sup is in the sense of < (vector-maximization). Xcan be categorized as follows. A Proposition 5: X exists and is defined by t = (M.t(v )) 1, where tV is the transposition of V, (V-)i = -Vi, and (M-1) = -M... Moreover, if A equation (26) has a solution, then X is the greatest solution. U Now, the latest steady state of the system can be obtained by considering the earliest steady state as a due date constraint, i.e., by defining the sequence of vectors: A A Y(N-n), n > 0, such that Y(N) = XQO and V n < N, A n Y(N-n), = sup(Y(N-n)l Y(N-n)(M)n < XQ } (26) = ((Mx) * D(XQO) 1), using Theorem 4 t= (QXQt ) ), for n > n and n-d(n:d) = i. Hence the latest steady state is defined by the column vectors = t(Qd it(Xd-i)-l)-1 i= 1,..,d.

-34 - (In particular, Yd = QO.) The following property can be established: Proposition 6: For every i=l,...,d, Yi> xd-. Proof: Note that Vn > n0, denoting p = n:d and i = n-dp, Xd-i Y(N-n) I Y(N-n)(M)n XA XQ). Indeed, Xi(MdP+ = XQ0(M)d-i(M )iQ = XQo0 since Q02 = Q = Q0 (ML).But Xi is not the greatest element of the above defined set. (This maximizing element is Yi.) 1 Proposition 6 says that the earliest occurence times of events take place before the latest occurence times. Since each component denotes the firing time of some events, the slack times (s.) associated with the occurrence of events are defined by: Vj,sj=(Y )j d - ). (27) If j belongs to the critical graph of M, then s. = 0 can be established. EXAMPLE 3 Consider the matrix M in Example 2, with initial state X = (0,0,0). M is order-lperiodical. The steady state is: 4n Qo = 4n(0,2,0) = (4n,4n+2,4n). X0 = (0,2,0), X(1) = X M = (4,6,4), and X(2) = (8,10,8). Then steady state is reached (no = 1).

-35 - r n f 1 0 2 0 0 1 ty-1 = (Q t(x)-)1 = -5 0 -2 -2 -3 1 -3 0 0 0 = -2 = 2. -3 3 Thus the slack values are sl = 0, s2 = 0 (nodes 1 and 2 are critical nodes), and s3 = 3 (node 3 is not critical). It can be checked that (0,2,3)M = (4,6,4), but that (0,2,3+~)M = (4+s,6,4). Then 3 is a latest occurrence date for the event represented by vertex 3, if vertices 1 and 2 fire at t = 0 and 2, respectively. 4.4 Reducible Matrices In this section, we relax the assumption that the graph G(M) associated with matrix M is strongly connected. In this case, it is possible to compute strongly connected components {G1,...,Gp}, which are partially ordered by the relation >: Gi > Gj <==> there is a path from G. to Gj. Then, G. > G. means that Gi is upstream from G.. In terms 1 J I j 1 J of marked graphs, Gi sends tokens to Gj, but not conversely. Each graph Gi corresponds to a matrix M(i), which is irreducible and has its own eigenvalue, Xi, unless Gi is reduced to an isolated node with no loop. In the latter case, Gi is said to be degenerate. Let us assume for the moment that G(M) has only two strongly connected components, G1 and G2, which are not degenerate. M can be arranged as an upper blocktriangular matrix with the following structure:

-36 - M(1) M(12) M=, M(12)* 0 0 M(2) Figure 5. Matrix M. It is assumed that G1 > G2. Proposition 7. M has a left eigenvalue equal to the max(Xl, X2). Moreover, if X1 > A2, then,2 is also a left eigenvalue. M has no other eigenvalue. Proof: Let Xi be a left eigenvector of M(i), i=l or 2. Now [~,E,...,~X2]M = [~,~,E,...,eX2M(2)] = 2[,...,eX2]. Hence, X2 is an eigenvalue of M. Let X be the concatenation of vectors X1 and X2 and denoted by: X = [X1X2]. Then [X1X2]M = [X1M(l), X1M(12) ( X2M(2)] = XX if and only if: X1M(12) @ X2M(2) = X X2 That is, X1M(12) @ X2M(2) = X2, where M = XM. 1 1 That is, X2 = X1M(12)x (M(2)x )*. But (M(2)x )* exists only if M(2)2 has 1 1 1 2 only negative weight circuits, i.e., X1 > 2X. That M has no other eigenvalue is obvious from the unicity of the eigenvalues of M(1) and M(2). U Note that when X1 > X2, the eigenvectors of M for X2 are the eigenvectors of M(2) completed with e's, which amounts to cancelling both M(l) and M(12) in M. That is, the

-37 - system whose marked graph is G2 is run by its own dynamics. The eigenvectors for X1 are defined by: X=[X1X2] IX1 is an eigenvector of Mland X2 = X1M(12) (M(2) )*), 1 1 as shown in the proof of Theorem 4. When X2 > x'1 the system G1 cycles faster than G2 and sends tokens to G2 (through G(M(12) 12) ) A G at a rate which G2 cannot follow. Hence as time elapses, more and more tokens wait to be cancelled by firing the interface vertices between G2 and G12. Tokens accumulate in the system and stability is not preserved. Hence for a proper behavior of systems whose structure is not strongly connected, it is useful to assume that if G. is upstream of G., then G. is slower (X. > X.) than G.. 1 J 1 i J J Now the process defined by X(n) = X(n-l)M and X(O) = X can be studied as follows: M(l)n M(1,2,n) X(n)= X 0 M(2) where M(1,2,n) = M(l)n-lM(1,2) @ M(1,2,n-1) M(2) and M(1,2,1) = M(1,2). That is, if X (n) denotes the part of X(n) pertaining to G1, then X (n) = XlM(l)n. In the long run, if Q0() denotes the projector built on M(1), we have Xl(n) = XQ(l), for n - (n:dl) = i if d1 is the order of periodicity of M(1). Now X2(n)= Xl(n) M(1,2) X2(n-1)M(2). (28)

-38 - For a large enough n, we can compute a periodical behavior of X2(n) by noticing that hi is the only interesting eigenvalue of M when G1 has been excited as well as G2. This means, that there exists no and n > no such that X2(n) = XQi(1)Xln @ X2(n)l M(2) and we get X2(n) = X1Qi(1)Xln(M(2)l )*, for n-(n:d1) = i. 1 X2, the initial state of G2, does not appear in steady state. To see this, let Q0(2) be the projector associated with M(2), and let d2 be the order of periodicity for M(2). Then there exists d such that X2 M(2)n = X2Qj(2) + nK2 where n - d2(n:d) = j Now let us compare the kth component of X2(M(2))n and that of X2(n) as given by equation (28). n > n': (X2M(2)n)k = (X2Qj(2))k + n2< max {X d12 (A N )k= (AY ))krX2~ J='dmax -1X J (2)lk + 2A an. 2 1 2 n > n: (X2(n))k > (X Qi(l))k + nl > min {XQi(1)} +nX Abn i=0...id -1 Now, since Xi > X2, there exists n"0 such that n > n"0 ==> b > an, i.e., (X2(n))k > (X2M(2)n)k. Hence, the term X2M(2)n vanishes from X2(n), and does not affect its value in the long run. 5. ALGORITHMIC ISSUES In order to be able to use the results of ~~3 and 4 on practical problems, computational tools are needed. Such tools already exist in the literature, in graph theory (Karp [1978]). These are applied to the computation of eigenvalues of matrices in the (max,+) algebra. This section recalls a graph-theoretical interpretation of the eigenvalues. An algorithm is provided to compute the eigenvalue and to determine critical circuits of activities. We prove that adding tokens to a marked graph representation decreases the eigenvalue.

-39 - M is a square matrix with coefficients that are real numbers or e = -oo. Let G(M) be its associated graph whose nodes are rows (or columns) of the matrix. Arcs correspond to the entries that are different from ~. Each arc (ij) is labeled by Mij. Let X be the unique eigenvalue of M; this unicity holds when G(M) is strongly connected, which is assumed here. The eigenvalue is defined on the {max,+) algebra. 5.1 Computing Eigenvalues and Critical Circuits Recall that X is the average weight of any circuit in G(M) with maximal average weight. Finding this maximal average weight is a problem that has been solved by Karp [1978], who provides a very efficient algorithm to calculate X without requiring its algebraic interpretation. He proves that the eigenvalue of M can be obtained by choosing any vertex i of G(M) and calculating: (M).. - (Mk). (= max minn k (29) j=l,...m O<k<m-l m - where (M )i is the (i,j)-th entry of the k-th (max, +} power of M, i.e., the maximal weight of paths of length k from i to j in G(M). The implementation of equation (29) requires only the determination and storage of k row i of matrix M, for k = l,...,m. The computational time is then O(m X the number of arcs in G(M)). Karp's [1978] proof indicates that for any critical circuit, there is a node j* in this circuit such that (M)ii* - (M ( )i* t= min Ock<m-1 m - k for any choice of i. Moreover, a critical circuit is then trapped in one maximal weighted path in m arcs from i to j*. If this critical circuit has length d, then letting k* = n-d, i* (Mmi (M )i* m - k*

-40 - A critical circuit can be retrieved by a systematic check of the maximal weighted path from i to j* in m arcs. While computing the terms (M k)., V, the extremal paths can be stored, Ii J and critical circuits can thus be trapped. EXAMPLE 4 Suppose that M = e 13 1 2 1 1 1 e lie * (Recall that the identity e = 0.) The associated graph G(M) is the following: 1 e.1 2 Choosing i = 1, the following array A is built.

-41 - vertices j \ | I I Entry (jk) contains (Mk)ij for k > 2. Entry 1 | e e 4 (2) (,k) also contains a list, (il,...,iq), of vertices A = — l(3) (2) which are the predecessors ofj on each A = 2 | 1 4( 62 maximal weighted path from 1 to j in k arcs. _____ ______ _____ (3) (2) 3 a 3 3(1.3) (1) Note that M0 = E. Column k of this array is obtained as tV, Ajk= max {A4/,- +Mg V-j A =,...,3 j which says that (Mk), = (Mk-) M. Now array B, containing as entry (j,k) the term (M ) = (M )i. -3 - k i k = 0,1, and 2, is obtained as: 3 k 0 1 2 1 5/3 5/2 ( )1 2 +oo 5/2 2Q j 3 +oo Do 4 2 The circled entries are the minimum in their corresponding row. These values are placed in the right side of the array. The maximum of these minimum values is placed in a square. It is 2 (= X). There are two rows that provide this X: j = 2 and 3. For j = 3 and k = 1, we

-42 - can expect to capture a critical circuit y of length 3 - 1 = 2 in the maximal weighted path from I to 3 in 3 arcs. From array A and the knowledge of the predecessors, we obtain the path (1,3,1,3) containing the circuit Y= (1, 3, 1): 1 3 1 3 X X X X 3 1 3 Hence y = (1,3,1) is critical. Indeed, its weight is 4 and its length is 2. For j = 2 and k = 2, we capture a critical circuit of length 3-2 = 1 in the maximal weighted path from 1 to 2 retrieved from array A. This critical circuit is the critical loop (2,2) contained in the path (1,3,2,2). 5.2 The Influence of the Number of Tokens on x If we again interpret matrix M as derived from the analysis of a timed marked graph in the token space, each row of M corresponds to a token. Then a path i,i2,...,i in G(M) corresponds to one or more paths in the marked graph G, each path containing p tokens. In particular, a circuit of length p in G(M) is interpreted as a circuit in G containing p tokens. Hence, when G is strongly connected, if t(y) is the number of tokens on circuit y e G, we have: w(y) w(y) = -max -max. (30) yEG(M) [(Y) WG x(Y) This result has been proved by Ramchandani [1974] (see also Ramamoorthy and Ho [1980]). However, Ramchandani provided no computationally efficient method for computing X or for finding critical circuits. Moreover, Ramamoorthy and Ho only provide a polynomial algorithm to determine, given a guessed cycle time a, whether or not a X. Another interesting point is that any matrix M with nonnegative (and finite) entries can be associated with a marked graph G', as follows: * Associate with each row i, a vertex and an arc (i,j), VM.. > 0. * If M.. > 0, then there is a token on arc (i,j). 1j

-43 - We thus obtain a marked graph G', as demonstrated in Example 5. EXAMPLE 5 -2 1 P3M=3 2( ~O03 =2G 0 It is clear in Example 5 that matrices F0, F2, F3,... are, since every arc has one A token on it. We have X(n) = X(n) = X(n) = Xn _1F = X 1M. There are no redundant entries in X(n) with respect to each other. As a consequence, the above remark provides a technique to transform any timed marked graph G into another equivalent graph, G', such that each arc carries exactly one token. In particular, first construct M = B(Fo)*CK. Then, G' can be constructed from M. If M has any negative finite entries, then if w = min (Mij # e) < 0, it is possible to derive an associated marked graph by considering the matrix wM, and modifying the state variable accordingly (see Cohen et al. [1985a]). But in practice, starting from a timed marked graph always leads to M i > 0, Vi,j. Now, given a critical circuit yD on G(M), y, corresponds to a circuit ybof critical events in the original marked graph, G. Since X =, it is clear that by adding a token on the critical circuit y, the average weight of this circuit becomes w(yg)/((y + 1). This may make y no longer critical. On the other hand, thee is no other way of decreasing K (i.e., to improve the performance of the marked graph), since adding tokens on other circuits would leave X unchanged.

-44 - To see this in a more rigorous manner, let G be a timed marked graph with each arc carrying at most one token. We can always satisfy this condition (see ~3.4). Hence we have the following: X(n) = X(n)F0 D X(n-l)F1 = X(n-l)F1(FO)*. Now if we add a token to arc (i,j) in G, we must consider two cases: a) Case 1: Arc (ij) had contained no token. Hence (Fo)i. = ti. and (F1)i = ~. Adding a token yields Fband Fi such that V(ij) (ij), (Fij = (FO)ij, (F)ij = (F)ij. (Foi =, and (Fi)i = t. Now using matrices B, C, and K for working in the token space, and vector Z(n), where each component pertains to a token (see ~3.4), B', C', and K' are obtained as follows: B B' =, where b is an additional row such that b. = 0 bk = e, Vk = j, b J k - C = C c, where c is an additional column such that ci = 0, ck =, Vk = i, K ~ and K' =, which has one more row and column than K. te Now we consider Z'(n) = [Z(n), z(n)], where z(n) is the entry pertaining to the new token. In the token space matrix, M'= B'(F)*C'K'

-45 - B r -l K ~ Cc K< = b B(F%* ) o j-j ~ ~ ~ ~ ~ di = * [ CK' t - - ithrow [B(F1 *CK tijB(F*l L (F*) i CK ti (FRji j Since G(FO) has no circuit and moreover, (F0)ij > 0, then (F)*ji = ~. Deleting arc (ij) from G(FO) leads to (F&*ji = e again. Hence M'p+l+l = e. Now, assume that arc i,j belongs to a critical circuit in G, and let k and (be two tokens such that ~*is on an input arc of vertex i, *k is on an input arc of vertex ik. ~Arc iJ is on a maximal weight path from i to ik. ~There is no token on this path, except k. Now ((F%*)j CK)k = maximal weight of a path fromj to k in G = ((F jCK)k since all paths that originated on j in G(F) remain the same in G(F&. (Recall that G(FO) has no circuits.) Similarly, (tijB(F&* j)= (tijB(Fo)* i)r= M'p+, since no path that ends in i changes when G(Fo) turns into G(F).

-46 - Moreover, arc (i,j) is on a maximal-weighted path from i to ik in G(Fo) and so (F*i. + ti. + (F*. ik = (F )*iik. We can conclude (multiplying by K on the right), that M = M p++ M+lk' where "+" has its usual meaning. So adding a token to an arc i,j that belongs to a critical circuit is the same as breaking a critical arc 4k in G(M) (the graph whose nodes are tokens) by adding a node p+l (without a loop), while preserving the weight from Cto k, as pictured below: G(M % ----Vk Xkj ___ _ G(M') [X...Xk M k G(M) > X k X p+l (M'2) k= Mk Notice that there may still be an arc (4k) in G'(M'), but we have M' <~ M.. b) Case 2: Arc (i,jl already has a token. i t.. q 0 j G = X — ->X*>X p+1 s In this case, we transform G into G', which contains one more node q, with t. = tij and tqj = 0 (as done in ~3.4). Hence Fband Fiare defined as follows (IVI = q-l): Fl O F e e e since arcs (i,q) and (q,j) bear tokens. q q That is, Fbremains the same, except that one row and one column of S's are added to it. Moreover, Fjhas also one more row and column. Rows 1 to q-l and columns 1 to q-l of Fi are the same as those of Fl, except that (Fi)ij = E (because of the deletion of arc

-47 - (i,j)). Moreover, row (resp: column) q of F is filled with e's, except that row (F)qj = 0 (resp: (Fi)iq = tij). That is, Row i Columns j q tii e ~ 0 ~ E F Row q Now B' has p+l rows and q columns. Let s be the number of the token on arc (i,j) in G. Then the old token is still in the input arc of vertex j. The new token, p+l, is at the input of q. Hence: j q B ~ 0 That is, (B') = B i,for i <p and j q; (B (B)i but(B)p+,q=. BI= = I (B')p+lj= (3')iq =, but (Bp+l q = s p+l i C' C C e - - |- --- --- -- That is, (C'). = C, for i q and j < p. 6 0 -- -- --- - But C'i = (insteadof 0). Cqi=C p+- = C C s. — -- e, except C'. = 0 and C's = 0. e 0 eqs E O E E~~~~~~~~~~~~~~. q

-48 - I s p+l K 0 s p+l tij That is, (K')ii = K.., except that K = 0. K' l tp p+l,p+l ti Now, (F*) [-0] and B' B [ O ] and B'F*Cl= 0 0- -- Cl 0 LE OjLC 0. s BF*C 0 s E e E BF*C 0 p+1 (BF5)ji i sssJieJsssI s BF*CK 0 ~ E e BF*CK 0 ti (BF4)i _ I. Hence M' = EE e 0 E E It is easy to check that the last column of M', i.e., t.i(BFo). is the same as column s of M. Indeed,

-49 - M. =(B(Fo)*CK) s = B(Fo)*C(K) 5 = B(FO)* t8,where tij is on row i, since C. = 0. IS s As a result, it is not necessary to recompute everything to get M'. One only needs to add a token to an arc which already contains one. The column corresponding to the old token is shifted to the new column pertaining to the new token and a zero is put in the bottom of the old token column to make the new token row. That is, letting M = {M(l,s-l):M: M(sl+l,p)), * * s M(l,s-l) e M(s+l,p) M.s E ~ 0 e e, - - - - - - - Then M' = G(M') is easily obtained from G(M) as follows: let (s',s) be an arc on the critical graph of G(M). Then, add a token p+l to the arc of G that contains s. The results are: * The (s',s) arc is deleted (and there is no arc left between s' and s) (since M', = S S e). * All arcs in G(M) that end at s are deleted. They are input at the new' vertex, p+l. * A zero-weight arc is added from the new vertex p+1 to s. * The new vertex has no loop on it. S(M = /IM ( s 0 "ss /Ss G(M)=,i rs2 8 tssw " ~i a-S g\i^v"/ \s^ \^S

-50 - In other words, if arc (s',s) belongs to a critical circuit, then this circuit remains in M' with the same weight. However, one more arc (p+ l,s) of weight zero is added, thus decreasing the average weight. It may then happen that the circuit is no longer critical. Notice that when a token is added to a previously token-free arc, the computation of M' is more elaborate. However, we have seen that the same result is produced. 6. SUMMARY AND FUTURE RESEARCH NEEDS Previous research on the algebraic representation of timed marked graphs in terms of linear recurrence equations in a {max,+) algebra has been reviewed and extended. The results extend PERT/CPM concepts to asynchronous and repetitive production processes. Applications of this model to certain classes of flexible manufacturing systems that exhibit periodic behavior are provided in Dubois and Stecke [1989]. There are many open research problems involving this approach. Theoretically, determining the minimal representation of a timed marked graph is important. The token space, for instance, does not usually produce a minimal representation. One approach to address this problem might use the concept of minimal disconnecting sets of arcs in directed graphs. Another important open problem is to understand how the initial marking affects the steady state periodic behavior. It should be possible to define equivalence classes of initial markings, where all markings in a class lead to the same periodic behavior. This research problem is related to the reachability analysis of timed Petri nets. The problem is similar to that of determining ergodicity of Markov matrices, where various initial states in a Markov state transition graph may lead to various asymptotic probability vectors. Also, cyclic behavior can be observed (in the probabilistic sense). As vanishing states and disjoint sets of strongly connected states can be found in Markovian systems, it may be that the set of live markings in a timed marked graph can be clustered into a subset of vanishing markings and several disjoint cycles of markings, where each cycle corresponds to a specific periodic

-51 - behavior. A vanishing marking is one that is reachable from no marking in a cycle but not conversely. These are Conjectures to suggest further research. Timed marked graphs are a special type of Petri nets. This paper emphasizes the following analogy: marked graphs are to Petri nets what linear systems are to general continuous systems (differential equations) in the field of automatic control. Timed marked graphs are linear in a path algebra and can be analyzed by means of eigenvalues, eigenvectors, and projectors in a way similar to conventional linear systems. The analogy between linear systems theory and timed marked graphs has been examined by Cohen et al. [1985b, 1987]. ACKNOWLEDGEMENTS We gratefully acknowledge the expert evaluations of three anonymous Referees each for both this and the associated applications paper as well as the Associate Editors and the Editors, Joe Mazzola and Maurice Queyranne.

-52 - BIBLIOGRAPHY AJMONE MARSAN, MARCO, BALBO, GIANFRANCO, and CONTE, GIOVANNI, "A Class of Generalized Stochastic Petri Nets for the Performance Evaluation of Multiprocessor Systems", ACM Transactions on Computer Systems, Vol. 2, No. 2, pp. 93-122 (May 1984). AJMONE MARSAN, MARCO, BALBO, GIANFRANCO, and CONTE, GIOVANNI, Performance Models of Multiprocessor Systems, The MIT Press, Cambridge, MA (1986). BEL, GERARD and DUBOIS, DIDIER, "A Unified Setting for Various Models of Automated Material Flow and Production Systems", Computers in Industry, Vol. 6, pp. 227-235 (1985). BROWNE, JIM, DUBOIS, DIDIER, RATHMILL, KEITH, SETHI, SURESH P., and STECKE, KATHRYN E., "Classification of Flexible Manufacturing Systems", The FMS Magazine, Vol. 2, No. 2, pp. 114-117 (April 1984). BUZACOTT, JOHN A. and YAO, DAVID D. W., "Flexible Manufacturing Systems: A Review of Analytical Models", Management Science (1986). CARRE, B. A., "An Algebra for Network Routing Problems," Journal of the Institute of Mathematical Applications, Vol. 7, pp. 273-294 (1971). CHRETIENNE, PHILIPPE, "Les R6seaux de Petri Temporis6s," These d'Etat, Universit6 de Paris VI, France (June 1983). COHEN, GUY, DUBOIS, DIDIER, QUADRAT, JEAN PIERRE, and VIOT, MICHEL, "A Linear-System Theoretic View of Discrete-event Processes and Its Use for Performance Evaluation in Manufacturing", IEEE Transactions on Automatic Control, Vol. AC-30, No. 3, pp. 210-220 (March 1985a). COHEN, GUY, MOLLER, P., QUADRAT, JEAN PIERRE, and VIOT, MICHEL, "Linear System Theory for Discrete-event Systems", Proceedings of the 23rd IEEE Conference on Decision and Control, Las Vegas, Nevada, pp. 539-544 (December 1984). COHEN, GUY, MOLLER, P., QUADRAT, JEAN PIERRE, and VIOT, MICHEL, "Une Th6orie Lineaire des Systemes a Ev6nements Discrets," Rapport No. 362, INRIA, Rocquencourt, France (1985b). COHEN, GUY, MOLLER, P., QUADRAT, JEAN PIERRE, and VIOT, MICHEL, "Dating and Counting Events in Discrete Event Systems", Proceedings of the 25th IEEE Conference on Decision and Control, Athens, Greece (December 1986). COHEN, GUY, MOLLER, P., QUADRAT, JEAN PIERRE, and VIOT, MICHEL, "A 2-Discrete Event Linear System Theory", Algebres Exotiques et Systenes a Evenements Discrets. INRIA, Rocquencourt, France, pp. 147-165 (June 1987). COMMONNER, F., HOLT, A. W., EVEN, S., and PNUELI, A., "Marked Directed Graphs," Journal of the Computer Systems Society, Vol. 5, pp. 511-523 (1971).

-53 - CUNNINGHAME-GREEN, RAYMOND A., "Describing Industrial Processes and Approximating Their Steady-state Behavior", Operational Research Ouarterly, Vol. 13, pp. 95-100 (1962). CUNNINGHAME-GREEN, RAYMOND A., "Projections in a Minimax Algebra", Mathematical Programming, Vol. 10, pp. 111-123 (1976). CUNNINGHAME-GREEN, RAYMOND A., Minimax Algebra (Lecture Notes in Economics and Mathematical Systems, Vol. 166), Springer Verlag, New York (1979). DIAZ, MICHEL, "Modeling and Analysis of Communication and Cooperation Protocols Using Petri Net Based Models", Computer Networks. Vol. 6, No. 6, pp. 419-441 (December 1982). DUBOIS, DIDIER and STECKE, KATHRYN E., "Using Petri Nets to Represent Production Processes", Proceedings of the 22nd IEEE Conference on Decision and Control, San Antonio, Texas, pp. 1062-1067 (December 1983). DUBOIS, DIDIER and STECKE, KATHRYN E., "Dynamic Analysis of Repetitive Decision-free Discrete Event Processes: Applications to Production Systems", Working Paper No. 543-b, DOR, The University of Michigan, GSBA, Ann Arbor MI (October 1989). FLOYD, R. W., "Shortest Paths," Communications of the Association of Computing Machinery, p. 345 (1962). GONDRAN, M., "Les El6ments p-r6guliers dans les Diotdes", Discrete Mathematics, Vol. 25, pp. 33-39 (1979). GONDRAN, M. and MINOUX, M., Graphes et Algorithmes, Eyrolles Editions, Paris, France (1979). GONDRAN, M. and MINOUX, M., "Algebraic and Combinational Methods in Operations Research," (R. E. Burkard, R. A. Cunninghame-Green and U. Zimmermann, Editors), Annals of Discrete Mathematics, Vol. 19, North Holland, Amsterdam (1984). KARP, RICHARD M. "A Characterization of the Minimum Cycle Mean in a Digraph," Discrete Mathematics. Vol. 23, pp. 309-311 (1978). PETERSON, JAMES L., Petri Net Theory and the Modeling of Systems, Prentice-Hall, Inc., Englewood Cliffs NJ (1981). RAMAMOORTHY, C. V. and HO, GARY S., "Performance Evaluation of Asynchronous Concurrent Systems Using Petri Nets", IEEE Transactions on Software Engineering, Vol. 6, No. 5, pp. 440-449 (September 1980). RAMCHANDANI, CHANDER, "Analysis of Asynchronous Concurrent Systems by Timed Petri Nets", Ph.D. dissertation, Department of Electrical Engineering, MIT, Cambridge MA (1974). REITER, R., "Scheduling Parallel Computations", Journal of the Association of Computing Machinery, Vol. 15, pp. 590-599 (1968).

-54 -SMIGELSKI, T., MURATA, T. and SOWA, M., "A Timed Petri Net Model and Simulation of a Dataflow Computer", International Workshop on Timed Petri Nets. Torino, Italy, pp. 56-63 (July 1-3, 1985). ZIMMERMANN, U., "Linear and Combinational Optimization in Ordered Algebraic Structures", Annals of Discrete Mathematics, Vol. 10, North Holland, Amsterdam (1981).