Introduction to max-linear programming

Let a circle plus b = max(a, b) and a circle times b = a + b for a, b is an element of R. Extend this pair of operations to matrices and vectors in the same way as in linear algebra. Being motivated by scheduling of multiprocessor interactive systems, we introduce max-linear programs of the form f(T) circle times x -> min (or max) subject to A circle times x circle plus c = B circle times x circle plus d and develop solution methods for both of them. We prove that these methods are pseudopolynomial if all entries are integers. This result is based on an existing pseudo-polynomial algorithm for solving the systems of the form A circle times x = B circle times y.