Solving a tropical optimization problem with application to optimal scheduling

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

Результат исследований: Научные публикации в периодических изданияхстатьянаучнаярецензирование

1 Downloads (Pure)

Выдержка

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.
Язык оригиналаанглийский
Страницы (с-по)293-300
ЖурналVestnik St. Petersburg University: Mathematics
Том52
Номер выпуска3
Ранняя дата в режиме онлайн4 сен 2019
DOI
СостояниеОпубликовано - 2019

Отпечаток

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

  • Теория оптимизации
  • Алгебра и теория чисел
  • Теория управления и исследование операций

Цитировать

@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",

}

Solving a tropical optimization problem with application to optimal scheduling. / Кривулин, Николай Кимович; Баско, Ульяна Львовна.

В: Vestnik St. Petersburg University: Mathematics, Том 52, № 3, 2019, стр. 293-300.

Результат исследований: Научные публикации в периодических изданияхстатьянаучнаярецензирование

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 -