Solving a tropical optimization problem with application to optimal scheduling

Николай Кимович Кривулин, Ульяна Львовна Баско

Research outputpeer-review

Abstract

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.
Original language English 293-300 Vestnik St. Petersburg University: Mathematics 52 3 4 Sep 2019 https://doi.org/10.1134/S1063454119030117 Published - 2019

Fingerprint

Optimal Scheduling
Optimization Problem
Objective function
Idempotent
Semiring
Optimality Criteria
Explicit Solution
Eigenvector
Scheduling Problem
Schedule
Scheduling
Numerical Solution
Lower bound
Minimise
Algebra
Interval
Optimization problem
Optimization
Evaluation

Scopus subject areas

• Control and Optimization
• Algebra and Number Theory
• Management Science and Operations Research

Cite this

@article{aa667eb29e4c446391bcd7b869382497,
title = "Solving a tropical optimization problem with application to optimal scheduling",
abstract = "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.",
keywords = "idempotent semi-field, (max,+)-algebra, eigenvalues and eigenvectors of matrices, tropical optimization, scheduling problem",
author = "Кривулин, {Николай Кимович} and Баско, {Ульяна Львовна}",
note = "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",
year = "2019",
doi = "10.1134/S1063454119030117",
language = "English",
volume = "52",
pages = "293--300",
journal = "Vestnik St. Petersburg University: Mathematics",
issn = "1063-4541",
publisher = "Pleiades Publishing",
number = "3",

}

In: Vestnik St. Petersburg University: Mathematics, Vol. 52, No. 3, 2019, p. 293-300.

Research outputpeer-review

TY - JOUR

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

AU - Кривулин, Николай Кимович

AU - Баско, Ульяна Львовна

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

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 -