Сетевые графики и правила их построения

Сетевой график – это графическое изображение процессов, выполнение которых необходимо для достижения поставленной цели.

Методы сетевого планирования и управления (СПУ) базируются на теории графов. Графом называется совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами. В экономике обычно используются два вида графов: дерево и сеть. Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины. Сеть - это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, каждый сетевой график представляет собой сеть, состоящую из узлов(вершин) и соединяющих их ориентированных дуг (ребер). Узлы графика называются событиями, а соединяющие их ориентированные дуги - работами. На сетевом графике события изображаются кружками или иными геометрическими фигурами, а соединяющие их работы безразмерными стрелками (безразмерными они называются потому, что длина стрелки не зависит от объема работы, которую она отражает).

Каждому событию сетевого графика приписывают определенный номер (i ), а работу, соединяющие события, обозначают индексом (ij ). Каждая работа характеризуется своей продолжительностью (длительностью) t(ij) . Значение t(ij) в часах или днях проставляют в виде числа над соответствующей стрелкой сетевого графика.

В практике сетевого планирования используют несколько типов работ:

1) реальная работа, производственный процесс, который требует затрат труда, времени, материалов;

2) пассивная работа (ожидание), естественный процесс, который не требует затрат труда и материальных ресурсов, но осуществление которого может происходить лишь в течение определенного периода времени;

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

Каждая работа самостоятельно или в сочетании с другими работами заканчивается событиями, которые выражают результаты выполненных работ. В сетевых графиках выделяют следующие события: 1) исходное, 2) промежуточные, 3) завершающее (окончательное). Если событие имеет промежуточный характер, то оно является предпосылкой для начала следующих за ним работ. Считается, что событие не имеет продолжительности и осуществляется мгновенно после выполнения предшествующих ему работ. Исходному событию не предшествуют никакие работы. Оно выражает собой момент наступления условий для начала выполнения всего комплекса работ. Завершающее событие не имеет никаких последующих работ и выражает собой момент окончания всего комплекса работ и достижения намеченной цели.

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

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

Правилапостроения сетевого графика.

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

Неверно Правильно

3. В сети не должно быть «тупиков», то есть все события, кроме завершающего, должны иметь последующую работу (тупиками называются промежуточные события, из которых не выходит ни одна работа). Такая ситуация может иметь место, когда данная работа не нужна или какая-либо работа пропущена.

4. В сети не должно быть событий, кроме исходного, которым не предшествует хотя бы одна работа. Такие события называются «хвостовыми». Это может иметь место в случае пропуска предшествующей работы.

Для правильной нумерации событий сетевого графика используют следующую схему действий. Нумерацию начинают из исходного события, которому присваивают номер 0 или 1. Из начального события (1) вычеркивают все исходящие из него работы (ориентированные дуги), и на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию присваивают номер (2). Указанная последовательность действий повторяется до тех пор, пока не буду пронумерованы все события сетевого графика. Если при очередном вычеркивании одновременно возникают два события, не имеющие входящих работ, то номера им присваиваются произвольно. Номер завершающего события должен быть равен количеству событий в сетевом графике.

Пример .

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

Существуют различные варианты расчета стохастических временных оценок. Рассмотрим некоторые из них. В первом случае устанавливают три вида продолжительности выполнения конкретной работы:

1) максимальный срок, который исходит из наиболее неблагоприятных условий выполнения работы (t max );

2) минимальный срок, который исходит из наиболее благоприятных условий выполнения работы (t min );

3) наиболее вероятный срок, исходящий из реальной обеспеченности работы ресурсами и наличия нормальных условий ее выполнения (t в ).

На основе этих оценок рассчитывается ожидаемое время выполнения работы (ее временная оценка) по формуле

. (5.1)

Во втором случае задаются две оценки - минимальная (t min ) и максимальная (t max ). Продолжительность работы в этом случае рассматривается как случайная величина, которая в результате реализации может принять любое значение в заданном интервале. Ожидаемое значение данных оценок (t ож ) (при бета-распределении плотности вероятности) оценивается по формуле

. (5.2)

Для характеристики степени разброса возможных значений вокруг ожидаемого уровня используется показатель дисперсии (S 2 )

. (5.3)

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

Пример .

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

Таблица 5.1

Перечень работ сетевого графика

Построенный на основании данных табл. 5.1 предварительный сетевой график выполнения работ выглядит следующим образом (рис. 5.1).

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

Ниже приведен тот же самый график строительства складского здания, пронумерованный и с проставленными временными оценками работ (рис. 5.2).

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

События должны быть правильно пронумерованы, т. е. для каждой работы (i , j ) i < j . При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем:

а) нумерация событий начинается с исходного события, которому приписывается №1;

б) из исходного события вычеркиваются все исходящие из него работы (стрелки), и на оставшейся сети находят событие, в которое не входит ни одна работа, ему присваивается №2;

в) затем вычеркиваются работы, выходящие из события №2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают №3, и так продолжается до завершающего события, номер которого должен быть равен количеству событий в сетевом графике;

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

Завершающее событие лишь одно.

Отсутствуют тупиковые события (кроме завершающего), т. е. такие, за которыми не следует хотя бы одна работа.

Исходное событие лишь одно.

Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа.

Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой. Если два события связаны более чем одной работой, рекомендуется ввести дополнительное событие и фиктивную работу:

В сети не должно быть замкнутых циклов.

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

Например, для начала работы D достаточно окончания работы А. Для начала работы С нужно окончание работ А и В.

Временные параметры сетей. Резервы времени.

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

Обозначим
– продолжительность работы с начальным событием i и конечным событием j .

Ранний срок
совершения события j определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем
, а
гдеN - номер завершающего события. Правило вычисления:

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

Поздний срок
свершения события i характеризует самый поздний допустимый срок, к которому должно совершится событие, не вызывая при этом срыва срока совершения конечного события. Правило вычисления:

где минимум берется по всем событиям j , непосредственно следующим за событием i .

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

Резерв
события i показывает, на какой предельно допустимый срок может задержаться свершение события i без нарушения срока наступления завершающего события:

.

События лежащие на критическом пути (критические события) резервов не имеют.

Существуют различные методы расчета параметров сети: табличный и графический.

Рассмотрим графический метод.

При расчетах сетевого графика каждый круг, изображающий событие, делим диаметрами на четыре сектора:

Пример 55. Рассмотрим сеть проекта, представленную следующим графиком.

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

Найти критический путь. Сколько времени потребуется для завершения проекта? Можно ли отложить выполнение роботы D без отсрочки завершения проекта в целом? Насколько недель можно отложить выполнение работы C без отсрочки завершения проекта в целом?

1 этап. При вычислении раннего срока свершения события
перемещаемся от исходного события 1 завершающему событию 6.

.

В событие 2 входит только одна работа: .

Аналогично .

В событие 4 входят две работы →

Отсюда следует, что критическое время выполнения проекта = 22.

Внесем соответствующие данные в сетевой график.

2 этап. При вычислении позднего срока t п (i ) свершения события I перемещаемся от завершающего события 6 к исходному событию 1 по сетевому графику против направления стрелок.

.

Из события 4 выходят две работы: (4, 5) и (4, 6). Поэтому определяем поздний срок наступления события t п (4) по каждой из этих работ:

Внесем полученные данные в сетевой график.

3 этап. Вычисляем резерв
события i , то есть из чисел, полученных на этапе 2, вычитаем числа, полученные на этапе 1.

4 этап. У критических событий резерв времени равен нулю, так как ранние и поздние сроки их свершения совпадают. Критические события 1, 2, 4, 5, 6 и определяют критический путь 1-2-4-5-6, который по определению должен быть самым продолжительным по времени. На сетевом графике мы его покажем двумя чертами.

Теперь можно ответить на вопросы задачи.

Для завершения проекта потребуется 22 недели. Работа D расположена на критическом пути. Поэтому ее нельзя отложить без отсрочки завершения проекта в целом. Работа C не расположена на критическом пути, ее можно задержать на (недели).

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

• 1. Номер каждого последующего события должен быть больше номера любого предыдущего события. Выполнение этого правила позволяет обеспечить соблюдение логической последовательности выполнения работ.
• 2. Не должно быть событий, из которых не выходит ни одной работы (исключение - последнее событие), если данное правило не выполняется, то сетевой график построен неправильно или запланирована лишняя работа (см. рис. 10.7).

Рис. 10.7. Пример неправильного построения сетевого графика с лишней работой В

3. Не должно быть событий, в которые не входит ни одна работа (исключение - начальное событие). Если данное правило не выполняется, то это означает, что допущена ошибка при составлении сетевого графика или не запланирована работа, результат которого (например, событие 5 на рис. 10.8) необходим для начала работы Е.

Рис. 10.8.

А. В сетевом графике не должно быть замкнутых контуров, так как это приводит к ситуации, когда результатом выполнения последовательности работ (Б-В-Г-Д) является событие 2, с которого началась эта последовательность (рис. 10.9).

Рис. 10.9.

5. Любые два события должны быть соединены не более чем одной работой. Подобные ошибки возникают чаще всего при изображении параллельно выполняемых работ (рис. 10.10, а). Для правильного изображения этих работ необходимо ввести дополнительные фиктивные события 2" и 2" и фиктивные работы 2"-2 и 2"-2 (рис. 10.10, б).

Рис. 10.10.

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

Рис. 10.11.

Если для продолжения работы на каких-либо этапах необходимо получить результаты других работ, то следует разделить указанную работу на части, использовав промежуточные события (в данном примере - событие 4 нарис. 10.12).

Рис. 10.12.

Если до полного окончания работы необходимо видеть промежуточный результат, требующийся до начала следующей работы, также следует разделить работу на части, введя промежуточные события (рис. 10.13, б), работа 2-4).

Рис 10.13.

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

• обеспечивать изображение каждой отдельной задачи, за исключением задач без оговоренного срока исполнения;
• избегать деталей, которые более уместны в календарных планах (планах ключевых событий) или списках последовательности действий;
• использовать сетевой план для проверки, обоснования и определения способов устранения отклонений от календарного плана;
• при необходимости использовать компьютерные программы, учитывая, что не любое программное обеспечение подходит для решения различных задач планирования;
• проводить соответствующее обучение сотрудников проекта методам сетевого планирования;
• представлять результаты сетевого планирования высшему руководству организации, в которой выполняется проект.

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

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

В зависимости от принципов, заложенных в основу, выделяются четыре вида планов: объектно-ориентированные, функционально-ориентированные, фазово-ориентированные и смешано-ориентированные.

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

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

Выделяются следующие методы планирования:

• 1) составление плана ключевых событий и поэтапного плана (плана последовательности действий);
• 2) планирование с помощью полосовых диаграмм;
• 3) сетевое планирование.

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

Полосовые диаграммы дают наглядное представление о состоянии выполнения ряда параллельно осуществляемых работ проекта.

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

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

Пример. Необходимо построить сетевой график выполнения комплекса операций по реконструкции цеха. Список операций представлен в табл. 1. Итоговый сетевой график комплекса операций изображен на рис.1.

Решение. Опе­рации графика, за исключением операций 2→3 и 5→6, являются действительными. Числа в скобках, приписанные дугам, означают продолжитель­ность выполнения соответствующих операций. Операции а1 и а2 не опираются ни на какие операции, поэтому на графике изобразим их дугами, вы­ходящими из события (1), означающего начало выполнения комплекса операций. Операции а3 , а5 и а6 опираются на операцию а1, поэтому на графике эти дуги непосредственно следуют за дугой а1. Событие (2) озна­чает момент окончания операции а1 и начала операций, представленных дугами, выходящими из этого события. Операция а4, опирается на операции а1 и а2. Гра­фически это условие отражено посредством последовательного изображения опе­раций 1→3 и 3→4 и введения фиктивной операции 2→3. Событие (3) инци­дентно операциям 1→3 и 2→3, следовательно, моментом свершения события (3) будет такой момент, к которому будут выполнены все входящие в это собы­тие операции и может быть начата операция, отраженная дугой, выходящей из него. Аналогично с учетом технологии выполнения изображены на графике остальные операции. Завершающее событие (9) означает момент окончания вы­полнения всего комплекса операций по реконструкции цеха. Шифры операций (см. табл. 1) состоят из номеров начального и конечного событий и практиче­ски в список заносятся после составления графика.

Таблица 1– Список операций для построения сетевого графика

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

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

Рисунок 1

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

Задание на семинар №4

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

Рассмотрим применение сетевого графика на примере организации пикника. (Я, в общем-то, не настаиваю, чтобы вы каждый пикник планировали с помощью сетевого графика, но этот пример покажет основные приемы и возможности.)

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

В табл. 4 5 представлены семь работ, которые, как вы считаете, необходимо выполнить, чтобы подготовить пикник и добраться до озера.

Таблица 4.5. Список мероприятий по организации пикника на озере

Кроме того, вы соблюдаете следующие условия

Все работы начинаются в субботу в 8:00 утра у вас дома. До этого времени нельзя ничего делать.

Необходимо выполнить все работы по данному проекту.

Вы договорились не менять исполнителей запланированных работ.

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

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

Подруга должна сварить яйца, прежде чем готовить сэндвичи.

Вы вместе должны решить, на какое озеро ехать, прежде чем отправиться в путь.

В каком порядке выполнять остальные работы, зависит от вашего желания. Например, вы приняли такой порядок.

В первую очередь вы вместе решаете, на какое озеро ехать.

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

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

После принятия совместного решения об озере подруга начинает варить яйца.

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

После того как вы вернулись с заправки и подруга приготовила сэндвичи, грузите вещи в машину.

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

Табл. 4.6 иллюстрирует последовательность работ, которую вы определили.

Таблица 4.6. Последовательность работ для организации пикника

Чтобы построить сетевой график в соответствии с этой таблицей, выполните следующие действия.

1. Начните проект с события "Начало".

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

В нашем случае это единственная работа 5.

3. Начинаем рисовать сетевой график (рис. 4.5).

Определите все работы, для которых работа 5 является непосредственно предшествующей.

4. Из табл. 4.6 видно, что таких две: работа 2 и работа 7. Изобразите их в виде прямоугольников и проведите к ним стрелки от работы 5.

Продолжайте строить график по тому же принципу.

Для работы 6 предшествующей будет работа 2, а для работы 3 - работа 7. На данном этапе график примет вид, как на рис 4.6

Из таблицы видно, что работе 1 предшествуют две работы: работа 3 и работа 6, а работе 4 - только работа 1. И наконец, от работы 4 идет стрелка к событию "Конец"

На рис. 4.7 показан сетевой график в завершенном виде.

Теперь рассмотрим несколько важных вопросов. Во-первых, сколько времени вам потребуется, чтобы собраться и добраться до озера?

Верхний путь, включающий работы 2 и 6, - 15 минут.

Нижний путь, включающий работы 7 и 3, составляет 20 минут.

Самый длинный в графике - критический путь, он включает работы 5, 7, 3, 1 и 4. Его продолжительность - 57 минут. Именно столько вам понадобится, чтобы добраться до озера, если следовать этому сетевому графику.

Можно ли задержать выполнение некоторых работ и все же уложиться в 57 минут? Если да, то каких?

Верхний путь, включающий работы 2 и 6, - не критический.

Из сетевого графика следует, что поскольку работы 5, 7, 3, 1 и 4 находятся на критическом пути, они не могут быть задержаны ни в коем случае.

Однако работы 2 и 6 можно выполнять одновременно с работами 7 и 3. Работы 7 и 3 занимают 20 минут, в то время как работы 2 и 6 - 15 минут. Поэтому работы 2 и 6 имеют резерв времени в 5 минут.

На рис. 4.8 представлен тот же сетевой график, но в форме "события-работы". Событие А эквивалентно событию "Начало", а событие I эквивалентно событию "Конец".

Рис. 4.8. Окончательный вид сетевого графика для организации пикника в форме "события-работы "

Представленные на рис. 4.8 события пока не имеют названий. Вы можете дать их, например:

Событие В , конец работы 5 ("Выбрать озеро"), можно назвать "Решение принято";