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