Abstract: Рассматривается задача календарного планирования с ограниченными ре- сурсами по критерию минимизации длины расписания. В задаче учитываются технологические ограничения предшествования работ, а также ресурсные ограничения. Все ограниченные ресурсы считаются возобновимыми. Предложена схема ветвления, основанная на представлении расписания работ в виде списка, а также использовались два алгоритма построения нижней границы. Одна из них получена из решения релаксированной задачи со складируемыми ресурсами, другая – из решения другой релаксированной задачи, в которой свойство возобновимости сохраняется, а все работы имеют единичную длительность выполнения. Численный эксперимент на примерах из библиотеки PCPLIB показал конкурентоспособность предложенного алгоритма. Результаты численных экспериментов приводятся.

Cite: Гончаров Е.Н. , Мишин Д.В.
ТОЧНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ С ОГРАНИЧЕННЫМИ РЕСУРСАМИ
Прикладная математика и фундаментальная информатика. 2017. Т.4. №1. С.43–53.

Identifiers: No identifiers

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