Optimization of the time durations by exploiting time margins in Time Interval Models Philippe Declerck

Abstract-Considering Time Interval Models, which can describe a large class of models including Timed Event Graphs and P-time Event Graphs, a general aim is to control the system such that it follows a 1-periodic behavior starting from an initial state with a minimal or maximal cycle time. The aim of this paper is the optimization of the time durations in order to achieve a given rate of production when the quantity of resources (number of pallets, machines,...), usually represented by the initial marking, is assumed to be a fixed datum. A prior step is the determination of the critical subsystems, whose variations can influence these optimal values and affect the obtainment of the relevant trajectories, and the non-critical subsystems leading to time margins. Two approaches are proposed in that aim. A first technique is based on an adaptation of the classical Martínez and Silva's algorithm, where each solution gives a critical subsystem, while a second approach checks each inequality of the system by an optimality verification. Using this partition of the subsystems and particularly exploiting the time margins corresponding to idle times of machines, the approach allows an optimization of the non-critical time durations when the extremum cycle times and the resources are the constant parameters of the problem. In this paper, the definition of P-time Event Graphs is generalized by introducing the model of Time Supervisor Place which restricts the time behavior of a set of places. The approach is applied to a plant bakery composed of two production lines. keywords: Petri nets, Time Interval Model, P-time Event Graphs, cycle time, time margin, critical, linear programming, food industry, transportation network

I. INTRODUCTION

In this paper, we consider an algebraic model named Time Interval Model, which covers a large scope of models such as Timed Event Graphs, P-time Event Graphs and P-time Event Graphs with Affine-Interdependent Residence Durations ( [START_REF] Declerck | Extremum Cycle Times in Time Interval Models[END_REF], Chapter 3 in [START_REF] Declerck | Discrete Event Systems in Dioid Algebra and Conventional Algebra[END_REF], [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF]). Time Interval Models are dynamical linear inequality systems of the form A.x ≤ b, where the variable x represents the dates of the events, and "." denotes the usual matrix multiplication. The first objective of the present paper is to introduce a new class of systems that can be modeled as a Time Interval Model: P-time Event Graphs with Time Supervisor Place. Time Supervisor Places limit the admissible residence time of tokens within a set of places by introducing additional time constraints, which otherwise, could not be modeled in standard P-time Event Graphs. Our definition is different from the macro-places which are often used to create hierarchical Petri nets and to improve the readability of Petri nets by hiding substructures. P. Declerck is with LISA/LARIS EA4094, University of Angers, 62 avenue Notre-Dame du Lac, 49000 Angers, France. Tel. +33 241 226560 -Fax. +33 241 226561 E-mail. philippe.declerck@univ-angers.fr As Time Supervisor Places restrict the time behavior of a set of places, they cannot be implicit places which have the property that their addition to or their removal from a net system does not change its behavior, i.e., an implicit place represents redundancy [START_REF] Silva | Simplification des réseaux de Petri par élimination de places implicites[END_REF]. Therefore, usual macroplaces and implicit places do not extend the expressiveness of the modeling contrary to the Time Supervisor Places which enlarge the definition of the places of the P-time Event Graphs.

The extremum cycle time (remember that the production rate is the inverse of the cycle time) is clearly a crucial notion as it gives a picture of the possible speeds followed by the process. Let us consider a cost criterion depending the time durations of the places when the desired behavior is a periodic schedule. Practically, this cost criterion can express an energy saving or a financial economy produced by a slow-down of machines relevant to a subset of places, as a slow-down of a vehicle in a transportation system or a choice of slower vehicles. The slow-down of a machine, which is expressed by an increase of the lower bound of the relevant time duration, is possible as the end of a task does not always correspond to the beginning of another task by reason of time margins. Symmetrically, the upper bound can express a security limit for the workers as a place can describe a noisy equipment (e.g. a jackhammer) or a dangerous situation (e.g. a chemical hazard, a nuclear irradiation): in that case, the minimization of the upper bound is clearly an objective for a manager who desires to keep in good health a team which is exposed to these potential dangers. In the food industry, the quality of the product will be damaged if the cooking is too long and the reinforcement of this limit reduces the risk of unwanted manipulations. The same objective happens if the employees are paid hourly and the manager desires to reduce the financial cost by limiting overtime hours.

The objective of this paper is the optimization of the cost criterion function of the limits of the time durations where the process, here the Time Interval Model, follows a 1-periodic trajectory for a given cycle time. This problem allows the modeling of optimization problems in which we may optimize the speeds of the machines or better select the processing times, for instance if we have the choice between several machines with different speeds. This aim implies the resolution of two problems beforehand:

-The computation of the cycle time when the parameters of the Time Interval Model are assumed to be constant. When a Timed Event Graph or a P-time Event Graph is considered, values have been assigned to the initial marking and time durations.

-The analysis of the effects of the time durations on the cycle time. Indeed, a well-known fact in production management is that a critical task is relevant to a null time margin when the optimal path in the PERT graph (or better the Roy's potentialtask graph) is computed. For Timed Event Graphs, it may be observed that a limited variation of some time durations can influence the production rate while a modification of some other durations has no effect.

In the first case, the relevant substructures are named critical as they cannot be modified: if the process undergoes the corresponding unwanted variations, this situation shows a vulnerability of the process as it leads to a loss of controllability, that is, the non-attainment of the desired 1-periodic trajectory. Examples of systems presenting a weak robustness are as follows: a seasonal harvest can have an insufficient production produced by an unexpected closed frontiers limiting the flow of necessary workers; hospitals can be in a degraded mode coming from a lack of appropriate personal protective equipment; the passenger flow in a railway system can be perturbed by a military attack against critical infrastructures as shunting systems.

In the second case, the non-critical substructures can be considered as free parameters which can be modified and optimized. Indeed, the existence of time margins implies that some variations of non-critical relations are neutral. Therefore, an optimization of the system for a given production rate can have an effect on the non-critical subsystems but must keep the critical subsystems which determine the production rate. In that aim, a prior objective is the localization of the critical and non-critical relations.

Let us make the connections with some related works. In a manner of speaking, the problem considered in this paper is dual to the resource optimization problem [START_REF] Gaubert | Resource Optimization and (min,+) Spectral Theory[END_REF] [27] as we assume that the quantity of resources (typically, the number of pallets, machines,...) usually represented by the initial marking is a constant of the problem when a Petri net is considered. The study [START_REF] Gaubert | Resource Optimization and (min,+) Spectral Theory[END_REF] for Timed Event Graphs minimizes the cost of the resources needed to obtain (at least) a given periodic throughput while for the class of Timed Weighted Marked Graphs, the problem in [START_REF] Zhou He | Cycle time optimization of deterministic timed weighted marked graphs by transformation[END_REF] consists in finding an initial marking to minimize the cycle time while the weighted sum of tokens in places is less than or equal to a given value. Focusing on hardware circuits, [START_REF] Millo | Periodic scheduling of marked graphs using balanced binary words[END_REF] studies the representation under the form of a marked graph describing the communication channels and the computation of the components. The main problem is to minimize the size of memory resources used as buffer through the interconnection wires. Taking the ASAP (As Soon As Possible) semantic, contrary to this proposed paper, [START_REF] Millo | Periodic scheduling of marked graphs using balanced binary words[END_REF] gives an algorithm which consists in computing the best ASAP execution where execution rate is maximal and memory resources are minimal.

In this proposed paper, we can consider the model of P-time Event Graphs which was introduced in [START_REF] Khansa | Réseaux de Petri P-temporels[END_REF] and the model of Negative Event Graphs [START_REF] Lee | An Extended Event Graph With Negative Places and Tokens for Time Window Constraints[END_REF] which generalizes Timed Event Graphs [START_REF] Jeng | Comments on Timed Petri Nets in Modeling and Analysis of Cluster tools[END_REF] [15] [START_REF] Millo | Periodic scheduling of marked graphs using balanced binary words[END_REF]. A difference with [START_REF] Hanen | Periodic schedules for linear precedence constraints[END_REF] is that the linear precedence constraint graph cannot consider a maximum time duration.

The paper [START_REF] Campos | Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector[END_REF] addresses the problem of computing upper and lower bounds for the throughput of transitions in Petri net models having a unique consistent firing count vector. This paper identifies two interesting subclasses of nets having this characteristic (persistent nets and mono-T-semiflow nets) and contains a discussion of their ergodicity conditions. The Petri nets are bounded and the time interpretation is associated with transitions contrary to this proposed paper. [START_REF] Benabid-Najjar | Periodic Schedules for Bounded Timed Weighted Event Graphs[END_REF] focuses on the existence of periodic schedules connected to the critical circuits while the proposed paper generalizes this last concept to critical subsystems which can be circuits but not only. An interesting result illustrated by Fig. 7 in [START_REF] Benabid-Najjar | Periodic Schedules for Bounded Timed Weighted Event Graphs[END_REF] is that the system might be live although no periodic schedule exists. The liveness is out the scope of the proposed paper but clearly, the existence of a periodic schedule gives a sufficient condition of liveness. [START_REF] Benabid-Najjar | Periodic Schedules for Bounded Timed Weighted Event Graphs[END_REF] studies the influence of the initial marking with respect to the feasibility of the periodic schedules while the problem is here dual as the proposed paper is the optimization of the time durations in order to achieve a given rate of production when the initial marking is assumed to be a fixed datum. Based on the firing speeds of transitions, some studies focus on a control problem in first-order hybrid Petri nets: [START_REF] Dotoli | A First-Order Hybrid Petri Net Model for Supply Chain Management[END_REF] proposes controllers that employ the knowledge of the system state in order to exhibit a satisfactory performance in terms of throughput and product inventory levels while [START_REF] Balduzzi | First-order hybrid Petri Nets: A model for optimization and control[END_REF] makes a sensitivity analysis of throughput if a machine produces faster.

In general, a technique based on graph theory can only be employed for small systems as a simple search of any circuit faces a combinatorial explosion of the number of circuits (the complexity given Section 3.1.13 in [START_REF] Gaubert | Théorie des systèmes linéaires dans les dioïdes[END_REF] is e.(n-1)! with e=2.718). Moreover, an important characteristic of the articles [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF], Chapter 3 in [START_REF] Declerck | Discrete Event Systems in Dioid Algebra and Conventional Algebra[END_REF], [START_REF] Declerck | Extremum Cycle Times in Time Interval Models[END_REF], [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF], and this proposed paper is that each relation of the model can make the connection between more than two events. In that case, graph theory cannot direcly be applied, and a generalization must be studied. A solution is to develop an approach based on the linear programming. Note that the studies [START_REF] Campos | Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector[END_REF] [START_REF] Zhou He | Cycle time optimization of deterministic timed weighted marked graphs by transformation[END_REF] are limited to two events.

[15] [18] [19] [23] [20] [3] [22] [26]
In this paper, we assume that we can control all the dates of the state which allows to practically build the 1-periodic trajectory. We assume the feasibility of the 1-periodic trajectory on an infinite trajectory (this point is discussed in [START_REF] Declerck | Extremum Cycle Times in Time Interval Models[END_REF]). Contrary to the papers [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF] [START_REF] Declerck | Extremum Cycle Times in Time Interval Models[END_REF] which analyze the existence of the extremum cycle times and present techniques allowing the computation of the optimal trajectories, the proposed paper focus on the optimization of the time durations and contains two original techniques for determining the critical subsystems. Different from [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF], where the algorithm exploits directly the variations of time durations, the proposed approaches 1 and 2 are structural as no variation of durations is considered and the algorithms do not compute trajectories or initial conditions.

The paper is organized as follows: in Section II, we describe the Time Interval Model which can describe P-time Event Graphs with Time Supervisor Places. The concept of Time Supervisor Place is illustrated by a simple example of a company composed of two workers in Section II-D and a plant bakery composed of two production lines in Section IV. The aim is presented in section III-A while the computation of the optimal trajectories is remembered in section III-A. Section III-B introduces the concept of min-critical (respectively, maxcritical) subsystem and presents two techniques to determine these subsystems. It presents a new structural analysis based on the Martínez and Silva's algorithm [START_REF] Martínez | A simple and Fast Algorithm to Obtain all Invariants of a Generalised Petri Net, Application and Theory of Petri Nets[END_REF] in Section III-C and an original classification of the relations based on the checking of each relation with respect to the critical characteristic in Section III-D. Three examples illustrate the approaches. The example of the plant bakery described in [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] presents now a Time Supervisor Place which modifies its behavior.

II. ALGEBRAIC MODEL

In the paper, "resp." is an abbreviation of "respectively". The notation |E| stands for the cardinality of the set E while the notation A i,. corresponds to row i of matrix A. The transpose of the matrix A is denoted A t . Let us first introduce the following main notations which are defined in the rest of the paper if necessary:

• P is the set of places denoted p i , P sp is the set of Time Supervisor places, P = P ∪ P sp , q = |P | and, I = {1, . . . , 2.q}. • M is the current marking, M 0 is the initial marking and, M i is the marking of place p i . • m is the maximum number of tokens in the initial marking. • W is the incidence matrix.

• G -and G + are structural matrices defining the TIM and determining H, N. • T -, T + are the lower and upper time durations and, θ = ((-T -) t , (T + ) t ) t .

• T R is the set of transitions which are denoted x i and n = |T R|. • k ∈ N is the number of events.

• x i (k) ∈ R represents the date of the k th firing associated with transition x i . • λ represents the cycle time and, λ min, λ max are the minimal and maximal cycle times respectively. • ∆ is the vector of time margins.

• Y, Y -, Y = , Y + are sets of row-vectors denoted y.

A. Time Interval Model

In this paper, we focus on the following algebraic model which is named Time Interval Model (TIM) defined over R

G - G + . x(k) x(k + 1) ≤ -T - T + , (1)
for k ≥ 0 where: x(k -1) and x(k) ∈ R n ; T -and

T + ∈ (R ∪ {-∞,+∞}) q ; G -= G - 1 G - 0 and G + = G + 1 G + 0 ∈ R q ×2.
n . The addition of the constraints x(k) ≥ x(k -1) in the algebraic model guarantees that the trajectory is non-decreasing. In this paper, we assume the consistency of the TIM [START_REF] Balduzzi | First-order hybrid Petri Nets: A model for optimization and control[END_REF], that is, the existence of a state trajectory over R on an infinite horizon. For simplicity, we do not distinguish a relation and its relevant index and, a relation whose index is i is directly written "relation i" with i ∈ I = {1, . . . , 2.q}.

Below, the aim is to illustrate the possibilities of modeling of the Time Interval Models which can describe P-time Event Graphs and also the Time Supervisor Places which is an original model. Note that the study [START_REF] Becha | Modelling, Analysis and Control of Electroplating Line Modelled by P-Time Event Graphs[END_REF] proposes an algebraic model named implicit discrete model which is close to the interval model but with the restriction of a symmetric form. The problems solved in Section III directly consider the TIM (1) without being specific to particular Time Event Graphs and the relevant structures of matrices G -and G + .

In a first reading, the following section can be skipped as Section III exploits directly model [START_REF] Balduzzi | First-order hybrid Petri Nets: A model for optimization and control[END_REF].

B. Preliminary remarks on Petri nets

A brief description of the Petri nets and P-time Event Graphs is now presented. A Petri net is a pair (GR, M 0 ), where GR = (V, AR) is a bipartite graph defined as follows: the set V is a finite number of nodes which are partitioned into disjoint sets of places P and transitions T R; the set AR consists of pairs of the form (p i ,x j ) and (x j ,p i ) with p i ∈ P and x j ∈ T R. The initial marking M 0 is a vector of dimension |P | whose elements denote the number of initial tokens in the respective places and M 0 i is the initial marking of the place p i ∈ P . The set

• p i (resp., p • i ) is the set of input (resp., output) transitions of p i ∈ P . The set • x i (resp., x • i )
is the set of input (resp., output) places of the transition x i ∈ T R. For a Petri net with |P | places and |T R| transitions, the incidence matrix

W = [W ij ] is a |P | × |T R| matrix of

integers and its entry is given by

W ij = W + ij -W - ij where W + ij ≥ 0
is the weight of the arc from transition j to place i, and W - ij ≥ 0 is the weight of the arc from place i to transition j. The characteristic vector s of a firing sequence S is such that each component of s is a natural number corresponding to the number of firings of the corresponding transition. A marking M reached from an initial marking M 0 by the firing of a sequence S, can be calculated by the fundamental relation: M = M 0 +W.s where W.s is the usual matrix product of W by vector s. A Petri net is called an Event Graph if each place has exactly one input and one output transition: formally,

| • p| = |p • | = 1 (∀p ∈ P ).
All arc weights of the event graphs considered below are unitary. A Timed Event Graph is a triple (GR, M 0 , f ) where (GR, M 0 ) is an Event Graph and the mapping f : P → R + associates with each place p l a time duration.

C. P-time Event Graphs

To describe time constraints on tokens in P-time Event Graphs [START_REF] Bonhomme | Marking Estimation of P-Time Petri Nets With Unobservable Transitions[END_REF] [6], we associate a temporal interval defined in

R + × (R + ∪ {+∞}) with each place: each place p l ∈ P is associated with an interval [T - l , T + l ],
where T - l is the lower bound and T + l is the upper bound. A P-time Event Graph is a triple (GR, M 0 , f ) where (GR, M 0 ) is an Event Graph, and the mapping f :

P → R + × (R + ∪ {+∞}) associates with each place p l an interval [T - l , T + l ] with 0 ≤ T - l ≤ T + l .
Each considered event is the firing of transition x i ∈ T R and the relevant date is usually denoted x i (k) ∈ R with k ∈ N for the sake of simplicity. Let m ∈ N be the maximum number of the initial tokens: m = max{M 0 l |l ∈ {1, |P |}}. A numbering of the events can be made if we assume a FIFO (First In First Out) functioning of the places which guarantees that the tokens do not overtake one another and the absence of token deaths. Therefore, the following system can describe a P-time Event Graph for each place p l ∈ P where each place p l links one upstream transition {x j } = • p l and one downstream transition

{x i } = p • l . x p • l (k) -x• p l (k -M 0 l ) ∈ [T - l , T + l ] (2)
The rewriting of (2) leads to the form of the TIM (1) defined over R. We take the assumption m ∈ {0, 1} which is not limiting as we can apply the building given in appendix of [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF]. To summarize, the column-vectors -T -and

T + are duration vectors of dimension |P | and interval [T - l ,T + l ] is the time interval of place p l ; the dimension of G -= [G - 1 G - 0 ] and G + = [G + 1 G + 0 ] is equal to |P | x (2).|T R|; so, q = |P | and n = |T R|. Matrices G -and G + express time connec-

tions inside the time Petri net and matrix

G - G + presents a symmetric form as we have G + = -G -. Some connections between the rows of W and G -are made in the following property when m = 1.

Property 1: [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF], Chapter 3 in [START_REF] Declerck | Discrete Event Systems in Dioid Algebra and Conventional Algebra[END_REF] and [START_REF] Declerck | Extremum Cycle Times in Time Interval Models[END_REF] Let us assume that m = 1. For each place p l ∈ P , we have:

(G - 0 ) l,. = W l,. and (G - 1 ) l,. = 0 if M 0 l = 0 ; (G - 0 ) l,. = -(W -) l,. and (G - 1 ) l,. = (W + ) l,. if M 0 l = 1.

Example 1

The inequalities describing the elementary P-time Event Graph of Fig. 1 relatively to places p 1 , p 2 , p 3 are as follows.

   T - 1 ≤ x 2 (k) -x 1 (k -1) ≤ T + 1 T - 2 ≤ x 1 (k) -x 2 (k -1) ≤ T + 2 T - 3 ≤ x 2 (k) -x 1 (k -1) ≤ T + 3 So, we ob- tain n = |T R| = 2 , q = |P | = 3, T -=   T - 1 T - 2 T - 3   , T + =   T + 1 T + 2 T + 3   , G - 1 =   1 0 0 1 1 0   , G - 0 =   0 -1 -1 0 0 -1   , G + 1 = -G - 1 and G + 0 = -G - 0 .
Moreover, we have shown that the TIM (1) can describe P-time Event Graphs with affine-interdependent residence durations [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF]: in general, each entry in column-vectors T -and T + is a time duration of a place but this usual interpretation is generalized in the case of affine-interdependent residence durations, that is, a residence duration of a token in a place determines the time duration of another place. The equality G + = -G -is not kept and the inequalities expressed by the TIM (1) can contain three or four variables contrary to the bi-variable inequalities (2) of the P-time Event Graphs. Finally, these new relations are more complex since the coefficients depend not only on the entries of the incidence matrix in {-1, 0, 1} but also on the coefficients of the affine interdependence over R.

D. Time Supervisor Places

We now present another possibility of the TIM [START_REF] Balduzzi | First-order hybrid Petri Nets: A model for optimization and control[END_REF]. Let us add some specifications to the considered model under the form of a set of Time Supervisor Places denoted P sp (sp for supervisor places) which extends the initial set of places P of the Petri net. The complete set of places is P = P ∪ P sp . The relevant marking (respectively, initial marking) of the event graph with supervisor places is denoted M (resp., M 0, ); so, M is a subvector of M . We consider a set of additional constraints l ∈ {1, . . . , |P sp |} where each constraint represented by a Time Supervisor Place supervises the behavior of a subset of places P l ⊂ P. The Time Supervisor Place relevant to the subset P l ⊂ P is denoted as a standard place p |P |+l ∈ P sp but its index |P | + l starts at |P | + 1 and finishes at |P | + |P sp | = |P |. Its current marking (resp., initial marking) is the sum of the marking of the places of P l , that is,

M |P |+l = p l ∈P l M l (resp., M 0 |P |+l = p l ∈P l M 0 l ).
We can now generalize the definition (2) to a set of places where the additional constraint expresses lower and upper bounds to the sum of place durations. Formally, the constraint of a Time Supervisor Place p |P |+l ∈ P sp is algebraically defined by

p l ∈P l (x p • l (k) -x• p l (k -M 0 l )) ∈ [T - |P |+l , T + |P |+l ] (3)
for l ∈ {1, . . . , |P sp |}. The analysis of [START_REF] Benabid-Najjar | Periodic Schedules for Bounded Timed Weighted Event Graphs[END_REF] shows that this definition can also describe a place of a P-time Event Graph when |P l | = 1 : in that case, the sum in (3) disappears. Therefore, each place is a Time Supervisor Place and this new model includes the model of P-time Event Graphs. Moreover, the definition of Time Supervisor Place needs only a time evolution of a Petri net and is separated from the definition of the P-time Petri net: it implies that Time Supervisor Places can be applied to other models as timed Petri nets and time Petri nets. The above relation (3) can easily be rewritten under the form of TIM [START_REF] Balduzzi | First-order hybrid Petri Nets: A model for optimization and control[END_REF]. Equality G + = -G -is kept and matrix G -is defined as follows.

Property 2: Let us assume that m = 1. For each Time Supervisor Place p i with i = |P | + l and l ∈ {1, . . . , |P sp |}, we have:

(G - 0 ) i,. = p l ∈P l (G - 0 ) l,. = p l ∈P l |M 0 l =0 W l,.
-

p l ∈P l |M 0 l =1 (W -) l,. and
(G - 1 ) i,. = p l ∈P l (G - 1 ) l,. = p l ∈P l |M 0 l =1 (W + ) l,. . Proof.
Immediate from the definition of the constraint of a Time Supervisor Place (3) and the previous property 1. Example 2 Fig. 2 considers a customer whose building is being renovated by a company composed of two workers. The relevant jobs correspond to places p 1 and p 3 . The firing of x 3 expresses the end of the renovation. The company wants a maximum payment for this work which is calculated from the presence of two workers, whereas the customer wants a minimum payment. Assuming that the presence of a token in a place corresponds to an effective task of a worker, we consider that the sum of the tasks associated with p 1 and p 3 must belong to the interval [T - 5 , T + 5 ]. This constraint defines the Time Supervisor Place p 5 relevant to the places p 1 and p 3 which is represented by an oval in grey. The additional constraint 1 is: the sum of the task durations associated with p 1 and p 3 must belong to the interval [T - 5 , T + 5 ] = [START_REF] Gaubert | Resource Optimization and (min,+) Spectral Theory[END_REF][START_REF] Gros | DEA report in "Biotechnologies et Industries Alimentaires[END_REF].

So, T - 5 ≤ (x 3 (k) -x 1 (k -1)) + (x 3 (k) -x 2 (k -1)) ≤ T + 5 or +x 1 (k -1) + x 2 (k -1) -2.x 3 (k) ≤ -T - 5 -x 1 (k -1) -x 2 (k -1) + 2.x 3 (k) ≤ T + 5 . (G - 1 ) 5,. = -(G + 1 ) 5,. = 1 1 0 and (G - 0 ) 5,. = -(G + 0 ) 5,. = 0 0 -2 .
Therefore, a Time Supervisor Place can be seen as an additional place having a set of input and output transitions (the Time Supervisor Place p 5 has two input transitions in Example 2) which implies that the general structure is no longer an event graph: the model cannot be described by a bipartite graph or equivalently by an incidence matrix which presents at most two entries per row. Moreover, a row in matrices G -and G + can present entries different from 1, -1 and 0 as shown in Example 2. As a consequence, a problem considering Time Supervisor Places cannot be solved completely by classical graph theory, and so, we will use linear programming in the following sections.

To summarize, the general form of TIM (1) can describe P-time Event Graphs with Time Supervisor Places under a modification of the set of places which is now P . So, q = |P |. The term m is relevant to the set P of places of the P-time Event Graphs and the expression m = max{M 0 l |l ∈

III. OPTIMIZATION OF THE TIME DURATIONS

A. Aim and principle

Let u be a unitary vector with |u| = |x(k)| = n, that is, u = (1 . . . 1)

t . A basic objective is to control the TIM (1) such that it follows a 1-periodic trajectory which is now defined. Definition 1: [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] The TIM (1) follows a 1-periodic behavior when its trajectory satisfies equality x(k + 1) = λ.u + x(k) for k ≥ 0 where λ is the cycle time.

The following relations can simply be deduced after the introduction of x(k + 1) = λ.u + x(k) in TIM (1):

H.x(k) + N.λ ≤ θ (4)
with

H = G - 1 + G - 0 G + 1 + G + 0 , N = G - 0 .u G + 0 .u and θ = -T - T +
. The dimensions of these matrices are respectively (2.q × n), (2.q × 1) and (2.q × 1).

The difference θ -(H.x(k) + N.λ) provides a vector of time margins denoted ∆ 2.q×1 = (∆ - q×1 ) t (∆ + q×1 ) t t which can be used to improve the behavior of each equipment by modifying the time durations. Indeed, if we subtract a component of ∆ in the right-hand side θ of (4), it corresponds to increase

T - i (-T - i → -T - i -∆ - i ) or to decrease T + i (T + i → T + i -∆ + i
) under the condition that the time durations are finite.

Example 1 continued

In place p 1 , a token created from the firing of transition x 1 at time x 1 (k -1) is available at time x 1 (k -1) + T - 1 for the firing x 2 (k) but its use is not immediate in general: the token must wait during the duration

x 2 (k) -(x 1 (k -1) + T - 1 )
. Considering that this time margin is useless in general, an increase of the time duration T - 1 which corresponds to a slow-down of the task represented by place p 1 can reduce it. Therefore, the choice of the greatest time leads to a value which can be added to the time duration T - 1 if the general constraints of the problem are kept.

Symmetrically, the token death which can occur at the time x 1 (k -1) + T + 1 can express a loss of quality of a product (excessive baking) or a security rule (e.g. noisy equipment, dangerous situation). The available duration is

x 1 (k -1) + T + 1 -x 2 (k)
which is also a time margin which can be exploited. We can desire to reenforce the specifications and to fix more strict official rules: the search of the best time margin under the general constraints of the problem yields a value which can be subtracted to the time duration T + 1 . Inequality (4) for a given λ describes a set of possible relevant 1-periodic trajectories. The objective is the optimization of a cost criterion function of the limits of the time durations by exploiting the time margins where the process, here the Time Interval Model (1), follows a 1-periodic trajectory defined by (4) for a given cycle time. The linear programming problem which focuses on the maximization of the time margins for a given cycle time λ is defined as follows:

max(c.∆) with c ≥ 0 such that H I 2.q×2.q 0 I double q×2.q . x(k) ∆ ≤ θ -N.λ T + -T - for k ≥ 0
with x(k), ∆ ≥ 0 and I double q×2.q = I q×q I q×q .

(5) Naturally the condition T - i ≤ T + i for each relation must be satisfied and the condition T - i + ∆ - i ≤ T + i -∆ + i is added in the linear programming problem. This aim needs the resolution of two other problems beforehand:

-The computation of the possible cycle times λ when H, N, θ in (4) are constant. The variables of the problem are x(k) and λ. The approach is remembered in Section III-A -The analysis of the time durations which can modify the given cycle time λ and improve the value of the criterion c.∆. This study is treated in Section III-B.

An example of the maximization of the time margins based on ( 5) is made in Example 3 Section IV.

Remark. For the sake of clarity, the cost criterion in the above problem is linear but more general criterion can be chosen as a quadratic criterion. Moreover, the problem can be adapted to treat the case of a finite set of possible modifications of the time durations. Let Ψ = {v 1 , v 2 , . . . , v |Ψ| } be the relevant set of possible values for the time margin ∆ i . So, ∆ i = i=1,...,|Ψ| z i .v i where z i is a boolean variable satisfying i=1,...,|Ψ| z i = 1 as a unique choice is possible. The linear programming problem becomes a mixed-integer linear programming problem after applying the same technique to any time margin.

In fact, (4), and any problem using it as (5) consider an infinite horizon k ≥ 0. The following definition and results solve this difficulty.

Definition 2: [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] TIM (1) is said to be forwardhomogeneous (resp., backward-homogeneous) if any trajectory of TIM ( 1) is invariant by shifting with any positive delay (resp., negative delay), that is: if a trajectory x(k) satisfies (1), then the trajectory x(k) + ω.µ.u with ω = 1 (resp., ω = -1) also satisfies (1) for any delay µ ∈ R with µ > 0. TIM (1) is said to be strictly-homogeneous when it is forwardhomogeneous and backward-homogeneous.

The following theorem gives an algebraic way to analyze the homogeneity of the TIM (1).

Theorem 1: [START_REF] Declerck | Extremum Cycle Times in Time Interval Models[END_REF] [12] TIM (1) is forward-homogeneous (resp., backward-homogeneous) if and only if H.ω.u ≤ 0 with ω = 1 (resp., ω = -1) . TIM (1) is strictly-homogeneous if and only if H.u = 0.

Theorem 2: When H.ω.u ≤ 0 with ω = 1, TIM (1) satisfies x(k + 1) = λ.u + x(k) for any k ≥ k 1 for some given cycle time λ if this assertion holds for a given k = k 1 .

Proof. We assume that the trajectory {x(k 1 ), x(k 1 + 1)} with x(k 1 + 1) = x(k 1 ) + λ.u satisfies (1) with k = k 1 . If H.ω.u ≤ 0 with ω = 1, Theorem 1 says that the TIM (1) is forward-homogeneous: by definition, if an elementary trajectory {x(k 1 ), x(k 1 + 1)} satisfies (1), we can deduce that {x(k 1 ) + ω.µ.u, x(k 1 + 1) + ω.µ.u} also satisfies (1) for any non-negative µ ∈ R. Taking the particular value µ = λ, we can deduce that {x(k 1 )+λ.u, x(k 1 +1)+λ.u} also satisfies [START_REF] Balduzzi | First-order hybrid Petri Nets: A model for optimization and control[END_REF]. As {x(k 1 ) + λ.u, x(k 1 + 1) + λ.u} = {x(k 1 + 1), x(k 1 + 1) + λ.u} satisfies (1) with x(k) = x(k 1 + 1) and x(k + 1) = x(k 1 + 1) + λ.u, k corresponds to k 1 + 1 and finally, the trajectory {x(k 1 + 1), x(k 1 + 2)} with x(k 1 + 2) = x(k 1 + 1) + λ.u satisfies [START_REF] Balduzzi | First-order hybrid Petri Nets: A model for optimization and control[END_REF]. As the reasoning can be repeated for {x(k 1 ) + i), x(k 1 + 1) + i} with i ≥ 2, the result is proved.

Consequently, the consideration of a given k is sufficient in the maximization of the time margins [START_REF] Campos | Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector[END_REF] and the following problems using (4), if the TIM (1) is forward-homogeneous. This assumption is taken in the sequel.

An objective is to determine the minimum or maximum cycle time such that the TIM (1) follows a 1-periodic behavior starting from k = 0. If we assume the consistency of ( 4), the problems of minimization and maximization of the cycle time λ can be written under the following form of a linear programming problem [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF] Remark. The desired 1-periodic trajectory facilitates the presentation of the approach but can be extended to more general periodic behaviors as the e-periodic trajectories starting at k = 1 with a cyclicity e = 1. So, the expression x(k) = λ.u + x(k -1) for k ≥ 1 and the unitary vector u is replaced by x(k + e) = γ.u + x(k -1) for k ≥ 1 and the cycle time is λ = γ e . For a cyclicity e, we can compute a eperiodic trajectory by following the same technique. The initial step is to develop the system on a horizon and to establish an inequality similar to [START_REF] Campos | Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector[END_REF]. Sequences with different periodic behaviors can also be considered.

B. Critical and non-critical subsystems

An objective of this paper is the analysis of the 2.q relations of TIM (1) presenting the form

G - G + i,. . x(k) x(k + 1) ≤ θ i (6)
with i ∈ I = {1, . . . , 2.q} and precisely the determination of the min-critical (resp., max-critical) relations relevant to minimum cycle time (resp., maximum cycle time). A characteristic feature of Timed Event Graphs is that, for the places of a circuit presenting the maximum ratio, a small variation of any time durations can modify the value of the minimum cycle time. We now generalize the concept of these critical places to the notion of critical relations. Definition 3: [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] The relation i ∈ I in TIM ( 1) is said min-critical (resp., max-critical) for the minimization (resp., maximization) if there is a small variation of θ i which modifies the optimal value of the cycle time.

Considering P-time Event Graphs with Time Supervisor Places, the sets of min-critical pairs (p i , |θ i |) relevant to relation i ∈ I (resp., non-min-critical pairs) are denoted P crit min (resp., P non-crit min

). So, P crit min ∩ P non-crit min = ∅ and the places relevant to first elements of the pairs of P crit min ∪ P non-crit min define P . A symmetrical notation is used for the max-critical pairs with P crit max and P non-crit max . For a P-time Event graph, each relation corresponds to a pair (p i , T - i ) for i ∈ {1, . . . , q} or (p i-q , T + i-q ) for i ∈ {q + 1, . . . , 2.q} and the variation is on T - i or T + i . Note that a relation i corresponding to an infinite θ i cannot be critical as it cannot lead to a variation of the optimal value of the cycle time.

Example 1 continued.

Let T - 1 = 1, T - 2 = 5, T - 3 = 3, T + 1 = 6, T + 2 = 7, T + 3 = 8.
If the upper bounds of the time durations are neglected, a Timed Event Graph is obtained. Let us apply the classical technique where the minimum cycle time for Timed Event Graphs is based on the consideration of the circuits and is determined by the calculation of the maximum of the ratios defined by the sum of the time durations to the sum of the number of the initial tokens, for each elementary circuit: so, λ min = max( , that is, we give the possibility to slow down the process relevant to place p 1 without modifying the maximum speed 1/λ min of the whole system. As a time margin for a trajectory operating at the minimum cycle time is available, it can be reduced. However, as explained in the introduction, a simple search of any circuit faces a combinatorial explosion of the number of circuits [START_REF] Gaubert | Théorie des systèmes linéaires dans les dioïdes[END_REF]. In addition, the resolution made by the linear programming problem I provides the extremum cycle time but the optimal solution κ is not unique as different solutions x(0) and different time margins can be obtained. It is worth noting that the time margin is null when a relation i is critical, but the converse is not true in general. Therefore, other approaches must be developed.

T - 1 +T - 2 2 , T - 3 +T - 2

C. Approach 1 using Martínez and Silva's algorithm

The determination of the critical relations can exploit the following theorem which analyzes the existence of a 1-periodic trajectory without its computation. Let Y = {y ∈ R 1×2.q | y.H = 0 with y ≥ 0} with the following partition

Y = Y -∪ Y = ∪ Y + where Y -= {y ∈ Y | y.N = -1} Y = = {y ∈ Y | y.N = 0} Y + = {y ∈ Y | y.N = 1} (7)
and consider the two conditions

(∀y ∈ Y = ) y.θ ≥ 0 (8)
and

λ min = max ∀y∈Y -(-y.θ) ≤ λ max = min ∀y∈Y + (y.θ). (9)
Theorem 3: [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] When H.ω.u ≤ 0 with ω = 1, TIM (1) satisfies x(k + 1) = λ.u + x(k) for any k ≥ 1 for some given cycle time λ, if and only if constraints ( 8) and ( 9) are satisfied.

Inequality λ min ≤ λ max can be seen as a consistency condition. As Theorem 3) says that λ min = max ∀y∈Y -(-y.θ) and λ max = min ∀y∈Y + (y.θ), we can deduce that the minimal cycle time is the maximum of the possible terms -y.θ for any y ∈ Y -and the maximal cycle time is the minimum of the possible terms y.θ for any y ∈ Y + . This point implies that an arbitrary vector y ∈ Y -(resp. y ∈ Y + ) can correspond or not to the optimal cycle time λ min (resp. λ max ). The expression λ min = max ∀y∈Y - (-y.θ) (resp., λ max = min ∀y∈Y + (y.θ)) also shows that each relation relevant to a non-null entry y i of y ∈ Y -(resp., y ∈ Y + ) leading to the optimal cycle time (that is, -y.θ = λ min (resp., y.θ = λ max )) represents a critical relation i ∈ I as a small variation of the relevant entry θ i with the pertinent sign can modify the optimal value. Naturally, this interpretation holds for every non-null entry y i for each y ∈ Y -(resp., y ∈ Y + ) leading to the optimal cycle time and the relevant vectors y can be named min-critical (resp., max-critical) : only some vectors of Y -(resp., Y + ) are critical. Therefore, a synthesis of the relevant supports of min-critical (resp., max-critical) vectors with respect to the non-null entries gives the sets of min-critical and max-critical relations, respectively. The computation of all the vectors of Y can be made by an adaptation of the classical Martínez and Silva's algorithm which allows the determination of every Pinvariant [START_REF] Martínez | A simple and Fast Algorithm to Obtain all Invariants of a Generalised Petri Net, Application and Theory of Petri Nets[END_REF]. Note that even if the concepts are close, the row-vector y below is over R 1×2.q and is not a P-invariant (also named P-semiflow) which is a vector of N q . Example 1 continued.

We have

H = 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1 t , N = -1 -1 -1 1 1 1 t and x(k) = x 1 (k) x 2 (k) t .
For the condition y.H = 0 with y ≥ 0, the application of the classical Martínez and Silva's algorithm can provide the following integer solutions: y 1 = 1 1 0 0 0 0 , y 2 = 0 1 1 0 0 0 , y 3 = 0 0 0 0 1 1 , y 4 = 0 0 0 1 1 0 , y 5 = 1 0 0 1 0 0 , y 6 = 1 0 0 0 0 1 , y 7 = 0 0 1 1 0 0 , y 8 = 0 0 1 0 0 1 and, y 9 = 0 1 0 0 1 0 . 2) The conditions y.N = -1, y.N = +1 and y.N = 0 yields a classification and a modification of the vectors as follows:

Y -= { y1 2 , y2 2 } , Y + = { y3 2 , y4 2
} and, Y = = {y 5 , y 6 , y 7 , y 8 , y 9 }. 3)

λ min = max(-y.θ) = max( T - 1 +T - 2 2 , T - 2 +T - 3 2 ) = max(3, 4) = 4 for y ∈ Y -.
Finally, only y2 2 satisfies the optimality condition: relations i ∈ {2, 3} are min-critical. Symmetrically, λ max = min(y.θ) = min(

T + 2 +T + 3 2 , T + 1 +T + 2 2
) = min(7.5, 6.5) = 6.5 for y ∈ Y + .

So, only y4 2 satisfies the optimality condition: relations i ∈ {1, 2} are max-critical. Let us also consider the consistency condition ( 8) which becomes -T -

1 +T + 1 ≥ 0, -T - 1 +T + 3 ≥ 0 , -T - 3 + T + 1 ≥ 0, -T - 3 + T + 3 ≥ 0 and -T - 2 + T + 2 ≥ 0.
To avoid the three steps and the classification of the previous example, we now present a more synthetic approach where the Martínez and Silva's algorithm can be applied in one step. Let us consider the min-critical relations. 1) The condition y.H = 0 with y ≥ 0 which must be satisfied, presents the convenient form which can be solved by Martínez and Silva's algorithm. 2) The condition y.N = -1 becomes y.N + α = 0 where α is an artificial scalar equal to 1. 3) Moreover, we must select the vectors y giving the optimal cycle time λ min = -y.θ which can be replaced y.θ + α.λ min = 0 with α = 1. After introducing a real number β > 0, the application of the Martínez and Silva's algorithm can compute all the nonnegative solutions y β in y β .

H N θ 0 1 λ min = 0 1x(n+1) [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF] and each row vector 1 β . y β = y α which clearly satisfies the condition α = 1, gives a desired solution y satisfying y.H = 0, y.N = -1 and λ min = -y.θ, that is, a desired y ∈ Y -where each non-null entry is relevant to a min-critical relation. Symetrically, the resolution must treat

y β . H N θ 0 -1 -λ max = 0 1x(n+1) (11)
for the max-critical relations.

As the optimal cycle times have already been obtained, Y -= ∅ (resp., Y + = ∅) and these systems are consistent, that is, at least a solution must be obtained.

Remark. If matrix H, vector N are integers (which is satisfied in this paper as we consider the class of P-Time Event Graphs with Time Supervisor places), and parameters θ and λ min (resp. λ max ) are integers, a slight modification of the Martínez and Silva's algorithm allows to provide integer solutions. Indeed, the generation of integers facilitates the writing of elegant solutions in general: as a division by β is made, the technique allows to express solutions with simple fractions and not real numbers with a fractional component.

Example 2 continued

The matrices of the time interval model are as follows: The values of the minimum cycle time and maximum cycle time which are 5.25 and 13 respectively, can be computed by applying Theorem 3 or the linear programming problem I. Let us apply the improved technique based on Martínez and Silva's algorithm.

G - 1 =       1 0 0 0 0 1 0 1 0 0 0 1 1 1 0       , G - 0 =       0 0 -1 -1 0 0 0 0 -1 0 -1 0 0 0 -2       , G + 1 = -G - 1 , G + 0 = -G - 0 , T - = T - 1 T - 2 T - 3 T - 4 T - 5 t = 1 2
Knowing that λ min = 5.25 and λ max = 13, we obtain a unique vector y β = 0 1 0 1 1 0 0 0 0 0 4 and 0 0 0 0 0 0 1 0 1 1 4 which satisfies [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF] and [START_REF] Declerck | Extremum Cycle Times in Time Interval Models[END_REF], respectively for λ min and λ max .

The set of min-critical pairs is

P crit min = {(p 2 , T - 2 ), (p 4 , T - 4 ), (p c1 , T - c1 )} while the set of max-critical pairs is P crit max = {(p 2 , T + 2 )
, (p 4 , T + 4 ), (p c1 , T + c1 )}. We can verify that λ min = -y.θ = (2 + 4 + 15)/4 = 5.25 and λ max = y.θ = (19 + 17 + 16)/4 = 13.

However, the analysis of the algorithm and its use shows that the complexity is not polynomial and is time costly even if it can be useful for some examples. Therefore, a more efficient approach is necessary.

D. Approach 2: Checking of each relation

Synthetic linear programming problem. Deduced from Theorem 3, the following property allows to compute the optimal cycle times with a synthetic form of linear programming problem.

Property 3: The computation of the optimal cycles times can be made with the following problem denoted Problem II λ min , λ max = -ρ. min y∈R 1×2.q y.b with y.A = c and y ≥ 0 [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] with A = H N , b = θ and c = 0 . . . 0 -ρ where ρ = +1 and ρ = -1 for the minimization and the maximization of the cycle time, respectively. Proof. From Theorem 3, we can directly deduce the two following linear programming problems. y.b = max y∈R 1×2.q (-y.b) which is the expression of λ min . As c = 0 . . . 0 -1 , the relevant linear programming problem is deduced. If ρ = -1, we have min y∈R 1×2.q y.b which is the expression of λ max and c = 0 . . . 0 +1 : the second linear programming problem is obtained. Remark. The Problem II proposes explicit forms which can directly be used in the software tools. Indeed, we can only consider the minimization min y∈R 1x2.q (y.θ) for the two optimizations and deduce the exact sign of the desired value with a multiplication by coefficient -ρ . Similarly, we can only use a maximization for the two optimizations and make a multiplication by ρ : another expression of the criterion is ρ. max y∈R 1x2.q (-y.θ) as -ρ. min

y∈R 1×2.q y.b = ρ.(-min y∈R 1×2.q y.b) = ρ. max y∈R 1x2.q (-y.θ).
Technique based on the computation of the cycle time for a constrained problem Let us exploit Problem II expressed by [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF]. The proposed technique is to check if a selected pair for i ∈ I gives the same optimal cycle time by adding the constraint y i = 0 in system [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF]. As y i ≥ 0, this constraint is replaced by y i > 0 or y i ≥ ε i where ε i is assumed to be a positive number sufficiently small such that a possible solution with y i > 0 and the relevant criterion are not modified by this constraint. So, y i ≥ ε i ⇔ y i -sl = ε i where sl ≥ 0 is a slack variable. The addition of a new variable and constraint gives the following system

y sl . H N d 0 0 -1 = 0 -ρ ε i (13)
with y, sl ≥ 0, d = 0 . . . 0 1 0 . . . 0 t where 1 is in the i-th position if we consider y i > 0. As the constraints of system [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] are included in the new equality [START_REF] Dotoli | A First-Order Hybrid Petri Net Model for Supply Chain Management[END_REF], the resolution of the new problem gives a solution satisfying y ∈ Y -and y ∈ Y + , respectively. But any vector of Y -and Y + does not satisfy [START_REF] Dotoli | A First-Order Hybrid Petri Net Model for Supply Chain Management[END_REF] as a new constraint is added.

The criterion of the non-modified system ( 12) is kept if we take a new vector b = θ 0 as -ρ. min y∈R 1×2.q ,sl≥0,sl∈R

y sl . θ 0 = -ρ. min y∈R 1×2.q y.θ
To summarize, the problem denoted Problem III relevant to the analysis of the i -th relation for i ∈ I and, ρ = +1 and ρ = -1, respectively, is -ρ .min The following property analyzes the results of problem III for each i ∈ I.

Property 4: For problem III:

• If the computed cycle time for ρ = 1 (resp., ρ = -1) is λ min (resp., λ max ) for i ∈ I, the relevant relation is min-critical (resp., max-critical) (Case 1). • If the optimal cycle time λ min , λ max is not kept, the relevant relation is not min-critical (resp., max-critical) and a lower value (resp., greater value) is obtained for ρ = 1 (resp., ρ = -1) (Case 2). • If the problem is inconsistent, the relevant relation is not min-critical (resp., max-critical) (Case 3). Proof. Let λ opt be the optimal cycle time λ min , λ max of the nonmodified system [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF]. As the constraints of ( 14) include the constraints defining Y and Y -(resp. Y + ), each solution to problem III is a vector y ∈ Y -(resp. y ∈ Y + ) and can correspond or not to the optimal cycle time λ min (resp. λ max ). Moreover, the restriction y i = 0 is added. The following cases are distinguished.

Case 1. If the solution y ∈ Y -(resp., Y + ) of the completed problem ( 14) leads to an optimal criterion -ρ.y.θ = λ opt with y i = 0, a small variation of the relevant entry θ i with the pertinent sign can modify the optimal value. Definition 3 implies that the selected pair i is min-critical (resp., maxcritical). Note that this conclusion can be extended to any pair i = i such that y i = 0 in vector y which is min-critical (resp., max-critical).

Case 2. As the solution y ∈ Y -(resp., Y + ) does not lead to the optimal solution of ( 12), vector y is not min-critical (resp., max-critical). For ρ = +1, as the non-null entry y i selects a vector y ∈ Y -which does not reach the optimal cycle time λ min , only a lower value is obtained as shown by the formula λ min = -min y∈R 1×2.q y.θ = max y∈R 1x2.q (-y.θ)and we obtain λ < λ min . For ρ = -1, a greater value is obtained as the optimal maximal cycle time is the minimum of the possible terms y.θ for any y ∈ Y + with y i = 0. So, λ max < λ.

Case 3. If the problem III is inconsistent for a given i ∈ I, there is no y ∈ Y -(resp., Y + ) having a component y i ≥ ε i where ε i is assumed to be sufficiently small. A fortiori, y and y i cannot be critical.

Complexity

The complexity of Approach 2 and the approach presented in [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF], is clearly polynomial as only the application of a standard algorithm of linear programming is necessary. Precisely, the complexity is polynomial in the worst case if modern algorithms are used (the complexities of the ellipsoid algorithm of Khashiyan and the interior point algorithm of Karmarkar in the worst case are respectively O(n 4 × L) and O(n 3.5 × L) where n is the number of variables and L is the number of bits necessary in the storage of the data [START_REF] Culioli | Introduction à l'optimisation[END_REF]). The complexity is also polynomial in the average case if the Simplex is used (the simplex is known to be efficient in practice as it has polynomial-time average-case complexity in some general case [START_REF] Schrijver | Theory of linear and integer programming[END_REF]). Approach 2 and the approach presented in [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF], need 2.q resolutions of a linear programming problem with q = |P | where P is the number of places including the Time Supervisor places, for each optimal cycle time λ min or λ max . The sizes of the systems to be solved are almost the same as they are (2.q × n + 1) and (2.q + 1 × n + 2) for [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] and Approach 2, respectively. Considering the 72 problems of the complete approach (4.q with q = 18 for λ min and λ max ) checking the critical pairs in example 3 presented below, the CPU times for [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] and Approach 2 are approximately equal (respectively 0.124s and 0.186s with a PC Intel Core 2.93GHz and function linpro() of Software Scilab).

E. Example 2 continued

The table I contains the computed cycle time for each pair (place, duration) with ε = 0.01. The results give the same critical pairs as the approach 1 using Martínez and Silva's algorithm. The values show the extension of the interval [λ min ,λ max ] depending on the selected pair. In other words, the obtained cycle time λ satisfies λ ∈ [0, λ min ] and λ ∈ [λ max , +∞] for the minimization and the maximization of the cycle time, respectively. Remember that λ min = 5.25 and λ max = 13. Throughout these examples, the cycle time of an identified critical pair is in bold in the tables. Obtained with [START_REF] Gaubert | Théorie des systèmes linéaires dans les dioïdes[END_REF], the set of min-critical pairs is P crit min = Example 3 in Fig. 3 considers a baking process. The modelling of this process under the form of a P-time Event Graph has been presented in [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] but the replacement of some places by a Time Supervisor place modifies the behavior of the system and the results are different. The plant bakery is composed of two production lines giving a bread of higher quality (upper range 1) and of an ordinary quality (ordinary range 2) respectively. The two ranges are described by places p 1 , p 2 , p 3 , p 4 , p 5 , p 6 , p 17 and p 7 , p 8 , p 9 , p 10 , p 11 , p 12 , p 13 , p 16 , respectively. They follow the same production sequence on four machines which are the kneading machine, the dividing machine, the molding machine and the oven. The system contains 15 transitions and 18 places composed of 17 standard places and a Time Supervisor place p 18 represented by an oval in grey. We take M 0 = 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 t . Taken from a semi-industrial plant bakery [16] [17], the time durations specific for each range and an additional operation of proofing (place p 8 ) for the range 2 lead to two different qualities. The main operations are as follows. After mixing the ingredients, the dough is kneaded. This step of kneading is represented by places p 1 and p 7 .

The following step is the first proofing which is the process of leaving the dough in the machine for 10 to 30 minutes at a steady temperature of 27 • C which leads to a fermenting. Only the process 2 contains this step (place p 8 ). Then, the dough is divided into pieces of about 900 grams each and placed in nets in the proofer (this step of dividing is represented by p 2 for the process 1 and p 9 for the process 2). The following step is the second proofing which lasts 180 minutes for the range 1 (p 3 ) and 15 to 20 minutes for the range 2 (p 10 ). Then each piece of dough is shaped with a molding machine (the molding step is represented by p 4 for the range 1 and p 11 for the range 2). Then the operation of final proofing provides the last fermenting (p 5 for the range 1 and p 12 for the range 2). Finally, Baking the bread takes up 20 to 25 minutes at a temperature of 250 to 280 • C in the oven and is identical for the two ranges (the baking corresponds to p 6 for the range 1 and p 13 for the range 2). Assumed to be sufficiently large, the oven can take the two productions. The following operations as the cooling, the packing and the transport are not considered.

A connection between the two production lines are expressed by places p 14 , p 15 corresponding to two molding machines. We assume an upper limit of 300 minutes in the period of use of the molding machines otherwise another production line not described in the event graph can take one of these machines.

The two production lines share a unique dividing machine whose behavior is described by a time supervisor place p 18 : the lower limit expresses the time necessary to the production of the two lines while an upper bound represents a limit of its use to avoid a premature wear.

Let us apply Problem I in Section III-A. The values of the extremum cycle time λ min , λ max which are 148 and 187 respectively, are computed with the function linpro() of the software Scilab. The analysis of the critical pairs by approach 1 using Martínez and Silva's algorithm does not succeed as the execution implies an overtake of the available memory. The checking of the pairs by approach 2 with ε = 0.1 can be executed and the results of the 72 problems are given in the table II.

Let us apply [START_REF] Gaubert | Théorie des systèmes linéaires dans les dioïdes[END_REF] ), (p 10 , T + 10 )}. So, the set P crit min (resp. P crit max ) depends on the lower and upper bounds of the time durations and does not correspond to some (oriented) circuits of the event graph. The relevant time durations cannot be modified if we desire to keep the values of the extremum cycle times and the choice of reliable machines is necessary for the corresponding critical pairs. A fortiori, the intersection of the two sets which is non-empty (P crit min ∩ P crit max = ∅) corresponds to a crucial set where a variation of a time duration leads to a variation of the optimal cycles. Let us illustrate this point by considering a unitary increase of T - 1 which takes the value 26. The relevant computation leads to an increase of the minimum cycle time (λ min =149) and a decrease of the maximum cycle time (λ max =186).

Finally, Section III-A with [START_REF] Campos | Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector[END_REF] where the non-critical pairs are optimized can be applied. To avoid a general slow-down of the whole process, the best cycle time λ min which corresponds to the greatest production rate of the entire process, is a fixed parameter. In this context, a greater time duration is possible for the dividing step in the range 1 and the kneading, the dividing step and the molding step in the range 2 as the relevant pairs (p 2 , T - 2 ), (p 7 , T - 7 ), (p 9 , T - 9 ) and (p 11 , T - 11 ) are not critical. This possibility implies an energy saving and so a financial economy by reducing the speed of the relevant machines without modifying the best production rate of the whole process. Another possibility is the replacement

V. CONCLUSION

In this paper, we have introduced the model of Time Supervisor Place which is different from the model of implicit places which represents redundancy and the model of macroplace often used to improve the readability of Petri nets by building a hierarchical structure. It can be seen as a generalization of the class of P-time Event graphs since the time behavior of each place can be described by a time macroplace. We have shown that P-time Event Graphs with time macro-places can be described by the TIM (1) using the dater form. Even if it follows the spirit of P-time Event Graphs, a perspective is to apply this new possibility of modeling to other types of time Petri nets such as Time Stream Petri nets [START_REF] Courtiat | Formal models for the description of timed behaviors of multimedia and hyper media distributed systems[END_REF] [START_REF] Declerck | Discrete Event Systems in Dioid Algebra and Conventional Algebra[END_REF].

The robustness of Time Interval Models is analyzed through the minimum and the maximum cycle times which depend on pairs composed of a place and a time duration which correspond to the rows of the Time Interval Model. Based on Theorem 1 [START_REF] Declerck | Cycle Time of a P-time Event Graph with Affine-Interdependent Residence Durations[END_REF], a first approach using the Martínez and Silva's algorithm detects all the critical pairs. As this technique is non-polynomial and cannot be applied to every common Petri net, we propose another approach which selects each relation by forcing the relevant component of the solution to a non-null value and checks the relevant optimality: if the computed cycle time is optimal, the relation is critical. Otherwise, a lower value (resp., greater value) of the cycle time is obtained. The complexity of approach 2 is clearly polynomial and is numerically equivalent to the approach in [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] exploiting a variation of the time durations. Approach 2 leads to an enlargement of the time interval [λ min , λ max ] while the approach [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] restricts it. After noticing that approaches 1 and 2 are structural, that is, the computing is independent of the trajectories, a perspective is to analyze the possible duality with approach [START_REF] Declerck | Critical subsystems in Time Interval Models. Application to a baking process[END_REF] and to study the effects of the variation of coefficients of the incidence matrix of the Petri net or inside the matrices defining the TIM system. Finally, the system optimization applied to the plant bakery shows that some modifications of specific phases as the knead-ing, the dividing and the molding can lead to an energy saving and a financial economy without affecting the production rate. A natural perspective is to develop a bi-criteria approach combining optimization of the time durations and optimization of the resources.

Fig. 1 .

 1 Fig. 1. Example 1: Elementary P-Time Event Graph

Fig. 2 .

 2 Fig. 2. Example 2: P-time Event Graph with a time supervisor-place

[ 1 ,

 1 |P |]} is kept. Therefore, we have T -and T + ∈ R |P | , G - and G + ∈ R |P | ×2.|T R| , and n = |T R|.

  (resp., max κ∈R n+1 c.κ) under constraints A.κ ≤ b with A = H N , b = θ, c = 0 . . . 0 1 and κ = x(0) λ .

2 )

 2 = max(3, 4) = 4. So, the relations corresponding to pairs (p 2 , T - 2 ) and (p 3 , T - 3 ) are critical as an increase of the time duration T - 2 or T - 3 modifies the value of the cycle time contrary to T - 1 . Therefore, we can increase T - 1

λ

  min = max(-y.θ) with y.A = c and y ≥ 0 over R where A = H N and c = 0 . . . 0 -1 . Respectively, λ max = min(y.θ) with y.A = c and y ≥ 0 over R where A = H N and c = 0 . . . 0 +1 . Let us show that Problem II is an equivalent form: If ρ = 1, we obtain -min y∈R 1×2.q y.b. From property -min(-x) = max(x), we deduce -min y∈R 1×2.q

  sl ≥ 0, d = 0 . . 0 1 0 . . . 0 t where 1 is in the i -th position and b = θ 0 .

Fig. 3 .

 3 Fig. 3. Example 3: Plant bakery

  of the relevant machines by less efficient machines. Desiring optimized the four machines, the criterion in the optimization (5) is null except an unitary value for each machine. For λ min , the results of the maximization are as follows: respectively, the components of ∆ are ∆ 2 = 3, ∆ 7 = 5, ∆ 9 = 5 and ∆ 11 = 5 for T - 2 , T - 7 , T - 9 and T - 11 and the new values of time durations are 10 + ∆ 2 = 13, 15 + ∆ 7 = 20, 10 + ∆ 9 = 15, 15 + ∆ 11 = 20.

TABLE I EXAMPLE 2 :

 I2 CHECKING OF EACH RELATION BY APPROACH 2

	P air	(p 1 , T	-1 )	(p 2 , T	-2 )	(p 3 , T	-3 )	(p 4 , T 4 ) -	(pc 1 , T -c 1	)	(p 1 , T	+ 1 )	(p 2 , T	+ 2 )	(p 3 , T	+ 3 )	(p 4 , T	+ 4 )	(pc 1 , T + c 1	)
	min -critical	5.175	5.25	5.215	5.25	5.25		5.135	5.08	5.135	5.12	5.24
	max -critical	13.06	13.17	13.06	13.13	13.01		13.13	13		13.09	13		13
	{(p 2 , T -2 ), (p 4 , T -4 ), (p c1 , T -c1 )} and the set of max-critical pairs is P crit max = {(p 2 , T + 2 ), (p 4 , T + 4 ), (p c1 , T + c1 )}. The relevant sets of non-critical pairs P non-crit min and P non-crit max can be
	deduced easily.
	IV. INDUSTRIAL PROCESS: A PLANT BAKERY COMPOSED
	OF TWO PRODUCTION LINES

TABLE II EXAMPLE 3 :

 II3 CHECKING OF EACH RELATION BY APPROACH 2

	P air	(p 1 , T	-1 )	(p 2 , T	-2 )	(p 3 , T	-3 )	(p 4 , T	-4 )	(p 5 , T	-5 )	(p 6 , T	-6 )	(p 7 , T	-7 )	(p 8 , T	-8 )	(p 9 , T	-9 )	(p 10 , T	-10 )
	min -critical	148	147.7		148		148	142	147.5	147.5	146	147.5	147.5
	max -critical	187	187.3		187	187.5	193	187.5	187.5	189	187.5	187.5
	P air	(p 11 , T	-11 )		(p 12 , T	-12 )		(p 13 , T	-13 )		(p 14 , T	-14 )	(p 15 , T	-15 )	(p 16 , T	-16 )	(p 17 , T	-17 )	(p 18 , T	-18 )
	min -critical		147.5			145				147.5		121.4			148			-9852	-9836.7	148
	max -critical		187.5			190				187.5		217				190.9	10187	10171.7	187
	P air	(p 1 , T	+ 1 )	(p 2 , T	+ 2 )	(p 3 , T	+ 3 )	(p 4 , T	+ 4 )	(p 5 , T	+ 5 )	(p 6 , T	+ 6 )	(p 7 , T	+ 7 )	(p 8 , T	+ 8 )	(p 9 , T	+ 9 )	(p 10 , T	+ 10 )
	min -critical	147.8	147.8		146.7	147.5	142	147.5	148	148	148	148
	max -critical	187.2	187.2		188.3	187.5	193	187.5	187	187	187	187
	P air	(p 11 , T	+ 11 )		(p 12 , T	+ 12 )		(p 13 , T	+ 13 )		(p 14 , T	+ 14 )	(p 15 , T	+ 15 )	(p 16 , T	+ 16 )	(p 17 , T	+ 17 )	(p 18 , T	+ 18 )
	min -critical		147.5			145				147.5		144.1			138			-9836.7	-9852	145.8
	max -critical		187				190				187.5		187				193.6	10171.7	10187	189.2