Схема приближённого решения задачи $1|R_j|L_{\max}$

Рассматривается NP-трудная в сильном смысле задача теории расписаний о минимизации максимального временного смещения на одном приборе при неодновременном поступлении работ. Представлена схема приближённого решения, основанная на отыскании по заданному примеру другого (наиболее близкого в некоторой метрике) примера, принадлежащего к известному полиномиально разрешимому классу примеров. Для нескольких конкретных вариантов схемы (с использованием различных полиномиально разрешимых классов примеров) найдены аналитические формулы, позволяющие по любому заданному примеру легко вычислить оценку абсолютной погрешности его приближённого решения.
Библ. 18.