A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem Full article
| Journal |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2022, Volume: 16, Number: 4, Pages: 672–683 Pages count : 12 DOI: 10.1134/S1990478922040081 | ||||
| Tags | resource-constrained project scheduling problem, renewable resources, Tabu search, variable neighborhood search, PSPLIB | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
Abstract:
We consider the resource-constrained project scheduling problem (RCPSP). The
problem accounts for technological constraints of activities precedence together with resource
constraints. All resources are renewable. Activities interruptions are not allowed. This problem
is NP-hard in the strong sense. We present a new local search algorithm that uses a Tabu-list
and two types of neighborhoods. The algorithm is evaluated using three data bases of instances
of the problem: 480 instances of 60 activities, 480 of 90, and 600 of 120 activities, respectively,
taken from the PSPLIB library available online. Numerical experiments demonstrate that the
proposed algorithm produces better results than existing algorithms described in the literature
for large-sized instances. For some instances from the dataset j120, the best known heuristic
solutions were improved.
Cite:
Goncharov E.N.
A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem
Journal of Applied and Industrial Mathematics. 2022. V.16. N4. P.672–683. DOI: 10.1134/S1990478922040081 Scopus РИНЦ OpenAlex
A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem
Journal of Applied and Industrial Mathematics. 2022. V.16. N4. P.672–683. DOI: 10.1134/S1990478922040081 Scopus РИНЦ OpenAlex
Original:
Гончаров Е.Н.
Алгоритм локального поиска для задачи календарного планирования с ограниченными ресурсами
Дискретный анализ и исследование операций. 2022. Т.29. №4. С.15-37. DOI: 10.33048/daio.2022.29.734 РИНЦ
Алгоритм локального поиска для задачи календарного планирования с ограниченными ресурсами
Дискретный анализ и исследование операций. 2022. Т.29. №4. С.15-37. DOI: 10.33048/daio.2022.29.734 РИНЦ
Dates:
| Submitted: | Apr 21, 2022 |
| Accepted: | May 26, 2022 |
| Published print: | Mar 6, 2023 |
| Published online: | Mar 6, 2023 |
Identifiers:
| Scopus: | 2-s2.0-85149973586 |
| Elibrary: | 59198323 |
| OpenAlex: | W4323344556 |
Citing:
Пока нет цитирований