Реферат: Рассматривается задача минимизации среднего взвешенного времени для выполнения работ одинаковой длительности на одном станке при заданных временах поступления работ и возможности их прерывания. В настоящее время вычислительная сложность этой задачи неизвестна. В работе предложен алгоритм предобработки входных данных, что позволяет свести задачу к более узкому и регулярному классу примеров. Обоснованы свойства оптимальных решений, на основе которых разработан алгоритм построения конечного подмножества решений, содержащего оптимальное расписание. Описан подход к проведению параметрического анализа расписаний из этого подмножества, который позволяет сформировать подкласс расписаний, оптимальных при некоторых значениях весов. Выделен полиномиально разрешимый случай задачи. Табл. 1, ил. 10, библиогр. 16.

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

Переводная: 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

Даты:

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

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

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

Альметрики: