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

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

 

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

---

Номер 22-71-10015

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

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

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

Период выполнения при поддержке РНФ

07.2022 - 06.2025

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

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

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

Код ГРНТИ27.47.19

---

 

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

---

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

Ожидаемые результаты
В ходе выполнения проекта ожидаются следующие основные результаты: 1. Построение и обоснование новых нижних и верхних оценок для различных задач составления расписаний с учетом структурных связей между операциями и ресурсных ограничений. Доказательство NP-трудности или полиномиальной разрешимости важных случаев, в частности с использованием компьютерных программ и методов из нелинейного программирования. Установление границы применимости точных методов и оценки погрешности приближенных методов. Проверка гипотезы о существовании точного алгоритма с трудоемкостью полиномиальной от числа деталей для задачи минимизации общего времени обработки идентичных деталей со сложным технологическим маршрутом. 2. Маршрутизация, технологические ограничения, онлайн условия поступления и нечеткие исходные данные в задачах позволят перейти к более общим и актуальным для практики постановкам. Новый подход к учету нечетких чисел через вспомогательный критерий будет адаптирован и экспериментально проанализирован для широкого класса задач на перестановках со структурными ограничениями и различными временными критериями. 3. Модели целочисленного программирования и динамического программирования, алгоритмы с жадными и оптимизированными стратегиями, алгоритмы локального поиска для задач теории расписаний, возникающих в компьютерных и производственных системах. Модели будут основаны как на дискретном, так и на непрерывном представлении времени, а также будут задействовать различные приемы по моделированию частичного порядка и учету ресурсов. Проверка гипотезы о переносе оценок точности алгоритмов жадного типа для задач без ресурсных ограничений на задачи с учетом потребления энергии работами. Параллельная реализация операторов проблемно-ориентированных алгоритмов с использованием суперкомпьютера. Результаты тестирования и статистического анализа алгоритмов на задачах с реальными и близкими к ним исходными данными. Сравнение с точными решениями и результатами других известных подходов. 4. Известные подходы к решению практических задач сильно зависят от специфики конкретной задачи и даже небольшие изменения условий могут потребовать существенного изменения алгоритма. Будут выработаны общие подходы к решению широкого класса задач составления производственных расписаний за счет применения высокопроизводительных вычислений с использованием многоядерных CPU, GPU и суперкомпьютерного кластера. Здесь будут задействованы новые конкурентоспособные алгоритмы с механизмами адаптации, машинного обучения и различными оптимизированными операторами для однокритериальных и многокритериальных задач. 5. Подходы к доказательству NP-трудности задач, возникающих в оптимизированных операторах метаэвристик, с учетом свойств исходной задачи, разработка проблемно-ориентированного метода решения задач оптимальной рекомбинации для исследуемых задач составления расписаний в эволюционных алгоритмах. Переход к многокритериальным постановкам в задачах оптимальной рекомбинации и к задачам многокритериального выбора, где вводится дополнительная информация о предпочтениях одного расписания другому. Указанные направления активно развиваются и результаты публикуются в международных научных журналах и трудах конференций. Участники проекта имеют значительный теоретический и экспериментальный задел в данной области. Достижение поставленных целей позволит создать конкурентоспособные алгоритмы, которые могут быть использованы на крупных производственных заводах и в многопроцессорных компьютерных системах. Результаты исследований будут представлены на российских и международных конференциях и в сериях статей в научных журналах.

---

 

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

---