Распределение заданий между участниками в условиях ограничений

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

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