. Nous-avons-mr-etx1l-sicx-xt, Donc d'après la propriété 4.3, f(Mp) S f(Ms)

A. Du, T. De, and . Moyen-dans-ce-paragraphe, nous donnons des conditions d'atteignabilité d'un temps de cycle donné C. Nous donnons également une condition nécessaire et suffisante d'atteignabilité d'un temps de cycle égal au maximum des moyennes des variables aléatoires représentant les temps de franchissement des transitions. Nous notons c* ce maximum

. Pour-démontrer-ce-théorème, Pour cela, nous introduisons les notations suivantes : -{ac,r(k)}r=1,..,-Sort des séquences de variables aléatoires i.i.d. mutuellement indépendantes avec a1, At, vol.r, issue.1

A. Lemme, l : St(k) <st G(k), V te T et V b0

C. At, pour tout r,t? T, sont des variables aléatoires mutuellement indépendantes et comme ar,t(l) =st Ar,t(l) Sic* X =st h,r(l), d'après la propriété 3.3.i dans [01], nous avons : G1(1) = Mq {a, (l)}<i.* naax {U..,11)} = Ht(t) teu-(t)' teu-(t

C. Gt, Ht(K) et b1,1(K+1), pour tout I,t? T, sonr des variables aléatoires mutuellement indépendantes, d'après la propriété 3.3.i dans [01, nous avons : Gt(K + 1) = f1(G1(K),at,r(K + 1)) Sic* fr(Hr(K),bt,r(K + l)) = Ht(K + 1) c.Q.F.D

. .. Pour-tout-(-h, and . Tde-ctg, tk) la version indépendante des variables aléatoires B(h, ..., tk), c'est-à-dire que les variables, sont mutuellement indépendantes et B*(to, ..., tk) =st B(tg, ..., ti). D'après la proposition 3.5 de [01], Ht(k) <sr -Max--. .{g * (tg,...,t1)}

<. Par, k} > II(t -exp(-h(x)

. To, ,rk )?cr (k)

F. Baccelli and A. M. Makowski, Queueing Models for _Sys.aems with Synchronization Constraints, Proc. of ùe IEEE, pp.138-161, 1989.

F. Baccelli and P. Konstantopoljlos, Estimates of Cyclefimes in Stochastic Petri Nets, Rapport de rechercheno LS'IZ, 1991.

F. Baccelli, Ergodic Theory of Stochastic Petri Networks, The Annals of Probability, vol.20, issue.1, pp.350-374
DOI : 10.1214/aop/1176989932

URL : https://hal.archives-ouvertes.fr/inria-00075521

F. Baccelli and Z. Liij, Comparison Properties of Stochastic Decision Free Petri Nets", I EE E Transactio ns o n Automatic e o nrol, p.7997

F. Baccelli, G. Cohen, G. J. Olsder, and J. P. Quadrat, Synchronization and Linearity, 1993.

G. Berthelot, Checking properties of nets using transformations, Lecture Notes in Computer Science, vol.222, pp.19-40, 1986.
DOI : 10.1007/BFb0016204

G. W. Brams, Réseaux de Petri : Théorie et Pratique, Masson, 1983.

J. A. Buzacott and D. D. Yao, On Queuing Network Models of Flexible Manufacturing - Systems, Queuing Syst.Theory and Applications, vol.1, 1986.

P. Camion, Modules unimodulaires, Journal of Combinatorial Theory, vol.4, issue.4, pp.301-362, 1968.
DOI : 10.1016/S0021-9800(68)80061-4

URL : https://doi.org/10.1016/s0021-9800(68)80061-4

J. Campos, G. Chiola, and M. Silva, Properties and performance bounds for closed free choice synchronized monoclass queueing networks, IEEE Transactions on Automatic Control, vol.36, issue.12, pp.1368-1382, 1991.
DOI : 10.1109/9.106153

J. B. Cavaille and J. M. Proth, Pratique de la Simularion en Production Discontinue, 1987.

P. U2l, F. Chretienne-réseaux-de-petri-temporisés-tl3l, A. Commoner, S. Holt, A. Even et al., MarkedDirected GraphsManufacturing llo_y-liqç Systems: a Review of Models and Analytical Results, Journal of Computer and System Science, vol.5, issue.5, 1971.

R. David and H. Alla, Du Grafcet aux Réseaux de Petri, Edition Hermès, 1989.

F. Dicesare, G. Harhalakis, J. M. Proth, and M. Silva, Practice of Petri Nets in - Manufacturing, 1993.
DOI : 10.1007/978-94-011-6955-4

M. N. Di, Y. Iascolo, Y. Frein, R. Dallery, and . David, A Unified Modeling of Kanban Systems Using Petri Nets, 1989.

M. D. Mascolo, Modélisation et Evaluation de Perfo-rmances deSystèmes de Production gérés en Kanban, Thèse de Docteur de I'INPG, 1990.

I. B. Dugan, K. S. Trivedi, R. M. Geist, and V. F. Nicola, Extended Stochastic Petri Nets: Applications and Analysis, 1984.
DOI : 10.21236/ADA148439

URL : http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA148439&Location=U2&doc=GetTRDoc.pdf

Ï. G. Flozun and S. Natkin, Les Réseaux de Petri Stochastiques, Technique et Sciences Informatiques, pp.143-160, 1985.

P. Glasserman and D. D. Yao, Algebraic structure of some stochastic discrete event systems, with applications, Discrete Event Dynamic Systems, vol.5, issue.1, pp.7-35, 1991.
DOI : 10.1016/S0022-0000(76)80047-5

P. J. Haas and G. S. Shedler, Stochastic Petri net representation of discrete event simulations, IEEE Transactions on Software Engineering, vol.15, issue.4, pp.381-393, 1989.
DOI : 10.1109/32.16599

Î. P. Haas and G. S. Shedler, Stochastic Petri Nets: Modeling Power and Limit Theorems, Probabiliry in Engineering and Informational Scineces, pp.7-98, 1991.
DOI : 10.1080/15326348708807064

H. P. I24l and . Hillion, Perfonnance Evaluation of Decision Making Organisations using Timed Petri Nets, 1986.

H. P. I25l, J. M. Hiluon, and . Proth, Analyse de Fabrications non Linéaires et Répétitives à laide des Graphes d'Evénements Temporisés, 1988.

Ï. H. Hillion and J. M. Proth, Performance evaluation of job-shop systems using timed event-graphs, IEEE Transactions on Automatic Control, vol.34, issue.1, pp.3-9, 1989.
DOI : 10.1109/9.8644

H. P. Hillionc, X. R. Ho, and . Cao, Modélisation et Analyse des Systèmes de Production Discrets par les Réseaux de Petri temporisésPerturbation Analysis of Discrete Event Dynamic Systems, Thèse de doctorat, 1989.

B. W. Hollocs, Improving Manufacturing Operations with WITNESS Computer Simulation, AT&T Technology, vol.6, issue.1, pp.16-21, 1991.

R. Johnsonbaugh and T. Murata, Petri Nets and marked graphs -Mathematical Models of Concurrent Computation, The American Math. Monthly, vol.89, issue.8, pp.552-566, 1982.

S. Laftit, Les Graphes d'Evénements Déterministes et Stochastiques : Application aux sysÈmes de Production, Thèse de doctorat, 1991.

S. Laftit, J. M. Proth, and X. L. Xie, Optimisation of invariant criteria for event graphs, IEEE Transactions on Automatic Control, vol.37, issue.5, pp.547-555, 1992.
DOI : 10.1109/9.135488

M. K. Molloy, Performance Analysis Using Stochastic Petri Nets, IEEE Transactions on Computers, vol.31, issue.9, pp.541-580, 1982.
DOI : 10.1109/TC.1982.1676110

M. K. Molloy, Discrete Time Stochastic Petri Nets, IEEE Transactions on Software Engineering, vol.11, issue.4, pp.417-423, 1985.
DOI : 10.1109/TSE.1985.232230

C. Murgiano, A tutorial on WITNESS, 1990 Winter Simulation Conference Proceedings, pp.177-86, 1990.
DOI : 10.1109/WSC.1990.129510

S. Natkin, Les Réseaux de Petri Stochastiques et le-ur-Application à I'Evaluation des Systèmes, Thèse de Docteur-Ingénieur, 1980.

J. J. O-'reilly and N. K. Ryan, Introd"ction to SLAM II and SLAMSYSTEM, Proceedings of the 1992 Winter Simulation Conference, pp.352-358, 1992.

C. D. Petden, R. E. Shannon, and R. P. Sadowski, Introduction to Simulation with Siman, 1990.

J. L. Peterson, Perri Net Theory and the Modeling of Systmes, 1981.

C. A. Petzu, Kommunikation mit Automaten, 1962.

J. M. Protti, Conception et Gestion des systèmes de Production, P.IJ.F, 1992.

J. M. Proth, N. Sauer, and X. L. Xie, stochastic Timed Event G_ryqlq: Bounds,-Cycle Time Reachability and Marking Optimization, 1992.
DOI : 10.1109/9.299640

J. M. I44l, X. L. Proth, and . Xie, Invariant Criteria for Detreministic Event Graphs Comptes Rendus de I'Accadémie des Sciences 313, Série I, pp.797-800, 1991.

J. M. Proth and X. L. Xie, Cycle time of stochastic event grfphs:_ev_aluatiol_and marking optimization, IEEE Transacttons on Automatic Control, vol.39, issue.7, 1994.

J. M. Proth, N. Sauer, Y. Wardi, and X. L. Xie, Marking Optimization of Stochastic Timed Evenr Graphs using IPA, Proc. of 32nd IEEE Conference on Decision and Control, pp.686-691, 1993.

C. V. and G. S. Ho, Performance Evaluation of Asynchronous Concurrent Systems Using Petri Nets, IEEE Trans. on Software Engineering, issue.6 5, 1980.

C. Ramchandani, Analysis of Asynchronous_Concurrent Slstems Using Petri N?ts, 1974.

J. A. Resing, R. E. De, V. , G. Hooghiemstra, M. S. Keane et al., Asymptotic Behaviour of Random Discrete Event Systems, Stochastic Processes and their Applicartons, pp.195-216, 1990.

N. Sauer and X. L. Xie, New Performance Bounds a1{ }ry_mptotic Properties of Stochastic Timed Event Graphs, 1992.

N. Sauer and X. L. Xie, Marking Optimization of Stochastic Timed_Event Ç3phs]', Application and Theory of Peni Nets, Ajmone-Marson, Lecture Notes in Côinputer Science 091, pp.357-376, 1993.

J. Sifakis, IJse of Petri Nets for Performance Evaluation, Acta Cybernet, vol.4, issue.2, pp.185-202, 1978.

J. Sifakis, Performance Evaluation of Systems usin_g Petri_Ne-ts",_N{ Th^eory and Application, Lecture Notes in Computer Scienc-e, 1980.

M. Silva and R. Valette, Petri nets and flexible manufacturing, Rozenberg, Lecture Notes of Computer Science, vol.424, pp.374-417, 1989.
DOI : 10.1007/3-540-52494-0_38

D. Stoyan, Comparison Methods for Queues and_Other Stochastic Models, 1984.

X. L. Xie, On the Impact of Randomness in Production Lines Controlled by Kanbans, Proceed.ings of the Sec^ond European Control Conference (ECC 93), 1993.

X. L. Xie, Superposition Properties and Performance Bounds of Stochastic Timed Event Graphs, 1992.
URL : https://hal.archives-ouvertes.fr/inria-00074865

. Dans-le-cas-de-durées-opératoires-déterministes,-i-'objectif-est-de-maximiser-la-productivité-avec-un-nombre-de-ressources-de, En terrnes de graphes d'événements, ceci consiste à minimiser une somme pondérée des marquages des places (i.e-un critère linéaire p-invariant) sous la contrainte d'obtenir un temps de cycle donné. Pour résoudre ce problème, nous proposons une méthode exacte qui utilise un algorithme de type "Branch and Bound"' Dans le cas des graphes d'événements à temporisations stochastiques, I'objectif est d'atteindre des performances moyennes données avec un nombre de jetons aussi réduits que possible. Pour résoudre ce problème d'optimisation des jetons, nous proposons deux nouvelles heuristiques qui nous donnent une solution proche de la solution optimale. Elles utilisent I'analyse perturbationnelle pour identifier les places dans lesquelles les nouveaux jetons sont ajoutés à chaque itération' Des séries d'expériences numériques, nous pennettent d'évaluer les performances de toutes les méthodes (exactes et heuristiques) que nous proposàns dans ce travail. lncidemment' nous donnons une méthode efficace pour accélérer la simulation ainsi que de nombreuses bornes du temps de cycle moyen. Nous établissons également d'importantes propriétés du critère p-invariant en fonction du marquage, nous appliquons ces résultats à quelques exemples de systèmes de production répétitifs (ateliers flexibles, systèmes dassemblage et systèmes de type Kanban

. Mots-clés, Réseaux de petri, Graphes d'événements déterministes et stochastiques, Evaluation des performances, Optimisation du marquage, Analyse perturbationnelle, Systèmes de production