Abstract: Рассматривается задача календарного планирования с ограниченными ресурсами по критерию минимума длины расписания. Все ресурсы возобновимы, прерывания операций (работ) не допускаются. Эта задача NP-трудна в сильном смысле. Ограниченность ресурсов лежит в основе сложности её решения. К числу перспективных для решения этой задачи относят эвристические алгоритмы. В данной работе предлагается ранжировать ресурсы по степени их критичности (дефицитности). Эвристические алгоритмы могут использовать это ранжирование ресурсов для построения сравнительно лучших эвристических решений. Ранжирование ресурсов получаем из релаксированной задачи, в которой ресурсы складируемы. Предложенный метод ранжирования ресурсов был применён в генетическом алгоритме. Вычислительные эксперименты на примерах из электронной библиотеки PSPLIB показали его эффективность. Для нескольких примеров из PSPLIB найдены новые лучшие (ранее неизвестные) решения.

Cite: Гимади Э.Х. , Гончаров Е.Н.
Об одном методе ранжирования ресурсов для задачи календарного планирования с ограниченными ресурсами
Дискретный анализ и исследование операций. 2026. Т.33. №2. С.5-18. DOI: 10.33048/daio.2026.33.864

Dates:

Submitted:	Apr 8, 2026
Accepted:	Apr 27, 2026
Published print:	Oct 1, 2026
Published online:	Oct 1, 2026

Identifiers: No identifiers

Altmetrics: