Сетевые графики

Баранов Виктор Павлович. Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 16. Сетевые графики

Лекция 16. СЕТЕВЫЕ ГРАФИКИ

План лекции:

1. Определение сетевого графика.

2. Алгоритм отыскания критического пути.

3. Определение резервов времени и коэффициентов напряженности работ.

4. Построение сетевого графика по заданной упорядоченности работ.

Определение сетевого графика

Примерно с 60-х годов получила широкое распространение система сетевого планирования (СПУ), основным элементом которой является сетевой график. Сетевой график представляет собой изображение хода проекта при помощи ациклической сети. Под сетью понимается ориентированный граф, в котором выделены две вершины: одна из них называется началом и не имеет входящих дуг, другая – концом, она не имеет выходящих дуг. Последовательность различных дуг, в которой начало каждой дуги совпадает с концом предыдущей, называется путем. Замкнутый путь называется контуром или ориентированным циклом. Если в сети нет ориентированных циклов, она называется ациклической. Дуги сети изображают отдельные работы, а вершины – события, состоящие в завершении одной или нескольких работ. Каждой дуге в сетевом графике приписано целое неотрицательное число – продолжительность соответствующей работы.

Обозначим – продолжительность работы (, ). Рассмотрим некоторый путь на сетевом графике: . Длиной пути назовем сумму продолжительностей входящих в него работ: .

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

Алгоритм отыскания критического пути

Опишем алгоритм для нахождения критического пути в сетевом графике. В процессе работы алгоритма для каждой вершины рассчитывается величина – максимальная длина пути из начала в вершину .

1°. Правильная нумерация сети. Нумерация вершин сети называется правильной, если номер начала любой дуги сети меньше, чем номер ее конца. Правильная нумерация ациклической сети всегда возможна и производится следующим образом. Нумеруем начальную вершину сети нулем и удаляем ее из сети вместе со всеми выходящими из нее дугами. В получающейся сети непременно образуются вершины, не имеющие входящих дуг (это следует из ацикличности), которые назовем вершинами первого ранга и занумеруем их числами 1, 2, … Далее удалим все вершины первого ранга и выходящие из них дуги. Появившиеся вершины без входящих дуг назовем вершинами второго ранга и дадим им очередные номера. Этот процесс продолжается до тех пор, пока не будут занумерованы все вершины сети.

2°. Расстановка отметок. Пусть сеть правильно занумерована. Для каждой вершины вычисляем отметку по следующим правилам:

– полагаем ;

– просматриваем вершины в порядке их номеров и для -ой вершины вычисляем по формуле

, (1)

где максимум берется по всем вершинам , имеющим дугу , направленную в вершину .

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

3°. Построение критического пути. Начиная с вершины-конца, последовательно находим дуги , для которых . Эти дуги и образуют критический путь.

Определение резервов времени и коэффициентов напряженности работ

Параметр , вычисляемый при построении критического пути, называется «ранний срок свершения события ». Для каждого события можно рассчитать также поздний срок его свершения . Смысл этого параметра состоит в следующем: если событие «запоздает, однако произойдет не позднее , то длина критического пути (время выполения всего проекта) не изменится.

Метод расчета аналогичен методу расчета , если его «вывернуть наизнанку». Пусть для правильной сети концевая вершина получила номер . Тогда для каждой вершины вычисляем отметку по следующим правилам:

– полагаем ;

– просматриваем вершины в обратном порядке их номеров и для -ой вершины вычисляем по формуле

, (2)

где минимум берется по всем вершинам , в которые ведут дуги из вершины .

Резервом времени работы называется величина

. (3)

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

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

При практическом применении сетевых графиков более удобными по сравнению с резервами времени являются коэффициенты напряженности работ, определяемые как отношение длины максимального пути из начала в конец, проходящего через данную работу, к длине критического пути:

. (4)

Из формулы (4) следует, что , причем для работ с нулевым резервом (лежащих на критическом пути) , а для работ с большим резервом времени – . На основании этого всю совокупность работ делят на зоны: критическую с , подкритическую с , и резервную.

Построение сетевого графика по заданной упорядоченности работ

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

(Работы пронумерованы и в дальнейшем ссылаемся на каждую работу по ее порядковому номеру).

Предположим далее, что для каждой работы j (1 j n) указаны ее непосредственные предшественники, то есть множество работ, выполнение которых является необходимым условием для начала работы j.

Пример. , то есть весь комплекс работ, составляющих проект, разбит на 7 работ, соотношения между ними отображены в таблице 1.

Таблица 1

Работы
Предшественники	–	–

Требуется построить сетевой график, соответствующий заданной упорядоченности работ.

Процедура построения сетевого графика распадается на несколько этапов.

Транзитивное замыкание отношения предшествования. Если работа i предшествует работе j, а работа j предшествует работе k, то, очевидно, работа i должна завершиться до начала работы k. Множество работ называется замкнутым (по транзитивности), если вместе с каждой работой оно содержит и всех ее предшественников.

Наименьшее замкнутое множество, содержащее множество работ М, называется транзитивным замыканием М.

На этапе I для каждого множества предшественников работы j строится его транзитивное замыкание. Оно будет состоять из всех работ i, для которых можно найти цепочку работ j1, j2,…jp, такую, что i предшествует j1, j1 предшествует j2, … jp предшествует j. Будем называть эти множества полными предшественниками работы j.

Продолжение примера. Полные предшественники для 7 работ рассматриваемого выше примера приведены в таблице 2.

Таблица 2

Работы

Полные

предшественники

–

Среди построенных множеств встречаются одинаковые. Найдем все различные множества полных предшественников и обозначим их

. (5)

Продолжение примера. В рассматриваемом примере полагаем

, , , .

Построением множеств (1) заканчивается этап I. Каждому из множеств в сетевом графике, который будет построен, соответствует вершина. Она так же будет обозначаться .

II. Построение конституент для множеств полных предшественников. Пусть – совокупность всех работ. Разбиение множества U на непересекающиеся подмножества

(6)

будем называть разбиением на конституенты, если каждое из множеств (5) полных предшественников можно представить в виде объединения некоторых конституент.

Продолжение примера. Пусть в рассматриваемом примере

, , , .

Тогда

, , , (7)

( представляется в виде пустой суммы).

Построением множеств (2) заканчивается этап II. Каждому из множеств в сетевом графике, который будет построен, соответствует вершина. Она так же будет обозначаться .

Ш. Построение сетевого графика.

а) Вершинами сетевого графика служат построенные множества () и , (.

б) Работа изображается дугой с началом в множестве полных предшественников работы и ведущей в конституенту, содержащую работу . На рис. 1 показан фрагмент сетевого графика, содержащий работу 4.

Рис. 1

в) Сетевой график содержит также пустые дуги, помогающие обеспечить требуемую упорядоченность работ. Эти дуги не соответствуют работам (или можно считать, что они изображают работы с нулевым временем выполнения) и называются фиктивными. Фиктивные дуги проводятся следующим образом: для каждого представления множеств в виде суммы :

проводятся фиктивные дуги из каждой вершины в вершину .

Продолжение примера. Фиктивные дуги, соответствующие представлениям (7) для рассматриваемого нами примера показаны на рис. 2.

Рис. 2

Чтобы выяснить роль фиктивных дуг, рассмотрим, например, работу 4. Изображающая ее дуга начинается в вершине . В силу (3) . Фиктивные дуги "подводят" к вершине вершины и , где заканчиваются дуги, изображающие работы 2 и 1, 3 – предшественники работы 4. Следовательно, работа 4 будет начинаться после завершения всех ей предшествующих.

IV. Упрощение графа. Граф, построенный на предыдущем этапе можно упростить, удаляя из него некоторые фиктивные дуги (иногда все). Для этого применяются следующие два правила.

1°. Если фиктивная дуга соединяет вершины, между которыми есть другой путь, то эту дугу следует удалить.

2°. Если единственная дуга, выходящая из вершины (входящая в вершину) является фиктивной, то эту дугу следует удалить и слить ее концы в одну вершину.

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

Продолжение примера. Работы 1 и 2 начинаются в и заканчиваются в и соответственно. Работа 3 начинается в , согласно (3), надо провести фиктивную дугу из в . На рис. 4 изображен фрагмент сетевого графика, построенный к этому моменту.

Рис. 4. Этап 1

Так как фиктивная дуга является единственной входящей в (и останется таковой до конца построения, потому что только один раз фигурирует в левых частях (7)), то вершины и можно слить в одну (рис.5).

Рис. 5

В вершине (,) будет начинаться работа 3, которая заканчивается в вершине . Чтобы изобразить работу 4, вводим новую вершину – начало работы 4. В силу (7) ее нужно соединить фиктивными дугами с вершинами и (рис. 6).

Рис. 6

Дугу от к можно удалить по правилу 1°, так как имеется путь между этими вершинами. После удаления дуга – будет единственной входящей в и вершины и можно слить в одну по правилу 2°. Действуя подобным образом, приходим окончательно к графу, показанному на рис. 7.

Рис. 7

EMBED Equation.DSMT4

EMBED Equation.DSMT4 C2

EMBED Equation.DSMT4

EMBED Equation.DSMT4 11

EMBED Equation.DSMT4 EMBED Equation.DSMT4

EMBED Equation.DSMT4

Сетевые графики