Рассматривается применение одного точного и двух приближенных методов решения расширенных перестановочных flow shop-задач теории расписаний: метода ветвей и границ, муравьиной колонии и имитации отжига. Приведены расширения flow shop задач, описанные рекурсивными функциями и использующими предикат AND. Данная модель позволяет решать задачи планирования некоторых видов сборочных производств. Задачи создаются параметризованным генератором псевдослучайных ориентированных ациклических графов, что позволило выпполнить тесты для 14, 20, 100 и 200 работ и вычислить для них время поиска решения, значение makespan. В статье также рассматривается достаточно распространенная производственная задача SDST с временем настройки, зависимым от последовательности работ. Для нее описана соответствующая рекурсивная функция. Выполненная работа показала, что рекурсивная модель PFSP является рабочей и заслуживает дальнейшего развития. Разработка новых прикладных рекурсивных функций для решения задач теории расписаний позволяет использовать рассмотренные алгоритмы и программы оптимизации, так как рекурсивные функции имеют один набор аргументов и использованные приближенные методы опираются на определение элементарной перестановки и требование вычислимости рекурсивной функции.