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

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