Приближенные методы решения flow shop-задач с использованием рекурсивных функций

Автор(ы): Куприянов Б.В., Рощин А.А.

Выпуск: 119

Рубрика: Управление техническими системами и технологическими процессами

Год: 2026

Библиография: Куприянов Б.В., Рощин А.А. Приближенные методы решения flow shop-задач с использованием рекурсивных функций // Управление большими системами. - 2026. - Вып. 119. - С.330-345.

Дата опубликования: 31.01.2026

Ключевые слова: задачи permutation flow shop , рекурсивные функции, метод ветвей и границ, муравьиная колония, имитация отжига

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

Author(s): Kuprijanov B., Roschin A.

Article title: Methods of quasi-optimization for schedules in flow shop problems represented by recursive functions

Issue: 119

Year: 2026

Keywords: permutation flow shop problem; recursive functions; branch and bound method; ant colony scheduling; simulated annealing

Abstract: The application of one exact and two approximate methods for solving extended permutation flow shop problems of scheduling theory is considered: the branch and bound method, the ant colony method, and simulated annealing. Extensions of flow shop problems defined by recursive functions and using the $and$ predicate are given. This model allows solving planning problems for certain types of assembly production. The problems are generated by a parameterized generator of pseudo-random directed acyclic graphs, which made it possible to perform tests for 14, 20, 100, and 200 jobs and calculate the solution search time and makespan value for them. The paper also discusses a fairly common SDST manufacturing problem with sequence-dependent setup times. A corresponding recursive function is defined for that problem. The work performed has shown that the recursive PFSP model is viable and deserves further development. The development of new applied recursive functions for solving scheduling theory problems allows the use of the considered algorithms and optimization programs, since the recursive functions have one set of arguments and the approximate methods used are based on the definition of an elementary permutation and the requirement of computability of the recursive function.