Switched max-plus linear-dual inequalities: cycle time analysis and applications
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- The non-positive circuit weight problem in parametric graphs: A solution based on dioid theoryDiscrete Applied Mathematics, 2022
- Critical subsystems in time interval modelsDiscrete Event Dynamic Systems, 2020
- Analysis of Cycle Time in Interval P-Time Event Graphs in Dioid AlgebrasIFAC-PapersOnLine, 2017
- Steady state analysis of timed event graphs with time window constraintsDiscrete Applied Mathematics, 2014
- Towards a new schedulability technique of real-time systems modeled by P-time Petri netsThe International Journal of Advanced Manufacturing Technology, 2012
- Max-linear Systems: Theory and Algorithms2010
- Supervisory Control of (max,+) Automata: A Behavioral ApproachDiscrete Event Dynamic Systems, 2009
- Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence, setups, and time-window constraintsEuropean Journal of Operational Research, 2008
- Modelling and control of discrete event systems using switching max-plus-linear systemsControl Engineering Practice, 2006
- Cyclic scheduling in a robotic production lineJournal of Scheduling, 2002