Быстрый алгоритм вычисления нижней оценки для решения задачи ресурсно-календарного планирования с тестированием на примерах библиотеки PSPLIB | Sciact - Система учета научной деятельности ИМ СО РАН

Быстрый алгоритм вычисления нижней оценки для решения задачи ресурсно-календарного планирования с тестированием на примерах библиотеки PSPLIB Научная публикация

Журнал

Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN)
ISSN: 0134-4889 , E-ISSN: 2658-4786

Вых. Данные

Год: 2021, Том: 27, Номер: 1, Страницы: 22-36 Страниц : 15 DOI: 10.21538/0134-4889-2021-27-1-22-36

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

управление проектами, задача планирования проектов с ограниченными ресурсами, нескладируемые ресурсы, складируемые ресурсы, полиномиальный алгоритм, PSPLIB, нижняя оценка.

Авторы

Гимади Э.Х. ¹ , Гончаров Е.Н. ¹ , Штепа А.А. ²

Организации

1	Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences
2	Novosibirsk State University (NSU)

В статье рассматривается труднорешаемая задача ресурсно-календарного планирования (ЗРКП). Пред- полагается, что функции интенсивности выделения и потребления ресурсов постоянны в заданных вре- менн´ ых интервалах, а директивные сроки отсутствуют. Построена процедура вычисления нижней оценки длины расписания ЗРКП на основе релаксации задачи (посредством замены нескладируемых ресурсов на складируемые). Временн´ ая сложность этой процедуры зависит от числа работ n как функция O(nlogn). Из анализа численных расчетов (проведенных на примерах задач из электронной библиотеки PSPLIB) следует высокая конкурентоспособность предлагаемой процедуры, дающей в некоторых сериях задач результаты, близкие к лучшим значениям нижних оценок, опубликованных в библиотеке PSPLIB, при чрезвычайно малом процессорном времени (миллисекунды).

Гимади Э.Х. , Гончаров Е.Н. , Штепа А.А.
Быстрый алгоритм вычисления нижней оценки для решения задачи ресурсно-календарного планирования с тестированием на примерах библиотеки PSPLIB
Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN). 2021. Т.27. №1. С.22-36. DOI: 10.21538/0134-4889-2021-27-1-22-36 WOS Scopus OpenAlex

Поступила в редакцию:	25 сент. 2020 г.
Принята к публикации:	25 нояб. 2020 г.

Web of science:	WOS:000630926400003
Scopus:	2-s2.0-85114222080
OpenAlex:	W3137271724

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