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

Cite: Захарова Ю.В.
Приближенные алгоритмы для вариантов задачи open shop с учетом расхода энергии
Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN). 2024. Т.30. №4. С.117-133. DOI: 10.21538/0134-4889-2024-30-4-117-133 WOS Scopus РИНЦ OpenAlex

Translated: Zakharova Y.V.
Approximation Algorithms for Open Shop Variations Subject to Energy Consumption
Proceedings of the Steklov Institute of Mathematics. 2024. V.327. P.S286–S301. DOI: 10.1134/S0081543824070216 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Oct 6, 2024
Accepted:	Oct 28, 2024
Published print:	Dec 16, 2024
Published online:	Dec 16, 2024

Identifiers:

Web of science:	WOS:001412872200010
Scopus:	2-s2.0-105003836482
Elibrary:	75134210
OpenAlex:	W4404824602

Citing: Пока нет цитирований

Altmetrics: