Сетевой график — графическое изображение сетевой модели.
Графом будем называть множество точек (вершин) {P0, Pn} и множество ориентированных дуг {(Pi, Pj)}, соединяющих некоторые пары этих точек; при этом дуга (Pi, Pj) имеет начало в Рi и конец в Рj. На схеме дугу (Pi, Pj) обозначают в виде направленного отрезка.
Граф называется симметрическим, если вместе с данной дугой (Рi, Рj) он содержит и симметричную дугу (Рj, Рi) и антисимметрическим, если ему может принадлежать лишь одна из пары симметричных дуг (Pi, Pj) и (Рj, Рi). В дальнейшем рассматриваются лишь антисимметрические графы.
Дуги, берущие начало в точке Рi назовем выходящими из Рi, а дуги, конец которых в Рj — входящими в Рj.
Граф, в котором существует лишь одна точка Р0, не имеющая входящих дуг, и лишь одна точка Рm, не имеющая выходящих дуг, и каждой дуге которого приписано некоторое число, мы назовем сетью (рис.4).
Последовательность дуг (Рj1, Рj2), (Рj2, Рj3),…,(Рjk–1, Рjk), (Рjk, Рjk+1) в которой конец каждой предыдущей совпадает с началом последующей, назовем путем (Рj1, Рj2,..., Pjk+1) из Pj1 в Рjk+1. Числа, приписанные дугам, будем часто называть их длинами; длиной пути будем называть сумму длин последовательности его дуг.
Сетевой график (стрелочная диаграмма, сетевая модель, логическая сеть) — наглядное изображение проекта в виде графа, отображающее технологическую взаимосвязь между работами Начальная информация о проекте должна содержать перечень всех работ, последовательность их выполнения и продолжительность каждой работы
Рис. 4. Пример сетевого графика
Так, например, информация о некотором проекте может быть задана табл. 1.
Таблица 1
Работа
Каким работам предшествует
Продолжи-тельность
Работа
Каким работам предшествует
Продолжи-тельность
2,3
—
6,7
—
6,7
—
Ориентированные дуги графа — сетевого графика — обычно интерпретируют работы.
Работа — один из главных элементов сетевой модели. Означает протяженный во времени процесс, требующий затрат ресурсов, или ожидание, или зависимость (фиктивная работа). Ожидание — протяженный во времени процесс, не требующий затрат труда (твердение бетона, сушка поверхности после покраски и т.д.). Зависимость (фиктивная работа) — логическая связь между двумя или несколькими работами (событиями), не требующими затрат труда, материальных ресурсов или времени. Она указывает, что возможность одной работы непосредственно зависит от результатов другой. Вершины графа, соединенные дугами называют событиями. Одно и то же событие — вершина может служить началом одних и концом других дуг — работ. Событие — момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта.
Событие выражает готовый результат: все работы, входящие в событие, окончены. Оно также выражает логическую связь между работами, заключающуюся в том, что работы, входящие в данное событие, непосредственно предшествуют работам, выходящим из него; ни одна выходящая из данного события работа не может начинаться до окончания всех работ, входящих в это событие. Если работа не имеет предшествующей, то она выходит из события, являющегося началом проекта, т.е. из события, не имеющего входящих дуг. Работы, которые не предшествуют никаким другим, входят в событие, являющееся концом проекта, т.е. в событие, не имеющее выходящих дуг. Любое другое событие имеет входящие и выходящие дуги.
В приведенном примере проекта работы 1, 4, 5 не имеют предшествующих, поэтому в сетевом графике дуги, соответствующие этим работам, будут выходить из события — начала проекта. Работы же 7, 8, 9 не предшествуют никаким другим работам проекта, и поэтому дуги, соответствующие этим работам, будут входить в событие — конец проекта. Событие, являющееся концом работы 1, одновременно служит началом работ 2 и 3 и т.д. Сетевой график этого проекта изображен на рис. 5 (номера работ проставлены на дугах в кружках).
Рис. 5. Сетевой график с обозначением номеров работ
События будем обозначать, как и вершины графа, прописными буквами Р0, P1,..., Pm,..., Рn, где Р0 — начало проекта, а некоторое Рm — его конец. Работы же будем обозначать, как и дуги графа, через (Рi, Рj) где Рi — событие начала работы, а Рj — событие конца работы. Продолжительность tij работы (Рi, Рj) будем проставлять на дуге, изображающей эту работу. На рис. 6 приведен сетевой график проекта, заданного табл. 1, с обозначенными событиями и проставленными продолжительностями работ.
Рис. 6. Сетевой график с обозначением событий и продолжительностями работ
Для определения продолжительности отдельной работы (Pi, Pj) обычно на основе опыта дают ее верхнюю и нижнюю оценки, так называемые пессимистическое bij и оптимистическое аij времена выполнения этой работы. Пессимистическое время — максимальная продолжительность выполнения данной работы, когда учитываются все даже самые маловероятные причины срывов, а оптимистическое — минимальная продолжительность выполнения данной работы при самых благоприятных условиях. Планируемую продолжительность работы в этом случае вычисляют по формуле:
которая следует из вероятностных соображений.
Если же, кроме указанных верхней и нижней оценок, известно наиболее вероятное время mij выполнения данной работы, то планируемую продолжительность работы вычисляют по формуле:
Отметим, наконец, что в сетевом графике невозможны циклы, т. е. пути, начальная и конечная точки которых совпадают. Это следует из того, что каждая работа, входящая в событие, предшествует работе, из него выходящей.
На рис. 7 изображен граф с циклом, образованным работами (P1, P2), (Р2, Р3) и (Р3, Р1). В сетевом графике, как уже отмечалось, такая ситуация невозможна, так как для выполнения работы (Р3, Р1) необходимо выполнение работы (Р2, Р3), для чего в свою очередь необходимо выполнение работы (Р1, Р2). Но для начала работы (P1, P2) должны быть выполнены работы (Р0, Р1) и (Р3, Р1), так что (Р3, P1) не может начаться до окончания (P1, P2), а (Р1, Р2) — до окончания (Р3, Р1), что несовместимо.
Рис. 7. Граф с циклом
Порядок и правила построения сетевых графиков.
Если k>1 работ выходят из одного и того же события Рi и входят в одно и то же событие Рj (рис. 8, а), то для того чтобы их различать, то есть чтобы каждую пару событий соединяла не более чем одна работа, вводим k–1 дополнительных событий Рi1,..., Рik–1, которые соединяем с Рj фиктивными работами нулевой продолжительности, изображаемыми пунктиром (рис. 8, б).
Рис. 8. Преобразование графа для замкнутого контура
Если в событие Рi входит более чем одна работа, например, (Pk1, Рi) и (Pk2, Рi), и из него выходит более чем одна работа, например, (Pi, Pj1), (Pi, Рj2), (Pi, Pj3) (рис.9, а), но для выполнения некоторых выходящих работ, например, (Pk1, Рi), то введением дополнительных событий и фиктивных работ нулевой продолжительности строим сетевой график так, как указано на (рис. 9, б).
Рис. 9. Преобразование графа для открытого контура
Если некоторое событие Pk при k¹m (k¹0) не имеет выходящих (входящих) дуг, т.е. нет работ, выполнение которых возможно лишь после наступления события Pk (нет работ, лишь после выполнения которых наступит Pk), то Pk (P0) следует соединить фиктивной работой нулевой продолжительности с Pm (Pk) (рис. 10).
Рис. 10 Графы с фиктивной работой
Все работы в сетевом графике должны быть простыми втом смысле, что только выполнение всей работы может повлечь за собой начало выполнения следующих. Если же, например, работа (Рj, Pk) может наступить после выполнения работы (Рi ,Рi1) (рис. 11,а), являющейся частью работы (Рi, Рj), а работа (Pj, Pk2) — после выполнения (Рi, Рi1), являющейся также частью работы (Рi, Рj),то введением дополнительных событий Рi1 и Pi2 разбиваем сложную работу (Рi, Рj)на простые работы (Pi, Pi1),(Pi1, Pi2) и (Рi2 , Рj) (рис.11,б).
Рис. 11. Преобразование сложной работы в простые
Наконец, если внутри сети можно выделить некоторую подсеть, планирование которой может быть произведено независимо от всей сети, то можно составить укрупненную сеть, заменив эту подсеть одной работой, продолжительность которой равна критическому, т.е. минимально необходимому времени подсети, за которое могут быть выполнены все работы. Этим замечанием пользуются при планировании больших сетей, которые обычно удается разбить на несколько подсетей и планировать по частям. На рис. 12 подсеть с началом Рi и концом Рj заменена работой (Рi, Pj).
