Представлен графический метод решения задач комбинаторной оптимизации, при решении которых допускается декомпозиция задачи на подзадачи меньшей размерности и использование принципа оптимальности Беллмана при их решении. В отличие от алгоритмов динамического программирования, использующих тот же принцип, в графическом алгоритме все возможные состояния системы рассматриваются не отдельно, а группами. Это становится возможным если принимать во внимание аналитический вид целевой функции, т.е. работать с "графиком" функции, преобразовывая его на каждой стадии согласно аналитическому виду. Графический метод позволяет значительно сократить трудоемкость решения многих задач, а также строить эффективные аппроксимаци- онные схемы. Результаты численных экспериментов свидетельствуют об эффективности графического метода (pdf).

Задачи оптимального планирования возникают на разных уровнях управления с разной степенью детализации и актуальности. Можно упомянуть такие долгосрочные планы, как план строительства, план разработки новой модели автомобиля, планы оперативные, например, расписание выпуска автомобилей разной комплектации сменой и т.д. Можно упомянуть следующие задачи, встречающиеся в практике автомобильных концернов:

    Одним из важных элементов управления космическими полетами является планирование полета Международной Космической Станции (МКС). Под планированием полета понимается планирование всевозможных действий или операций, происходящих на борту МКС: научных экспериментов, технического обслуживания станции, бытовых действий космонавтов, и так далее. В связи с быстрым увеличением количества полетных операций на российском сегменте МКС остро встает вопрос о совершенствовании методов их планирования, а также об их  автоматизации, а также вопросы согласования действий международных экипажей. Институт Проблем Управления (ИПУ) РАН готово выполнить научно-исследовательские работы по автоматизации и совершенствованию методов планирования полета МКС и предполётной подготовки. В ИПУ существует лаборатория 68 «Теории расписаний и дискретной оптимизации», деятельность которой как раз и направлена на решение подобных вопросов.

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