On Propeties of the LIP Model in the Class of RCPSPs

Andrey I. Kibzun and Varvara A. Rasskazova ()
Additional contact information
Andrey I. Kibzun: Moscow Aviation Institute, National Research University, 125993 Moscow, Russia
Varvara A. Rasskazova: Moscow Aviation Institute, National Research University, 125993 Moscow, Russia

Mathematics, 2023, vol. 11, issue 9, 1-10

Abstract: The Resource-Constrained Project Scheduling Problem (RCPSP) is a significant and important issue in the field of project management. It arises during project planning when resources must be allocated among tasks with specific time constraints. Solving this problem enables the optimization of project execution time, minimization of resource costs, and increased efficiency of the entire team’s work. Due to the increasing complexity of projects, the development of new methods and algorithms to solve RCPSP is relevant nowadays. The existing methods for obtaining approximate solutions with guaranteed accuracy are characterized by high computational complexity and are often ineffective in considering the specific constraints of the problem. Fast heuristic approaches also have several drawbacks related to fine-tuning algorithm parameters and strong dependence on the quality of the initial solution. This paper investigates the features of the linear integer programming (LIP) model to solve RCPSP. The proposed LIP model is universal and scalable, enabling it to fully consider all specific aspects of the problem. The paper provides a construction algorithm of a functional space of the model and discusses the estimation of complexity. From the estimation of the mentioned algorithm’s complexity, it is observed that the general complexity of the proposed approach is proportional to a controlled parameter of the LIP. Increasing this controlled parameter can significantly reduce the dimensionality of the initial problem, thus leading to the effectiveness of the LIP model-based approach in terms of computational resources. An upper bound for the value of this parameter is obtained for a special case of the RCPSP. Using the obtained balanced value, a numerical experiment was carried out on real-world samples.

Keywords: linear integer programming (LIP); resource constrained project scheduling problem (RCPSP); continuous production; controlled parameter; upper bound (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/9/2086/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/9/2086/ (text/html)

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:gam:jmathe:v:11:y:2023:i:9:p:2086-:d:1134790

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().