Abstract: Рассматривается новая модификация обобщённой задачи о назначениях с ограничениями на объёмы и типы работ. Заданное множество работ необходимо распределить между агентами (исполнителями). Каждая работа имеет объём и тип. Для каждого агента заданы ограничения на количество типов назначенных работ, общий объём назначенных работ, а также эффективность выполнения работ. Требуется максимизировать суммарную эффективность назначения при заданных ограничениях на загрузку. Исследуется вычислительная сложность задачи. Предлагается алгоритм локального поиска с окрестностями произвольного размера, где учитываются известные подходы к решению обобщённой задачи о назначениях и дополнительные условия рассматриваемой задачи. Окрестности строятся путём частичного фиксирования значений переменных, соответствующих назначению работ. Для решения соответствующих подзадач используются точные алгоритмы из известных пакетов решения задач математического программирования. Экспериментальные результаты показывают, что предложенный алгоритм демонстрирует конкурентоспособные результаты по качеству получаемых решений в сравнении с гибридными алгоритмами на основе методов ветвей и отсечений из известных пакетов Gurobi и SCIP при заданном ограничении времени счёта на серии тестовых примеров с различными структурными свойствами.

Cite: Захарова Ю.В. , Заозёрская Л.А.
Матэвристика на основе локального поиска для одной модификации обобщённой задачи о назначениях
Дискретный анализ и исследование операций. 2026. Т.33. №1. С.71–90. DOI: 10.33048/daio.2026.33.842

Dates:

Submitted:	Oct 15, 2025
Accepted:	Dec 22, 2025
Published online:	Aug 25, 2026

Identifiers: No identifiers

Altmetrics: