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

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

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

Dates:

Submitted:	Jul 26, 2022
Accepted:	Mar 22, 2024
Published print:	Dec 1, 2024
Published online:	Dec 1, 2024

Identifiers:

Scopus:	2-s2.0-85211231243
Elibrary:	75143769
OpenAlex:	W4404901217

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

Altmetrics: