Аннотация:
Рассматривается задача open shop с учетом расхода энергии. Исследуется вычислительная сложность и предлагаются подходы к решению для различных ее вариантов. Алгоритмы используют двухэтапную схему построения расписаний, где на первом этапе строятся оценки целевой функции и длительностей работ, а затем осуществляется переход от задачи с вариативными скоростями к задаче с фиксированными скоростями и используются методы списочного типа. В результате доказывается NP-трудность в общем случае и предлагаются полиномиальные точные и приближенные алгоритмы для практически значимых частных случаев, когда допускаются или нет прерывания, когда набор скоростей дискретен или непрерывен, когда потребление энергии ограничивается или оптимизируется. Строится модель частично целочисленного выпуклого программирования на основе непрерывного представления времени с использованием точек событий.
Ключевые слова:
open shop, расписание, NP-трудность, алгоритм.
Полный текст:
PDF файл (269 kB)