Sciact
  • EN
  • RU

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

Journal Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN)
ISSN: 0134-4889 , E-ISSN: 2658-4786
Output data Year: 2021, Volume: 27, Number: 1, Pages: 22-36 Pages count : 15 DOI: 10.21538/0134-4889-2021-27-1-22-36
Tags управление проектами, задача планирования проектов с ограниченными ресурсами, нескладируемые ресурсы, складируемые ресурсы, полиномиальный алгоритм, PSPLIB, нижняя оценка.
Authors Гимади Э.Х. 1 , Гончаров Е.Н. 1 , Штепа А.А. 2
Affiliations
1 Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences
2 Novosibirsk State University (NSU)

Abstract: В статье рассматривается труднорешаемая задача ресурсно-календарного планирования (ЗРКП). Пред- полагается, что функции интенсивности выделения и потребления ресурсов постоянны в заданных вре- менн´ ых интервалах, а директивные сроки отсутствуют. Построена процедура вычисления нижней оценки длины расписания ЗРКП на основе релаксации задачи (посредством замены нескладируемых ресурсов на складируемые). Временн´ ая сложность этой процедуры зависит от числа работ n как функция O(nlogn). Из анализа численных расчетов (проведенных на примерах задач из электронной библиотеки PSPLIB) следует высокая конкурентоспособность предлагаемой процедуры, дающей в некоторых сериях задач результаты, близкие к лучшим значениям нижних оценок, опубликованных в библиотеке PSPLIB, при чрезвычайно малом процессорном времени (миллисекунды).
Cite: Гимади Э.Х. , Гончаров Е.Н. , Штепа А.А.
Быстрый алгоритм вычисления нижней оценки для решения задачи ресурсно-календарного планирования с тестированием на примерах библиотеки 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
Dates:
Submitted: Sep 25, 2020
Accepted: Nov 25, 2020
Identifiers:
Web of science: WOS:000630926400003
Scopus: 2-s2.0-85114222080
OpenAlex: W3137271724
Citing: Пока нет цитирований
Altmetrics: