Лаборатория № 68 «Теории расписаний и дискретной оптимизации»

Лаборатория «Теория расписаний и дискретной оптимизации»  под руководством доктора физико-математических наук, профессора Лазарева Александра Алексеевича была создана в 2010 году решением Ученого совета Института.

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

Наиболее важные научные результаты:

  • для задач теории расписаний с одним или несколькими приборами и критериями   получены свойства оптимальных расписаний и построены соответствующие алгоритмы решения;
  • для классических задач комбинаторной оптимизации РАЗБИЕНИЕ (PARTITION) и РАНЕЦ (KNAPSACK) предложены алгоритмы решения графического типа, которые существенно превосходят алгоритмы динамического типа по эффективности (время работы и требуемый объем памяти);
  • для задачи управления выполнением проекта (RCPSP) проведен анализ известных нижних оценок значения целевой функции. Показано, что задача нахождения эффективных оценок оптимального значения функционала является сама по себе NP-трудной. Для приближенного решения задачи построен алгоритм с оценкой трудоемкости наименьшей из известных на сегодняшний день;
  • для задач теории расписаний введено понятие метрики в пространстве примеров, предложены эффективные подходы к нахождению таких метрик. Получен метод, который позволяет находить приближенное решение исходного сложного примера с гарантированной погрешностью оптимального значения целевой функции;
  • введено понятие мера полиноминальной неразрешимости NP-трудной задачи. Для  NP-трудной в сильном смысле задачи  1│ rj │Lmax   найдено значение этой меры  1 ∕ √3 ;
  • показана NP-трудность некоторых одноприборных задач с обратными целевыми функциями и задач с невозобновляемыми ресурсами;
  • для ряда поставленных задач железнодорожного планирования разработаны точные и эвристические алгоритмы решения. Эффективность предложенных подходов подтверждена вычислительными экспериментами, в том числе на реальных данных. Рассмотрены следующие задачи:
    • задача управления парком грузовых железнодорожных вагонов;
    • задача перепланирования движения при закрытии одного из путей на двухпутной железной дороге;
    • задача построения оптимального графика движения поездов между двумя станциями, соединенными однопутной дорогой;
    • задача планирования грузоперевозок между железнодорожными станциями;
    • задачи распределения локомотивов и локомотивных бригад;
    • задача о распределении мощностей пункта технического обслуживания локомотивов.
  • проведено масштабное (по 100 000 матриц для каждой размерности) статистическое исследование сложности индивидуальных асимметричных задач коммивояжера. Предложено представление сложности, позволяющее решать задачу прогнозирования на большие размерности (см. рис.1.). Прогноз дает верхнюю оценку квантилей и позволяет по вероятности оценить сложность индивидуальной задачи.

Рис. 1. Прогнозы квантилей сложности (пунктир) и экспериментальные результаты по контрольной выборке (точки). Значение n – размерность задачи (число вершин полного графа).

  • на основании полученных результатов сформулирована гипотеза об унификации, состоящая в том, что параметры нормального распределения логарифма сложности, деленного на размерность задачи, не зависят от размерности. Показано, что алгоритм Лина-Кернигана-Хельсгауна позволяет получить близкие к оптимальным значения туров коммивояжера в асимметричной постановке за приемлемое время;
  • при совместной работе с Центром подготовки космонавтов им. Ю.А. Гагарина разработаны точные и эвристические алгоритмы для автоматизации планирования подготовки космонавтов к работе на Международной космической станции.

С 2013 года исследования лаборатории финансово поддержаны ежегодными грантами Российского Фонда Фундаментальных Исследований (РФФИ), с 2017 года – грантом Российского Научного Фонда (РНФ), грантами зарубежных государств DAAD (Germany), CNRS и “Metchnikov” (France).

Сотрудники лаборатории участвуют в работе диссертационных и учёных советов как нашего института, так и ведущих ВУЗов страны, а также программных и организационных комитетов международных конференций. Преподавательская деятельность сотрудников лаборатории (МГУ им. М.В.Ломоносова, ВШЭ, МФТИ) способствует притоку в лабораторию научной молодёжи. С момента образования лаборатории по настоящее время сотрудники лаборатории обучались в аспирантуре и докторантуре Института.