Tropical optimization problems with application to project scheduling with minimum makespan

Nikolai Krivulin

Published 2014-03-02, updated 2014-12-15Version 3

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 in a finite-dimensional semimodule over an idempotent semifield and calculated by means of multiplicative conjugate transposition. We start with an unconstrained problem and offer two complete direct solutions, which follow different 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. The second 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. We apply the results obtained to solve problems in project scheduling under the minimum makespan criterion subject to various precedence constraints imposed on the time of initiation and completion of activities in the project. To illustrate the solutions, simple numerical examples are also included.