Research output: Contribution to journal › Article › peer-review
A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem. / Goncharov, E. N.
In: Journal of Applied and Industrial Mathematics, Vol. 16, No. 4, 2022, p. 672-683.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem
AU - Goncharov, E. N.
N1 - Публикация для корректировки.
PY - 2022
Y1 - 2022
N2 - We consider the resource-constrained project scheduling problem (RCPSP). The problemaccounts for technological constraints of activities precedence together with resource constraints.All resources are renewable. Activities interruptions are not allowed. This problem is NP-hard inthe strong sense. We present a new local search algorithm that uses a Tabu-list and two types ofneighborhoods. The algorithm is evaluated using three data bases of instances of the problem: 480instances of 60 activities, 480 of 90, and 600 of 120 activities, respectively, taken from the PSPLIBlibrary available online. Numerical experiments demonstrate that the proposed algorithm producesbetter results than existing algorithms described in the literature for large-sized instances. Forsome instances from the dataset j120, the best known heuristic solutions were improved.
AB - We consider the resource-constrained project scheduling problem (RCPSP). The problemaccounts for technological constraints of activities precedence together with resource constraints.All resources are renewable. Activities interruptions are not allowed. This problem is NP-hard inthe strong sense. We present a new local search algorithm that uses a Tabu-list and two types ofneighborhoods. The algorithm is evaluated using three data bases of instances of the problem: 480instances of 60 activities, 480 of 90, and 600 of 120 activities, respectively, taken from the PSPLIBlibrary available online. Numerical experiments demonstrate that the proposed algorithm producesbetter results than existing algorithms described in the literature for large-sized instances. Forsome instances from the dataset j120, the best known heuristic solutions were improved.
KW - PSPLIB
KW - Tabu search
KW - renewable resources
KW - resource-constrained project scheduling problem
KW - variable neighborhood search
UR - https://www.mendeley.com/catalogue/5db9f0c5-76ff-3197-acc6-c210a3dc16d1/
U2 - 10.1134/S1990478922040081
DO - 10.1134/S1990478922040081
M3 - Article
VL - 16
SP - 672
EP - 683
JO - Journal of Applied and Industrial Mathematics
JF - Journal of Applied and Industrial Mathematics
SN - 1990-4789
IS - 4
ER -
ID: 55697604