Sciact
  • EN
  • RU

Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances Full article

Conference The 9th International Conference on Analysis of Images, Social Networks and Texts
15-16 Oct 2020 , Moscow
Journal Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349
Output data Year: 2021, Volume: 12602, Pages: 407-420 Pages count : 14 DOI: 10.1007/978-3-030-72610-2_31
Tags project management, Resource-Constrained Project Scheduling Problem, renewable resources, cumulative resources, PSPLIB, lower bound
Authors Gimadi E.Kh. 1,2 , Goncharov E.N. 1 , Shtepa A.A. 2
Affiliations
1 Sobolev Institute of Mathematics
2 Novosibirsk State University

Abstract: We consider the intractable Resource-Constrained Project Scheduling Problem (RCPSP). It is assumed that the intensity functions of resource allocation and consumption are constant on specified time intervals and there are no deadlines. The procedure for calculating the lower bound for the RCPSP is constructed on the basis of the relaxation of the problem by replacing renewable resources with cumulative ones. The time complexity of this procedure depends on the number of activities n as a function of O(nlogn). From the analysis of numerical experiments (which are carried out on examples of problems from the electronic library PSPLIB), it follows that the proposed procedure is highly competitive, and in some series of instances gives results close to the best lower bounds published in the PSPLIB with dramatically small CPU time (milliseconds).
Cite: Gimadi E.K. , Goncharov E.N. , Shtepa A.A.
Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances
Lecture Notes in Computer Science. 2021. V.12602. P.407-420. DOI: 10.1007/978-3-030-72610-2_31 Scopus OpenAlex
Dates:
Published online: Apr 9, 2921
Identifiers:
Scopus: 2-s2.0-85104756010
OpenAlex: W3153380395
Citing: Пока нет цитирований
Altmetrics: