Algebraic solution of project scheduling problems with temporal constraints

Nikolai Krivulin () and Sergey Gubanov ()
Additional contact information
Nikolai Krivulin: St. Petersburg State University
Sergey Gubanov: JSC “Design Bureau “Lutch”

Operational Research, 2024, vol. 24, issue 4, No 17, 27 pages

Abstract: Abstract 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.

Keywords: Idempotent semiefield; Tropical optimization; Minimax optimization problem; Temporal project scheduling; Project management; 90C24; 15A80; 90C47; 90B35 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-024-00880-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:24:y:2024:i:4:d:10.1007_s12351-024-00880-3

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-024-00880-3

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().