Г Л А В А  7 СЕТЕВЫЕ МЕТОДЫ ПЛАНИРОВАНИЯ.

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

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

Рассмотрим числовой пример.

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

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

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

Что считать работой ? ( Забить гвоздь, построить корпус завода - это все работа).

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

Итак, пусть список работ включает:

1. Подвоз необходимых материалов к строительной площадке.

2. Подведение электричества.

3. Подведение водоснабжения.

4. Закладку фундамента первого цеха.

5. Прокладку труб теплоцентрали и т.д.

В принципе этот список может включать многие сотни работ.

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

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

Как  только это сделано, можно приступать к созданию сетевой модели строительства.

Результаты работ будем изображать кружком с соответствующим номером внутри. При этом, если работа  i предшествует работе j, то будем изображать так:

Пусть далее tij означает, что работа j может быть завершена через время tij после окончания работы i. Будем считать, что величины tij для всего списка работ известны. Стрелка на этой модели обозначает собственно работу, а кружки - результат.

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

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

Рассмотрим этот график, называемый сетевым. Естественно, что работы 6 и 8 могут начаться после того, как закончится работа 3. Если их начать сразу после окончания работы 3, то они закончатся через время, равное соответственно t36 и t38. Далее работы 2,3,4 и 5 могут выполняться одновременно, если, конечно, закончилась работа 1 - первая (начальная) во всем комплексе работ. Работа 9 - последняя работа в комплексе, ее завершение равносильно завершению всех работ по строительству, т.е. завершению строительства.

Модель готова. В чем ее польза?

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

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

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

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

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

Рассмотрим один из них. (см. динамическое программирование методом Беллмана Р.,     Калаба С.)

Введем ряд дополнительных условий. Если сетевой график не содержит отрезка, соединяющего работы i и j, то считаем  tij = - . Далее положим  tii = 0. Тогда с математической точки зрения задача состоит в следующем: найти такой путь = [ E1, Ei1, Ei2, ..., Eik, En ], где  Еj  - работы, n - число работ, при котором величина  t1,i1 + ti1,i2 + ... + tik,n достигает максимума.

В основе метода лежит метод ДП. Обозначим через vi (i = 1, 2, ..., n-1) величину максимального пути от вершины i до конечной вершины. ( Предполагается, что вершины занумерованы так, что начальная имеет номер 1, а последняя, завершающая, номер n).

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

На первом этапе определяем величины:

                                                                    vi(1) = tin         i  = 1, 2, ..., n-1;

                                                                    vn(1) = 0           i = 1, 2, ..., n-1.  

Ясно, что они выражают продолжительности времени, необходимого для того, чтобы достичь вершины n от i-ой вершины за один шаг.

Далее переходим к вычислению:

                                                           vi(2) = max (tij + vj(1))        i = 1, 2, ..., n-1,

                                                                           j

                                                                 vn(2) = 0,                        j = 1, 2, ..., n,                                   

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

Рассуждая аналогично, шаг за шагом, вычисляем:

                                                            vi(k) = max ( tij + vj(k-1) )        i = 1, 2, ..., n-1;

                                                                            j

                                                                 vn(k) = 0                                  j = 1, 2, ..., n,

до тех пор, пока не окажется, что выполнены условия:

                                                              vi(k) = vi(k-1)                             i = 1, 2, ..., n.        

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

Числовой пример.

Пусть имеем числовой график.

Составим матрицу, указывающую,  между какими вершинами графика возможны переходы. Там, где переходы не разрешены (нет стрелок), ставим - .

Из этой таблицы ищем пути из двух звеньев ( считаем,  что  в  сумме  любое  число  и  -  есть - ).

Результаты сводим в таблицу:

В этой таблице последние две строки совпали. Отсюда вывод, что критический путь найден. Он состоит из четырех звеньев, соединяющих вершины 1,2,4,9,10. Величина критического пути равна 25.

Это означает, что комплекс работ, изображенный сетевым графиком, не может быть выполнен менее, чем за 25 единиц времени с момента завершения первой работы. Это "жаркая" линия.

Каков интервал свободы у работы 3? Обязательно ли ее начать сразу после  завершения  работы 1 ? Нет. Резерв времени у нее в 2 единицы, так как для того, чтобы не задерживать выполнение работ, лежащих на критическом пути, продолжительность работ 1,3,4 должно быть не более продолжительности работ 1,2,4. Разность между этими продолжительностями составляет две единицы времени. Значит, работу 3 можно начать на 2 единицы времени позже, либо выполнять с интенсивностью в два раза меньшей, используя ресурсы на выполнение критических работ. Общая продолжительность времени работ не изменится.

Вводя стоимостные характеристики в сетевой график, можно оценивать и стоимость строительства в целом.

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

Разработка сетевых графиков.

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

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

Основные правила построения сетевых графиков следующие:

1. Между двумя событиями может быть только одна работа, поэтому в график при необходимости вводят дополнительные события и фиктивные работы.

Например:

2. Сложную работу, промежуточные результаты которой служат началом других работ, нужно дробить на отдельные этапы.

Например:

3. Следует вводить фиктивные работы, если результат двух работ ( 1,2 и 4,2 ) нужен только для одной из двух ( 2,3 ) последующих работ.

Например:

4. Работа обязательно должна начинаться и кончаться событием:

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

Например: Событие 3 на следующем графике является "тупиковым".

6. В сетевом графике не должно быть событий, за исключением исходного, в которые не входит ни одной работы.

Например: Событие 5 в предыдущем графике.

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

Например: Событие 1,2,4 и их связи (работы) 1 2 4 1.

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

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

Способы задания сетевой модели.

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

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

В таком виде модель используется для расчета вручную или для ввода данных в ЭВМ.

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

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

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

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

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

Третий тип работ - это так называемые фиктивные работы. Они не требуют затрат ни материальных ресурсов, ни времени, они показывают зависимость какого-либо события от другого. На сетевых графиках они показываются пунктирными стрелками.

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

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

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

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

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

Обычно исходное событие - это принятое решение о начале какого-либо процесса (комплекса работ). Например: 7.

Завершающее событие - это конечный результат всего комплекса работ. Например: 9.

Есть еще несколько типов событий.

Начальное событие - событие, непосредственно предшествующее каждой работе.

Конечное событие - событие, которым оканчивается какая-либо работа.

Например: на предыдущем графике для работы 2 - 3 события. 2 - начальное, 3 - конечное.

Граничными событиями называются события, фиксирующие окончание работ какого-либо исполнителя (организации). Например: факт передачи исходных данных, выпуск чертежей и т.п.

Сетевой график обычно содержит одно исходное и одно завершающее событие.

Если завершающих событий несколько, то такой график называется многоцелевым.

Сетевые графики обладают важным свойством - наглядностью.

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

Графическое представление сетевой модели значительно упрощает ее составление, расчет, анализ и изучение.

Сетевой график - это не только график, но и модель какого-либо производственного процесса.

Важной особенностью сетевых методов является способ оценки параметров предстоящих работ. Оценку дает либо непосредственный исполнитель, либо эксперт, имеющий большой опыт работ в соответствующей области. Каждая работа оценивается по времени. Часто с временными характеристиками даются оценки:

- количества исполнителей,

- трудоемкости,

- стоимости  и т.п.

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

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

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

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

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

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

Кроме выявления критического пути, расчет сетевого графика позволяет получить целый ряд других показателей:

- ранние и поздние сроки начала и окончания работ,

- резерв времени,

- вероятность наступления событий и т.д.

Эти показатели применяются для оптимизации плана и для принятия решения по рациональной организации выполнения всего комплекса работ.

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

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

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

- сетевого графика, как наглядного отображения сетевой модели,

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

- специальных процедур сбора, обработки и подготовки информации для   принятия решений.

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

Рассмотрим способы определения параметров конкретного сетевого графика.

Пусть tij - продолжительность работы и измеряется, например, в днях. Индексы i и j указывают на начальное и конечное событие работы.

В процессе расчета сетевого графика (модели) определяются и анализируются следующие основные параметры:

     t (L)                      - продолжительность пути L,

     t кр                       - продолжительность критического пути Lкр,

     ti(p) , ti(п)            - ранний и поздний сроки совершения событий,

     tij(pн)  , tij(пн)    - ранний и поздний сроки начала работы,

     tij(ро)  , tij(по)     - ранний и поздний сроки окончания работы,

     R(L)                      - полный резерв времени пути,

     Rij(п)                    - полный резерв времени работы,

     Rijп , Rijп      - частные резервы времени.

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

Продолжительность пути t(L) есть сумма продолжительности работ, составляющих этот путь.

Рассмотрим конкретный сетевой график:

Продолжительность пути L1 через события 0, 1, 4, 5, 11, 13 t(L1) = t01 + t14 + t45 + t511 + t1113 = 18 + 22 + 30 + 22 + 48 = 140 дням.

Всего в рассматриваемом графике девять путей. Все пути имеют разную продолжительность. Путь с наибольшей продолжительностью - критический. В примере таким путем является путь, проходящий через события 0, 2, 7, 10, 11, 13, его продолжительность 170 дней.

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

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

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

Пусть максимальный предшествующий событию i путь есть L(I-i)max. Тогда:

                                                                         ti(p)   =  t [ L(I-i)max ].

Например, событие 5. Оно свершиться только в том случае, если будут выполнены непосредственно предшествующие ему работы 0, 1; 1, 4; 1, 5; 4, 5, лежащие на путях L1(0,1, 4, 5) и L2(0, 1, 5).

Сумма продолжительностей работ на пути L1 = 70 и больше суммы продолжительностей работ на пути L2 = 30.

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

                                                  t5(р)  = t [ L (0-5)max] = t01 + t14 + t45 = 70.

Это значит, что событие 5 не может наступить ранее, чем через 70 дней после свершения исходного события.         

Как определяются поздние сроки свершения событий  ti(п)   ?

Очевидно, что для завершающего события сети ранний срок свершения является одновременно и поздним сроком, т.е.:

                                                                      t13(п)  = t13(р)  = 170.

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

Пусть максимальный путь, следующий за событием i  есть L (i-C)max, тогда получим:

                                                             ti(п)  =  tкр  -  t [ L(i - C)max ]

От события 5 к завершающему событиию 13 идут два пути L1 = (5, 11, 13) и L2 = (5, 12, 13). Суммарная продолжительность пути  L2 = 50 меньше чем сумма для  L1 = 70, следовательно,

                                                    t [L(5 - 13)max] = t511 + t1113 = 70.

Тогда событие 5 должно свершиться не позднее чем за 70 дней до свершения события 13. Поэтому поведем отсчет времени от момента завершающего события сети:

                                                        t5(п)  = tкр - t [ L(5, 11, 13)] = 170 - 70 = 100.

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

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

Ранние сроки начала работ tijрн определяются ранними сроками свершения начальных событий, а поздние сроки окончания работ tijпо - поздними сроками свершения конечных событий.

Зная продолжительность работы, можно определить и поздние сроки начала и ранние сроки окончания работ:

                                                                          tijпн  = tjп  -  tij,

                                                                          tijрн  = tiр  +  tij.

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

Для всех работ критического пути ранние начала равны поздним началам и ранние окончания - поздним, т.е. у них нет резервов времени.

Резерв времени. Разница между продолжительностью критического пути  tкр и любого другого пути t(L)  называется полным резервом времени пути L и обозначается R(L):

                                                                          R(L) = tкр - t(L).

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

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

Работы критического пути резервов времени не имеют.

Берем, например, работу 4, 5. Через нее проходят два пути L1(0,1,4,5,11,13) и L2(0,1, 4,5,12,13). Продолжительность и резервы этих путей различные:

                                                                 t(L1) = 140,    R(L1) = 30,

                                                                 t(L2) = 120,    R(L2) = 50.

Полный резерв времени работы 4,5 не может быть больше 30,  так  как увеличение его даст t(L1) > tкр = 170. И несмотря на то, что работа 4,5 принадлежат двум путям, величина ее полного резерва времени определяется только одним из них, т.е. L1, максимальным по продолжительности.

При увеличении продолжительности работы 4,5 на 30  она  уже  будет  иметь  60 дней. Но тогда t(L) = 140 + 30 = 170, а R(L1) = 0, т.е. у всех работ на этом пути Rijп = 0. Продолжительность L2 стала равной t(L2) = 120 + 30 = 150, а R(L2)  = 50.

Cледовательно, полный резерв времени работ 5,12 и 12,13 уменьшается на 30 дней и R512 = R1213 = 20, т.е., если использовать полный резерв времени частично или целиком, то соответственно уменьшатся полные резервы времени у остальных работ, имеющих с данной работой общий путь.

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

Рассмотрим путь L2 = (0,1,4,5,12,13). Работы его имеют разные резервы времени. Полные резервы времени у работ 0,1; 1,4 и 4,5 определяются резервом времени пути (0,1,4,5,11,13), равного 30, а у 5,12  и  12,13    R(L2)  = 50.

Следовательно, резерв времени пути не может быть отнесен к работам 0,1 и 4,5, хотя они и лежат на этом пути. То есть работы, лежащие на одном пути, могут иметь разные по величине полные резервы времени, меньшие, чем резерв времени данного пути и резерв времени. R(L) пути L может быть распределен между отдельными работами на данном пути только в пределах полных резервов времени этих работ.

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

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

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

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

                                                                           Rijп = tjп - ti(п) - tij.

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

                                                                      Rijп = tjр - ti(р) - tij.

У работы 5,12, следующей непосредственно за начальным событием отрезка пути (5,12,13), есть частный резерв времени первого вида.

У работы 12,13, предшествующей непосредственно конечному событию отрезка (5,12,13), есть частный резерв времени второго вида:

                                                            R512n    = 160 - 100 - 40 = 20,

                                                            R1213n= 160 - 100 - 10 = 50.

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

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

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

Рассмотрим числовой пример.

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

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

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

Что считать работой ? ( Забить гвоздь, построить корпус завода - это все работа).

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

Итак, пусть список работ включает:

1. Подвоз необходимых материалов к строительной площадке.

2. Подведение электричества.

3. Подведение водоснабжения.

4. Закладку фундамента первого цеха.

5. Прокладку труб теплоцентрали и т.д.

В принципе этот список может включать многие сотни работ.

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

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

Как  только это сделано, можно приступать к созданию сетевой модели строительства.

Результаты работ будем изображать кружком с соответствующим номером внутри. При этом, если работа  i предшествует работе j, то будем изображать так:

Пусть далее tij означает, что работа j может быть завершена через время tij после окончания работы i. Будем считать, что величины tij для всего списка работ известны. Стрелка на этой модели обозначает собственно работу, а кружки - результат.

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

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

Рассмотрим этот график, называемый сетевым. Естественно, что работы 6 и 8 могут начаться после того, как закончится работа 3. Если их начать сразу после окончания работы 3, то они закончатся через время, равное соответственно t36 и t38. Далее работы 2,3,4 и 5 могут выполняться одновременно, если, конечно, закончилась работа 1 - первая (начальная) во всем комплексе работ. Работа 9 - последняя работа в комплексе, ее завершение равносильно завершению всех работ по строительству, т.е. завершению строительства.

Модель готова. В чем ее польза?

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

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

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

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

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

Рассмотрим один из них. (см. динамическое программирование методом Беллмана Р.,     Калаба С.)

Введем ряд дополнительных условий. Если сетевой график не содержит отрезка, соединяющего работы i и j, то считаем  tij = - . Далее положим  tii = 0. Тогда с математической точки зрения задача состоит в следующем: найти такой путь = [ E1, Ei1, Ei2, ..., Eik, En ], где  Еj  - работы, n - число работ, при котором величина  t1,i1 + ti1,i2 + ... + tik,n достигает максимума.

В основе метода лежит метод ДП. Обозначим через vi (i = 1, 2, ..., n-1) величину максимального пути от вершины i до конечной вершины. ( Предполагается, что вершины занумерованы так, что начальная имеет номер 1, а последняя, завершающая, номер n).

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

На первом этапе определяем величины:

                                                                    vi(1) = tin         i  = 1, 2, ..., n-1;

                                                                    vn(1) = 0           i = 1, 2, ..., n-1.  

Ясно, что они выражают продолжительности времени, необходимого для того, чтобы достичь вершины n от i-ой вершины за один шаг.

Далее переходим к вычислению:

                                                           vi(2) = max (tij + vj(1))        i = 1, 2, ..., n-1,

                                                                           j

                                                                 vn(2) = 0,                        j = 1, 2, ..., n,                                   

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

Рассуждая аналогично, шаг за шагом, вычисляем:

                                                            vi(k) = max ( tij + vj(k-1) )        i = 1, 2, ..., n-1;

                                                                            j

                                                                 vn(k) = 0                                  j = 1, 2, ..., n,

до тех пор, пока не окажется, что выполнены условия:

                                                              vi(k) = vi(k-1)                             i = 1, 2, ..., n.        

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

Числовой пример.

Пусть имеем числовой график.

Составим матрицу, указывающую,  между какими вершинами графика возможны переходы. Там, где переходы не разрешены (нет стрелок), ставим - .

Из этой таблицы ищем пути из двух звеньев ( считаем,  что  в  сумме  любое  число  и  -  есть - ).

Результаты сводим в таблицу:

В этой таблице последние две строки совпали. Отсюда вывод, что критический путь найден. Он состоит из четырех звеньев, соединяющих вершины 1,2,4,9,10. Величина критического пути равна 25.

Это означает, что комплекс работ, изображенный сетевым графиком, не может быть выполнен менее, чем за 25 единиц времени с момента завершения первой работы. Это "жаркая" линия.

Каков интервал свободы у работы 3? Обязательно ли ее начать сразу после  завершения  работы 1 ? Нет. Резерв времени у нее в 2 единицы, так как для того, чтобы не задерживать выполнение работ, лежащих на критическом пути, продолжительность работ 1,3,4 должно быть не более продолжительности работ 1,2,4. Разность между этими продолжительностями составляет две единицы времени. Значит, работу 3 можно начать на 2 единицы времени позже, либо выполнять с интенсивностью в два раза меньшей, используя ресурсы на выполнение критических работ. Общая продолжительность времени работ не изменится.

Вводя стоимостные характеристики в сетевой график, можно оценивать и стоимость строительства в целом.

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

Разработка сетевых графиков.

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

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

Основные правила построения сетевых графиков следующие:

1. Между двумя событиями может быть только одна работа, поэтому в график при необходимости вводят дополнительные события и фиктивные работы.

Например:

2. Сложную работу, промежуточные результаты которой служат началом других работ, нужно дробить на отдельные этапы.

Например:

3. Следует вводить фиктивные работы, если результат двух работ ( 1,2 и 4,2 ) нужен только для одной из двух ( 2,3 ) последующих работ.

Например:

4. Работа обязательно должна начинаться и кончаться событием:

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

Например: Событие 3 на следующем графике является "тупиковым".

6. В сетевом графике не должно быть событий, за исключением исходного, в которые не входит ни одной работы.

Например: Событие 5 в предыдущем графике.

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

Например: Событие 1,2,4 и их связи (работы) 1 2 4 1.

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

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

Способы задания сетевой модели.

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

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

В таком виде модель используется для расчета вручную или для ввода данных в ЭВМ.

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

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

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

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

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

Третий тип работ - это так называемые фиктивные работы. Они не требуют затрат ни материальных ресурсов, ни времени, они показывают зависимость какого-либо события от другого. На сетевых графиках они показываются пунктирными стрелками.

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

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

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

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

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

Обычно исходное событие - это принятое решение о начале какого-либо процесса (комплекса работ). Например: 7.

Завершающее событие - это конечный результат всего комплекса работ. Например: 9.

Есть еще несколько типов событий.

Начальное событие - событие, непосредственно предшествующее каждой работе.

Конечное событие - событие, которым оканчивается какая-либо работа.

Например: на предыдущем графике для работы 2 - 3 события. 2 - начальное, 3 - конечное.

Граничными событиями называются события, фиксирующие окончание работ какого-либо исполнителя (организации). Например: факт передачи исходных данных, выпуск чертежей и т.п.

Сетевой график обычно содержит одно исходное и одно завершающее событие.

Если завершающих событий несколько, то такой график называется многоцелевым.

Сетевые графики обладают важным свойством - наглядностью.

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

Графическое представление сетевой модели значительно упрощает ее составление, расчет, анализ и изучение.

Сетевой график - это не только график, но и модель какого-либо производственного процесса.

Важной особенностью сетевых методов является способ оценки параметров предстоящих работ. Оценку дает либо непосредственный исполнитель, либо эксперт, имеющий большой опыт работ в соответствующей области. Каждая работа оценивается по времени. Часто с временными характеристиками даются оценки:

- количества исполнителей,

- трудоемкости,

- стоимости  и т.п.

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

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

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

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

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

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

Кроме выявления критического пути, расчет сетевого графика позволяет получить целый ряд других показателей:

- ранние и поздние сроки начала и окончания работ,

- резерв времени,

- вероятность наступления событий и т.д.

Эти показатели применяются для оптимизации плана и для принятия решения по рациональной организации выполнения всего комплекса работ.

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

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

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

- сетевого графика, как наглядного отображения сетевой модели,

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

- специальных процедур сбора, обработки и подготовки информации для   принятия решений.

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

Рассмотрим способы определения параметров конкретного сетевого графика.

Пусть tij - продолжительность работы и измеряется, например, в днях. Индексы i и j указывают на начальное и конечное событие работы.

В процессе расчета сетевого графика (модели) определяются и анализируются следующие основные параметры:

     t (L)                      - продолжительность пути L,

     t кр                       - продолжительность критического пути Lкр,

     ti(p) , ti(п)            - ранний и поздний сроки совершения событий,

     tij(pн)  , tij(пн)    - ранний и поздний сроки начала работы,

     tij(ро)  , tij(по)     - ранний и поздний сроки окончания работы,

     R(L)                      - полный резерв времени пути,

     Rij(п)                    - полный резерв времени работы,

     Rijп , Rijп      - частные резервы времени.

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

Продолжительность пути t(L) есть сумма продолжительности работ, составляющих этот путь.

Рассмотрим конкретный сетевой график:

Продолжительность пути L1 через события 0, 1, 4, 5, 11, 13 t(L1) = t01 + t14 + t45 + t511 + t1113 = 18 + 22 + 30 + 22 + 48 = 140 дням.

Всего в рассматриваемом графике девять путей. Все пути имеют разную продолжительность. Путь с наибольшей продолжительностью - критический. В примере таким путем является путь, проходящий через события 0, 2, 7, 10, 11, 13, его продолжительность 170 дней.

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

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

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

Пусть максимальный предшествующий событию i путь есть L(I-i)max. Тогда:

                                                                         ti(p)   =  t [ L(I-i)max ].

Например, событие 5. Оно свершиться только в том случае, если будут выполнены непосредственно предшествующие ему работы 0, 1; 1, 4; 1, 5; 4, 5, лежащие на путях L1(0,1, 4, 5) и L2(0, 1, 5).

Сумма продолжительностей работ на пути L1 = 70 и больше суммы продолжительностей работ на пути L2 = 30.

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

                                                  t5(р)  = t [ L (0-5)max] = t01 + t14 + t45 = 70.

Это значит, что событие 5 не может наступить ранее, чем через 70 дней после свершения исходного события.         

Как определяются поздние сроки свершения событий  ti(п)   ?

Очевидно, что для завершающего события сети ранний срок свершения является одновременно и поздним сроком, т.е.:

                                                                      t13(п)  = t13(р)  = 170.

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

Пусть максимальный путь, следующий за событием i  есть L (i-C)max, тогда получим:

                                                             ti(п)  =  tкр  -  t [ L(i - C)max ]

От события 5 к завершающему событиию 13 идут два пути L1 = (5, 11, 13) и L2 = (5, 12, 13). Суммарная продолжительность пути  L2 = 50 меньше чем сумма для  L1 = 70, следовательно,

                                                    t [L(5 - 13)max] = t511 + t1113 = 70.

Тогда событие 5 должно свершиться не позднее чем за 70 дней до свершения события 13. Поэтому поведем отсчет времени от момента завершающего события сети:

                                                        t5(п)  = tкр - t [ L(5, 11, 13)] = 170 - 70 = 100.

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

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

Ранние сроки начала работ tijрн определяются ранними сроками свершения начальных событий, а поздние сроки окончания работ tijпо - поздними сроками свершения конечных событий.

Зная продолжительность работы, можно определить и поздние сроки начала и ранние сроки окончания работ:

                                                                          tijпн  = tjп  -  tij,

                                                                          tijрн  = tiр  +  tij.

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

Для всех работ критического пути ранние начала равны поздним началам и ранние окончания - поздним, т.е. у них нет резервов времени.

Резерв времени. Разница между продолжительностью критического пути  tкр и любого другого пути t(L)  называется полным резервом времени пути L и обозначается R(L):

                                                                          R(L) = tкр - t(L).

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

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

Работы критического пути резервов времени не имеют.

Берем, например, работу 4, 5. Через нее проходят два пути L1(0,1,4,5,11,13) и L2(0,1, 4,5,12,13). Продолжительность и резервы этих путей различные:

                                                                 t(L1) = 140,    R(L1) = 30,

                                                                 t(L2) = 120,    R(L2) = 50.

Полный резерв времени работы 4,5 не может быть больше 30,  так  как увеличение его даст t(L1) > tкр = 170. И несмотря на то, что работа 4,5 принадлежат двум путям, величина ее полного резерва времени определяется только одним из них, т.е. L1, максимальным по продолжительности.

При увеличении продолжительности работы 4,5 на 30  она  уже  будет  иметь  60 дней. Но тогда t(L) = 140 + 30 = 170, а R(L1) = 0, т.е. у всех работ на этом пути Rijп = 0. Продолжительность L2 стала равной t(L2) = 120 + 30 = 150, а R(L2)  = 50.

Cледовательно, полный резерв времени работ 5,12 и 12,13 уменьшается на 30 дней и R512 = R1213 = 20, т.е., если использовать полный резерв времени частично или целиком, то соответственно уменьшатся полные резервы времени у остальных работ, имеющих с данной работой общий путь.

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

Рассмотрим путь L2 = (0,1,4,5,12,13). Работы его имеют разные резервы времени. Полные резервы времени у работ 0,1; 1,4 и 4,5 определяются резервом времени пути (0,1,4,5,11,13), равного 30, а у 5,12  и  12,13    R(L2)  = 50.

Следовательно, резерв времени пути не может быть отнесен к работам 0,1 и 4,5, хотя они и лежат на этом пути. То есть работы, лежащие на одном пути, могут иметь разные по величине полные резервы времени, меньшие, чем резерв времени данного пути и резерв времени. R(L) пути L может быть распределен между отдельными работами на данном пути только в пределах полных резервов времени этих работ.

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

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

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

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

                                                                           Rijп = tjп - ti(п) - tij.

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

                                                                      Rijп = tjр - ti(р) - tij.

У работы 5,12, следующей непосредственно за начальным событием отрезка пути (5,12,13), есть частный резерв времени первого вида.

У работы 12,13, предшествующей непосредственно конечному событию отрезка (5,12,13), есть частный резерв времени второго вида:

                                                            R512n    = 160 - 100 - 40 = 20,

                                                            R1213n= 160 - 100 - 10 = 50.

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