Open AccessAlgebraic solution of a problem of optimal project scheduling in project management
Author(s) -
Nikolay K. Krivulin,
Sergey A. Gubanov
Publication year - 2021
Publication title -
vestnik sankt-peterburgskogo universiteta. matematika. mehanika. astronomiâ/vestnik sankt-peterburgskogo universiteta. seriâ 1, matematika, mehanika, astronomiâ
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.233
H-Index - 8
eISSN - 2587-5884
pISSN - 1025-3106
DOI - 10.21638/spbu01.2021.107
Subject(s) - semiring , mathematical optimization , idempotence , mathematics , job shop scheduling , minimax , scheduling (production processes) , flow shop scheduling , computer science , discrete mathematics , schedule , operating system
A problem of optimal scheduling is considered for a project that consists of a certain set of works to be performed under given constraints on the times of start and finish of the works. As the optimality criterion for scheduling, the maximum deviation of the start time of works is taken to be minimized. Such problems arise in project management when it is required, according to technological, organizational, economic or other reasons, to provide, wherever possible, simultaneous start of all works. 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 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 further analysis of solutions and straightforward computations. As an illustration, a numerical example of solving optimal scheduling problem is given for a project that consists of four works.