Abir Benabid-Najjar

Claire Hanen

Olivier Marchetti

Alix Munier-Kordon

Claire Benabid

Olivier Hanen

Marchetti

Periodic schedules for bounded timed weighted event graphs

Keywords:

Timed event graphs (TEGs) and timed weighted event graphs (TWEGs) which have multiple arc cardinalities, have been widely used for automated production systems such as robotized work cells or embedded systems. TWEGs are useful for modeling batch flows of entities such as batch arrivals or processing of jobs. Periodic schedules, that combine an explicit description of starting times and an easy implementation are particularly interesting, and have been proved to be optimal for ordinary timed event graphs (TEGs). In this paper, we present polynomial algorithms to check the existence of periodic schedules of bounded TWEGs and to compute their optimal throughput. These results can be considered as generalizations of those for ordinary timed event graphs. We then establish that periodic schedules are suboptimal for TWEGs and may not exist even for a live TWEG.

The gap between optimal throughput and throughput of an optimal periodic schedule is experimentally investigated for a subclass of TWEGs, namely timed weighted circuits.

I. INTRODUCTION

Cyclic scheduling problems, in which a set of generic tasks T has to be performed infinitely often, have numerous practical applications in production or multi-processors systems. Several models and a wide class of mathematical tools for such task systems exist in the literature [START_REF] Commoner | Marked directed graphs[END_REF], [START_REF] Levner | A parametric critical path problem and an application for cyclic scheduling[END_REF], [START_REF] Lee | Synchronous data flow[END_REF], [START_REF] Chrétienne | Les réseaux de petri temporisés[END_REF], [START_REF] Serafini | A mathematical model for periodic scheduling problems[END_REF], [START_REF] Cohen | Algebraic tools for theperformance evaluation of discrete event systems[END_REF].

In this paper we focus on the powerful subclass of timed Petri nets [START_REF] Peterson | Petri Net Theory and the Modeling of Systems[END_REF] called timed weighted event graph model (TWEG). Transitions are associated with generic tasks and their firings have a given duration. Each place p has exactly one input and one output transition weighted by respective integer values w(p) and v(p): at the completion of a firing of the input transition of p, w(p) tokens are added to p. At the firing of the output transition of p, v(p) tokens are removed from p. If v(p) = w(p) = 1 for every place, the net is a timed event graph (in short TEG).

Although TWEGs model problems without resource conflicts, integer weights allow to model complex practical optimization problems.

In the context of manufacturing systems, TWEGs are considered to model assembly lines.

Operations (resp. products) are usually modelled by transitions (resp. tokens). Between two successive transformations, products (i.e. tokens) have to be stored or to be moved from one buffer to another. Cyclic production systems with batch scheduling, the assembling of products or buffers of limited capacity may easily be considered using this formalism [START_REF] Cavory | A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints[END_REF], [START_REF] Trouillet | Transformation of the cyclic scheduling problem of a large class of fms into the search of an optimized initial marking of a linearizable weighted t-system[END_REF]. Synchronous Data-Flow (SDF) [START_REF] Lee | Synchronous data flow[END_REF] is a well-known formalism considered for modeling embedded applications such as video compression treatment and is equivalent to TWEG. Here transitions represent processes and places model buffers. Tokens model data transferred from a process to another. Some practical optimization problems and examples can be found in [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF], [START_REF] Benazouz | A polynomial algorithm for the computation of buffer capacities with throughput constraint for embedded system design[END_REF], [START_REF] Govindarajan | Rate-optimal schedule for multi-rate dsp computations[END_REF], [START_REF] Bhattacharyya | Looped schedules for dataflow descriptions of multirate signal processing algorithms[END_REF].

When a TWEG that models an industrial application is given, the first question which comes to mind is whether a feasible infinite schedule exists or not, i.e. whether a TWEG is live or not.

The second concerns the construction of an optimal infinite schedule. A usual objective is to maximize the throughput λ = min t i ∈T {λ t i }, where λ t i measures the average number of firings of a transition t i by time unit.

An infinite schedule might be described either by a dynamic policy for each transition, or by an explicit description of its firing times. The former needs to define for each transition a finite policy describing when it may fire with respect to the state of its input places. The latter needs a finite representation of the infinite number of firing times, and thus some periodicity properties. Notice that if the underlying system does not have synchronization mechanisms, as for embedded system applications, an explicit description of the schedule is needed. In this paper we focus on the computation of explicit schedules.

The simplest policy for any TWEG (or TEG) is to fire transitions as early as possible. The resulting schedule is called the earliest schedule. This policy is feasible if and only if the TWEG is live, since there are no resource conflicts. Moreover, its throughput is maximum.

The computation of the earliest schedule raises two main problems: first, checking the liveness and computing the optimal throughput of a TWEG by running the earliest schedule may require an important number of transitions firings. Several authors proved, by studying the structure of the longest paths in a global precedence graph, that for TEGs [START_REF] Chrétienne | Les réseaux de petri temporisés[END_REF], [START_REF] Cohen | Algebraic tools for theperformance evaluation of discrete event systems[END_REF] and for TWEGs [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problèmed'assemblage[END_REF], the earliest schedule reaches a steady state depending on a set of circuits (called critical circuits) of the initial network. The number of firings required for its transitory phase has up to now been bounded for strongly connected TEG [START_REF] Hartmann | Transience bounds for long walks[END_REF] by a non polynomial function with respect to the instance size. The existence of polynomial upper bound (or the existence of a non polynomial lower bound) is an interesting open question.

Furthermore, this earliest schedule may not be polynomially represented. Indeed, it is proved in [START_REF] Bacelli | Synchronisation and Linearity: an Algebra for Discrete Event Systems[END_REF] for TEG that the number of firings needed to encode the steady state depends on the least common multiplier of the total markings of the critical circuits. The existence of a polynomial encoding for the steady state of a TEG is another interesting open question.

However, liveness and computation of the optimal throughput of TEGs are both polynomially solved [START_REF] Commoner | Marked directed graphs[END_REF], [START_REF] Chrétienne | Les réseaux de petri temporisés[END_REF], [START_REF] Reiter | Scheduling parallel computations[END_REF], [START_REF] Ramamoorthy | Performance evaluation of asynchronous concurrent systems using petri nets[END_REF], [START_REF] Ramchandani | Analysis of asynchronous systems by timed petri nets[END_REF]. Indeed, it has been shown that the liveness of a TEG is equivalent to the existence of a periodic schedule (in which a transition t i is fired every w i time units).

Moreover, the optimal throughput is reached by a periodic schedule that can be computed in polynomial time. Lastly, the size of its encoding depends linearly on the number of transitions: thus, many authors restrict their studies to this class of schedules to get an efficient solution, particularly in the presence of resource constraints (see for example [START_REF] Hanen | Cyclic scheduling on parallel processors: An overview[END_REF], [START_REF] Brucker | Tabu search algorithms for cyclic machine scheduling problems[END_REF]).

For a TWEG, the complexity of checking liveness and computing the optimal throughput remains open. However, it has been shown in [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problèmed'assemblage[END_REF] that any live bounded TWEG can be transformed into an equivalent TEG which might be of exponential size with respect to the size of the TWEG. So, this transformation, called expansion, cannot produce efficient algorithms in an industrial context. The existence of algorithms with polynomial time complexity to check the liveness of a TWEG and to compute an optimal schedule is a challenging problem from a theoretical as well as from a practical point of view.

The main purpose of this paper is to study the computation and the efficiency of periodic schedules for TWEGs. From a theoretical point of view, it can be viewed as a generalization of well-known results for TEGs. For practitioners, periodic schedules for TWEGs might easily be implemented in real systems (see for example [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF], [START_REF] Benazouz | A polynomial algorithm for the computation of buffer capacities with throughput constraint for embedded system design[END_REF]). Thus, even if they cannot outperform the earliest schedule with respect to the throughput, they might be used to get an easily encoded solution.

We establish in this paper that a TWEG might be live although no periodic schedule exists.

A polynomial condition for the existence of periodic schedules is stated, thus giving a sufficient condition of liveness. This is surprisingly similar to the one given in [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF]. We provide a polynomial specific algorithm, based on graphs algorithms, to compute the optimal periodic schedule. But we show that, unlike TEG, an optimal periodic schedule of a TWEG might not be optimal among all schedules. Its throughput is then a lower bound on the optimal throughput and the distance between these two values is experimentally investigated. Experiments show that if the initial marking is not too close to the minimum value that allows the existence of a periodic schedule, then periodic schedules might have a competitive throughput. This paper is organized as follows: basic definitions and an example modeling an assembly line are presented in Section II. Section III recalls a simplification of the weights of the places of a live bounded WEG, namely the normalization presented initially in [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF]. An original characterization of the minimum weights is then stated. Section IV deals with the characterization of periodic schedules, and defines the linear constraints met by feasible ones. The computation of an optimal periodic schedule is investigated in Section V. In Section VI, we study the throughput of periodic schedules on a subclass of TWEG. Section VII concludes the paper.

II. DEFINITIONS AND EXAMPLE

Definitions and assumptions related to WEG and TWEG are first presented. Then, we motivate the use of the TWEG model by showing an example of an assembly line problem with a batching transportation device.

A. Weighted event graphs

A weighted event graph H = (P, T, M 0 ) (in short WEG) is a decision-free Petri net given by a set of places P = {p 1 , . . . , p m }, a set of transitions T = {t 1 , . . . , t n } and an initial marking M 0 (p), p ∈ P .

Every place p ∈ P has exactly one input transition and one output transition. It is thus defined by the two transitions t i and t j and is denoted by p = (t i , t j ). For any transition t ∈ T , we denote by P + (t) = {p = (t, t ′ ) ∈ P, t ′ ∈ T } the set of output places of transition t. Similarly, P -(t) = {p = (t ′ , t) ∈ P, t ′ ∈ T } denotes the set of input places of t.

The arcs (t i , p) and (p, t j ) are weighted by strictly positive integers denoted respectively by w(p) and v(p). At each firing of the transition t i (resp. t j ), w(p) (resp. v(p)) tokens are added to (resp. removed from) place p. Figure 1 presents a place p = (t i , t j ) of a WEG. For any place p ∈ P , gcd p denotes the greatest common divisor of integers v(p) and w(p). It has been proven in [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF] that the initial marking M 0 (p) of any place p = (t i , t j ) may be replaced by M ⋆ 0 (p) = M 0 (p) gcdp

• gcd p without any influence on the feasible firing sequences of a WEG.

Roughly speaking, if M 0 (p) is not a multiple of gcd p , there will always be M 0 (p) -M ⋆ 0 (p) tokens remaining in p that will never be considered for the firings of t j . Thus in the rest of the paper, it is assumed that the initial marking M 0 (p) of any place p ∈ P is a multiple of gcd p .

If v(p) = w(p) = 1 for every place p ∈ P , then H is an event graph (in short EG), also called marked graph in [START_REF] Commoner | Marked directed graphs[END_REF].

For any integer ν > 0 and any transition t i ∈ T , t i , ν denotes the νth firing of t i .

A path µ of a WEG is a sequence of transitions t i 1 , . . . , t i k such that any two consecutive transitions t i j , t i j+1 are linked by a place p j = (t i j , t i j+1 ). A circuit is a closed path such that t i 1 = t i k . We denote by P µ the set of places crossed by µ.

t i t j p M 0 (p) w(p) v(p)

B. Timed weighted event graphs

A timed weighted event graph (in short TWEG) is a WEG H associated with a function ℓ : T → N -{0} such that, for any t ∈ T , ℓ(t) is the duration of a firing of t. It is usually denoted by G = (H, ℓ).

Firing a transition t i at time τ removes tokens from its input places according to the arcs values. Then, at time τ + ℓ(t i ), tokens are dropped into its output places. Thus for every place p = (t i , t j ) ∈ P , w(p) (resp. v(p)) tokens are added to p (resp. removed from p) ℓ(t i ) time units after the firing start time of t i (resp. at the firing start time of t j ).

M (τ, p) denotes the instantaneous marking of the place p ∈ P at time instant τ ≥ 0. Clearly,

M (0, p) = M 0 (p).
We assume that transitions are non-reentrant, i.e. that two successive firings of the same transition cannot overlap: this is modeled by loop places p = (t i , t i ), ∀t i ∈ T with w(p) = v(p) = 1 and M 0 (p) = 1. For the sake of readability, these loops are not shown in the figures. A TWEG is said to be a TEG if the underlying Petri net is an EG, i.e. if all weights are equal to 1.

C. Example

Let us now illustrate the modeling power of TWEGs through an example which combines cyclic assembling process, buffers, batch operations, and the limitation of the work-in-process.

We consider a three level assembling process shown in figure 2. At level 2, two parallel machines This automated process is modelled by 5 timed transitions representing the different operations.

Transitions and their corresponding durations are given by Table I. A model of this assembling line using a TWEG is depicted by figure 3.

M 1 M 2 I P level 2 level 1 level 0 2 3
Fig. 2. Levels for the assembling of products.

It is assumed that the line is empty at the beginning and that the work-in-process is at most 2 (in terms of finished products). So, there are at most 4 items processed by M 1 and 6 items by M 2 before a finished product outputs machine P (completion of firing of t 4 ), allowing 2 new tokens in p 3 and 3 new tokens in p 5 . That is modelled by the initial marking M 0 (p 3 ) = 4 and M 0 (p 5 ) = 6.

At the starting point, there are 6 items waiting to be processed by M 1 and 9 for M 2 . Places p 7 and p 8 model the buffers of items in front of M 1 and M 2 with the respective initial marking

M 0 (p 7 ) = 6 and M 0 (p 8 ) = 9.
The transporting device is modeled by transition t 5 and its adjacent places.

t 1 t 2 t 3 t 4 t 5 p 1 1 2 p 2 1 3 4 p 3 2 1 p 4 1 1 6 p 5 3 1 p 6 1 3 6 p 7 6 1 9 p 8 9 1
Fig. 3. Modeling an assembling line using a TWEG.

III. SIMPLIFICATION OF BOUNDED WEIGHTED EVENT GRAPHS

The aim of this section is to present a simplification of a bounded WEG, called minimal normalized WEG, and to characterize the values of its weights. This simplification is needed in the next section to compute the maximum throughput of a periodic schedule. We show that any polynomial algorithm on the minimal normalized WEG is also polynomial with respect to the size of the original WEG.

A simple well-known necessary condition of liveness is first recalled. A characterization of live bounded WEG is then presented. Next, we recall the normalization of a bounded WEG, as presented in [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF]. The last part is devoted to an original characterization of the minimal weights of a normalized WEG.

A. A necessary condition of liveness of a weighted event graph

A WEG is said to be live if each transition can be fired infinitely often. A TWEG is said to be live if its underlying WEG is live.

Liveness checking of an event graph H is a polynomial problem: setting the height of a circuit [START_REF] Commoner | Marked directed graphs[END_REF] that M 0 is a live marking if and only if the height of every circuit of H is not null. In the case of a WEG, up to now, no polynomial algorithm for liveness checking has been found: the algorithms developed to answer this question are not polynomial [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problèmed'assemblage[END_REF].

c of H to be H(c) = p∈Pc M 0 (p), it is proved in
However, a simple necessary condition of liveness has been noticed by several authors [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problèmed'assemblage[END_REF], [START_REF] Karp | Properties of a model for parallel computations: Determinacy, termination, queueing[END_REF], [START_REF] Teruel | On weighted T-systems[END_REF]. Let us define the gain [START_REF] Karp | Properties of a model for parallel computations: Determinacy, termination, queueing[END_REF] of every path µ of a weighted event graph H, denoted by

W (µ) as W (µ) = p∈Pµ w(p) v(p) .
Then, if a weighted event graph H is live, every circuit has a gain not less than 1. Intuitively, if W (c) < 1, the number of tokens decreases while firing transitions and tends to 0.

This condition is fulfilled by the WEG shown in figure 3. Note that this condition is not sufficient, since the liveness of a WEG also depends on the initial marking.

B. Bounded and unitary weighted event graphs

A WEG is said to be bounded if there exists an integer B such that the marking of any place p is not greater than B for any firing sequence.

As mentioned previously, if a WEG H is live, then every circuit c has a gain W (c) ≥ 1. Now, if W (c) > 1 or if H is not strongly connected, then the whole number of tokens in c will be unbounded. Thus, a live bounded WEG H is strongly connected and the gain of any circuit c of H equals 1. Any WEG which satisfies these two conditions is said to be unitary (or consistent) in the literature.

In the following, we suppose that WEGs considered are all unitary.

C. Normalization of a unitary WEG

A transition t i is normalized if all its input and output arcs have the same weight: there exists

(Z 1 , . . . , Z n ) ∈ (N -{0}) n such that    ∀p ∈ P + (t i ), w(p) = Z i , ∀p ∈ P -(t i ), v(p) = Z i .
A WEG is said to be normalized if all its transitions are normalized.

Note that a unitary WEG might not be normalized: for example, the WEG depicted by figure 3 is unitary, but transition t 4 is not normalized.

However, it is stated in [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF] that any unitary WEG can be polynomially transformed into an equivalent normalized WEG by multiplying weights and initial markings by positive integers α(p), p ∈ P such that ∀t i ∈ T there exists an integer Z i with

   ∀p ∈ P + (t i ), α(p)w(p) = Z i , ∀p ∈ P -(t i ), α(p)v(p) = Z i .
For any transition t i , Z i becomes the new weight of all arcs adjacent to t i . The corresponding initial marking of any place p = (t i , t j ) is then α(p)M 0 (p). Z = (Z 1 , . . . , Z n ) is called a normalization vector.

The two WEGs are equivalent in the sense that they both have the same firing sequences.

Hence in the rest of the paper, we will assume that WEGs are normalized, without loss of generality.

Note that the normalization concept is quite different from the traditional P -semiflow concept.

P -semiflows (they are left annullers of the incidence matrix) aim at finding invariants of the number of tokens in a Petri net, since the sum of the markings of the places belonging to the support of a P -semiflow is constant. Normalization aims at modifying the weights of the arcs to get an equivalent Petri net so that every circuit constitutes a support of a P -semiflow.

D. Minimum normalization of a unitary WEG

A normalization vector can be polynomially computed from the system defined above as in [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF]. However, the minimum solution of this system can be completely characterized, as stated by the following theorem:

Theorem 1. Let H be a WEG, and let

Z ⋆ = (Z ⋆ 1 , . . . , Z ⋆ n ), s.t. Z ⋆ i > 0, i ∈ {1, .
. . , n} be the minimum integer solution of the following system:

χ(H) : ∀p = (t i , t j ) ∈ P, Z i w(p) = Z j v(p) .
Z ⋆ is then the minimal normalization vector.

Proof: Every normalization vector Z is a solution of χ(H). Thus, if Z ⋆ is a feasible normalization vector, it is the minimum one.

By χ(H), Z ⋆ ∈ (N -{0}) n . We must prove that, for every place p = (t i , t j ), the initial

marking M ⋆ 0 (p) = Z ⋆ i w(p) M 0 (p) is an integer value. Clearly, M ⋆ 0 (p) = Z ⋆ i w(p) • M 0 (p) gcd p • gcd p .
Since by assumption M 0 (p) may be divided by gcd p , we must prove that Z ⋆ i can be divided by w(p) gcd p .

Let Q be the set of rationals and

∆ ∈ Q-{0}, such that Z ⋆ i w(p) = Z ⋆ j v(p) = ∆ gcd p . If ∆ ∈ Q-N,
then there is a couple of integers (r, q) ∈ (N -{0}) 2 such that gcd(r, q) = 1 and ∆ = r q . Since For example, the system χ(H) associated with the TWEG shown in figure 3 is:

Z ⋆ i = r q • w(p) gcd p and Z ⋆ j = r q • v(
                                     Z 1 = Z 3 2 Z 2 = Z 3 3 Z 4 2 = Z 1 Z 3 = Z 4 Z 4 3 = Z 2 Z 4 = Z 5 3 Z 5 6 = Z 1 Z 5 9 = Z 2
The minimum normalization vector is then Z ⋆ = (3, 2, 6, 6, 18). The associated minimum normalized TWEG is shown in figure 4.

The polynomial normalization algorithm of [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF] can be used, after few minor modifications, to compute Z ⋆ . The idea of the algorithm is to consider that the equation system χ(H) is a difference constraint system (with product and division instead of addition and substraction) [START_REF] Cormen | Introduction to Algorithms[END_REF],

which can be solved by using a shortest path algorithm on a graph.

Note that the size of a reasonnable encoding of this new WEG, which can be expressed as

O(n+m log(max t i ∈T Z i ))

IV. CHARACTERIZATION OF PERIODIC SCHEDULES

This section is devoted to properties of periodic schedules of a normalized bounded TWEG.

Thanks to the normalization recalled in Section III, our study can be reduced to this subclass of TWEGs. We first introduce schedules of TWEGs and precedence relations induced by a place.

Then we define periodic schedules, and we show that every place p defines a linear inequality on the starting times of the first firings of its adjacent transitions. From that we deduce that a periodic schedule with minimum periods is an optimal solution of a linear program.

A. Schedules

Let G be a TWEG. A schedule is a function s : T × (N -{0}) → Q + which associates, with any tuple (t i , q) ∈ T × (N -{0}), the starting time of the qth firing of t i . There is a strong relationship between a schedule and the corresponding instantaneous marking. Let p = (t i , t j ) be a place of P and R + -{0} the set of strictly positive real numbers. For any value τ ∈ R + -{0}, let us denote by E(τ, t i ) the number of firings of t i completed at time τ . More formally,

E(τ, t i ) =    0 if s(t i , 1) + ℓ(t i ) > τ max{q ∈ N -{0}, s(t i , q) + ℓ(t i ) ≤ τ } otherwise.
Similarly, B(τ, t j ) denotes the number of firings of t j started up to time τ and

B(τ, t j ) =    0 if s(t i , 1) > τ max{q ∈ N -{0}, s(t i , q) ≤ τ } otherwise.
Clearly, the instantaneous marking of place p at time τ is the initial marking plus the number of tokens produced by the firings of t i completed up to time τ minus the number of tokens removed from p by the firings of t j started up to time τ :

M (τ, p) = M (0, p) + w(p) • E(τ, t i ) -v(p) • B(τ, t j ).
A schedule (and its corresponding marking) is feasible if M (τ, p) ≥ 0 for every tuple (τ, p) ∈ (R + -{0}) × P . The throughput of a transition t i for a schedule s is defined by

λ s t i = lim q→∞ q s(t i , q) + ℓ(t i ) .
The throughput of s is the smallest throughput among the transitions throughputs

λ s = min t i ∈T {λ s t i }.

B. Precedence relations

Let us consider a TWEG G. The set of constraints induced by any place p = (t i , t j ) ∈ P on the firings of the adjacent transitions t i and t j may be expressed as classical precedence relations, inducing inequalities on each schedule. A schedule is then feasible if and only if it satisfies the precedence relations induced by places.

We say that p induces a precedence relation from the firing occurrence t i , ν i to that of t j , ν j if the two following conditions hold:

Condition 1: t j , ν j may occur after the end of t i , ν i ;

Condition 2: t j , ν j -1 may occur before the end of t i , ν i but t j , ν j may not.

Such a precedence relation induces the following inequality for any schedule s:

s(t i , ν i ) + ℓ(t i ) ≤ s(t j , ν j ). (1)
The following lemma was proved in [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problèmed'assemblage[END_REF] and characterizes the set of precedence relations induced by a place: Lemma 1. A place p = (t i , t j ) ∈ P of a TWEG G induces a precedence relation from the ν i th firing of t i to the ν j th firing of t j if and only if

w(p) > M 0 (p) + w(p)ν i -v(p)ν j ≥ max{w(p) -v(p), 0}.
Moreover, it is stated in [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problèmed'assemblage[END_REF] that a schedule fulfils the precedence relations defined by Lemma 1 if and only if it is feasible. For example, inequalities associated with the place shown in figure 5 are:

2 > 1 + 2ν i -3ν j ≥ 0 If 1 + 2ν i -3ν j = 0, then we get the couples (ν i , ν j ) = {(1 + 3k, 1 + 2k), k ∈ N}. Similarly, if 1 + 2ν i -3ν j = 1, (ν i , ν j ) = {(3 + 3k, 2 + 2k), k ∈ N}.
Lemma 2 characterizes the couples of strictly positive integers (ν i , ν j ) for which a precedence relation from the firings t i , ν i to t j , ν j exists.

Lemma 2. Let us consider a place p = (t i , t j ) ∈ P of a TWEG G, and let the integer values

k min = max{w(p) -v(p), 0} -M 0 (p) gcd p and k max = w(p) -M 0 (p) gcd p -1.
1) If p induces a precedence relation from the firings t i , ν i to t j , ν j then there exists

k ∈ {k min , . . . , k max } such that w(p)ν i -v(p)ν j = k • gcd p .
2) Conversely, for any k ∈ {k min , . . . , k max }, there exist an infinite number of tuples (ν i , ν j ) ∈ (N-{0}) 2 such that w(p)ν i -v(p)ν j = k•gcd p and p induces a precedence relation between firings t i , ν i and t j , ν j .

Proof:

1) Since gcd p = gcd(v(p), w(p)), for any tuple (ν i , ν j ) ∈ (N -{0}) 2 there exists k ∈ Z such that w(p)ν iv(p)ν j = k • gcd p . Now, if there is a precedence relation from t i , ν i to t j , ν j , we get by Lemma 1, as we assumed that M 0 (p) is a multiple of gcd p ,

w(p) -M 0 (p) > w(p)ν i -v(p)ν j ≥ max{w(p) -v(p), 0} -M 0 (p),
which is equivalent to

w(p) -M 0 (p) -gcd p ≥ k • gcd p ≥ max{w(p) -v(p), 0} -M 0 (p)
and thus k min ≤ k ≤ k max .

2) Conversely, there exists (a, b) ∈ Z 2 such that aw(p)bv(p) = gcd p . Then for any k ∈ {k min , . . . , k max }, and any integer q ≥ 0, the couple of integers (ν i , ν j ) = (ka+qv(p), kb+ qw(p)) is such that w(p)ν i -v(p)ν j = k•gcd p . Thus p induces a precedence relation between t i , ν i and t j , ν j , which achieves the proof.

C. Periodic schedules

Let Q + denotes the set of positive rationals. A schedule s is periodic if there exists a vector w = (w 1 , . . . , w n ) ∈ Q +n such that, for any couple (t i , q) ∈ T ×N-{0}, s(t i , q) = s(t i , 1)+(q -1)w i .

w i is then the period of the transition t i and λ s t i = 1 w i its throughput.

In [START_REF] Reiter | Scheduling parallel computations[END_REF], Reiter proved that it is always possible to compute an optimal periodic schedule with a unique period ( i.e. ∀t i ∈ T , w i = w), for a subclass of computation graphs [START_REF] Karp | Properties of a model for parallel computations: Determinacy, termination, queueing[END_REF] equivalent to TEGs. This result has been later obtained by Ramchandani in [START_REF] Ramchandani | Analysis of asynchronous systems by timed petri nets[END_REF].

For a TWEG, each transition needs its own period. Consider for example the place p = (t i , t j )

shown in figure 5 with ℓ(t i ) = ℓ(t j ) = 2: three firings of t i are needed for firing t j twice, thus we must have 3w i ≤ 2w j , and so w i = w j . Figure 6 presents a feasible periodic schedule with periods w i = 2 and w j = 3 and starting times s(t i , 1) = 0 and s(t j , 1) = 3.

t i t j p 1 2 3
Fig. 5. A place p = (ti, tj).

D. A linear program for periodic schedules

Let G be a unitary normalized TWEG. By using the results of the previous subsections, we now establish a set of inequalities that have to be met by a periodic schedule s of G.

t i , 1 t i , 2 t i , 3 t i , 4 t i , 5 t i , 6 t i , 7 t j , 1 t j , 2 t j , 3 t j , 4
Fig. 6. A periodic schedule for transitions ti and tj and place p = (ti, tj) presented by figure 5.

Let us consider a transition t i and any output place p of t i . The place p receives Z i tokens from t i every w i time units. So, on average, a token is produced on p every w i Z i time units. We call average token flow time of t i the ratio w i Z i . The following theorem establishes that in any periodic schedule, all transitions have the same average token flow time K, and that feasible periodic schedules satisfy linear inequalities.

Theorem 2. Let G be a unitary normalized TWEG. For any feasible periodic schedule s, there exists a strictly positive rational K, called the average token flow time of s such that, for any transition t i ∈ T , w i Z i = K. Moreover, the precedence relations associated with any place p = (t i , t j ) are fulfilled by s if and only if

s(t j , 1) -s(t i , 1) ≥ ℓ(t i ) + K(Z j -M 0 (p) -gcd p ).
Proof: Let p = (t i , t j ) ∈ P be a place inducing a precedence relation from t i , ν i to t j , ν j .

According to inequality (1), and since s is periodic, we get

s(t i , 1) + (ν i -1) • w i + ℓ(t i ) ≤ s(t j , 1) + (ν j -1) • w j .
By Lemma 2, there exists k ∈ {k min , . . . , k max } such that

ν j = w(p)ν i -k • gcd p v(p) and
s(t j , 1) -s(t i , 1) ≥ ℓ(t i ) + w j -w i + ν i w i - w(p)ν i -k • gcd p v(p) • w j .
So,

s(t j , 1) -s(t i , 1) ≥ ℓ(t i ) + w i - w(p) v(p) w j ν i + 1 + k • gcd p v(p) w j -w i .
This inequality must be true for arbitrarily large values ν i ∈ N -{0}, so w i -w(p) v(p) w j ≤ 0 and then

w i w(p) ≤ w j v(p) . As G is normalized, w(p) = Z i and v(p) = Z j . Since G is unitary, it
is strongly connected and thus, for any place p = (t i , t j ),

w i Z i = w j Z j
. So, there exists a value

K ∈ Q -{0} such that, for any transition t i ∈ T , w i Z i = K.
Then, the previous inequality becomes

s(t j , 1) -s(t i , 1) ≥ ℓ(t i ) + KZ j 1 + k • gcd p Z j -KZ i
and thus

s(t j , 1) -s(t i , 1) ≥ l(t i ) + K(Z j -Z i + k • gcd p ).
Now, the right member increases with k and according to Lemma 2, there exists

(ν i , ν j ) ∈ (N -{0}) 2 such that k = k max = Z i -M 0 (p) gcd p - 1
s(t j , 1) -s(t i , 1) ≥ ℓ(t i ) + K(Z j -Z i + Z i -M 0 (p) -gcd p )
which is equivalent to

s(t j , 1) -s(t i , 1) ≥ ℓ(t i ) + K(Z j -M 0 (p) -gcd p ).
Conversely, assume this last inequality and that ∀t i ∈ T , w i Z i = K. Then, for any integers ν i and ν j with w(p)ν iv(p)ν i = k • gcd p for k ∈ {k min , . . . , k max }, it can be proved that s checks the precedence relation from t i , ν i to t j , ν j using similar arguments.

For the example shown in figure 3, the average token flow time and the periods of a periodic schedule satisfy:

w 1 3 = w 2 2 = w 3 6 = w 4 6 = w 5 18 = K.
Moreover, the equations associated with the places p 1 , . . . , p 8 are:

                                     s(t 3 , 1) -s(t 1 , 1) ≥ 2 + 3K s(t 3 , 1) -s(t 2 , 1) ≥ 2 + 4K s(t 1 , 1) -s(t 4 , 1) ≥ 10 -12K s(t 4 , 1) -s(t 3 , 1) ≥ 2 s(t 2 , 1) -s(t 4 , 1) ≥ 10 -12K s(t 5 , 1) -s(t 4 , 1) ≥ 10 + 12K s(t 1 , 1) -s(t 5 , 1) ≥ 12 -18K s(t 2 , 1) -s(t 5 , 1) ≥ 12 -18K
According to Theorem 2 the average token flow time of a schedule defines entirely the periods of the transitions and thus their throughput. Thus maximizing the throughput can be expressed as minimizing the average token flow time through a linear program:

Corollary 1. An optimal periodic schedule is a solution of the following linear program:

         M in K ∀p = (t i , t j ) ∈ P, s(t j , 1) -s(t i , 1) ≥ ℓ(t i ) + K(Z j -M 0 (p) -gcd p ). ∀t i ∈ T, s(t i , 1) ≥ 0 V.

POLYNOMIAL TIME ALGORITHMS FOR THE EXISTENCE AND THE COMPUTATION OF AN OPTIMAL PERIODIC SCHEDULE

Although linear programming provides a polynomial solution for checking existence of periodic schedules and computing an optimal one, specific algorithms on graphs often have a lower complexity (e.g longest paths, network flows). They also provide a deeper understanding of unfeasibility or optimality. In this section, we investigate graph properties on which the computation of periodic schedules rely and we develop polynomial time algorithms for both problems for normalized TWEGs.

A. Existence and performance of periodic schedules

In this subsection, we establish that checking the existence of periodic schedules can be expressed as finding a circuit of non positive value in a valued oriented graph.

Let us first build a bi-valued graph G = (T, E, L, H) as follows: the nodes of G are the transitions, and any place p = (t i , t j ) induces an arc e from node t i to node t j . The two valuations of this arc are L(e) = ℓ(t i ) and H(e) = M 0 (p) + gcd pv(p). Let c be a circuit of G.

We note L(c) the summation of L(e) over all arcs e crossed by c. Similarly we define H(c). For any value K ∈ Q -{0}, we also denote by G K = (T, E, δ K ) the graph G defined previously but which arcs are valued by δ K (e) = L(e) -KH(e).

According to Theorem 2, starting times {s(t i , 1), t i ∈ T } exist for a fixed value of the average token flow time K ∈ Q -{0} if and only if the sum of the valuations δ K on every circuit c of G K is such that δ K (c) = e∈c δ K (e) ≤ 0. This induces the following necessary and sufficient condition of existence of periodic schedules:

Theorem 3. Let G be a unitary normalized TWEG and C(G) the set of circuits from G. There exists a periodic schedule if and only if for every circuit c of G, H(c) > 0. Moreover, if this condition is fulfilled, and if

K min = max c∈C(G) L(c) H(c)
, and Z max = max

t i ∈T {Z i }
then for any K ≥ K min there exists a periodic schedule s with average token flow time K and throughput

λ s = 1 KZ max .
Proof: To prove that the condition is necessary, let us suppose that there exists a circuit c of G with H(c) ≤ 0. Then, for every value K ∈ Q -{0}, δ K (c) > 0 and no periodic schedule exists.

To prove that the condition is sufficient, assume that for each circuit c of G, H(c) > 0. Let us consider any K ≥ K min . Then, for each circuit c of G K , δ K (c) ≤ 0. By Theorem 2, there is a set of constraints that rules the existence of periodic schedule with average token flow time K. This set of constraints is clearly a system of difference constraints [START_REF] Cormen | Introduction to Algorithms[END_REF]. As δ K (c) ≤ 0, there exists a periodic schedule with average token flow time K. The period of a task i in this schedule is w i = KZ i , so that the throughput of the schedule is λ s = 1 max i∈{1,...,n} {w i } Surprisingly, the condition expressed by Theorem 3 is similar to a sufficient condition of liveness of a WEG proved in [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF] with different arguments. It is also proved that this condition is a necessary and sufficient condition of liveness for circuits composed by two transitions. So, the following corollary can easily be deduced:

Corollary 2. Let G be a unitary normalized TWEG composed by a circuit of two transitions. G is live if and only if G has a periodic schedule.

This corollary does not hold for circuits with 3 transitions. For example, let us consider the normalized TWEG G shown in figure 7 with no particular assumption on firing durations. The sequences of firings s = t 3 t 1 t 1 t 1 t 2 t 3 t 1 t 1 t 1 t 1 t 2 t 2 can be repeated infinitely, so it is live. However,

3 i=1 M 0 (p i ) = 28 and 3 i=1 (v(p i ) -gcd p i ) = 29
, so the condition of Theorem 3 does not hold. Thus this circuit has no periodic schedule.

B. Computation of an optimal periodic schedule

Assume that G is a bounded TWEG. From Section III, it can be transformed to an equivalent normalized TWEG using a polynomial time algorithm. Three steps are then required to compute, if it exists, a periodic schedule of maximum throughput.

1) Check that H(c) > 0 for every circuit c of G: An algorithm of time complexity bounded by O(max{nm, m max t i ∈T {log Z i }}) can be found in [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF] to check this condition.

2) Computation of K min : Several polynomial and pseudo-polynomial algorithms were developed to compute the critical circuit of a graph, which will give the K min value (see. for example [START_REF] Dantzig | Finding a cycle in a graph with minimum cost to time ratio with applications to a ship routing problem[END_REF], [START_REF] Gondran | Graphs and algorithms[END_REF], [START_REF] Gondran | Les problèmes de ratio minimum en optimisation combinatoire[END_REF]). An experimental study of these algorithms can be found in [START_REF] Dasdan | Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems[END_REF].

Then, for every transition t i ∈ T , we set w ⋆ i = K min Z i and the optimum throughput is

λ s ⋆ = 1 K min .Zmax .
3) Starting times of an optimal periodic schedule: The set of constraints associated with a periodic schedule s can be viewed as a system of difference constraints ( [START_REF] Cormen | Introduction to Algorithms[END_REF]). Thus, if we add a dummy source node φ to G K min and ∀t i ∈ T a null weighted arc (φ, t i ), computing the starting times {s(t i , 1), t i ∈ T } is equivalent to determine for each node t i ∈ T the maximal length of a path from φ to t. This classical graph problem is polynomially solved using Bellmann-Ford algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF]. First step of the algorithm used on this example concludes that for any circuit c, H(c) > 0 and thus, a periodic schedule exists. At step 2, K min = 13 is computed from the bivalued graph by considering its critical circuit c = (t 2 , t 3 , t 4 , t 5 , t 2 ) with L(c) = 2 + 2 + 10 + 22 = 36 and H(c) = -4 + 0 -12 + 18 = 2. As Z max = 18, the maximum throughput of a periodic schedule is λ s = 1 13×18 = 1 234 . Then, the optimal periods are computed: w ⋆ 1 = 39, w ⋆ 2 = 26, w ⋆ 3 = 78, w ⋆ 4 = 78 and w ⋆ 5 = 234. Figure 9 depicts the graph G 13 (omitting the dummy node) and starting times {s ⋆ (t i , 1), t i ∈ T } computed in step 3 of the algorithm.

VI. OPTIMAL PERIODIC THROUGHPUT VERSUS OPTIMAL THROUGHPUT

The aim of this section is to compare the maximal throughput of a periodic schedule with those of the earliest schedule. First we show that for a circuit with two places the throughput of a periodic schedule may be quite far from the optimum if the initial marking is minimum with respect to the condition of existence stated in Theorem 3. We then show in Section VI-B that if the initial marking of a timed weighted circuit is sufficiently large, the optimal periodic schedule has an optimal throughput. Then we present an experimental study of the ratio between optimal periodic throughput and optimal throughput for circuits; it suggests that periodic schedules might be competitive compared to optimal schedules when the initial marking is a small percentage greater than the minimum initial marking.

A. Circuit with two places

Let us consider a normalized TWEG which consists of a circuit with two places p 1 = (t 1 , t 2 ),

p 2 = (t 2 , t 1 ) such that gcd p 1 = gcd p 2 = 1, M 0 (p 1 ) = v(p 1 ) + w(p 1 ) -1 = Z 2 + Z 1 -1 and
M 0 (p 2 ) = 0. This TWEG has the minimal initial marking such that the condition stated in Theorem 3 holds: M 0 (p 1 ) + M 0 (p 2 ) + gcd p 1 + gcd p 2 -Z 2 -Z 1 = 1. The associated bi-valued graph G is then shown in figure 10.

t 1 t 2 (l(t 1 ), Z 1 ) (l(t 2 ), Z 2 ) (l(t 1 ), Z 1 ) (l(t 2 ), 1 -Z 1 )
Fig. 10. Bi-valued graph G associated with the normalized TWEG with two places.

We get

K min = max ℓ(t 1 ) Z 1 , ℓ(t 2 ) Z 2 , ℓ(t 1 ) + ℓ(t 2 ) = ℓ(t 1 ) + ℓ(t 2
) and the throughput of transitions for the optimum periodic schedule s ⋆ per is λ

s ⋆ per t 1 = 1 w ⋆ 1 = 1 Z 1 (ℓ(t 1 )+ℓ(t 2 )) and λ s ⋆ per t 2 = 1 w ⋆ 2 = 1 Z 2 (ℓ(t 1 )+ℓ(t 2 )
) . Now, since the number of tokens in the circuit is Z 1 + Z 2 -1, in any schedule transitions t 1 and t 2 will never fire simultaneously. Moreover, if we denote by n 1 (resp.

n 2 ) the number of firings of t 1 (resp. t 2 ) such that the system will return in its initial state (i.e.

with Z 1 + Z 2 -1 tokens in p 1 and 0 tokens in p 2 ), then we must have n 1 Z 1n 2 Z 2 = 0, so there exists k ∈ N -{0} with n 1 = kZ 2 and n 2 = kZ 1 . Thus, the throughput of transitions t 1 and t 2 for the earliest schedule s e is λ se

t 1 = Z 2 Z 2 ℓ(t 1 )+Z 1 ℓ(t 2 ) and λ se t 2 = Z 1 Z 2 ℓ(t 1 )+Z 1 ℓ(t 2 ) . Now, R = λ se t 1 λ s ⋆ per t 1 = λ se t 2 λ s ⋆ per t 2 = Z 1 Z 2 (ℓ(t 1 ) + ℓ(t 2 )) Z 2 ℓ(t 1 ) + Z 1 ℓ(t 2 ) .
Assume without loss of generality that Z 1 ≥ Z 2 , then

R = λ se λ s ⋆ per = λ se t 1 λ s ⋆ per t 1 = Z 1 Z 2 ℓ(t 1 ) + Z 1 ℓ(t 2 ) -(Z 1 -Z 2 )ℓ(t 2 ) Z 2 ℓ(t 1 ) + Z 1 ℓ(t 2 ) . So, R = Z 1 1 - (Z 1 -Z 2 )ℓ(t 2 ) Z 2 ℓ(t 1 ) + Z 1 ℓ(t 2 ) < Z 1 .
The ratio R is then maximum when ℓ(t 1 ) tends to infinity and the bound max{Z 1 , Z 2 } is asymptotically reached. We conclude that this ratio is not bounded by a constant value.

B. Periodic schedule of a circuit

We now consider a TWEG for which the underlying graph is a circuit C. We define a relevant range of values {x min , . . . , x max } for the initial marking x of C such that if x < x min no periodic schedule exist, whereas if x ≥ x max the optimal periodic throughput equals the optimal throughput. We then define a value x ⋆ ≥ x max which is independent on the durations of the transitions, that we use as an upper bound of initial markings in the next experimental section.

Let us consider a circuit C = (t 1 , p 1 , t 2 , . . . , t n , p n , t 1 ) of n transitions and n places with n ≥ 2. We also set t n+1 = t 1 in order to simplify the expressions below. Let us consider x = n i=1 M 0 (p i ). We define by K min (x) the minimum average token flow time of the circuit for an initial marking value x. Let us set

V = n i=1 (Z i -gcd(Z i , Z i+1 )), x min = V + 1, K ⋆ = max t i ∈T ℓ(t i ) Z i .
According to Theorem 3, a periodic schedule exists if and only if H(C) > 0, i.e. x ≥ x min . Now, assuming x ≥ x min , we get:

K min (x) = max c∈C(G) L(c) H(c) = max K ⋆ , L(C) H(C) = max K ⋆ , L(C) x -V .
Notice that tokens distribution in the different places has no incidence on the minimum average token flow time. Let x max be the minimum integer value such that K min (x) = K ⋆ . Then, we have

L(C) x max V ≤ K ⋆ and L(C) x max -1 -V > K ⋆ and thus x max = L(C) K ⋆ + V. Now, if x min ≤ x ≤ x max , then K min (x) = L(C) x -V . Theorem 4 follows.
Theorem 4. The throughput of an optimal periodic schedule s ⋆ per for the normalized circuit C with initial marking x is:

λ s ⋆ per (x) =    x-V L(C) • 1 Zmax if x min ≤ x < x max , 1 K ⋆ • 1 Zmax if x ≥ x max .
Moreover, if x ≥ x max , λ s ⋆ per (x) equals λ se (x), the throughput of the earliest schedule.

Proof: As transitions are non-reentrant, the throughput of the earliest schedule s e is bounded as follows:

λ se (x) ≤ 1 K ⋆ Z max , ∀x ≥ x min .
As the the earliest schedule is optimum, we have λ se (x) ≥ λ s ⋆ per (x), ∀x ≥ x min .

Then ∀x ≥ x max , λ se (x) = 1 K ⋆ Z max = λ s ⋆ per (x).
However, the earliest schedule may reach this maximum throughput for a smaller value of

x. For instance, let us consider a normalized TWEG which consists of a circuit of two places the schedule s ⋆ per has idle times for both transitions whereas t 1 can be fired periodically without idle time in the schedule e .

p 1 = (t
x min , the value x max depends on the durations {ℓ(t i ), t i ∈ T }. The following proposition defines an upper bound for x max which does not depend on the durations, that will be used in our experiments. For this purpose, let us define x ⋆ as follows:

x ⋆ = n i=1 Z i + V. Proposition 1. x max ≤ x ⋆ . Moreover, if there exists ρ ∈ Q, ρ > 0 such that, ∀i ∈ {1, . . . , n}, ℓ(t i ) Z i = ρ, then the bound is tight (i.e. x ⋆ = x max ). Proof: Let i ⋆ ∈ {1, . . . , n} such that ℓ(t i ⋆ ) Z i ⋆ = max t i ∈T ℓ(t i ) Z i
. Then, for all t i ∈ T , it follows that

Z i ⋆ n i=1 ℓ(t i ) ≤ ℓ(t i ⋆ ) n i=1 Z i n i=1 ℓ(t i ) n i=1 Z i ≤ max t i ∈T ℓ(t i ) Z i L(C) K ⋆ ≤ n i=1 Z i .
That implies x max ≤ x ⋆ . Now, if there exists ρ ∈ Q +⋆ such that, ∀i ∈ {1, . . . , n}, ℓ(t i ) Z i = ρ, then K ⋆ = ρ and we have

x max = L(C) K ⋆ + V = n i=1 ρZ i ρ + V = n i=1 Z i + V = x ⋆ .
Hence, the second part of the lemma holds.

C. Experimental study of circuits

We ran our experiments on randomly generated normalized circuits C in order to analyze the ratio R between optimal throughput and periodic optimal throughput in function of the initial marking and the size of the circuit.

For any fixed integer value n corresponding to the number of transitions, the integer values Z i and the durations ℓ(t i ), i ∈ {1, . . . , n} are randomly fixed respectively in {1, . . . , 100} and {1, . . . , 50}. By Theorem 4 and Proposition 1, {x min , . . . , x ⋆ is a relevant range of initial markings. In order to study the influence of the initial marking, with respect to the feasibility condition of periodic schedules, we introduce a parameter f which measures the relative increase of tokens in this interval. Thus, we set x = x min + ⌈f • n i=1 Z i ⌉ for different values of f in [0, 1) (from 0 to 1 with step 0.02). The optimal throughput was obtained by running the earliest schedule until the throughput of transitions converges.

We first considered the special case f = 0, depicted by figure 12, for which the initial marking is the minimum number such that there exists a periodic schedule. It appears that the ratio may then be very important (up to 268) and much greater than the bound observed for circuits with two transitions. Moreover, the mean and max ratio roughly increase with the number of transitions, even if some decreasing parts can be observed. Then we observed that while for lower values of f the mean and the max ratio increase with n, once f gest above 0.02, this trend is reversed, both ratios decrease when n increases. Moreover, the mean ratio is less than 1.8 for n ≥ 10, and very close to 1 for n ≥ 50.

This could be understood by considering that if f > 0.02, enough flexibility is given to the system, so that the influence of the periodic firing of a transition is limited to its close neighbours, and does not so much affect the overall performance, whereas if f = 0, the artificial waiting times of transitions introduced by the periodic behavior will be accumulated along the circuit, since there are not enough tokens, thus increasing the largest period. Finally, if we consider the variation of the ratio in terms of the value f , shown in figure 14, we observe that the ratio (mean and max) decreases dramatically. For f = 0.02 the mean ratio equals 5, whereas when f ≥ 0.08 the mean ratio is less than 2 and reaches 1 for f = 0.8.

We can also notice that in all the experiments, the mean and the max curves are quite far from each other, due to a few number of worst case instances that have a huge ratio compared to the transition durations and the values of the arcs.

These experiments suggest that periodic schedule might be very competitive for TWEGs if the initial marking is not too close to the minimum value, i.e. if for any circuit c of a TWEG, M 0 (c) >> p∈Pc v(p)gcd p . This gives a first insight on the quality of the optimal periodic throughput with respect to optimal one. In the future, we shall run experiments on more complex graphs.

VII. CONCLUSIONS

In this paper we established a condition of existence and a polynomial algorithm to compute the optimal periodic schedule of a TWEG based on graph reformulation. Experiments prove that although such schedules are suboptimal, their computation might provide an interesting lower bound on the optimal throughput if the condition of existence stated in Theorem 3 is not tight, i.e. if the initial marking is large enough.

In the future, it would be interesting to derive a lower bound on the ratio between the optimal throughput and the optimal periodic throughput of a general TWEG, and to further study the complexity of the liveness problem.

Fig. 1 .

 1 Fig. 1. A place p = (ti, tj) of a WEG.

M 1 and M 2

 2 are working on items, one item at time. Machine I at level 1 loads two parts produced by M 1 and three parts produced by M 2 and assembles them to get one product, finished at level 0 by a single machine P . A batching transportation device removes 3 finished products from the workshop and brings 6 items to machine M 1 and 9 to machine M 2 .

Fig. 4 .

 4 Fig. 4. Equivalent minimum normalized TWEG.

  , thus the precedence relation holds if and only if

Fig. 7 .

 7 Fig. 7. G is live but has no periodic schedule.

Figure 8

 8 Figure 8 presents the bi-valued graph G associated with the normalized TWEG of figure 4.

Fig. 9 .

 9 Fig. 9. G13 and starting times s ⋆ (ti, 1), ti ∈ T (in circles) associated with the TWEG of figure 4.

Fig. 12 .

 12 Fig. 12. Mean and worst ratio for f = 0 increase with the number of transitions.

Fig. 13 .

 13 Fig. 13. Mean and max ratio decreases as the number of transitions n increases for f ≥ 0, 02.

Fig. 14 .

 14 Fig. 14. Mean and worst ratio decrease when f increases.

  is polynomial in terms of the initial encoding O(n+m log(A)). Indeed, if A is the maximum weight of an arc in the original WEG, Z i ≤ A n , and thus log(max t i ∈T Z i ) ≤ n log(A), so that the encoding of the new WEG is O(n + nm log(A)). This theoretical point ensures that the normalization step preserves the polynomial complexity of any polynomial algorithm that handles any of the two WEGs (normalized or not).

													18
	3	t 1	3	3	p 1	6	t 3	12 p 3 6	p 4	6	t 4	6	p 7		t 5	18
	2	t 2	2	2	p 2	6		12 p 5			6	p 8 6	p 6	18	18
													18

  Fig. 11. A TWEG G for which the schedule se reaches the best throughput whereas the schedule s ⋆ per cannot.

		3		s e	t 2	t 1	t 2	t 1	t 2
	t 1	3	2	t 2
		4		s ⋆ per		t 1 t 2	t 2	t 1	t 2

1 , t 2 ), p 2 = (t 2 , t 1 ) and such that ℓ(t 1 ) = 4 and ℓ(t 2 ) = 2 (see. figure

11

). For this initial marking, we have K min = 1.5 and then w ⋆ 1 = 4.5 and w ⋆ 2 = 3 . One can see on figure

11

, that

This work was supported by the NANO2008 project