Метод ветвей и границ для решения задачи минимизации платы за внешние ресурсы

Автор(ы): Мусатова Е.Г., Лазарев А.А.

Выпуск: 117

Рубрика: Математическая теория управления

Год: 2025

Библиография: Мусатова Е.Г., Лазарев А.А. Метод ветвей и границ для решения задачи минимизации платы за внешние ресурсы // Управление большими системами. - 2025. - Вып. 117. - С.119-140.

Дата опубликования: 30.09.2025

Ключевые слова: дискретная оптимизация, теория расписаний, метод ветвей и границ, алгоритмы, минимизация использования внешних ресурсов

Аннотация: Рассматривается задача построения расписания работ, выполняемых на одном приборе. Заданы отношения предшествования между работами, а также подмножества работ, требующих дополнительные внешние ресурсы, за аренду которых взимается плата. Для каждого внешнего ресурса однозначно определены крайние (первая и последняя) работы, выполняемые с использованием этого ресурса. Необходимо упорядочить работы, не нарушив отношения предшествования и минимизируя суммарные арендные выплаты. Доказана теорема об NP-трудности данной задачи в сильном смысле даже при условии одинаковой продолжительности всех работ и одинаковых цен на все внешние ресурсы. На основе свойств целевой функции для решения поставленной задачи предлагаются нижние оценки и метод ветвей и границ, в котором перебор ведется по допустимым перестановкам крайних работ, использующих внешние ресурсы. Проведенный вычислительный эксперимент показал эффективность предлагаемых нижних оценок целевой функции, позволяющих отсекать бесперспективные ветви в дереве поиска. Определен тип входных данных задачи, для которого разработанный метод работает лучше других известных вариантов точных методов, в которых перебор происходит на множестве всех работ. В частности, на задачах большой размерности при количестве внешних ресурсов меньше 20 данный метод оказывается эффективнее решателя CP Optimizer на базе программирования в ограничениях.

Author(s): Musatova E., Lazarev A.

Article title: Branch-and-bound algorithn for solving problem of minimizing fees for external resources

Issue: 117

Year: 2025

Keywords: discrete optimization, scheduling, branch-and-bound method, algorithms, minimizing the use of external resources

Abstract: We consider a problem of scheduling jobs performed on a single machine. Precedence relations between jobs are established, as well as subsets of jobs that require additional external resources, for which a fee is charged. For each external resource, the extreme (first and last) job to be executed using that resource is uniquely determined. It is necessary to order the jobs without violating the precedence relations and minimizing total rent payments. We have proved that this problem is NP-hard in the strong sense, even if the processing times of all jobs are the same and the prices of all external resources are equal. Based on the properties of the objective function, lower bounds and the branch-and-bound method are proposed to solve the problem. In this method, enumeration is performed according to feasible permutations of extreme jobs using external resources. The computational experiment showed the efficiency of the proposed lower bounds of the objective function, which make it possible to cut off unpromising branches in the search tree. We also determined the type of input data for which the developed method is more successful than another known variant of exact methods that enumerate all jobs. In particular, for large-dimensional problems with fewer than 20 external resources, this method proves to be more efficient than CP Optimizer solver which is based on constraint programming.