Standard

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 journalArticlepeer-review

Harvard

APA

Vancouver

Goncharov EN. A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem. Journal of Applied and Industrial Mathematics. 2022;16(4):672-683. doi: 10.1134/S1990478922040081

Author

Goncharov, E. N. / A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem. In: Journal of Applied and Industrial Mathematics. 2022 ; Vol. 16, No. 4. pp. 672-683.

BibTeX

@article{a7b647025f25477c9143b0b5704b932f,
title = "A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem",
abstract = "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.",
keywords = "PSPLIB, Tabu search, renewable resources, resource-constrained project scheduling problem, variable neighborhood search",
author = "Goncharov, {E. N.}",
note = "Публикация для корректировки.",
year = "2022",
doi = "10.1134/S1990478922040081",
language = "English",
volume = "16",
pages = "672--683",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "4",

}

RIS

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