An Exploratory Study in Max-Plus Linear Parameter Varying Systems

Abstract

Max-plus algebra is an algebra that is entirely based on the mathematical operations max(a,b) and a+b, hence the name max-plus algebra. It can be used to describe Discrete Event Systems (DES) that require scheduling, such as a printer or train network. Max-plus algebra is studied because of its interesting properties, which make some non-linear systems in conventional algebra linear in max-plus algebra. These systems are called Max-Plus Linear (MPL) systems. This exploratory study introduces Max-Plus Linear Parameter Varying (MP-LPV) systems, systems that are not entirely linear in max-plus algebra but not that non-linear either, like LPV systems in conventional algebra. An urban railway line will be taken as an example of an MP-LPV system. Urban railway lines often operate relatively freely, with a passenger-dependent variable dwell time which can be modelled in max-plus algebra as a linear variable dependency on the arrival and departure times. It will be shown that such an MP-LPV system of an urban railway line can be rewritten to a set of linear inequalities, which can be used in an optimization framework to optimize for both minimal total passenger travel time and minimal absolute operation time. Some study cases will be shown in with it can be observed that these systems compute very rapidly, which makes a possible practical implementation interesting. Finally, some algebraic analysis on the MP-LPV system of an urban railway line will be done, such as on the definition of stability. But future work is still necessary on further analysis on the general class of MP-LPV systems.