Реферат: We consider the open shop scheduling problem subject to speed scaling and energy consumption. The computational complexity is analyzed and approaches to solving various versions of the problem are proposed. The algorithms use a two-stage scheduling scheme. At the first stage, bounds on the objective function and processing times of jobs are constructed. At the second stage, the speed scaling problem is reduced to the classical problem with fixed job speeds, and list-type methods are applied for scheduling. As a result, NP-hardness is proved in the general case, and polynomial-time exact and approximation algorithms are proposed for the practically important special cases when preemptions are allowed or not, when the set of speeds is discrete or continuous, and when energy consumption is bounded or optimized. A model of mixed-integer convex programming is constructed based on continuous time representation using the notion of event points.

Библиографическая ссылка: 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

Оригинальная: Захарова Ю.В.
Приближенные алгоритмы для вариантов задачи 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 РИНЦ OpenAlex

Даты:

Поступила в редакцию:	6 окт. 2024 г.
Принята к публикации:	28 окт. 2024 г.
Опубликована в печати:	10 мар. 2025 г.
Опубликована online:	10 мар. 2025 г.

Идентификаторы БД:

Web of science:	WOS:001447279100012
Scopus:	2-s2.0-105000060988
РИНЦ:	80438669
OpenAlex:	W4408289256

Цитирование в БД: Пока нет цитирований

Альметрики: