Зав. лаб. № 68 Александр Алексеевич Лазарев

Лаборатория основана в 2009 г. на базе сложившейся к тому времени в Казанском государственном университете научной группы (http://www.orsot.ru), возглавляемой доктором физико-математических наук, профессором Александром Алексеевичем Лазаревым. Сегодня это единственная в России лаборатория по теории расписаний. В настоящее время в ней работают 13 человек, из которых 2 доктора и 1 кандидат физико-математических, один доктор и 1 кандидат технических наук. Сотрудники преподают в Высшей школе экономики, Московском государственном университете им. М.В. Ломоносова и Московском физико-техническом институте.

Сотрудники занимаются сложными практическими задачами теории расписаний, комбинаторной оптимизации, объёмно-календарного планирования, а также изучают модели, возникающие при исследовании практических задач планирования и управления комплексами взаимосвязанных операций при ресурсных ограничениях.

При исследовании NP-трудных задач комбинаторной оптимизации существенным является изучение структуры сложности примеров, получение новых свойств оптимальных решений и построение на их основе полиномиальных и псевдополиномиальных алгоритмов решения частных случаев этих задач. Полученные свойства и алгоритмы выделенных полиномиально разрешимых частных случаев могут быть использованы при построении эффективных алгоритмов нахождения точных и приближённых решений для общего случая задачи. Аналогичный подход выделения частных случаев задач, нахождения их эквивалентных хорошо изученных постановок и построения алгоритмов решения является эффективным при исследовании возникающих на практике задач большой размерности.

Сотрудниками лаборатории разработан метод изменения параметров, который позволяет находить приближённое решение с минимальной абсолютной погрешностью целевой функции из области допустимых (полиномиально разрешимых) решений для задач объёмно-календарного планирования.

В лаборатории активно развивается новый метод решения задач комбинаторной и дискретной оптимизации, представляющий собой модификацию классического метода динамического программирования, основанного на принципе оптимальности Беллмана. Предложенный метод, названный «графическим», был успешно применён для решения ряда задач теории расписаний и дискретной оптимизации, с его помощью можно существенно сократить трудоёмкость решения для некоторых задач комбинаторной оптимизации. Более того, показано, что для некоторых задач, трудоёмкость решения которых была неизвестна, можно построить полиномиальный алгоритм решения.

Научная группа нацелена на практическое применение сформулированных решений и построение эффективных методов нахождения точных и приближённых решений с гарантированной погрешностью для задач управления движением подвижных средств в транспортных и логистических системах, включая задачи формирования, маршрутизации и диспетчеризации транспортных потоков, а также задач планирования и управления комплексом взаимосвязанных операций.

Основные направления работы:

• NP-трудные задачи теории расписаний, объёмно-календарного планирования и смежных областей комбинаторной и дискретной оптимизации.
• Графические алгоритмы получения приближённых решений NP-трудных задач теории расписаний.
• Новые методы решения трудоёмких задач на основе графического подхода.
• Разработка и внедрение информационных систем с математической составляющей.
• Получение эффективных метрик для рассматриваемых задач и построение на их основе полиномиальных алгоритмов решения с гарантированной абсолютной погрешностью.
• Задачи управления движением на железнодорожном транспорте.
• Задачи управления движением в транспортных сетях.
• Методы оптимизации при составлении учебных расписаний вузов.
• Задачи управления инвестиционным портфелем.

Лаборатория имеет богатый опыт в создании интерфейсов и программных комплексов для решения учётно-аналитических задач. Сотрудники участвовали в создании ИТ-продуктов для известных фирм «1С», «Главстрой», Siemens, Wabco и др.

К настоящему времени сотрудниками опубликовано около 300 работ, в том числе 29 книг: монографии, учебники и учебные пособия для ведущих университетов нашей страны. Более 60 работ опубликовано в изданиях, индексируемых Web of Science или Scopus. Сотрудники лаборатории редактируют раздел «Исследование операций» реферативного журнала «Математика» (ВИНИТИ), работают в редколлегиях журналов «Автоматика и телемеханика», «Проблемы управления», «Управление большими системами» и диссертационных советах.

Лаборатория сотрудничает с рядом крупных зарубежных научных центров: Otto-von-Guericke University (г. Магдебург, Германия), CNRS Institute for Information Science and Technology, INRIA (г. Бордо, Франция), Ecole des Mines de Nantes (г. Нант, Франция), Sydney University of Technology (Австралия). Полученные в лаборатории теоретические и прикладные результаты соответствуют мировому уровню, что подтверждается успешной апробацией на ведущих международных конференциях и публикациями в международных изданиях.