Strong, Strongly Universal and Weak Interval Eigenvectors in Max-Plus Algebra

Abstract

The scheduling or project management optimization problems, in which the objective function depends on the operations maximum amd plus, can be naturally formulated and solved in max-plus algebra. A system of discrete activations of processors in parallel computing, or activations of some other cooperating machines, is described by a systems of max-plus linear equations. In particular, if the system is in a steady state, such as a synchronized computer network in data processing, then the state vector is an eigenvector of the system. In particular, if the system is in a steady state, such as a synchronized computer network in data processing, then the state vector is an eigenvector of the system. The properties and recognition algorithms for several types of interval eigenvectors are studied in this paper. Then, the strong and the strongly universal eigenvectors are studied and described as max-plus linear combinations of generators. Moreover, a polynomial recognition algorithm is suggested and its correctness is proved. Similar results are presented for the weak eigenvectors. The results are illustrated by numerical examples.