TY - JOUR

T1 - Solving a tropical optimization problem with application to optimal scheduling

AU - Krivulin, N. K.

AU - Basko, U. L.

N1 - Krivulin N. K., Basko U. L. Solving a tropical optimization problem with application to optimal scheduling // Vestnik St. Petersburg University, Mathematics. 2019. Vol. 52, N3. P. 293-300. DOI: 10.1134/S1063454119030117

PY - 2019

Y1 - 2019

N2 - A multidimensional optimization problem is formulated and solved in terms of tropical mathematics that is concerned with the theory and applications of semi-rings with idempotent addition. The problem, whose objective function is defined by a matrix, is proposed to be solved via idempotent algebra and tropical optimization tools. A strict lower bound is first derived for the objective function, used for solving the problem, to allow the evaluation of its minimum value. The objective function and its minimum value are then combined into an equation whose complete solution is obtained in the form of all eigenvectors of the matrix. A practical application of the problem is considered using the example of an explicit solution for the optimal scheduling of a project that consists of a set of activities defined by constraints on their start and end times. The optimality criterion for scheduling is defined to minimize the maximum, over all activities, of the working cycle time, which is described as the time interval between the start and the end of the activity. The analytical result extends and supplements the existing algorithmic numerical solutions to optimal scheduling problems. As an illustrative example, the solution of a problem to schedule a project consisting of three activities is presented to illustrate the result.

AB - A multidimensional optimization problem is formulated and solved in terms of tropical mathematics that is concerned with the theory and applications of semi-rings with idempotent addition. The problem, whose objective function is defined by a matrix, is proposed to be solved via idempotent algebra and tropical optimization tools. A strict lower bound is first derived for the objective function, used for solving the problem, to allow the evaluation of its minimum value. The objective function and its minimum value are then combined into an equation whose complete solution is obtained in the form of all eigenvectors of the matrix. A practical application of the problem is considered using the example of an explicit solution for the optimal scheduling of a project that consists of a set of activities defined by constraints on their start and end times. The optimality criterion for scheduling is defined to minimize the maximum, over all activities, of the working cycle time, which is described as the time interval between the start and the end of the activity. The analytical result extends and supplements the existing algorithmic numerical solutions to optimal scheduling problems. As an illustrative example, the solution of a problem to schedule a project consisting of three activities is presented to illustrate the result.

KW - idempotent semi-field

KW - (max,+)-algebra

KW - eigenvalues and eigenvectors of matrices

KW - tropical optimization

KW - scheduling problem

UR - http://www.scopus.com/inward/record.url?scp=85071946159&partnerID=8YFLogxK

U2 - 10.1134/S1063454119030117

DO - 10.1134/S1063454119030117

M3 - Article

VL - 52

SP - 293

EP - 300

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 3

ER -