Abstract: 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.

Cite: 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

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

Dates:

Submitted:	Oct 6, 2024
Accepted:	Oct 28, 2024
Published print:	Mar 10, 2025
Published online:	Mar 10, 2025

Identifiers:

Web of science:	WOS:001447279100012
Scopus:	2-s2.0-105000060988
Elibrary:	80438669
OpenAlex:	W4408289256

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

Altmetrics: