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

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

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

Dates:

Submitted:	Jul 26, 2022
Accepted:	Mar 22, 2024
Published print:	Sep 20, 2024
Published online:	Sep 20, 2024

Identifiers:

Elibrary:

75142764

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

Altmetrics: