Псевдополиномиальный приближенный алгоритм решения $NP$-полной задачи минимизации максимального временного смещения

В статье предлагается и обосновывается приближенный алгоритм псевдополиномиальной трудоемкости для решения известной $NP$-полной в сильном смысле задачи теории расписаний – минимизации максимального временного смещения для одного прибора при запрещении прерываний в обслуживании требований. Получена оценка абсолютной погрешности значения целевой функции расписания, построенного с помощью предложенного алгоритма.