Упорядочение сетевых моделей

При построении сетевого графика, как правило, сначала формируется эс­кизная сетевая модель, главная цель которой точно отразить логику взаи­мосвязи между работами. Затем эта модель тщательно проверяется на пред­мет несоответствия правилам построения сетей. После этого производится упорядочение сетевой модели.

Упорядочение сетевого графика заключается в том, чтобы добиться такого расположения событий и работ, при котором для любой работы предшествующее ей событие было расположено левее и имело меньший номер по сравнению с завершающим эту работу событием, а все работы были направлены слева направо - от событий с меньшими номерами к событиям с большими номерами.

Также сетевые модели упорядочивают, чтобы ликвидировать излишние логи­ческие связи и события, изменить расположение событий и работ для наглядного изображения, уменьшить количество пересечений. Совсем избежать пересечений в сетевом графике практически невозможно, но уменьшить их количество можно. Чем меньше пересечений, тем обо­зримее сетевой график.

Наиболее простым, но эффективным и часто применяемым методом упо­рядочения сетевых моделей является перемещение событий из одних об­ластей графика в другие.

Более сложным методом является метод логического зонирования по сло­ям. Основным механизмом этого метода является условное разбиение всего сетевого графика на зоны — так называемые вертикальные слои. В каждом слое события размещаются таким образом, чтобы не возника­ло вертикально направленных стрелок. Иными словами, в один верти­кальный слой не могут попасть события, между которыми существует непосредственная связь, т.е. которые соединены стрелкой. Наиболее удобный способ такого разбиения заключается в том, чтобы события, уже помещенные в слой, мысленно вычеркивались из графика вместе с выходящими из него работами (стрелками). Тогда события, оставшиеся без входящих стрелок, попадут в следующий слой, и так далее до конеч­ного события сетевого графика. При этом можно двигаться как от начала к концу (слева направо) путем исключения «предков» (предшествующих событий), так и от конца к началу (справа налево) путем исключения «потомков» (последующих событий).

После размещения всех событий в вертикальных слоях достаточно просто изменять нумерацию событий или перемещать их, если это необходимо, чтобы модель стала правильной. Рассмотрим на примере, как применяется метод логического зонирования путем исключения «предков».

Допустим, существует некая эскизная сетевая модель (рис. 5.28а). Услов­но разобьем сетевой график на несколько вертикальных слоев (обводим их пунктирными линиями и обозначаем римскими цифрами) так, чтобы не возникало стрелок между событиями, входящими в один слой. Резуль­тат логического вертикального зонирования представлен на рис. 5.286. Теперь мы видим, что первоначальная нумерация событий не совсем правильная. Так, событие 6 лежит в слое VI и имеет номер меньший, чем событие 7 из слоя V. То же можно сказать о событиях 9 и 10, 4 и 3. Изменив нумерацию сетевого графика, получим упорядоченную сетевую модель (см. рис. 5.28).

Пример. Для упорядочения условно разобьем сетевой график на несколько вертикальных слоев, обозначив их римскими цифрами (рис. 4.6).

Рис. 4.5. Первоначальный вариант сетевого графика

Рис. 4.6. Процесс упорядочения сетевого графика

Поместив в слой I начальное событие 1, мысленно вычеркнем на рис. 4.6 это событие и выходящие из него стрелки, тогда без входящих стрелок останется событие 2, которое мы поместим в слой II. Вычеркнув событие 2, с выходящими из него работами, обнаружим, что без входящих стрелок останутся события 3, 4, 5, которые составят слой III. Вычеркнем события 3, 4, 5 с выходящими из них работами - тогда в слое IV окажутся события 6 и 7. Носче вычеркивания последних без входящих стрелок окажется событие 8, которое расположим в слое V. После аналогичных операций в слое VI окажется завершающее событие 9. Теперь не представляет труда изобразить окончательный вид графика с указанием продолжительности всех работ (рис. 4.7).

Рис. 4.7. Упорядоченный сетевой график

Заметим, что упорядоченный график отражает последовательность событий и работ гораздо более наглядно и четко. В сложных сетях упорядочение графика является непременным условием его последующего анализа. Правильно составленный график всегда может быть упорядочен, чего нельзя сказать о графике, содержащем петли и контуры.

Из теории графов известно, что сетевую модель можно представлять не только в графической, но и в матричной форме. Чаще всего используют квадратную матрицу, количество строк и граф которой равно количеству событий в сетевой модели. На пересечении строки, соответствующей начальному событию, и графы, соответствующей последующему событию, ставится 1, во всех остальных ячейках — 0. При этом каждая связь между событиями, т.е. стрелка (работа), отображается в матрице только один раз - в строке, соответствующей начальному событию.

Допустим, существует некая сетевая модель (рис. 5.29а). Представим эту модель в виде матрицы. Мы имеем шесть событий, поэтому матрица, соответствующая модели, будет иметь 6 строк и 6 граф (рис. 5.296).

Рассмотрим событие 0. Оно связано с последующими событиями 1 и 2, поэтому в строке 0 (соответствующей событию 0) на пересечении с графами 1 и 2 ставим цифру 1. Во всех остальных ячейках строки 0 ставим цифру 0.

Рассмотрим событие 1. Оно объединяется с событиями 2 и 3. Поэтому на пересечении с графами 2 и 3 записываем единицы, а во всех остальных ячейках нули.

Аналогичным образом заполняем и другие строки матрицы и таким образом получаем полностью заполненную матрицу сетевого графика (рис 5.29в).

Логическое зонирование может быть осуществлено с помощью матрично­го представления сети.

Наиболее простой матричный метод логического зонирования по слоям

был изобретен французским исследователем М. Демукроном (М. Demoucron). Этот метод логического зонирования является «матричным» аналогом упо­мянутого метода исключения «потомков». Он заключается в следующем.

Если обозначить графы матрицы сетевой модели векторами V₀, V₁, V₃,.... V_n, то на основе операций с ними можно последовательно исключать собы­тия, не имеющие «потомков» (связанных с ними последующих событий).

Определим вектор V⁰:

V⁰= V₀ + V₁+ V₃ +... + V_n,

т.е. этот вектор равен сумме всех значений строки матрицы. Он содержит некоторое количество нулей, которые будут соответствовать событиям, образующим слой 0.

Затем вычислим V¹:

V¹ = V⁰ — сумма векторов, соответствующих событиям слоя 0.

Вновь появившиеся нули в этом векторе будут соответствовать событиям, образующим слой 1.

Чтобы определить события, образующие слой 2, необходимо вычислить вектор V²:

V² = V¹ — сумма векторов, соответствующих событиям слоя 1.

Новые нули в этом векторе соответствуют событиям слоя 2.

И так далее, до тех пор пока не получится последний вектор, состоящий из одних нулей. Этот вектор соответствует последнему слою, а вновь появив­шиеся нули на этом слое соответствуют событиям последнего слоя.

Так как вычисления производились справа налево, то необходимо поме­нять нумерацию слоев, чтобы получить упорядоченное расположение со­бытий по слоям.

Приведем пример матричного упорядочения сетевого графика, представ­ленного на рис. 5.30а.

График имеет 12 событий, поэтому его матрица будет иметь размерность 12x12. Заполним матрицу в соответствии с системой взаимосвязей между событиями нашего графика (рис. 5.30б).

Рассчитаем вектор V⁰.

Суммируем все значения строки 0 и помещаем полученный результат в ячейку, находящуюся на пересечении строки 0 и графы V⁰ (рис. 5.316). (Такие расчеты удобно вести в электронных таблицах, например в про­грамме Microsoft Excel.) Затем суммируем все значения строки 1 и запол­няем следующую ячейку графы V⁰ и т.д.

Ноль появился в строке события 11. Поэтому на графике выносим это событие в отдельный нулевой слой (рис. 5.31а).

Теперь рассчитаем вектор V¹ как V⁰ – V₁₁, т.е. как графу разностей зна­чений графы V⁰ и графы 11. Ноль появился в строке события 9 (рис. 5.316). Поэтому в слой 1 попадает событие 9 (см. рис. 5.31а).

Далее рассчитаем вектор V² как разность столбца V¹ и графы 9, так как именно это событие «осталось» в слое 1 (см. рис. 5.316). В слой 2 попадают события 8 и 10 (см. рис. 5.31а). Подобным образом рассчитаем векторы V³, V⁴ V⁵, V⁶, V⁷, V⁸.

Их значения получаются следующим образом:

События 6 и 4 располагаются на слое 3. Событие 7 располагается на слое 4. События 5 и 3 — на слое 5.

Событие 2 — на слое 6.

Событие 1 — на слое 7.

Событие 0 — на слое 8.

Теперь необходимо пронумеровать слои в обратном порядке (рис. 5.32а).

И наконец, перестроить сетевой график и изменить нумерацию событий (рис. 5.326). После этого упорядочение сетевого графика матричным мето­дом можно считать завершенным.

Рис. 5.32. Нумерация слоев в обратном порядке (а). Упорядоченная сетевая модель (б)