TY - GEN
T1 - Lower Bound Polynomial Fast Procedure for the Resource-Constrained Project Scheduling Problem Tested on PSPLIB Instances
AU - Gimadi, E. Kh
AU - Goncharov, E. N.
AU - Shtepa, A. A.
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2021
Y1 - 2021
N2 - We consider the Resource-Constrained Project Scheduling Problem (RCPSP) with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. No activity preemption is allowed. We consider relaxation of RCPSP with special types of non-renewable resources to get a lower bound of the problem. We present new lower bound algorithm for the RCPSP with time complexity depending on the number of activities n as O(nlog n), and we test it on PSPLIB instances. Numerical experiments demonstrate that the proposed algorithm produces on some series of instances lower bounds very close to the best existing lower bounds published in the PSPLIB, while their calculation time is a fraction of a second. We get especially good marks for large-sized instances.
AB - We consider the Resource-Constrained Project Scheduling Problem (RCPSP) with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. No activity preemption is allowed. We consider relaxation of RCPSP with special types of non-renewable resources to get a lower bound of the problem. We present new lower bound algorithm for the RCPSP with time complexity depending on the number of activities n as O(nlog n), and we test it on PSPLIB instances. Numerical experiments demonstrate that the proposed algorithm produces on some series of instances lower bounds very close to the best existing lower bounds published in the PSPLIB, while their calculation time is a fraction of a second. We get especially good marks for large-sized instances.
KW - Cumulative resources
KW - Lower bound
KW - Project management
KW - PSPLIB
KW - Renewable resources
KW - Resource-constrained project scheduling problem
UR - http://www.scopus.com/inward/record.url?scp=85104756010&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-72610-2_31
DO - 10.1007/978-3-030-72610-2_31
M3 - Conference contribution
AN - SCOPUS:85104756010
SN - 9783030726096
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 407
EP - 420
BT - Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Selected Papers
A2 - van der Aalst, Wil M.
A2 - Batagelj, Vladimir
A2 - Ignatov, Dmitry I.
A2 - Khachay, Michael
A2 - Koltsova, Olessia
A2 - Kutuzov, Andrey
A2 - Kuznetsov, Sergei O.
A2 - Lomazova, Irina A.
A2 - Loukachevitch, Natalia
A2 - Napoli, Amedeo
A2 - Panchenko, Alexander
A2 - Pardalos, Panos M.
A2 - Pelillo, Marcello
A2 - Savchenko, Andrey V.
A2 - Tutubalina, Elena
PB - Springer Science and Business Media Deutschland GmbH
T2 - 9th International Conference on Analysis of Images, Social Networks and Texts, AIST 2020
Y2 - 15 October 2020 through 16 October 2020
ER -