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

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

В статье рассматривается труднорешаемая задача ресурсно-календарного планирования (ЗРКП). Предполагается, что функции интенсивности выделения и потребления ресурсов постоянны в заданных временных интервалах, а директивные сроки отсутствуют. Построена процедура вычисления нижней оценки длины расписания ЗРКП на основе релаксации задачи (посредством замены нескладируемых ресурсов на складируемые). Временная сложность этой процедуры зависит от числа работ n как функция О (n log n). Из анализа численных расчетов (проведенных на примерах задач из электронной библиотеки PSPLIB) следует высокая конкурентоспособность предлагаемой процедуры, дающей в некоторых сериях задач результаты, близкие к лучшим значениям нижних оценок, опубликованных в библиотеке PSPLIB, при чрезвычайно малом процессорном времени (миллисекунды).
Переведенное названиеA fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances
Язык оригиналарусский
Номер статьи3
Страницы (с-по)22-36
Число страниц15
ЖурналTrudy Instituta Matematiki i Mekhaniki UrO RAN
Том27
Номер выпуска1
DOI
СостояниеОпубликовано - 2021

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

  • project management
  • Resource-Constrained Project Scheduling Problem
  • renewable resources
  • cumulative resources
  • PSPLIB
  • lower bound
  • CLASSIFICATION

Предметные области OECD FOS+WOS

  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ
  • 1.01 МАТЕМАТИКА
  • 1.01.PN МАТЕМАТИКА, ПРИКЛАДНАЯ
  • 2.03.PU МЕХАНИКА

ГРНТИ

  • 27 МАТЕМАТИКА

Цитировать