Оценки абсолютной погрешности и схема приближенного решения задач теории расписаний

Предлагается подход к нахождению оценки абсолютной погрешности и построению приближенного решения классических NP-трудных задач теории расписаний для одного и нескольких приборов с критериями минимизации максимального временнóго смещения и минимизации общего момента окончания обслуживания требований. Вводится понятие метрики (расстояния) между примерами задачи. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удается найти оптимальное или приближенное решение с минимальным расстоянием до исходного примера во введенной метрике. Вместо решения исходной задачи (примера) предлагается рассмотреть множество аппроксимирующих ее полиномиально/псевдополиномиально разрешимых задач (примеров), выбрать пример на минимальном расстоянии от заданного примера и затем полученное расписание применить к исходному примеру. Библ. 34. Фиг. 2.