TY - JOUR

T1 - Algebraic Solution of a Problem of Optimal Project Scheduling in Project Management

AU - Krivulin, N. K.

AU - Gubanov, S. A.

N1 - Publisher Copyright:
© 2021, Pleiades Publishing, Ltd.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/1

Y1 - 2021/1

N2 - Abstract: A problem of the optimal scheduling is considered for a project that consists of a certain set of works to be performed under given constraints on the time of starting and finishing the works. The deviation of the starting time of the works that needs to be minimized is taken as the optimality criterion for scheduling. Such problems arise in project management when it is required, due to technological, organizational, economic, or other reasons, to ensure, wherever possible, that all works start simultaneously. The scheduling problem under consideration is formulated as a constrained minimax optimization problem and then solved using methods of tropical (idempotent) mathematics, which deals with the theory and applications of semirings with idempotent addition. First, a tropical optimization problem is investigated, which is defined in terms of a general idempotent semifield (an idempotent semiring with invertible multiplication), and a complete analytical solution of the problem is derived. The result obtained is then applied to find a direct solution of the scheduling problem in a compact vector form ready for the further analysis of the solutions and straightforward computations. As an illustration, a numerical example of solving a problem of optimal scheduling is given for a project that consists of four works.

AB - Abstract: A problem of the optimal scheduling is considered for a project that consists of a certain set of works to be performed under given constraints on the time of starting and finishing the works. The deviation of the starting time of the works that needs to be minimized is taken as the optimality criterion for scheduling. Such problems arise in project management when it is required, due to technological, organizational, economic, or other reasons, to ensure, wherever possible, that all works start simultaneously. The scheduling problem under consideration is formulated as a constrained minimax optimization problem and then solved using methods of tropical (idempotent) mathematics, which deals with the theory and applications of semirings with idempotent addition. First, a tropical optimization problem is investigated, which is defined in terms of a general idempotent semifield (an idempotent semiring with invertible multiplication), and a complete analytical solution of the problem is derived. The result obtained is then applied to find a direct solution of the scheduling problem in a compact vector form ready for the further analysis of the solutions and straightforward computations. As an illustration, a numerical example of solving a problem of optimal scheduling is given for a project that consists of four works.

KW - idempotent semifield

KW - minimax optimization problem

KW - project management

KW - project scheduling

KW - tropical optimization

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

U2 - 10.1134/S1063454121010088

DO - 10.1134/S1063454121010088

M3 - Article

AN - SCOPUS:85102708492

VL - 54

SP - 58

EP - 68

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 1

ER -