Количественное измерение NP-трудности задач дискретной оптимизации и теории расписаний

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