A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem | Sciact - Система учета научной деятельности ИМ СО РАН

A Local Search Algorithm for the Resource-Constrained Project Scheduling Problem Научная публикация

Журнал

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Вых. Данные

Год: 2022, Том: 16, Номер: 4, Страницы: 672–683 Страниц : 12 DOI: 10.1134/S1990478922040081

Ключевые слова

resource-constrained project scheduling problem, renewable resources, Tabu search, variable neighborhood search, PSPLIB

Авторы

Goncharov E.N. ^1,2

Организации

1	Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
2	Novosibirsk State University

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0019

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.

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

Гончаров Е.Н.
Алгоритм локального поиска для задачи календарного планирования с ограниченными ресурсами
Дискретный анализ и исследование операций. 2022. Т.29. №4. С.15-37. DOI: 10.33048/daio.2022.29.734 РИНЦ

Поступила в редакцию:	21 апр. 2022 г.
Принята к публикации:	26 мая 2022 г.
Опубликована в печати:	6 мар. 2023 г.
Опубликована online:	6 мар. 2023 г.

Scopus:	2-s2.0-85149973586
РИНЦ:	59198323
OpenAlex:	W4323344556

Пока нет цитирований