Tropical optimization problems with application to project scheduling with minimum makespan

Abstract

We consider multidimensional optimization problems in the framework of tropical mathematics. The problems are formulated to minimize a nonlinear objective function that is defined on vectors over an idempotent semifield and calculated by means of multiplicative conjugate transposition. We start with an unconstrained problem and offer two complete direct solutions to demonstrate different practicable argumentation schemes. The first solution consists of the derivation of a sharp lower bound for the objective function and the solving of an equation to find all vectors that yield the bound. The second is based on extremal properties of the spectral radius of matrices and involves the evaluation of this radius for a certain matrix. This solution is then extended to problems with boundary constraints that specify the feasible solution set by a double inequality, and with a linear inequality constraint given by a matrix. To illustrate one application of the results obtained, we solve problems in project scheduling under the minimum makespan criterion subject to various precedence constraints on the time of initiation and completion of activities in the project. Simple numerical examples are given to show the computational technique used for solutions.

22 pages

References in corpus (11)

• Tropical linear-fractional programming and parametric mean payoff games
• Extremal properties of tropical eigenvalues and solutions to tropical optimization problems
• A multidimensional tropical optimization problem with nonlinear objective function and linear constraints
• A constrained tropical optimization problem: complete solution and application example
• Algebraic solutions to multidimensional minimax location problems with Chebyshev distance
• The Analytic Hierarchy Process, Max Algebra and Multi-objective Optimisation
• A new algebraic solution to multidimensional minimax location problems with Chebyshev distance
• Complete solution of a constrained tropical optimization problem with application to location analysis
• A maximization problem in tropical mathematics: a complete solution and application examples
• Direct solutions to tropical optimization problems with nonlinear objective functions and boundary constraints
• Explicit solution of a tropical optimization problem with application to project scheduling

Cited by in corpus (5)

• Tropical implementation of the Analytical Hierarchy Process decision method
• Direct solution to constrained tropical optimization problems with application to project scheduling
• Using tropical optimization techniques in bi-criteria decision problems
• Tropical optimization technique in bi-objective project scheduling under temporal constraints
• Algebraic solution of project scheduling problems with temporal constraints