DZDavide Zorzenon

Davide Zorzenon

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Davide Zorzenon has a total of 8 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Infinite precedence graphs for consistency verification in P-time event graphs

    by Davide Zorzenon, Jörg Raisch

    Precedence constraints are inequalities used to model time dependencies. In 1958, Gallai proved that a finite system of precedence constraints admits solutions if and only if the corresponding precedence graph does not contain positive-weight circuits. We show that this result extends naturally to the case of infinitely many constraints. We then analyze two specific classes of infinite precedence graphs – $$\mathbb {N}$$ -periodic and ultimately periodic graphs – and prove that the existence of solutions of their related constraints can be verified in strongly polynomial time. The obtained algorithms find applications in P-time event graphs, which are a subclass of P-time Petri nets able to model production systems under cyclic schedules where tasks need to be performed within given time windows.


  • Open Access

    Infinite precedence graphs for consistency verification in P-time event graphs

    by Davide Zorzenon, Jörg Raisch

    Precedence constraints are inequalities used to model time dependencies. In 1958, Gallai proved that a finite system of precedence constraints admits solutions if and only if the corresponding precedence graph does not contain positive-weight circuits. We show that this result extends naturally to the case of infinitely many constraints. We then analyze two specific classes of infinite precedence graphs -- $\mathbb{N}$-periodic and ultimately periodic graphs -- and prove that the existence of solutions of their related constraints can be verified in strongly polynomial time. The obtained algorithms find applications in P-time event graphs, which are a subclass of P-time Petri nets able to model production systems under cyclic schedules where tasks need to be performed within given time windows.

  • Open Access

    Switched max-plus linear-dual inequalities: cycle time analysis and applications

    by Davide Zorzenon, Jan Komenda, Jörg Raisch

    P-time event graphs are discrete event systems suitable for modeling processes in which tasks must be executed in predefined time windows. Their dynamics can be represented by max-plus linear-dual inequalities (LDIs), i.e., systems of linear dynamical inequalities in the primal and dual operations of the max-plus algebra. We define a new class of models called switched LDIs (SLDIs), which allow to switch between different modes of operation, each corresponding to a set of LDIs, according to a sequence of modes called schedule. In this paper, we focus on the analysis of SLDIs when the considered schedule is fixed and either periodic or intermittently periodic. We show that SLDIs can model a wide range of applications including single-robot multi-product processing networks, in which every product has different processing requirements and corresponds to a specific mode of operation. Based on the analysis of SLDIs, we propose algorithms to compute: i. minimum and maximum cycle times for these processes, improving the time complexity of other existing approaches; ii. a complete trajectory of the robot including start-up and shut-down transients.


  • Open Access

    Switched max-plus linear-dual inequalities: cycle time analysis and applications

    by Davide Zorzenon, Jan Komenda, Jörg Raisch

    P-time event graphs are discrete event systems suitable for modeling processes in which tasks must be executed in predefined time windows. Their dynamics can be represented by max-plus linear-dual inequalities (LDIs), i.e., systems of linear dynamical inequalities in the primal and dual operations of the max-plus algebra. We define a new class of models called switched LDIs (SLDIs), which allow to switch between different modes of operation, each corresponding to a set of LDIs, according to a sequence of modes called schedule. In this paper, we focus on the analysis of SLDIs when the considered schedule is fixed and either periodic or intermittently periodic. We show that SLDIs can model a wide range of applications including single-robot multi-product processing networks, in which every product has different processing requirements and corresponds to a specific mode of operation. Based on the analysis of SLDIs, we propose algorithms to compute: i. minimum and maximum cycle times for these processes, improving the time complexity of other existing approaches; ii. a complete trajectory of the robot including start-up and shut-down transients.

  • Open Access

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

    by Davide Zorzenon, Jan Komenda, Joerg Raisch

    Let us consider a parametric weighted directed graph in which every arc $(j,i)$ has weight of the form $w((j,i))=\max(P_{ij}+\lambda,I_{ij}-\lambda,C_{ij})$, where $\lambda$ is a real parameter and $P$, $I$ and $C$ are arbitrary square matrices with elements in $\mathbb{R}\cup\{-\infty\}$. In this paper, we design an algorithm that solves the Non-positive Circuit weight Problem (NCP) on this class of parametric graphs, which consists in finding all values of $\lambda$ such that the graph does not contain circuits with positive weight. This problem, which generalizes other instances of the NCP previously investigated in the literature, has applications in the consistency analysis of a class of discrete-event systems called P-time event graphs. The proposed algorithm is based on max-plus algebra and formal languages, and improves the worst-case complexity of other existing approaches, achieving strongly polynomial time complexity $\mathcal{O}(n^4)$ (where $n$ is the number of nodes in the graph).

  • Open Access

    Machine learning for computationally efficient electrical loads estimation in consumer washing machines

    by Vittorio Casagrande, Gianfranco Fenu, Felice Andrea Pellegrino, Gilberto Pin, Erica Salvato, Davide Zorzenon

    Estimating the wear of the single electrical parts of a home appliance without resorting to a large number of sensors is desirable for ensuring a proper level of maintenance by the manufacturers. Deep learning techniques can be effective tools for such estimation from relatively poor measurements, but their computational demands must be carefully considered, for the actual deployment. In this work, we employ one-dimensional Convolutional Neural Networks and Long Short-Term Memory networks to infer the status of some electrical components of different models of washing machines, from the electrical signals measured at the plug. These tools are trained and tested on a large dataset (502 washing cycles $$\approx$$ ≈ 1000 h) collected from four different washing machines and are carefully designed in order to comply with the memory constraints imposed by available hardware selected for a real implementation. The approach is end-to-end; i.e., it does not require any feature extraction, except the harmonic decomposition of the electrical signals, and thus it can be easily generalized to other appliances.


  • Open Access

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

    by Davide Zorzenon, Jan Komenda, Joerg Raisch

    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$.

  • Periodic Trajectories in P-Time Event Graphs and the Non-Positive Circuit Weight Problem

    by Davide Zorzenon, Jan Komenda, Jorg Raisch

    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.