Обозначения и цели работы алгоритма

Si – i-й организационный элемент

Pi – «разрешенное» поле этого организационного элемента

Pi = {fj}i,где fj – j – й функциональный элемент (задача, проблема).

Рассмотрим случай работы алгоритма назначений с точки зрения доминирующего ресурса, имеющего некоторую количественную меру. Цель алгоритма таким образом распределить(закрепить) fj за конкретным Si, чтобы по возможности выровнять суммарную количественную меру ресурса для каждого из организационных элементов Si. Обозначим количественную меру доминирующего ресурса для fj функционального элемента через Tj

Шаг 1

· Построение вспомогательного графа организационных элементов Gs(S,U). В качестве вершин этого графа берутся сами организационные элементы Si. Ребро между Sl и Se в таком графе, обозначаемое Ule присутствует тогда, когда Pl Ç Pe ¹ Æ, т. е. есть общие функциональные элементы в этих «разрешенных» полях.

Шаг 2

· Определение «весов» вершин такого графа Gs. «Вес» вершины Si, обозначаемый Wi, определяется

Шаг 3

· Определение «весов» ребер графа Ule

Шаг 4

· Выделение подмножеств {fi}j* из функциональных элементов, которые входят лишь в «разрешенное» поле Sj.

· fiÎ{fi}j*, если("k) fiÎPi& fi¹Pk,k¹i

Шаг 5

· Закрепление этих функциональных элементов за соответствующими организационными

Шаг 6

· Если для всех ребер Ule Ψle=Ø, то работа алгоритма закончена и все функциональные элементы закреплены за соответствующими организаци-онными. Переходим к шагу 11.

Шаг 7

* Иначе выбор из множества Si вершины с min значением Wi. Допустим это вершина Sm. Если для всех ребер Ume, связанных с данной вершиной

- то выбор другой вершины (по возрастанию Wi).

Шаг 8

· Выбор из {fj}m функционального элемента, входящего в максимальное количество организационных элементов. Допустим это некоторый элемент fn.

Шаг 9

· «Закрепление» этого элемента за выбранной на шаге 7 вершиной Wi (Sm организационным элементом).

Шаг 10

· «Корректировка» весов вершин W и «весов» ребер y. При этом «вес» вершины уменьшается на Tn, если fnÎPm. На эту же величину уменьшаются и все «веса» ребер y le, если fnÎPeÇPm. Переходим к шагу 6.

Шаг 11

· Завершение работы «алгоритма назначений». Проверка структуры ограничений организационной системы