Min-max functions |
| |
Authors: | Jeremy Gunawardena |
| |
Affiliation: | (1) Department of Computer Science, Stanford University, 94305 Stanford, CA;(2) Present address: Hewlett-Packard Labs, Filton Road, Stoke Gifford, BS12 6QZ Bristol, England |
| |
Abstract: | A variety of problems in operations research, control theory, computer science, etc., can be modeled as discrete event systems with maximum and minimum constraints. When these systems require only maximum constraints (or, dually, only minimum constraints) they can be studied by linear methods based on max-plus algebra. Systems with mixed constraints, however, are nonlinar from this perspective and relatively little is known about their behaviour. The paper lays the foundations of the theory of discrete event systems with mixed constraints. We introduce min-max functions,F:R
n
R
n
, which are constructed using finitely many operations of min, max and +, and study them as dynamical systems. Among other results, we give a complete account of the periodic behavior of functions of dimension 2; we introduce and characterize the concept of balance which generalizes irreducibility in the linear theory; and we give a formula for the cycle time (eigenvalue) of a min-max function which generalizes the maximum cycle mean formula. |
| |
Keywords: | cycle time discrete event system dynamical system eigenvalue fixed point max-plus algebra min-max function |
本文献已被 SpringerLink 等数据库收录! |
|