Periodic trajectories in P-time event graphs and the non-positive circuit weight problem

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 the present paper, 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$.

Minor corrections

References in corpus (1)

• The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory

Cited by in corpus (4)

• Switched max-plus linear-dual inequalities: cycle time analysis and applications
• Weak consistency of P-time event graphs
• The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory
• Switched Max-Plus Linear-Dual Inequalities: Application in Scheduling of Multi-Product Processing Networks