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

Cite: Гончаров Е.Н. , Мишин Д.В.
ТОЧНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ С ОГРАНИЧЕННЫМИ РЕСУРСАМИ
VII Международная молодежная научно-практическая конференция с элементами научной школы, посвященной 60-летию Института математики им. С. Л. Соболева СО РАН 25 апр. - 4 мая 2017