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

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

Сотрудниками лаборатории получены следующие результаты:

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

Лаборатория поддерживает связи с ведущими зарубежными учеными и научными коллективами:

Профессор Петер Брюкнер, университет г. Оснабрюка, Германия,

Профессор Франк Вернер, университет им. Отто фон Герике, г. Магдебург, Германия,

Профессор Филипп Баптист, Высшая политехническая школа, Франция;

Профессор Эдмунд Бурке, исследовательская группа ASAP, Ноттингемский ун-т, Великобритания,

Профессор Т.С.Е.Ченг, Гонконгский политехнический университет.