×

zbMATH — the first resource for mathematics

Networked conflicting timed event graphs representation in (Max,+) algebra. (English) Zbl 1267.93106
Summary: Timed Event Graphs (TEGs) are a specific class of Petri nets that have been thoroughly studied given their useful linear state representation in (Max,+) algebra. Unfortunately, TEGs are generally not suitable for modeling systems displaying resources sharing (or conflicts). In this paper, we show that if a system with conflicts is modeled using a NCTEG (Networked Conflicting Timed Event Graphs), it is quite possible to obtain an equivalent (Max,+) representation. More precisely, we prove that the evolution of a NCTEG satisfies linear time-varying (Max,+) equations. In case of cyclic NCTEGs, which are a natural model of many repetitive systems, we provide a standard time-invariant (Max,+) representation. As an application of the proposed approach to exhibit its interest, we consider the case of Jobshops. We first propose a generic NCTEG-based model of these systems and subsequently apply the corresponding (Max,+) representation to evaluate some of their performances.

MSC:
93C65 Discrete event control/observation systems
15A80 Max-plus and related algebras
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Addad B, Amari S, Lesage JJ (2010) Linear time-varying (Max,+) representation of conflicting timed event graphs. In: 10th int. workshop on discrete event systems, Berlin, Germany, pp 310–315
[2] Baccelli F, Cohen G, Olsder GJ, Quadrat JP (1992) Synchronization and linearity: an algebra for discrete event systems. Wiley, New York · Zbl 0824.93003
[3] Baccelli F, Foss S, Gaujal B (1996) Free choice Petri nets: an algebraic approach. IEEE Trans Automat Contr 41(12):1751–1778 · Zbl 1041.93500 · doi:10.1109/9.545714
[4] Bolzern P, Colaneri P, Scatolini R (1986) Zeros of discrete time linear periodic systems. IEEE Trans Automat Contr 31:1057–1058 · Zbl 0606.93036 · doi:10.1109/TAC.1986.1104172
[5] Boutin O, Cottenceau B, L’Anton A, Loiseau JJ (2009) Modeling systems with periodic routing functions in dioid (Min,+). In: 13th IFAC symposium on information control problems in manufacturing, Moscow, Russia, pp 1377–1382
[6] Cohen G, Gaubert S, Quadrat JP (1999) Max plus algebra and systems theory: where we are and where to go now. Annu Rev Control 23:207–219
[7] Correia A, Abbas-Turki A, Bouyekhf R, El Moudni A (2009) A dioid model for invariant resource sharing problems. IEEE Trans Syst Man Cybern Part A Syst Humans 39(4):770–781 · doi:10.1109/TSMCA.2009.2019867
[8] Gaubert S (1995) Resource optimization and (min,+) spectral theory. IEEE Trans Automat Contr 40(11):1931–1934 · Zbl 0845.93035 · doi:10.1109/9.471219
[9] Gaubert S, Mairesse J (1999) Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans Automat Contr 44(4):683–697 · Zbl 0955.68082 · doi:10.1109/9.754807
[10] Hillion H, Proth JM (1989) Performance evaluation of jobshop systems using timed event graphs. IEEE Trans Automat Contr 34(1):3–9 · Zbl 0656.90054 · doi:10.1109/9.8644
[11] Laftit S, Proth JM, Xie XL (1992) Optimization of invariant criteria for event graphs. IEEE Trans Automat Contr 37(6):547–555 · Zbl 0763.90053 · doi:10.1109/9.135488
[12] Lahaye S, Boimond JL, Hardouin L (2004) Linear periodic systems over dioids. Discrete Event Dyn Syst 14(2):133–152 · Zbl 1129.93449 · doi:10.1023/B:DISC.0000018568.03525.93
[13] Litvinov GL, Sobolevski AN (2001) Idempotent interval analysis andoptimization problems. Reliab Comput (Kluwer) 7(5):353–377 · Zbl 1012.65065 · doi:10.1023/A:1011487725803
[14] Mayer E, Haus U-U, Raisch J, Weismantel R (2008) Throughput-optimal sequences for cyclically operated plants. Discrete Event Dyn Syst 18(3):355–383 · Zbl 1176.90232 · doi:10.1007/s10626-008-0038-3
[15] Misra P (1996) Time-Invariant representation of discrete periodic systems. Automatica 32(2):267–272 · Zbl 0844.93023 · doi:10.1016/0005-1098(96)85558-0
[16] Murata T (1989) Petri nets: properties analysis and applications. Proc IEEE 77(4):541–580 · doi:10.1109/5.24143
[17] Nait SM, Manier MA, El Moudni A, Wack M (2006) Petri net with conflicts and (max,plus) algebra for transportation systems. In: 11th IFAC symposium on transportation systems, The Netherlands
[18] Van Den Boom TJJ, De Shutter B (2006) Modeling and control of discrete event systems using switching Max-Plus linear systems. Control Eng Pract 14(10):1199–1211 · doi:10.1016/j.conengprac.2006.02.006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.