A maximization problem in tropical mathematics: a complete solution and application examples

Abstract

A multidimensional optimization problem is formulated in the tropical mathematics setting as to maximize a nonlinear objective function, which is defined through a multiplicative conjugate transposition operator on vectors in a finite-dimensional semimodule over a general idempotent semifield. The study is motivated by problems drawn from project scheduling, where the deviation between initiation or completion times of activities in a project is to be maximized subject to various precedence constraints among the activities. To solve the unconstrained problem, we first establish an upper bound for the objective function, and then solve a system of vector equations to find all vectors that yield the bound. As a corollary, an extension of the solution to handle constrained problems is discussed. The results obtained are applied to give complete direct solutions to the motivating problems from project scheduling. Numerical examples of the development of optimal schedules are also presented.

19 pages

Cited by in corpus (5)

• Tropical implementation of the Analytical Hierarchy Process decision method
• Tropical optimization problems with application to project scheduling with minimum makespan
• Using pairwise comparisons to determine consumer preferences in hotel selection
• Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling
• Methods of tropical optimization in rating alternatives based on pairwise comparisons