TY - JOUR

T1 - Algebraic solution of project scheduling problems with temporal constraints

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

AU - Губанов, Сергей Александрович

N1 - Krivulin N., Gubanov S. Algebraic solution of project scheduling problems with temporal constraints // Operational Research. 2024. Vol.24, N4. P.69. DOI: 10.1007/s12351-024-00880-3. URL: https://link.springer.com/article/10.1007/s12351-024-00880-3

PY - 2024/12/1

Y1 - 2024/12/1

N2 - New solutions for problems in optimal scheduling of activities in a project under temporal constraints are developed in the framework of tropical algebra which deals with the theory and application of algebraic systems with idempotent operations. We start with a constrained tropical optimization problem that has an objective function represented as a vector form given by an arbitrary matrix, and that can be solved analytically in a closed but somewhat complicated form. We examine a special case of the problem when the objective function is given by a matrix of unit rank, and show that the solution can be sufficiently refined in this case, which results in an essentially simplified analytical form and reduced computational complexity of the solution. We exploit the obtained result to find complete solutions of project scheduling problems to minimize the project makespan and the maximum absolute deviation of start times of activities under temporal constraints. The constraints under consideration include “start–start”, “start–finish” and “finish–start” precedence relations, release times, release deadlines and completion deadlines for activities. As an application, we consider optimal scheduling problems of a vaccination project in a medical centre.

AB - New solutions for problems in optimal scheduling of activities in a project under temporal constraints are developed in the framework of tropical algebra which deals with the theory and application of algebraic systems with idempotent operations. We start with a constrained tropical optimization problem that has an objective function represented as a vector form given by an arbitrary matrix, and that can be solved analytically in a closed but somewhat complicated form. We examine a special case of the problem when the objective function is given by a matrix of unit rank, and show that the solution can be sufficiently refined in this case, which results in an essentially simplified analytical form and reduced computational complexity of the solution. We exploit the obtained result to find complete solutions of project scheduling problems to minimize the project makespan and the maximum absolute deviation of start times of activities under temporal constraints. The constraints under consideration include “start–start”, “start–finish” and “finish–start” precedence relations, release times, release deadlines and completion deadlines for activities. As an application, we consider optimal scheduling problems of a vaccination project in a medical centre.

KW - idempotent semiefield

KW - tropical optimization

KW - minimax optimization problem

KW - temporal project scheduling

KW - project management

KW - Project management

KW - Temporal project scheduling

KW - 90C24

KW - Idempotent semiefield

KW - 90C47

KW - 90B35

KW - 15A80

KW - Tropical optimization

KW - Minimax optimization problem

UR - https://arxiv.org/abs/2401.09216

UR - https://www.mendeley.com/catalogue/ad231d49-baf3-3c0c-a9d0-0542e6ce0dbb/

U2 - 10.1007/s12351-024-00880-3

DO - 10.1007/s12351-024-00880-3

M3 - Article

VL - 24

JO - Operational Research

JF - Operational Research

SN - 1109-2858

IS - 4

M1 - 69

ER -