Full Text PDF
ESTD Year: 2017 | Impact Factor: 6.9
DOI Prefix: 10.47001/IRJIET
ESTD Year: 2017 | Impact Factor: 6.9
DOI Prefix: 10.47001/IRJIET
Vol 10 No 9 (2026): Volume 10, Issue 9, September 2026 | Pages: 150-163
International Research Journal of Innovations in Engineering and Technology
OPEN ACCESS | Research Article | Published Date: 26-09-2026
Timed event graphs describe manufacturing lines, transport networks and computing pipelines governed by synchronisation and delay, and they are linear over the max-plus dioid. Estimating their temporal parameters from one record of input and output firing dates is classically solved by residuation, which returns the greatest parameter vector whose predicted output never exceeds the measured one. This paper establishes when that estimator is trustworthy. First, a parameter is recovered exactly if and only if its regressor attains the maximum in the measured output at least once; for constant-rate excitation this yields closed-form critical rates governed by the chord slopes of the transient block, not by the eigenvalue as previously assumed, the eigenvalue governing only the periodic block. Second, the minimum record length is obtained in closed form and diverges as the excitation rate approaches the eigenvalue, which shows that the reported insensitivity to record length is an artefact of testing far from the critical rate. Third, the estimator is proved non-expansive with respect to timestamp errors, and under non-negatively biased timestamps the identified model is proved to be a guaranteed upper bound on the true system, so predicted completion dates are never optimistic. A campaign on two plants comprising more than seven thousand runs confirms every statement: the exactness criterion reproduces recovery in sixty of sixty cases, the record-length law holds in eighteen of nineteen configurations, and conservativeness is observed in all two thousand four hundred one-sided runs against none under symmetric errors. Excitation design rules follow.
max-plus algebra, dioid, timed event graph, discrete event system, system identification, residuation, identifiability, experiment design, robustness, manufacturing systems.
Ghadir Aryan. (2026). Excitation Design and Guaranteed Robustness Bounds for Residuation-Based Identification of Max-Plus Linear Discrete Event Systems. International Research Journal of Innovations in Engineering and Technology - IRJIET, 10(9), 150-163. Article DOI https://doi.org/10.47001/IRJIET/2026.109016
This work is licensed under Creative common Attribution Non Commercial 4.0 Internation Licence
B. Heidergott, G. J. Olsder, and J. van der Woude, Max Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton, NJ: Princeton Univ. Press, 2006.
R. A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166. Berlin, Germany: Springer-Verlag, 1979, doi: 10.1007/978-3-642-48708-8.
B. Cottenceau, L. Hardouin, J.-L. Boimond, and J.-L. Ferrier, "Model reference control for timed event graphs in dioids," Automatica, vol. 37, no. 9, pp. 1451–1458, 2001, doi: 10.1016/S0005-1098(01)00073-5.
B. De Schutter and T. van den Boom, "Model predictive control for max-plus-linear discrete event systems," Automatica, vol. 37, no. 7, pp. 1049–1056, 2001, doi: 10.1016/S0005-1098(01)00054-1.
J. Xu, T. van den Boom, and B. De Schutter, "Model predictive control for stochastic max-plus linear systems with chance constraints," IEEE Trans. Autom. Control, vol. 64, no. 1, pp. 337–342, 2019, doi: 10.1109/TAC.2018.2849570.
L. Hardouin, C. A. Maia, B. Cottenceau, and M. Lhommeau, "Observer design for (max, plus) linear systems," IEEE Trans. Autom. Control, vol. 55, no. 2, pp. 538–543, 2010, doi: 10.1109/TAC.2009.2037477.
L. Hardouin, Y. Shang, C. A. Maia, and B. Cottenceau, "Observer-based controllers for max-plus linear systems," IEEE Trans. Autom. Control, vol. 62, no. 5, pp. 2153–2165, 2017, doi: 10.1109/TAC.2016.2604562.
C. A. Maia, C. R. Andrade, and L. Hardouin, "On the control of max-plus linear system subject to state restriction," Automatica, vol. 47, no. 5, pp. 988–992, 2011, doi: 10.1016/j.automatica.2011.01.047.
Y. Shang, L. Hardouin, M. Lhommeau, and C. A. Maia, "An integrated control strategy to solve the disturbance decoupling problem for max-plus linear systems with applications to a high throughput screening system," Automatica, vol. 63, pp. 338–348, 2016, doi: 10.1016/j.automatica.2015.10.030.
M. Lhommeau, L. Hardouin, B. Cottenceau, and L. Jaulin, "Interval analysis and dioid: Application to robust controller design for timed event graphs," Automatica, vol. 40, no. 11, pp. 1923–1930, 2004, doi: 10.1016/j.automatica.2004.05.013.
T. Brunsch, L. Hardouin, C. A. Maia, and J. Raisch, "Duality and interval analysis over idempotent semirings," Linear Algebra Appl., vol. 437, no. 10, pp. 2436–2454, 2012, doi: 10.1016/j.laa.2012.06.025.
F. Gallot, J.-L. Boimond, and L. Hardouin, "Identification of simple elements in max-algebra: Application to SISO discrete event systems modelisation," in Proc. European Control Conf. (ECC), Brussels, Belgium, 1997, pp. 1866–1871, doi: 10.23919/ECC.1997.7082376.
L. Hardouin, E. Menguy, J.-L. Boimond, and J.-L. Ferrier, "SISO discrete event systems control in dioid algebra," J. Européen des Systèmes Automatisés, vol. 31, no. 3, pp. 433–452, 1997.
C. A. Maia, R. Santos-Mendes, and L. Hardouin, "Some results on identification of timed event graphs in dioid," 2003.
T. S. Blyth and M. F. Janowitz, Residuation Theory. Oxford, U.K.: Pergamon Press, 1972, doi: 10.1016/B978-0-08-016408-3.50004-8.
G. Cohen, "Residuation and applications," in Algèbres Max-Plus et Applications en Informatique et Automatique, École de Printemps d'Informatique Théorique, Noirmoutier, France: INRIA, 1998.
S. Klein, L. Litz, and J.-J. Lesage, "Fault detection of discrete event systems using an identification approach," IFAC Proc. Volumes (16th IFAC World Congress), vol. 38, no. 1, pp. 92–97, 2005, doi: 10.3182/20050703-6-CZ-1902.01440.
L. Ljung, System Identification: Theory for the User, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 1999.
S. Gaubert, "Théorie des systèmes linéaires dans les dioïdes," Ph.D. dissertation, École des Mines de Paris, France, 1992.
R. M. F. Cândido, L. Hardouin, M. Lhommeau, and R. S. Santos Mendes, "Conditional reachability of uncertain max-plus linear systems," Automatica, vol. 94, pp. 426–435, 2018, doi: 10.1016/j.automatica.2017.11.030.
G. Aryan, “A unified residuation framework for the identification of max-plus linear systems: moving-average, recursive and structural estimation,” manuscript submitted to the International Research Journal of Innovations in Engineering and Technology (IRJIET), 2026.