Эвристический метод решения целочисленных декомпозиционных многоиндексных задач

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

Статья представлена к публикации членом редколлегии: А. А. Лазарев