×

zbMATH — the first resource for mathematics

Minimax algebra and applications. (English) Zbl 0739.90073
Summary: We consider theories of linear and of polynomial algebra, over two scalar systems, often called max-algebra and min-algebra. Here, max-algebra is the system \(M=\left(\mathbb R\cup\{-\infty\},\oplus,\otimes\right)\) where \(x\oplus y=\max(x,y)\) and \(x\otimes y=x+y\). Min-algebra is the dual system \(M'=\left(\mathbb R\cup\{+\infty\},\oplus',\otimes'\right)\) with \(x\oplus' y=\min(x,y)\) and \(x\otimes'y=x+y\). Towards the end we also consider minimax algebra, the system \(M''=\left(\mathbb R\cup\{-\infty,+\infty\},\, \oplus,\otimes,\oplus',\otimes'\right)\). Application fields discussed include location problems, machine scheduling, cutting and packing problems, discrete-event systems and path-finding problems.

MSC:
15A80 Max-plus and related algebras
90B80 Discrete location and assignment
90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
93C83 Control/observation systems involving computers (process control, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ()
[2] Carré, B.A., Graphs and networks, (1979), Oxford University Press Oxford
[3] Cohen, G.; Dubois, D.; Quadrat, J.P.; Viot, M., A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing, IEEE trans. automat. control, 30, 210-220, (1985) · Zbl 0557.93005
[4] Cuninghame-Green, R.A., Minimax algebra, () · Zbl 0498.90084
[5] Cunninghame-Green, R.A.; Meijer, P.F.J., An algebra for piecewise-linear minimax problems, Discrete appl math., 2, 267-294, (1980) · Zbl 0448.90070
[6] Cuninghame-Green, R.A.; Huisman, F., Convergence problems in minimax algebra, J. math. anal. appl., 88, 196-203, (1982) · Zbl 0483.90085
[7] Cuninghame-Green, R.A., The characteristic maxpolynomial of a matrix, Math. anal. appl., 95, 110-116, (1983) · Zbl 0526.90098
[8] Francis, R.L.; McGinnis, L.F.; White, J.A., Locational analysis, European J. oper. res., 12, 220-252, (1983) · Zbl 0502.90019
[9] Gondran, M.; Minoux, M., Graphes et algorithmes, (1979), Eyrolles Paris · Zbl 0497.05023
[10] Karp, R.M., A characterization of the minimum cycle Mean in a digraph, Discrete math., 23, 309-311, (1978) · Zbl 0386.05032
[11] Olsder, G.J., On the characteristic equation and minimal realizations for discrete-event dynamic systems, () · Zbl 0801.90038
[12] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, () · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.