Optimization Problems under (max; min) - Linear Constraint and Some Related Topics

Title: Optimization Problems under (max, min)-Linear Constraints and Some Related Topics. Author: Mahmoud Gad Department/Institue: Department of Probability and Mathematical Statis- tics Supervisor of the doctoral thesis: 1. Prof. RNDr. Karel Zimmermann,DrSc 2. Prof. Dr. Assem Tharwat, Cairo University, Egypt Abstract: Problems on algebraic structures, in which pairs of operations such as (max, +) or (max, min) replace addition and multiplication of the classical linear algebra have appeared in the literature approximately since the sixties of the last century. The first publications on these algebraic structures ap- peared by Shimbel [37] who applied these ideas to communication networks, Cunninghame-Green [12, 13], Vorobjov [40] and Gidffer [18] applied these alge- braic structures to problems of machine-time scheduling. A systematic theory of such algebraic structures was published probable for the first time in [14]. In recently appeared book [4] the readers can find latest results concerning theory and algorithms for (max, +)-linear systems of equations and inequalities. Since operation max replacing addition in no more a group, but a semigroup oppera- tion, it is a substantial difference between solving systems with variables on one side and systems with variables occuring on both sides of the equations...