Модели и эффективные алгоритмы для актуальных задач составления расписаний со сложными технологическими и ресурсными ограничениями

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 22-71-10015

НазваниеМодели и эффективные алгоритмы для актуальных задач составления расписаний со сложными технологическими и ресурсными ограничениями

Руководитель Захарова Юлия Викторовна, Кандидат физико-математических наук

Организация финансирования, регион федеральное государственное бюджетное учреждение науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук , Новосибирская обл

Конкурс №71 - Конкурс 2022 года «Проведение исследований научными группами под руководством молодых ученых» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-203 - Теория оптимизации и исследование операций

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

Код ГРНТИ27.47.19

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Основная цель проекта - построить новые математические модели и эффективные алгоритмы оптимизации для актуальных задач составления расписаний со сложными технологическими связями, ресурсными ограничениями и неточными исходными данными, возникающими на производстве и в компьютерных системах. Из широкого ряда таких задач нас будут интересовать, в первую очередь, актуальные производственные многостадийные задачи теории расписаний с маршрутизацией и технологическими ограничениями и задачи, связанные с параллельными вычислениями в системах, где заданы дополнительные ограничения на ресурсы, такие как энергопотребление, пропускная способность шины данных, кэш память и максимальная допустимая температура. Рассматриваемые задачи являются труднорешаемыми. Поэтому в ходе выполнения проекта основные усилия будут сосредоточены в следующих направлениях: - Анализ вычислительной сложности и выделение практически значимых полиномиально разрешимых классов примеров. - Разработка приближенных алгоритмов с гарантированной оценкой точности, построение серий примеров с достижимостью оценки, исследование неаппроксимируемости. - Построение эффективных алгоритмов приближенного решения, основанных на гибридных схемах и параллельных вычислениях. Новизна проекта состоит в том, что: 1) рассматриваются задачи составления расписаний, возникающие на современном производстве и учитывающие специфику выпуска сложных изделий, маршрутизацию и переналадку машин, ресурсные ограничения и многокритериальную природу целевого показателя; 2) рассматриваются подходы к построению расписаний для взаимосвязанных работ с возможностями распараллеливания в многопроцессорных и многоядерных системах с учетом нескольких типов ресурсов, влияющих на длительность и порядок выполнения операций; 3) представленные типы задач исследуются в единой связке, выявляются их сходства и отличия, исследуются структурные свойства и предлагаются общие модели; 4) доказывается NP-трудность актуальных на практике задач с учетом различных параметров, в том числе с использованием авторских схем и компьютерных методов доказательства; 5) принимается во внимание различный характер неточных данных в задачах, используются новые подходы к учету неопределенностей, в том числе переход к многокритериальным задачам, где задействуются как основные критерии, так и оценка неточности данных; 6) предлагаются новые гибридные алгоритмы с оптимизированными операторами и механизмами адаптации, направленные на решение широкого круга задач, где используются методы, не чувствительные к небольшим изменениям условий и типам исходных данных; 7) активно применяется распараллеливание на CPU и GPU c учетом специфики методов для сложных производственных и многопроцессорных задач оптимизации.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Захарова Ю.В. Hybrid Evolutionary Algorithm with Optimized Operators for Total Weighted Tardiness Problem Lecture Notes in Computer Science, Vol. 13930 (год публикации - 2023)

2. Черных И.Д., Кривоногова О.С., Шмырина А.А. Approximation algorithms for two-machine proportionate routing open shop on a tree Lecture Notes in Computer Science, Vol. 13930 (год публикации - 2023)

3. Сахно М.Ю., Захарова Ю.В. Heuristics with Local Improvements for Two-processor Scheduling Problem with Energy Constraint and Parallelization NUMTA 2023 https://numta.org, Zakharova Y.V. , Sakhno M.Y. Heuristics with Local Improvements for Two-processor Scheduling Problem with Energy Constraint and Parallelization Lecture Notes in Computer Science.2024.P.241–256. DOI: 10.1007/978-3-031-81241-5_17 (год публикации - 2023)
10.1007/978-3-031-81241-5_17

4. Захарова Ю.В., Захаров А.О. О двухкритериальном подходе к решению задач составления расписаний на одной машине с нечеткими исходными данными Омский государственный университет им. Ф.М. Достоевского, Омск, C. 103-105 (год публикации - 2023)

5. Захаров А.О. Optimal Recombination Problem in Genetic Programming for Boolean Functions NUMTA 2023 https://numta.org, Zakharov A.O. Optimal Recombination Problem in Genetic Programming for Boolean Functions Lecture Notes in Computer Science.2024.P.226–240. DOI: 10.1007/978-3-031-81241-5_16 (год публикации - 2023)
10.1007/978-3-031-81241-5_16

6. Тавченко В.Ю. Циклические расписания для задачи минимизации общего времени обработки идентичных деталей Омский государственный университет им. Ф.М. Достоевского, Омск, С. 95-97 (год публикации - 2023)

7. Захарова Ю.В. О подходах к решению задач составления расписаний в многопроцессорных компьютерных системах с учетом распараллеливания и ресурсных ограничений Федеральный исследовательский центр информационных и вычислительных технологий, Новосибирск, С. 86-90 (год публикации - 2022)
10.25743/DIR.2022.65.16.015

8. Захаров А.О. Эвристики локальных улучшений для некоторых задач регрессии и классификации Федеральный исследовательский центр информационных и вычислительных технологий, Новосибирск, С. 83-85 (год публикации - 2022)
10.25743/DIR.2022.99.54.014

9. Борисовский П.А. Решение задачи составления производственного расписания с помощью параллельного алгоритма локального поиска на GPU Федеральный исследовательский центр информационных и вычислительных технологий, Новосибирск, С. 16-19 (год публикации - 2022)
10.25743/DIR.2022.37.39.003

10. Захарова Ю.В., Ушакова Е.В. Integer Model and Complexity of Worker Assignment and Job Scheduling in Production and Service Systems IEEE Publishing, pp. 1-5 (год публикации - 2022)
10.1109/Dynamics56256.2022.10014726

11. Борисовский П.А. On Solving the Robust Transfer Line Balancing Problem with Parallel Tasks and Interval Processing Times Lecture Notes in Computer Science (LNCS), 14395, 303–315 (год публикации - 2023)
10.1007/978-3-031-47859-8_22

12. Захарова Ю.В., Сахно М.Ю. Heuristics with Local Improvements for Two-processor Scheduling Problem with Energy Constraint and Parallelization Lecture Notes in Computer Science (LNCS) (год публикации - 2024)

13. Моршинин А.В. Экспериментальное исследование приближенных алгоритмов решения одной задачи кластеризации вершин графа Омский государственный технический университет, Омск, С. 19-20 (год публикации - 2023)

14. Моршинин А.В. Experimental Study of Semi-Supervised Graph 2-Clustering Problem Journal of Mathematical Sciences (United States), V. 275, № 1, P. 107-115 (год публикации - 2023)
10.1007/s10958-023-06663-z

15. Захаров А.О. A metaheuristic with optimized operators for problems with tree-based solution representation XXII International Conference “Mathematical Optimization Theory and Operations Research” (MOTOR 2023). Abstracts., P. 41-42. (год публикации - 2023)

16. Захарова Ю.В., Сахно М.Ю. Structure of schedules for problems with parallelizable jobs XXII International Conference “Mathematical Optimization Theory and Operations Research” (MOTOR 2023). Abstracts., P. 54 (год публикации - 2023)

17. Борисовский П.А. A Parallel “Go with the Winners” Algorithm for Some Scheduling Problems Journal of Applied and Industrial Mathematics, V. 17. N. 4. P. 687-697 (год публикации - 2023)
10.1134/S1990478923040014

18. Захарова Ю.В. Точные алгоритмы для задачи составления расписаний с предписаниями работ на одной машине Труды XI международной конференции "Дискретные модели в теории управляющих систем", ООО "МАКС Пресс", Москва, С. 45-50 (год публикации - 2023)
10.29003/m3789.978-5-317-07114-1

19. Захаров А.О. Optimal Recombination Problem in Genetic Programming for Boolean Functions Lecture Notes in Computer Science (LNCS) (год публикации - 2024)

20. Захарова Ю.В., Захаров А.О. Исследование множества Парето двухкритериальной задачи по выполнению многокомпонентных заказов клиентов Математическое и компьютерное моделирование : сборник материалов XI Международной научной конференции, посвященной памяти В.А. Романькова. Издательство Омского государственного университета, Омск., С. 37-38 (год публикации - 2024)

21. Захарова Ю.В., Сахно М.Ю. Adaptive Genetic Algorithm with Optimized Operators for Scheduling in Computer Systems Intelligent Information Processing XII. IIP 2024. IFIP Advances in Information and Communication Technology., Vol. 703. P. 317-328. (год публикации - 2024)
10.1007/978-3-031-57808-3_23

22. Захарова Ю.В., Сахно М.Ю. Адаптивный вызов процедур и настройка параметров в эволюционных алгоритмах для задач составления расписаний Математическое и компьютерное моделирование : сборник материалов XI Международной научной конференции, посвященной памяти В.А. Романькова. Издательство Омского государственного университета, Омск., С. 228-229 (год публикации - 2024)

23. Захаров А.О., Захарова Ю.В. Генетическое программирование с параллельными оптимизированными операторами в задаче регрессии булевских данных Параллельные вычислительные технологии – XVIII всероссийская научная конференция с международным участием, ПаВТ’2024. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, С. 184 (год публикации - 2024)
10.14529/pct2024

24. Захарова Ю.В. Приближенные алгоритмы составления расписаний в многопроцессорных компьютерных системах с учетом расхода энергии Параллельные вычислительные технологии – XVIII всероссийская научная конференция с международным участием, ПаВТ’2024. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, С.185 (год публикации - 2024)
10.14529/pct2024

25. Захаров А.О. Решение задачи регрессии булевых данных с помощью параллельного алгоритма генетического программирования XIX Всероссийская научная конференция с международным участием «Параллельные вычислительные технологии» (ПаВТ'2025). Короткие статьи и описания плакатов. (год публикации - 2025)

26. Борисовский П.А., Захарова Ю.В., Захаров А.О. Эволюционные алгоритмы с параллельными операторами для задачи составления расписаний выполнения заказов клиентов XIX Всероссийская научная конференция с международным участием «Параллельные вычислительные технологии» (ПаВТ'2025). Короткие статьи и описания плакатов. (год публикации - 2025)

27. Захарова Ю.В., Захаров А.О. Integer Programming Models and Metaheuristics for Customer Order Scheduling Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2024., Communications in Computer and Information Science. Vol 2239. C. 276–290. (год публикации - 2024)
10.1007/978-3-031-73365-9_19

28. Захарова Ю.В., Сахно М.Ю. Complexity and heuristic algorithms for speed scaling scheduling of parallel jobs with energy constraint Journal of Computational and Applied Mathematics, Vol. 457 (год публикации - 2025)
10.1016/j.cam.2024.116254

29. Борисовский П.А. Application of GPU computing to solving discrete optimization problems Издательство Омского государственного университета, Омск, MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций» (30 июня – 06 июля 2024 г.) С. 26 (год публикации - 2024)

30. Моршинин А.В. New integer linear programming models for a variant of correlation clustering problem Издательство Омского государственного университета, Омск, MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций» (30 июня – 06 июля 2024 г.) С. 71 (год публикации - 2024)

31. Сахно М.Ю. Investigation of operators and parameters in evolutionary algorithms for one scheduling problem with resource constraints Издательство Омского государственного университета, Омск, MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций» (30 июня – 06 июля 2024 г.) С. 81 (год публикации - 2024)

32. Захарова Ю.В., Черных И.Д., Кривоногова О.С. On Computational Complexity of Two-Machine Open Shop Variations with Routing and Resource Constraints Dorodnicyn Computing Centre of RAS, Book of abstrats of reports presented at the XV International Conferene on Optimization Methods and Appliations Optimization and appliations. P. 117 (год публикации - 2024)

33. Захарова Ю.В. Approximation algorithms for Open Shop variations subject to energy consumption Trudy Instituta Matematiki i Mekhaniki UrO RAN, Vol. 30, no. 4, pp. 117–133. (год публикации - 2024)
10.21538/0134-4889-2024-30-4-117-133

34. Устюгов В.Н. On Different Methods for Automated MILP Solver Configuration IEEE, Proceedings of 20th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS). P. 24-27. (год публикации - 2024)
10.1109/OPCS63516.2024.10720437

35. Захарова Ю.В. Computational complexity and exact techniques for scheduling problems with job prohibitions Journal of Scheduling , Online First (год публикации - 2025)
10.1007/s10951-025-00840-5

36. Сахно М.Ю. Адаптивный генетический алгоритм с оптимальной рекомбинацией для задачи составления расписаний с учетом расхода энергии Сибирский журнал вычислительной математики, N. 3, Т. 28 (год публикации - 2025)

37. Захарова Ю.В. Свойства решений в задачах составления расписаний с ресурсозависимыми длительностями работ Математическое и компьютерное моделирование : сборник материалов XII Международной научной конференции, Издательство Омского государственного университета им. Ф.М. Достоевского, С. 120-121. (год публикации - 2025)

38. Захарова Ю.В., Сахно М.Ю. Конструктивные алгоритмы для задач составления расписаний с ресурсными ограничениями Математическое и компьютерное моделирование : сборник материалов XII Международной научной конференции, Издательство Омского государственного университета им. Ф.М. Достоевского, С. 124-125 (год публикации - 2025)

39. Захаров А.О., Захарова Ю.В. Integer Programming Models and Metaheuristics for Customer Order Scheduling Издательство Омского государственного университета, Омск, MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций» (30 июня – 06 июля 2024 г.) С. 107 (год публикации - 2024)

40. Кривоногова О.С., Черных И.Д. Приближенные алгоритмы решения для соразмерной задачи Open shop с маршрутизацией Труды XX Международной научной конференции "Проблемы теоретической кибернетики". МГУ имени М.В. Ломоносова (год публикации - 2025)

41. Захарова Ю.В. Вычислительная сложность задачи составления расписаний с дополнительными ограничениями на размещение операций и потребление ресурсов Труды XX Международной научной конференции "Проблемы теоретической кибернетики". МГУ имени М.В. Ломоносова (год публикации - 2025)

42. Захаров А.О., Захарова Ю.В. Анализ решений задачи составления расписания выполнения заказов клиентов с двумя критериями Труды XX Международной научной конференции "Проблемы теоретической кибернетики". МГУ имени М.В. Ломоносова (год публикации - 2025)

43. Устюгов В.Н. On different methods for automated MILP solver configuration Издательство Омского государственного университета, Омск, MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций» (30 июня – 06 июля 2024 г.) С. 97 (год публикации - 2024)

44. Кривоногова О.С., Черных И.Д. Интервалы локализации оптимумов для соразмерной двухмашинной задачи Open shop с маршрутизацией Омский государственный технический университет, Омск, Материалы XIV Международной молодежной научно-практической конференции с элементами научной школы "Прикладная математика и фундаментальная информатика". Омск, 2024. С. 24 (год публикации - 2024)

45. Борисовский П.А., Захаров А.О., Захарова Ю.В. Evolutionary Algorithms for Customer Order Scheduling «Известия Иркутского государственного университета». Серия «Математика» (год публикации - 2025)

Публикации

19. Захаров А.О. Optimal Recombination Problem in Genetic Programming for Boolean Functions Lecture Notes in Computer Science (LNCS) (год публикации - 2024)

Аннотация результатов, полученных в 2025 году
Настоящий проект направлен на исследование новых математических моделей и разработку эффективных алгоритмов оптимизации для актуальных задач составления расписаний со сложными технологическими связями, ресурсными ограничениями и неточными исходными данными, возникающими на производстве и в компьютерных системах. За третий год выполнения проекта получены следующие основные результаты. Исследование вычислительной сложности и построение алгоритмов с гарантированной оценкой точности: 1. Для двухмашинной задачи open shop с маршрутизацией на транспортной сети с четырьмя вершинами построены приближенные алгоритмы линейной трудоемкости с оценками точности 5/4 для задачи с идентичными временами перемещения и 9/7 для случая независимых времен перемещения. 2. Найден точный интервал локализации оптимумов для двухмашинной задачи open shop c маршрутизацией и работами на рёбрах для частного случая транспортной сети, состоящей из двух вершин и двух параллельных ребер. Показано, что верхняя граница интервала составляет 4/3 от стандартной нижней оценки. Эта оценка может быть уменьшена до 6/5 для частного случая, в которым все вершинные работы расположены в базе. 3. Для двухмашинной задачи open shop с маршрутизацией в случае соразмерных длительностей операций и независимых времен перемещений построены линейные приближенные алгоритмы: 6/5-приближенный алгоритм для задачи, в которой транспортная сеть является цепью, и 31/25-приближенный алгоритм для задачи на произвольном дереве. Для соразмерной задачи open shop с маршрутизацией с m машинами получен линейный 5/2-приближенный алгоритм. 4. Для задачи open shop с ресурсозависимыми длительностями работ предложены новые точные алгоритмы и алгоритмы с гарантированной константной оценкой точности, выделены NP-трудные и полиномиально разрешимые практически значимые случаи. 5. Предложен точный алгоритм для класса задач составления расписаний с предписаниями работ, обусловленными технологическими и структурными ограничениями. Алгоритм показал свою перспективность в использовании в составе метаэвристик для задач на перестановках. 6. Построена оценка мощности множества Парето и алгоритм его построения в двухкритериальной задаче построения расписания выполнения заказов клиентов. Алгоритм имеет как точную, так и жадную версию. 7. Построена характеризация коматроидов с помощью функции обхвата. Полученные свойства функции обхвата могут применяться при доказательстве гарантированных оценок точности приближенных алгоритмов для задач, эквивалентных задаче нахождения цикла максимального или минимального веса в наследственной системе (системе независимости). Построение и исследование математических моделей и метаэвристик: 1. Для задачи open-shop с учетом расхода энергии построены модели частично целочисленного линейного программирования, которые показали экспериментальное и теоретическое преимущество в сравнении с известными ранее моделями. 2. Для задачи составления расписаний выполнения заказов клиентов предложены новый генетический алгоритм с оптимизированными операторами с возможностью распараллеливания и гибридный алгоритм итеративного локального поиска в сочетании с подходом ”Иди с победителями” предназначенный для выполнения на графическом процессоре. Алгоритмы показывают конкурентоспособные результаты на тестовых примерах известных библиотек. 3. Для задачи регрессии булевых данных предложена версия алгоритма генетического программирования с оптимизированными операторами, в котором распараллелено вычисление целевой функции. Вычислительный эксперимент показал перспективность параллелизма с ростом длины входа. 4. Предложенный ранее генетический алгоритм обобщен на произвольные задачи составления расписаний на перестановках. Особенностями алгоритма являются адаптивная схема выбора оператора кроссинговера, оптимальная рекомбинация и оригинальная декодировка решений, основанная на специфике постановки задач. Результаты экспериментального исследования показали статистически значимое преимущество над известными алгоритмами на сериях задач различной структуры. 5. Предложены конкурентоспособные конструктивные алгоритмы списочного типа для решения задач составления расписаний в многопроцессорных компьютерных системах с ресурсными ограничениями в онлайн постановке. Проведен вычислительный эксперимент, который позволил выявить лидеров среди предложенных алгоритмов по качеству решений и времени их получения. 6. Предложен алгоритм настройки решателей задач целочисленного программирования на основе локального поиска с чередующимися окрестностями с применением линейной регрессии. Получено статистически значимое снижение времени достижения оптимума в сравнении со стандартными правилами в Gurobi на задачах составления расписания для многоядерных процессоров малой размерности. 7. Построены новые модели целочисленного линейного программирования для невзвешенной и взвешенной задачи кластеризации вершин графа. Для невзвешенного варианта задачи с ограничением на число кластеров проведено экспериментальное исследование, которое показало преимущество этих моделей по сравнению с известными ранее. 8. Разработан гибридный генетический алгоритм для задач 2 и 3-кластеризации. Проведено экспериментальное исследование, показавшее, что этот алгоритм способен находить лучшие решения, чем известные ранее алгоритмы.

Публикации

19. Захаров А.О. Optimal Recombination Problem in Genetic Programming for Boolean Functions Lecture Notes in Computer Science (LNCS) (год публикации - 2024)

Возможность практического использования результатов
1. Использование параллельных алгоритмов для графического процессора при решении задач составления расписаний в производстве и логистике может позволить получать более выгодные решения, повысить допустимую размерность входных данных и сократить время вычислений по сравнению с известными широко применяемыми в настоящее время решателями (CPLEX, Gurobi). 2. Использование подхода к решению, когда основное ядро задачи используется в кодировке, а вспомогательные условия учитываются при оценке качества в декодировке, и адаптивной настройкой операторов и параметров приводит к эффективным алгоритмам с гибкой настройкой при изменении условий и поддержкой для задач составления расписаний, возникающих в производственных и компьютерных системах. 3. Новые подходы к задачам с нечеткими исходными данными в форме нескольких критериев при построении расписаний позволят получить компромиссные решения, которые будут учитывать различные стороны производственных задач, в том числе противоречивые. 4. Полученные свойства функций обхвата и ранга для наследственных систем и коматроидов позволяет строить приближенные алгоритмы для большого числа задач комбинаторной оптимизации, которые сводятся к оптимизации на наследственных системах.