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

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

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

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

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

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

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

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

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

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

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

Код ГРНТИ27.47.19

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

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

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

Аннотация результатов, полученных в 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-кластеризации. Проведено экспериментальное исследование, показавшее, что этот алгоритм способен находить лучшие решения, чем известные ранее алгоритмы.

Публикации

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

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

3. Захарова Ю.В., Захаров А.О. 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

4. Захарова Ю.В., Сахно М.Ю. 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

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

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

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

8. Захарова Ю.В., Черных И.Д., Кривоногова О.С. 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)

9. Захарова Ю.В. 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

10. Устюгов В.Н. 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

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

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

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

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

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

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

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

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

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

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

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

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