Построение комбинаторных моделей и разработка приближённых алгоритмов для решения оптимизационных задач на дискретных структурах : отчет о научно-исследовательской и опытно-конструкторской работе (заключительный) / БГУ ; научный руководитель В. М. Котов

Abstract

Объекты исследования – задачи дискретной оптимизации и задачи теории графов. Цели работы – построение комбинаторных моделей и разработка приближённых алгоритмов для решения оптимизационных задач. Методология проведения работы: использование известных, а также установление новых структурных и сложностных свойств решений оптимизационных задач. Результаты работы и их новизна: для задачи минимизации времени выполнения проекта на разноскоростных процессорах в условиях неполной информации (онлайн версия) была предложена новая схема классификации предметов, методика формирования групп процессоров и механизм пересчета нижних оценок оптимального решения, которые позволили построить алгоритм с рекордной гарантированной оценкой. Для семи онлайн версий задачи теории расписаний с двумя группами предметов была предложена новая схема классификации предметов и методика формирования групп процессоров, которые позволили построить алгоритм с рекордной гарантированной оценкой. Для задачи минимизации времени выполнения проекта на равноскоростных процессорах при наличии сервера была предложена серия приближенных алгоритмов, позволившая достичь рекордной гарантированной оценки. Была рассмотрена задача поиска в графе полного доминантного множества наименьшей мощности. Установлена вычислительная сложность и сложность аппроксимации этой задачи в наследственных классах графов. Область применения результатов: результаты могут быть использованы в различных областях промышленности и IT-сфере для использования в системах для поддержки принятия решений. Рекомендации по внедрению, или итоги внедрения результатов НИР: рРекомендуется внедрить в учебный процесс для обучения новым методам и моделям.