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