Periodic Trajectories in P-Time Event Graphs and the Non-Positive Circuit Weight Problem
- 2 June 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Letters
- Vol. 6, 686-691
Abstract
P-time event graphs (P-TEGs) are specific timed discrete-event systems, in which the timing of events is constrained by intervals. An important problem is to check, for all natural numbers d, the existence of consistent d-periodic trajectories for a given P-TEG. In graph theory, the Proportional-Inverse-Constant-Non-positive Circuit weight Problem (PIC-NCP) consists in finding all the values of a parameter such that a particular parametric weighted directed graph does not contain circuits with positive weight. In a related paper, we have proposed a strongly polynomial algorithm that solves the PIC-NCP in lower worst-case complexity compared to other algorithms reported in literature. In this letter, we show that the first problem can be formulated as an instance of the second; consequently, we prove that the same algorithm can be used to find d-periodic trajectories in P-TEGs. Moreover, exploiting the connection between the PIC-NCP and max-plus algebra we prove that, given a P-TEG, the existence of a consistent 1-periodic trajectory of a certain period is a necessary and sufficient condition for the existence of a consistent d-periodic trajectory of the same period, for any value of d.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (RA 516/14-1)
- Grantová Agentura České Republiky (19-06175J)
- MSMT INTER-EXCELLENCE Project (LTAUSA19098)
- RVO (67985840)
This publication has 15 references indexed in Scilit:
- Extremum Cycle Times in Time Interval ModelsIEEE Transactions on Automatic Control, 2017
- Analysis of Cycle Time in Interval P-Time Event Graphs in Dioid AlgebrasIFAC-PapersOnLine, 2017
- Modelling, analysis and control of electroplating line modelled by P-time event graphsIFAC Proceedings Volumes, 2013
- Duality and interval analysis over idempotent semiringsLinear Algebra and its Applications, 2012
- Max-linear Systems: Theory and Algorithms2010
- Schedulability Analysis of Time-Constrained Cluster Tools With Bounded Time Variation by an Extended Petri NetIEEE Transactions on Automation Science and Engineering, 2008
- Control of an electroplating line in the max and min algebrasInternational Journal of Systems Science, 1999
- A parametric critical path problem and an application for cyclic schedulingDiscrete Applied Mathematics, 1998
- P-Time Petri Nets for Manufacturing Systems with Staying Time ConstraintsIFAC Proceedings Volumes, 1997
- Topics in Matrix Analysis1991