Оценка абсолютной погрешности и полиномиальной разрешимости для классической $NP$-трудной задачи теории расписаний

Предложен метод нахождения приближённого решения $NP$-трудных задач теории расписаний. Для задачи минимизации максимального временно`го смещения показано, как с помощью метрики, введённой на пространстве примеров задачи, можно использовать полиномиально разрешимые области для нахождения приближённого решения с гарантированной абсолютной погрешностью. Приведена теоретическая и экспериментальная оценка метода, а также сравнительный анализ с $ED$-эвристикой. Предложена численная характеристика полиномиальной неразрешимости задачи - верхняя оценка на гарантированную абсолютную погрешность для каждого класса эквивалентности пространства примеров.