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