Реферат: We consider the problem of minimizing the weighted average execution time ofequal-length jobs performance on one machine at the specified time of job arrival and thepossibility of their interruption. The computational complexity of this problem is currentlyunknown. The article proposes an algorithm for preprocessing input data that allows reducing theproblem to a narrower and more regular class of examples. The properties of optimal solutions aresubstantiated. Based on them, an algorithm for constructing a finite subset of solutions containingan optimal schedule has been developed. A parametric analysis of the schedules in this subset hasbeen carried out that makes it possible to form a subclass of schedules that are optimal at somevalues of weights. A polynomially solvable case of the problem is isolated

Библиографическая ссылка: Lyashkova K.A. , Servakh V.V.
The Problem of One Machine with Equal Processing Time and Preemption
Journal of Applied and Industrial Mathematics. 2024. V.18. N3. P.479–488. DOI: 10.1134/S1990478924030098 Scopus РИНЦ OpenAlex

Оригинальная: Ляшкова К.А. , Сервах В.В.
Задача одного станка с равными длительностями работ и возможностью прерываний
Дискретный анализ и исследование операций. 2024. Т.31. №3. С.105-122. DOI: 10.33048.2024.31.750 РИНЦ

Даты:

Поступила в редакцию:	26 июл. 2022 г.
Принята к публикации:	22 мар. 2024 г.
Опубликована в печати:	1 дек. 2024 г.
Опубликована online:	1 дек. 2024 г.

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

Scopus:	2-s2.0-85211231243
РИНЦ:	75143769
OpenAlex:	W4404901217

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

Альметрики: