A. Imaev and R.P. Judd (USA)
max-plus algebra, i/o graph, eigenproblem, flow-shop, in verse Monge matrix.
In this paper we consider cyclic flow-shop system, which dynamics can be described by the max-plus vector equation of the form s(k + 1) = D ⊗ s(k), where D is the Dynam ics matrix of the system calculated from processing times of operations. The method for finding D in O(nm2 ) time is presented. We prove that D fulfills the inverse Monge property, i.e. dij + dkl ≥ dil + dkj for any i < k, j < l. We do this by introducing the concept of i/o graph. I/o graphs can be used for modeling max-plus linear discrete event systems. We show the relation between structural properties of i/o graph and the inverse Monge properties of its corresponding matrix. The period of the system equals max-plus algebraic eigenvalue of D and, since D is an in verse Monge matrix, its max-plus algebraic eigenvalue can be found in just O(m) time [1].
Important Links:
Go Back
