Max Plus at Work - Modelling and Analysis of Synchronized Systems - A Course on Max-Plus Algebra and Its Applications
This is the first textbook on max-plus algebra, which represents a convenient tool for the description and analysis of discrete event systems like traffic systems, computer communication systems, production lines and flows in networks. The book is divided into three main parts and an introductory chapter, which illustrates main ideas in an informal way. The first part provides the foundations of max-plus algebra viewed as a mutation of conventional algebra, where instead of addition and multiplication the central role is played by the operations maximization and addition, respectively. It starts with the definitions of fundamental concepts (max-plus algebra and semiring, vectors and matrices over max-plus algebra) and an investigation of their properties. Then the spectral theory of matrices over a max-plus semiring is built, followed by a study of linear systems in max-plus algebra and their behaviour in terms of throughput, growth rate and periodicity.
The first part of the book ends with two chapters dealing with numerical procedures for the calculation of eigenvalues and eigenmodes. The second part starts with an introduction to Petri nets and their subclass, event graphs that are shown to be a suitable modelling aid for constructions of max-plus linear systems. Real-life applications related to timetable design for railway networks are discussed. It covers construction of large-scale systems, the throughput and periodicity of such systems, delay propagation, stability measures for railway networks and optimal allocation of trains and their ordering. The last part deals with various extensions (stochastic extensions, min-max-plus systems that also contain a minimization operation and thus enable modelling of a larger class of problems, and continuous flows on networks viewed as the continuous counterpart of discrete events on networks). The whole text ends with a bibliography, a list of frequently used symbols and an index. The book can be warmly recommended to final-year undergraduate students of mathematics, as well as to all interested applied mathematicians, operations researchers, econometricians and civil, electrical and mechanical engineers with quantitative backgrounds.