Теория расписаний рассматривает задачи дискретной оптимизации, в которых необходимо для множества работ и процессоров и с учётом набора ограничений составить расписание с минимальной длительностью выполнения. Не смотря на практическую необходимость в их решении, для большинства классов теории расписаний не существует способа решения иначе как через перебор. Возникает необходимость в решении этих задач за полиномиальное время.
Одним из общих способов приближённого решения NP-трудных задач дискретной оптимизации за полиномиальное время является составление полиномиальной схемы, когда задачи рассматриваемого класса соотносятся с задачами некого «похожего» класса, для которого существуют полиномиальные алгоритмы решения. Решая «похожую» задачу и применяя полученное решение для исходной задачи, можно получить оптимальное решение исходной задачи с некоторой точностью.
Рассмотрена применимость полиномиальной схемы решения задач теории расписаний с двумя процессорами, двумя возможными длительностями работ, функцией запаздывания в качестве целевой функции и графом предшествования, задающим порядок выполнения работ. Проведены численные эксперименты для получения статистики среднего значения ошибки при применении схемы в зависимости от параметров задачи, даны теоретические обоснования полученным результатам. Рассмотрена возможность дать верхнюю границу ошибки метода при помощи составления метрического пространства над множеством задач рассматриваемого класса, и возможность алгоритма поиска ближайшей по метрике задаче из другого класса к задаче исходного класса.