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