Табличный метод расчета параметров сетевого графика. Основные параметры сетевого графика
Любая последовательность работ сетевого графика, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы, называется путем .
Путь сетевого графика, в котором начальная точка совпадает с исходным событием, а конечная - с завершающим событием, называется полным.
Путь от исходного события до любого взятого предшествует данному событию. Предшествующий событию путь, имеющий наибольшую длину, называется максимальным предшествующим . Он обозначается L 1 (i), а его продолжительность t.
Путь, соединяющий любое взятое событие с завершающим, называется последующим путем. Такой путь с наибольшей длиной называется максимально последующим и обозначается L 2 (i), а его продолжительность t.
Полный путь, имеющий наибольшую длину, называется критическим . Пути, отличные от критического, называются ненапряженными . Они имеют резервы времени.
Работы критического пути выделяются жирными линиями или двойными. Продолжительность критического пути считается главным параметром графика.
Рассмотрим алгоритм определения критического пути на сетевом графике, использующий алгоритм метода динамического программирования.
Упорядочим вершины графика по рангам и пронумеруем их с конца к началу. Это позволит совместить номера рангов с этапами попятного движения при отыскании условно-оптимальных управлений на последнем, двух последних и т.д. этапах. Нахождение критического пути разберем на примере сетевого графика, изображенного на рис. 10.7.
Согласно принципу оптимальности Беллмана , оптимальное управление на каждом этапе определяется целью управления и состоянием на начало этапа. Состояние системы - это события, лежащие на рангах. Для совершения конечного события Х 16 необходимо совершение предшествующих событий. Возможные состояния системы на начало последнего этапа работ - совершение событий Х 14 и Х 15. В кружках у точек Х 14 и Х 15 поставим максимальную продолжительность работ на последнем этапе: Х 14 5 , Х 15 7 . Найдем максимальную продолжительность работ на двух последних этапах. Состояние системы на начало предпоследнего этапа обусловлено событием Х 13. Максимальная продолжительность пути, ведущая из Х 13 к Х 16 равна .
Следовательно, в кружке у события Х 13 нужно поставить число 14 и т.д. Проводя этапы от конца к началу, узнаем длину критического пути t кр =96. Чтобы найти сам критический путь, процесс вычислений пройдем от начального события Х 1 к конечному Х 16 . Число 96 на первом этапе (от начала) мы получили, прибавив 16 к числу 80. Следовательно, критический путь на этом этапе будет равен (Х 1 , Х 3). Число 80 = 16 + 64. Следовательно, критический путь на втором этапе проходит через работу (Х 3 , Х 4) и т.д. На графике он выделен жирной линией:
X 1 - X 3 - X 4 - X 7 - X 8 - X 10 - X 11 - X 12 - X 13 - X 15 - X 16 .
Ранние и поздние сроки свершения событий. Резерв времени событий
Все пути, отличные по продолжительности от критического, располагают резервами времени. Разность между длиной критического пути и любого некритического называется полным резервом времени данного некритического пути и обозначается : 
.
Ранним сроком свершения события называется самый ранний момент времени, к которому завершаются все предшествующие этому событию работы, т.е. определяется продолжительностью максимального пути, предшествующего событию , т.е.:
или 
Чтобы найти ранний срок совершения события j , нужно знать критический путь ориентированного подграфа, состоящего из множества путей, предшествующих данному событию j . Ранний срок исходного события равен нулю: t p (1)=0.
Поздним сроком
совершения события
называется самый поздний момент времени, после которого остается ровно столько времени, сколько необходимо для завершения всех работ, следующих за этим событием. Самый поздний из допустимых сроков свершения события в сумме с продолжительностью выполнения всех последующих работ должен не превышать длины критического пути. Поздний срок свершения события вычисляется как разность между продолжительностью критического пути и продолжительностью максимального из последующих за событием путей : 
Для событий, лежащих на критическом пути, ранний и поздний сроки свершения этих событий совпадают .
Разность между поздним и ранним сроками свершения события составляет резерв времени события : 
. Интервал называется интервалом свободы события . Резерв времени события показывает максимально допустимое время, на которое можно отодвинуть момент его свершения, не увеличивая критический путь.
Так как сумма 
определяет продолжительность пути максимальной длины, проходящего через это событие, то , т.е. резерв времени любого события равен полному резерву времени максимального пути, проходящего через это событие .
При расчете временных параметров вручную удобно пользоваться четырехсекторным способом. При этом способе кружок сетевого графика, обозначающий событие, делится на четыре сектора. В верхнем секторе ставится номер события; в левом - наиболее раннее из возможных время свершения события (); в правом - наиболее позднее из допустимых время свершения события ; в нижнем секторе - резерв времени данного события : 
.
Для вычисления раннего срока свершения событий: 
, применяем формулу 
, рассматривая события в порядке возрастания номеров, от начального к завершающему, по входящим в это событие работам.
Поздний срок свершения событий вычисляем по формуле 
, начиная с конечного события, для которого ( - номер конечного события), по выходящим из него работам.
Критические события имеют резерв времени равный нулю. Они и определяют критические работы и критический путь.
Пример 10.2 . Пусть задан сетевой график, изображенный на рис. 10.8.
Решение. Вычислим ранние сроки свершения событий :
Итак, завершающее событие может произойти лишь на 14-ый день от начала выполнения проекта. Это максимальное время, за которое могут быть выполнены все работы проекта. Оно определяется самым длинным путем. Ранний срок свершения работы 6 =14 совпадает с критическим временем кр - суммарной продолжительностью работ, лежащих на критическом пути. Теперь можно выделить работы, принадлежащие критическому пути, возвращаясь от завершающего события к исходному. Из двух работ, входящих в событие 6 , , длина критического пути определила работы (5, 6), так как ( 5 + 56)=14. Поэтому работа (5, 6) - критическая и т.д. Работы (1, 3), (3, 4), (4, 5), (5, 6) определили критический путь: кр = (1-3-4-5-6).
Вычислим теперь поздние сроки свершения событий . Положим . Воспользуемся методом динамического программирования. Все расчеты будем вести от завершающего события к начальному событию. Поздние сроки свершения событий равны:
Так как после события 5 для завершения проекта нужно выполнить работу (5, 6) длительностью 3 дня. Из события 4 выходят две работы, поэтому:
Резерв времени для события 2 равен: . Резервы остальных событий равны нулю, так как эти события критические.
Ранние и поздние сроки начала и окончания работ. Определение резервов времени работ. Полный резерв времени работ.
Событие, непосредственно предшествующее данной работе, будем называть начальным и обозначать , а событие, непосредственно следующее за ней, - конечным и обозначать . Тогда любую работу будем обозначать . Зная сроки свершения событий, можно определить временные параметры работ.
Ранний срок начала работы равен раннему сроку свершения события : .
Ранний срок окончания работы
равен сумме раннего срока свершения начального события и продолжительности этой работы: 
или 
.
Поздний срок окончания работы совпадает с поздним сроком свершения ее конечного события : .
Поздний срок начала работы равен разности между поздним сроком свершения ее конечного события и величиной этой работы:
Поскольку сроки выполнения работ находятся в границах, определяемых и , то они могут иметь разного вида резервы времени.
Полный резерв времени работы - это максимальное время, необходимое для выполнения любой работы без превышения критического пути. Он вычисляется как разность между поздним сроком свершения конечного события и ранним сроком времени для выполнения самой работы: . Так как , то .
Таким образом, полный резерв времени работы - это максимальное время, на которое можно увеличить ее продолжительность, не изменяя продолжительности критического пути. Все некритические работы имеют полный резерв времени отличный от нуля.
Свободный резерв времени работы - это запас времени, которым можно располагать при выполнении данной работы при условии, что начальное и конечное ее события наступят в свои ранние сроки: .
Практическое занятие №2
Параметры сетевой модели
1. Порядок сетевого планирования
1. Установление полного перечня работ, которые необходимо выполнить при планировании комплекса работ.
2. Составление топологии сети - четкой последовательности и взаимосвязей всех работ и построение сетевого графика.
3. Оценка продолжительности выполнения отдельных работ.
4. Расчет параметров сетевого графика.
5. Анализ и оптимизация сетевого графика.
6. Управление ходом работ по сетевому графику.
Параметры сетевой модели
В системах СПУ применяются различные типы сетевых моделей, отличающиеся составом информации о комплексе работ.
Встречаются модели с детерминированной и вероятностной структурой сети, с детерминированными и вероятностными оценками продолжительности работ сети. При выборе модели руководителю проекта приходится принимать компромиссное решение: с одной стороны, сетевая модель должна быть простой, а с другой – адекватной объекту.
Широкое применение получила сетевая модель ПДВ (простейшая детерминированная временная), которая характеризуется следующими тремя моментами:
а) имеется сеть с единственным исходным и единственным завершающим событием;
б) продолжительности всех работ t ij известны, однозначно определены (вспомните из математики: детерминант – определитель) и указаны на графике (обычно в днях, в зарубежной практике – чаще в неделях);
в) задан момент начала выполнения комплекса Т 0 , а также задается (но не обязательно) директивный срок Т дир наступления завершающего события.
Рассмотрим временные параметры этой модели.
По известным продолжительностям работ легко определить продолжительность каждого пути – t(L) . Продолжительность любого пути равна сумме продолжительностей работ, его составляющих:
Для пояснения обратимся к рис.1. На графике над стрелками указаны продолжительности работ в днях (напомним, что продолжительность фиктивной работы равна нулю).
 |
Найдем на графике полные пути и определим их продолжительность (по номерам событий):
L 1 1 – 2 – 5 – 7 – 8 t(L 1) = 14 дн.
L 2 1 – 2 – 4 – 5 – 7 – 8 t(L 2) = 12 дн.
L 3 1 – 3 – 4 – 5 – 7 – 8 t(L 3) = 13 дн.
L 4 1 – 3 – 6 – 7 – 8 t(L 4) = 16 дн.
Всегда найдется путь, имеющий наибольшую продолжительность, он называется критическим – L кр . Его продолжительность получила особое обозначение:
t(L кр) = Т кр.
Понятие критического пути является центральным понятием в системе СПУ. Значение L кр , во-первых, состоит в том, что он является самым длинным путем в сети и, таким образом, является единственным путем, который определяет полную продолжительность процесса. Поэтому, если мы хотим определить полную продолжительность процесса, нужно определить Т кр , а определять для этой цели все остальные t(L) не имеет смысла. Во-вторых, если мы хотим сократить продолжительность процесса, нужно прежде всего сокращать продолжительность работ, принадлежащих L кр . Таким образом, логика сетевого планирования приводит нас к необходимости находить в сетях критические пути и определять их продолжительность.
На графике рис. 1 путь L 4 имеет наибольшую продолжительность, равную 16 дням, и потому является критическим. Обычно критический путь на графиках выделяется (цветными, двойными, жирными и т.п. стрелками).
Обратим внимание, что в сети может быть несколько критических путей (с точки зрения использования ресурсов – чем больше критических путей в графике, тем лучше).
Обычно к L кр принадлежит 10-15 % работ. Чем сложнее сеть, тем таких работ меньше (считается, что в сети средней сложности количество работ в 1,7 раза превышает количество событий).
Другие полные пути рассматриваемого сетевого графика могут либо полностью проходить вне критического пути (L 1 и L 2 ), либо частично с ним совпадать (L 3 ). Эти пути называются ненапряженными : на участках, не совпадающих с критической последовательностью работ, они имеют резервы времени. Задержка в наступлении событий, лежащих на этих участках, до определенного момента не влияет на срок завершения всего комплекса.
Из ненапряженных путей наибольшее внимание привлекают наименее напряженные и подкритические. Подкритические пути имеют продолжительность, близкую к Т кр (отличаются от Т кр на определенную величину, устанавливаемую руководителем проекта). Эти пути могут стать критическими в результате задержки выполнения их работ или в результате сокращения продолжительности работ, лежащих на критическом пути, и, следовательно, являются потенциально опасными с точки зрения соблюдения сроков завершения проекта.
Например, при увеличении времени выполнения работы 2-5 (рис. 1) на 2 дня это приведет к тому, что t(L 1) = 16 дн. = Т кр . Тогда L 1 тоже станет критическим и будет определять срок выполнения всего комплекса.
Наименее напряженные пути могут рассматриваться с точки зрения возможности использования ресурсов (рабочей силы, оборудования, денежных средств). Возможное удлинение этих путей, вызванное переброской ресурсов, до определенных пределов не опасно для сроков проекта.
Работы, принадлежащие критическому и подкритическим путям, составляют критическую зону комплекса (15-20 % всех работ).
Зная продолжительность всех работ, можно также определить сроки наступления всех событий сети. Для каждого события определяют ранний и поздний сроки его наступления.
Ранний срок наступления события – это минимальный из возможных моментов его наступления, когда будут выполнены все работы, предшествующие данному событию. Он определяется максимальной из продолжительностей всех путей, предшествующих данному событию:
где - путь, предшествующий данному событию i ;
Поясним это на примере рис. 1. Событию 5 предшествуют три пути: 1-2-5 с продолжительностью 7 дн., 1-2-4-5 с продолжительностью 5 дн. и 1-3-4-5 с продолжительностью 6 дн. Событие 5 не может наступить ранее 7 дней, т.к. только в течение этого периода будут выполнены все предшествующие ему работы 2-4, 3-4 и 2-5.
Легко увидеть, что для события 3 ранний срок его наступления = 4 дн., т.к. ему предшествует только один путь 1-2, состоящий из одной работы.
Поздний срок наступления события - это максимальный из допустимых моментов его наступления, при котором еще не изменяется общий срок выполнения всего комплекса. Поздний срок определяется разностью между Т кр и наибольшей из продолжительностей путей, следующих за событием i :
(3)
где - путь, следующий за событием i ;
Максимальный из этих путей.
Продолжим рассмотрение рис. 1. За событием 5 следует только один путь 5-7-8 продолжительностью 7 дней. Следовательно,
16 – 7 = 9 дн.
За событием 3 следуют два пути: 3-4-5-7-8 с продолжительностью 9 дн. и 3-6-7-8 с продолжительностью 12 дн. Следовательно, = 16 – 12 = 4 дн., т.е. событие 3 не может наступить позже 4 дней от начала работ, иначе это скажется на изменении срока всего комплекса.
Так как по определению критического пути
, (4)
то для всех событий, принадлежащих критическому пути, справедливо равенство:
В справедливости этого мы уже убедились из рассмотренного примера для события 3. Оно лежит на критическом пути, поэтому
Зная сроки наступления событий, можно для каждой работы сети определить сроки ее начала и окончания, выявив тем самым возможности смещения сроков. Применительно к каждой работе рассматриваются четыре срока:
Ранний срок начала работы ; (6)
Ранний срок окончания работы ; (7)
Поздний срок начала работы ; (8)
Поздний срок окончания работы . (9)
С учетом равенства (5) для событий, лежащих на критическом пути, можно сделать вывод, что у работ критического пути ранние и поздние сроки начала или окончания совпадают:
Следующим важным параметром является резерв времени – применительно к пути, событию и работе.
Критический путь является самым продолжительным в сети. Разность между продолжительностью критического пути Т кр и продолжительностью любого другого пути t(L) называется резервом времени пути L и обозначается :
(11)
Чем короче путь L , чем больше он по времени не совпадает с критическим, тем у него больше резерв времени. Физический смысл этого параметра таков: резерв времени пути показывает, на сколько в сумме могут быть увеличены продолжительности работ, принадлежащих пути L , чтобы при этом не изменился общий срок выполнения всего комплекса работ.
Так, L 1 (см. рис. 1) не совпадает с критическим на участке сети между 1 и 7 событиями. Его продолжительность, как было показано выше, составляет 14 дней, и, следовательно, резерв равен двум дням. Только двумя днями располагают руководители всех трех работ при непредвиденной задержке в их выполнении.
Все события, не лежащие на критическом пути, обладают резервом времени, который определяется как разность между поздним и ранним сроками его наступления:
Резерв времени события показывает, на какой предельно допустимый срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ. При большей задержке критический путь переместится на максимальный из путей, проходящих через данное событие i .
Так, для события 5 (рис.1) = 9 – 7 = 2 дн. При задержке этого события на 2 и более дней критический путь переместится на максимальный путь L 1 , проходящий через событие 5.
События, лежащие на критическом пути, имеют нулевой резерв времени , в том числе исходное и завершающее события.
Для работ сетевой модели определяются два резерва времени: полный и свободный.
Полный резерв времени работы - это резерв максимального из путей, проходящих через работу i,j
, (13)
где - поздний срок наступления конечного события этой работы;
Ранний срок наступления начального события этой работы;
Продолжительность выполнения работы.
Физический смысл этого параметра таков: этот резерв показывает, на сколько можно задержать начало или увеличить продолжительность отдельной работы, не изменяя директивного (или раннего, если директивный не задан) срока наступления завершающего события. В последнем случае (если директивный срок не задан) – не изменяя Т кр .
Обратим внимание на следующий важный момент: полный резерв принадлежит не одной работе, а всем путям, которые проходят через данную работу. Поэтому использование его полностью на одной из работ пути L аннулирует полные резервы времени всех работ , принадлежащих этому пути.
Например, = 2 дн. (см. рис.1), т.к. он определяется резервом пути L 1 . Если использовать его полностью на работе 5-7, то другие работы этого пути (1-2, 2-5) останутся без резервов времени.
Полные резервы времени принимают минимальное значение у работ, лежащих на критическом пути. Это свойство является необходимым и достаточным условием принадлежности работы критическому пути и используется для его нахождения при расчете сети. Минимальное значение полного резерва равно нулю, если Т дир не задан или превышает момент начала работ Т 0 на величину Т кр . В общем случае оно равно разности (Т кр - Т дир ).
Свободный резерв времени работы представляет собой максимальное время, на которое можно задержать начало или увеличить продолжительность работы i,j при условии, что все события сети наступают в свои ранние сроки:
. (14)
Свободный резерв образуется не у всех работ, а только у работ, непосредственно принадлежащих событиям, через которые проходят пути с различной продолжительностью. Это надо понимать так: если событию предшествует одна работа (например, работа 1-2 на рис.1), то для нее свободный резерв равен нулю по определению ( = 0), в других случаях – 0.
Свободный резерв является частью полного, и потому чаще на практике применяется другая формула:
где – резерв конечного события работы i,j .
Свободный резерв показывает, какая часть полного резерва времени работы может быть использована для увеличения ее продолжительности при условии, что это не вызовет изменения раннего срока наступления ее конечного события. Свободный резерв является независимым резервом, т.е. использование его на одной из работ не изменяет величины свободных резервов времени остальных работ сети. Используя свободный резерв времени, ответственный исполнитель может маневрировать в его пределах временем начала данной работы, ее окончания или ее продолжительностью, не затрагивая интересов других руководителей работ.
Практическое занятие №3
Расчет параметров сетевых графиков.
«Графический» способ
Для расчета параметров сетевых графиков предложен ряд способов:
а) непосредственно на самом графике (так называемый «графический» способ);
б) табличный способ;
в) матричный способ;
г) на основе машинных алгоритмов.
В средних и крупных комплексах такую работу выполняют специально выделенные работники, входящие в службу СПУ. В настоящее время на многих предприятиях и в организациях имеются стандартные и собственной разработки программы расчета параметров сети на ЭВМ.
«Графический» способ
Расчет параметров и запись результатов осуществляются на самом графике. Для этого сетевой график, желательно не имеющий пересечений, вычерчивается в укрупненном масштабе: диаметр кружков, изображающих на графике события, равен 15-25 мм. Кружки делятся на 4 сектора.
«Ключ» к чтению такого графика показан на рис. 2: в нижних секторах будем изображать номер события; в левых секторах – ранние сроки наступления событий; в правых – поздние сроки наступления событий; в верхних – резервы времени событий; в квадратных скобках под стрелкой – полный и свободный резерв каждой работы; над стрелкой – продолжительность работы.
Вначале график перечерчивается в укрупненном масштабе (рис. 4). Напомним, что продолжительность фиктивной работы равна нулю. И еще: не имеет значения, в какой сектор кружка направлена стрелка.
Параметры графика рассчитываются в следующем порядке.
1. Определение раннего срока наступления каждого события .
Для исходного события 1 имеем = 0 и это указывается в левом секторе. Для остальных событий 
в соответствии с формулой (2).
 |
Это означает, что если в событие входит одна стрелка (например, событие 2), то к раннему сроку наступления предыдущего события 1 прибавляется продолжительность работы 1-2, а результат записывается в левом секторе события 2.
В событие 3 входит две работы: 1-3 и 2-3. Поэтому вначале получаем два значения: 0 + 4 = 4 и 2 + 7 = 9. Большее значение (9 дней) является ранним сроком наступления события 3, что и отмечается в его левом секторе.
Поскольку завершающее событие всегда лежит на критическом пути, можно сказать, что = = 19 дней. Через какие работы и события пройдет критический путь, мы не знаем, но его продолжительность уже определена при расчете первого параметра сети.
2. Определение поздних сроков наступления событий .
Расчет ведется от завершающего события (с конца графика) в строго обратном порядке. Поскольку у событий, лежащих на критическом пути, ранние и поздние сроки совпадают, то для завершающего события = = 19 дней, что и отмечено в правом секторе (рис. 5).
 |
Для остальных событий в соответствии с формулой (3) можно записать . Для события 5 имеем = 19 – 4 = 15 дней, для события 6 = 19 – 2 = 17 дней, для события 4 = 15 – 0 = = 15 дней.
В эти события, идя с конца графика, можно попасть только одним путем, поэтому нет необходимости определять минимальное значение, как, например, для события 3. Из него выходят работы 3-4 и 3-6, поэтому вначале получаем два значения: 15 – 6 = 9 и 17 – 3 = 14. Меньшее значение (9 дней) является поздним сроком наступления события 3, что и отмечено в его правом секторе.
3. Определение резервов времени событий .
Расчет можно вести или с начала графика, или с его конца. Для любого события . Это значит, что для каждого события из значения его правого сектора надо вычесть значение левого сектора, а результат поставить в его верхний сектор (рис. 6).
 |
4. Нахождение критического пути на графике, т.е. находятся события и работы, лежащие на критическом пути.
Процедуру можно осуществлять с начала или конца графика.
а) Необходимое условие принадлежности события критическому пути: , т.е. отыскивают последовательно события с нулевыми резервами времени.
б) Если из события с нулевым резервом выходит несколько работ, имеющих нулевой резерв конечного события, то проверяется достаточное условие принадлежности работы критическому пути:
5. Определение полного резерва времени работы .
Находим полные резервы только для работ, не лежащих на критических путях и не являющихся фиктивными, по формуле (13) 
. Результат записывается в квадратных скобках под стрелкой или рядом с ней. Так, для работы 1-3 полный резерв времени равен 9 – 4 – 0 = 5 дней, для работы 2-5 имеем 15 – 6 – 2 = 7 дней и т.д.
Напомним, что если у работы , то она обязательно лежит на критическом пути (это для самопроверки).
6. Определение свободного резерва времени работы .
Свободный резерв времени является частью полного, поэтому его определяют у тех же работ, не лежащих на критическом пути и не являющихся фиктивными, по формуле (15) . Расчет по этой формуле проще, чем по формуле (14), т.к. к этому времени полные резервы работ и резервы событий уже рассчитаны. Так, для расчета надо взять значение полного резерва работы 2-5 (7 дней) и вычесть из него резерв конечного события этой работы (0 дней), результат указать под стрелкой и закрыть квадратную скобку. Аналогично быстро рассчитываются свободные резервы других работ.
б) для ускорения процесса расчета параметров этап 6 целесообразно совмещать с этапом 5, т.к. в сложных сетях каждый раз отыскивать на графике одну и ту же работу затруднительно.
Практическое занятие №4
Помимо табличного метода существуют следующие способы расчета: графический метод , метод потенциалов .
Пример
. Определить временные параметры сетевого графика на рисунке, пользуясь табличным методом.
Решение
проводим через калькулятор : все вычисления будем заносить в таблицу 3.
Перечень работ и их продолжительность перенесем во вторую и третью графы. При этом работы следует записывать в графу 2 последовательно: сначала начиная с номера 1, затем с номера 2 и т.д.
В первой графе поставим число, характеризующее количество непосредственно предшествующих работ (КПР) тому событию, с которого начинается рассматриваемая работа. Так, для работы (5,10) в графу 1 поставим число 2, т.к. на номер 5 оканчиваются 2 работы: (1,5) и (3,5).
Таблица 3 – Табличный метод расчета сетевого графика
| КПР | Код Работы | Продолжительность работы | Ранние сроки | Поздние сроки | Резервы времени | |||||||||||
| ( i, j) | t(i,j) | t рн (i,j) | t ро (i,j) | t пн (i,j) | t по (i,j) | R п | R с | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||||||||
| 1 | 2 | 3 | 4 | 5=3+4 | 6=7-3 | 7 | 8 | 9 | ||||||||
| 0 | (1,2) | 5 | 0 | 5 | 2 | 7 | 2 | 0 | ||||||||
| 0 | (1,3) | 7 | 0 | 7 | 0 | 7 | 0 | 0 | ||||||||
| 0 | (1,5) | 4 | 0 | 4 | 11 | 15 | 11 | 3 | ||||||||
| 1 | (2,4) | 0 | 5 | 5 | 7 | 7 | 2 | 2 | ||||||||
| 1 | (2,6) | 8 | 5 | 13 | 12 | 20 | 7 | 0 | ||||||||
| 1 | (3,4) | 0 | 7 | 7 | 7 | 7 | 0 | 0 | ||||||||
| 1 | (3,5) | 0 | 7 | 7 | 15 | 15 | 8 | 0 | ||||||||
| 1 | (3,8) | 7 | 7 | 14 | 13 | 20 | 6 | 0 | ||||||||
| 1 | (3,9) | 11 | 7 | 18 | 12 | 23 | 5 | 1 | ||||||||
| 2 | (4,7) | 12 | 7 | 19 | 7 | 19 | 0 | 0 | ||||||||
| 2 | (5,10) | 5 | 7 | 12 | 15 | 20 | 8 | 2 | ||||||||
| 1 | (6,11) | 7 | 13 | 20 | 20 | 27 | 7 | 7 | ||||||||
| 1 | (7,9) | 0 | 19 | 19 | 23 | 23 | 4 | 0 | ||||||||
| 1 | (7,11) | 8 | 19 | 27 | 19 | 27 | 0 | 0 | ||||||||
| 1 | (8,9) | 0 | 14 | 14 | 23 | 23 | 9 | 5 | ||||||||
| 1 | (8,10) | 0 | 14 | 14 | 20 | 20 | 6 | 0 | ||||||||
| 1 | (8,11) | 4 | 14 | 18 | 23 | 27 | 9 | 9 | ||||||||
| 3 | (9,11) | 4 | 19 | 23 | 23 | 27 | 4 | 4 | ||||||||
| 2 | (10,11) | 7 | 14 | 21 | 20 | 27 | 6 | 6 | ||||||||
Далее заполняем графы 4 и 5. Для работ, имеющих цифру 0 в графе 1, в графу 4 также заносятся нули, а их значения в графе 5 получаются в результате суммирования граф 3 и 4 (по формуле (2.4)). В нашем случае для работ (1,2), (1,3), (1,5) в графе 4 ставим 0, а в графе 5 - 0+5=5, 0+7=7, 0+4=4. Для заполнения следующих строк графы 4 , т.е. строк начиная с номера 2, просматриваются заполненные строки графы 5, содержащие работы, которые оканчиваются на этот номер, и максимальное значение переносится в графу 4 обрабатываемых строк. В данном случае такая работа одна - (1,2). Цифру 5 из графы 5 переносим в графу 4 для всех работ, начиная с номера 2, т.е. в две последующие строки с номерами (2,4) и (2,6). Для каждой из этих работ путем суммирования значений граф 3 и 4 сформируем значение графы 5: t р.о. (2,4)=0+5=5,
t р.о. (2,6)=8+5=13. Этот процесс повторяется до тех пор, пока не будет заполнена последняя строка таблицы.
Графы 6 и 7 заполняются “обратным ходом”, т.е. “снизу вверх”. Для этого просматриваются строки, оканчивающиеся на номер последнего события, и из графы 5 выбирается максимальная величина, которая записывается в графу 7 по всем строчкам, оканчивающимся на номер последнего события (т.к. t р (i)= t п (i)). В нашем случае t(11)=27 . Затем для этих строчек находится содержание графы 6 как разности граф 7 и 3 по формуле (2.7). Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е.
10. Для определения графы 7 этих строк (работы (8,10) и (5,10)) просматриваются все строчки, начинающиеся с номера 10. В графу 6 среди них выбирается минимальная величина, которая переносится в графу 7 по обрабатываемым строчкам. В нашем случае она одна - (10,11), поэтому заносим в строчки (8,10) и (5,10) графы 7 цифру 20. Процесс повторяется до тех пор, пока не будут заполнены все строчки по графам 6 и 7.
Содержимое графы 8 равно разности граф 6 и 4 или граф 7 и 5 (формула (2.8).
Содержимое графы 9 вычисляется по формуле (2.9):
R с (3,9)= t р.н (9,11)- t р.о. (3,9)=19-18=1.
Учитывая, что резерв времени имеют только события и работы, которые принадлежат критическому пути, получаем критический путь (1,3,4,7,11).
С помощью данной программы можно онлайн определить параметры сетевого графика
(рассчитать сроки свершения событий, резервы времени и критический путь), найти коэффициенты напряженности. Оптимизация сетевого графика проводится по следующим критериям: число исполнителей, резервы-затраты, сокращение сроков.
Сетевой график можно нарисовать, а также задать в виде матрицы или таблицы (меню Операции).
Размеры графического полотна
Ширина Высота
● ■ ▲ ⊗ ↔ ✍ ⊗
параметры сетевой модели (критический путь, резервы времени, построить диаграмму Ганта и многое другое).Для сформированного графа можно выполнить следующее действия:
Инструкция к сервису
Для добавления вершины на графическое полотно необходимо использовать соответствующую фигуре кнопку Добавить. Новый объект также можно вставить, предварительно выделив его левой кнопкой мыши, а затем щелкнуть мышкой на рабочем поле. Нумерация вершин может начинаться с 0 , для этого нужно снять отметку с пункта Нумерация вершин с №1 .
1 2 3 4
1 10 30 15
Нумерация вершин с 0
0 1 2 3
1 10 30 15
Чтобы соединить вершины, их необходимо предварительно выбрать (один клик мыши по объекту), а затем нажать на кнопку Соединить.
Сетевая модель может быть представлена в табличной форме и в виде матрицы весов (матрицы расстояний). Чтобы использовать данные представления, выберите меню Операции.
Основные определения
Ориентированный граф , в котором существует лишь одна вершина, не имеющая входящих дуг, и лишь одна вершина, не имеющая выходящих дуг, называется сетью . Сеть, моделирующая комплекс работ, называется его сетевой моделью или сетевым графиком . Дуги, соединяющие вершины графа, ориентированы в направлении достижения результата при осуществлении комплекса работ.Наиболее распространен способ представления моделируемого комплекса работ в понятиях работ и событий .
Понятие «работа» имеет следующие значения:
- «действительная работа» – процесс, требующий затрат времени и ресурсов;
- «фиктивная работа» – логическая связь между двумя или несколькими работами, указывающая на то, что начало одной работы зависит от результатов другой. Фиктивная работа не требует затрат времени и ресурсов, продолжительность ее равна нулю.
На сетевой модели событиям соответствуют вершины графа.
Правила построения сетевой модели
Правило 1 . Каждая операция в сети представляется одной и только одной дугой (стрелкой). Ни одна из операций не должна появляться в модели дважды. При этом следует различать случай, когда какая-либо операция разбивается на части; тогда каждая часть изображается отдельной дугой.Правило 2 . Ни одна пара операций не должна определяться одинаковыми начальным и конечным событиями. Возможность неоднозначного определения операций через события появляется в случае, когда две или большее число операций допустимо выполнять одновременно.
Правило 3
. При включении каждой операции в сетевую модель для обеспечения правильного упорядочения необходимо дать ответы на следующие вопросы:
а) Какие операции необходимо завершить непосредственно перед началом рассматриваемой операции?
б) Какие операции должны непосредственно следовать после завершения данной операции?
в) Какие операции могут выполняться одновременно с рассматриваемой?
При построении сетевого графика следует соблюдать следующие правила:
- в сети не должно быть "тупиков", т.е., событий, от которых не начинается ни одна работа, исключая завершающее событие графика;
- В сетевом графике не должно быть «хвостовых» событий, то есть событий, которым не предшествует хотя бы одна работа, за исключением исходного.
- в сети не должно быть замкнутых контуров (рис.1);
- Любые два события должны быть непосредственно связаны не более чем одной работой.
- В сети рекомендуется иметь одно исходное и одно завершающее событие.
- Сетевой график должен быть упорядочен. То есть события и работы должны располагаться так, чтобы для любой работы предшествующее ей событие было расположено левее и имело меньший номер по сравнению с завершающим эту работу событием.
завершается кружком – событием, в котором проставляется номер этого события. Нумерация событий произвольная. На следующем этапе построения изображаем работы, которым предшествуют уже нарисованные работы (то есть которые опираются на уже построенные работы) и т. д. На следующем этапе отражаем логические взаимосвязи между работами и определяем конечное событие сетевого графика, на которое не опираются никакие работы. Построение закончено, далее необходимо провести упорядочение сетевого графика.
Методы оптимизации сетевого графика
Логико-математическое описание, формирование планов и управляющих воздействий осуществляется на базе использования особого класса моделей, называемых сетевыми моделями .После построения и расчета сетевого графика (определения его параметров), выполнения анализа графика, заключающегося в оценке его целесообразности и структуры, оценке загрузки исполнителей, оценке вероятности наступления завершающего события в заданный срок, следует приступать к оптимизации сетевого графика. Процедура оптимизации заключается в приведение графика в соответствие с заданными сроками выполнения работ, возможностями подрядных организаций и т.д. В общем случае под оптимизацией следует понимать процесс улучшения организации выполнения работ.
Для возможности оптимизации сетевой модели, все исходные данные вводятся в виде таблицы (Операции/Добавить в виде таблицы).
- Оптимизация сетевой модели по критерию "число исполнителей". Заполняется столбец Количество исполнителей Ч
- Оптимизация сетевой модели по критерию "затраты". Заполняется столбец Коэффициент затрат на ускорение работ, h(i,j) .
- Оптимизация сетевого графика методом "время – стоимость". Заполняются столбцы t опт, Минимальное время работ, t min , Нормальная стоимость, Cн и Срочная стоимость, Cc .
Примеры сетевых моделей
Рассмотрим варианты сетевых графиков из кулинарной области на примере варки борща из курицы. а) Варка в обычной посуде10 2 3 4 5 1 10 30 15 7
Работы:
1,3: варить курицу, 30 мин.
2,3: положить капусту и варить 10 мин.
3,4: положить 1/2 свеклы, морковь и картофель. Варить 15 мин.
4,5: доложить остатки свеклы, лук, зелень. Варить 7 мин.
б) Варка в посуде с эффектом русской печи (трехслойное дно, крышка без отверстий) 1 2 3 4 5 10 10 20 30 60
Работы:
1,2: чистка овощей (капуста, морковь, картофель, свекла, лук), 10 мин.
1,4: варить курицу в обычной посуде, 30 мин.
2,3: положить овощи в спецпосуду, добавить 3 ложки воды, нагреть до T=70 C и выключить, 10 мин.
3,4: приготовление овощей в собственном соку, 20 мин.
4,5: добавить к курице приготовленные овощи. Настаивается 60 мин.
Список литературы
- Мушик Э., Мюллер П. Методы принятия технических решений. Пер. с нем. –М.: Мир, 1990.
- Таха Х. Введение в исследование операций. В 2-х книгах. Кн. 2. Пер. с англ. –М.: мир, 1985.
- Управление в системах РАВ: Учебник. –Л.: Воениздат, 1980.
Свойства вершины
Текст
Размер Цвет
Толщина Цвет
пунктирная - - - -Размеры в px и фон
w h
Отмена
Соединение (дуга)
Текст (вес)
Размер Цвет
Толщина Цвет
пунктирная - - -концевой маркер →
При составлении сетевого графика оценку времени ведут, исходя из предположения, что все наличные ресурсы могут быть применены для завершения каждой работы на основании проектов производства работ и технологических карт. Затем эта оценка времени уточняется за счет совмещения отдельных работ, исходя из принципов оптимального использования наличной рабочей силы и прочих ресурсов. В связи с тем, что трудоемкость работ обычно выражается в чел.-днях, данные, заимствованные из технологических карт или нормативных справочников, достаточно разделить на количество рабочих, имеющихся в распоряжении руководства стройкой для того, чтобы определить общую продолжительность работы, выраженной в днях. Единица времени, используемая в сетевых графиках, должна быть единой для всех видов работ, включенных в сеть.
По продолжительности каждого вида работ определяется общий срок строительства, который после привязки к календарю представляет собой календарный план строительства. Принимая продолжительность выполнения отдельных работ по данным, приведенным на рис. 121, можно найти критический путь по сетке с тем,чтобы определить самый ранний и самый поздний сроки окончания по каждой работе.
Рис. 121. Схема сетевого графика с критическим путем.
Критический путь начинается с первоначального события и идет по сети слева направо до конечного события. При этом самые ранние сроки начала и окончания работ определяются путем суммирования продолжительности всех работ, от которых зависит данная работа, начиная от начального события. Эти данные проставляются в квадратиках, располагаемых возле кружков событий.
Таким образом, расчет сетевого графика сводится к определению резервов времени отдельных работ и по ним - общей продолжительности критического пути.
При небольшом количестве событий указанный расчет не представляет собой сложности. Однако, если учесть, что сетевые графики пусковых комплексов промышленных предприятий обычно охватывают сотни и даже тысячи событий, то для их подсчета требуется значительное время. В таких случаях расчет сетевого графика ведется последовательно с использованием соответствующих формул и таблиц вручную при количестве событий до 500 или с помощью ЭВМ при большем их количестве. Для уяснения методики указанных расчетов можно использовать данные, приведенные на рис. 121.
Если принять буквенные обозначения начального события какой-либо из работ - т, конечного п и конечного события следующей за ней работы - к, то эти работы можно обозначить индексами m - n и n - к.
Ранее было сказано, что все работы, не лежащие на критическом пути, обладают запасами времени, и для них могут быть определены по два срока начала и окончания, соответственно наиболее ранние и наиболее поздние.
Приняв обозначения:
Расчет начинается с определения ранних сроков работ, т. е. с
Раннее начало первых работ 1-2 и 1-3, выходящих из начального события 1, равно нулю, или
т. е. если событие m является начальным, то раннее начало работы m - n будет
Самое раннее начало работы
определяется продолжительностью самого длинного пути от начального события до предшествующего события данной работы.
Например, для работы 7 - 8 раннее начало по цепи 1 - 2 - 7 равно:
Однако по технологической зависимости производства работ следует, что начать работу 7 - 8 до окончания работы 2 - 7 нельзя, поэтому раннее начало работы 7 - 8 следует принять через 9 дней, т. е. работу можно начать на 10-й день.
По аналогии определяем раннее начало для остальных работ:
Раннее начало работы 5 - 9:
Так как работа 5 - 9 не может быть начата дож окончания 7 - 8, следует принять ее начало по расчету цепи 1 - 2 - 7 - 8, т. е. через 14 дней после начала строительства. По этим же причинам раннее начало работы 8 - 9 следует принять по цепи 1 - 2 - 7 - 8, т. е.
Раннее начало работы 9 - 10:
Следует принять
18 дней, так как эта работа не может быть выполнена до окончания работы 7 - 8.
Ранние сроки окончания работ определяются путем добавления к раннему сроку начала работы ее заданной продолжительности по формуле:
Очевидно, что раннее начало последующей работы определяется ранним окончанием предыдущих работ, т. е.
Если данной работе предшествует несколько работ, то ее Тр.н будет максимальной из величин ранних окончаний предыдущих работ:
Равенство является прямым следствием того, что нельзя начать какую-либо работу, если не выполнена предыдущая работа или не выполнен ряд работ, сходящихся в одном событии и имеющих разные сроки их окончания.
Раннее окончание работы
определяется по формуле:
В рассматриваемом примере эти сроки будут:
Как видно из приведенного расчета, раннее начало и окончание определяются для всех работ графика последовательно от начального события. Расчет определения ранних сроков окончания работ все время идет по наибольшим величинам продолжительности работ.
Максимальная величина суммы ранних окончаний технологически связанной цепи работ, завершающаяся конечным событием всего графика (в нашем случае цепи 1 - 2 - 7 - 8 - 9 - 10), определяет продолжительность критического пути и срок строительства. В рассматриваемом примере Пкр = 23 дня.
Самое позднее начало работы, которое не вызовет задержки окончания строительства всего объекта, определяется разностью продолжительности критического пути и самого длинного пути от предшествующего события данной работы до конечного события. ^
Например, для работы 7 - 8 (рис. 121) позднее начало будет равно:
Несколько сложнее определить позднее начало работы 2 - 7 или самое позднее свершение события 2, от которого зависит начало последующих работ 2 - 7, 2 - 8, 2 - 9 и др. К работе 2 - 7 от конечного события 10 до рассматриваемого 2 можно подойти несколькими путями:
путь 1 (10 - 9 - 2) продолжительностью L1 = 5+ 10 = 15 дней;
путь 2 (10 - 9 - 8 - 2) продолжительностью L2 = 5 + 4 + 8 = 17 дней;
путь 3 (10 - 9 - 8 - 7 - 2) продолжительностью L3 = 5 + 4 + 5 + 6 = 20 дней.
Соответственно этим путям поздние сроки начала работы
будут равны:
Очевидно, чтобы не вызвать задержки в выполнении последующей работы и других работ, следует принять минимальное значение
т. е. начать работу 2 - 7 не позднее чем через 3 дня после начала строительства. Если взять больший срок позднего начала работы 2 -- 7, то все последующие работы будут также выполняться позднее, что вызовет в целом задержку в окончании строительства.
Самым поздним окончанием последней работы 9-10 в рассматриваемом сетевом графике явится свершение события 10, срок которого определяется продолжительностью критического пути, т. е. ранним сроком завершения работ, лежащих на пути 1 - 2 - 7 - 8 - 9 -- 10. В нашем случае Пкр = 23 дням и
23 дням, поэтому
или в общем виде
Позднее окончание других работ в рассматриваемой цепи определяют суммой позднего начала и продолжительности данной работы.
Для работы 7 - 8:
Для работы 2 - 7:
В общем виде определить поздний срок выполнения работы можно следующим образом. Позднее начало работ
равно разности позднего окончания
и продолжительности работы m - n, т. е.
Дальнейший анализ сетевого графика ведется путем сопоставления ранних и поздних характерных работ для выявления критического пути и определения резервов времени. Те работы, у которых ранние начала и окончания равны поздним началам и окончаниям, не имеют запаса времени, а следовательно, они лежат на критическом пути. Если это совпадение не установлено, то у рассматриваемых работ имеется определенный резерв времени.
Как указывалось ранее, различают полный резерв времени рассматриваемого пути (цепи), частный и общий резервы времени работы.
Полным резервом времени для данной цепи работ называют разницу во времени между суммарной продолжительностью работ, лежащих на критическом пути, и продолжительностью работ рассматриваемой цепи (пути), т. е.
где Пкр -суммарная продолжительность работ, лежащих на критическом пути;
Пц - то же, лежащая на рассматриваемой цепи.
В нашем примере величина полного резерва между критическим путем 1-2-7-8-9-10, равным 23 дням, и цепью 1-3-4-5-9-10, равной 2+4+3 + 3+5= 17 дням, будет Рпол = 23-17 = 6 дням.
Таким образом, полный резерв Рпол данной цепи (пути) равен сумме частных (свободных) резервов работ, лежащих на ней
В нашем примере:
Полный или общий резерв времени Р° работы m - n определяется как резерв времени у максимального из путей, проходящего через эту работу.
Величина
показывает, на какое время может быть увеличена продолжительность отдельной работы т п, чтобы при этом длина максимального из путей, проходящего через эту работу не превышала длины критического пути.
Общий запас времени определяют разностью позднего и раннего начала времени или позднего и раннего окончания работы.
Например, общий запас времени для работы 7 - 8 составляет
Сводный или частный резерв времени определяет то количество времени, на которое можно перевести начало работы или увеличить ее продолжительность без изменения раннего начала следующих за ней работ.
Такой запас может выявиться в том случае, когда событие является результатом двух или более работ. Он определяется разностью раннего начала последующей работы и раннего окончания данной работы.
Например, частный запас времени для работы 2 - 8 составляет:
В общем виде частный запас времени Рч определяют по формуле:
После окончания расчета сетевого графика легко определить критический путь по видам работ, у которых Р°=0; критический путь включает все работы (стрелки), расположенные последовательно одна за другой, т. е. он обозначает работы, на выполнение которых требуются наибольшие затраты времени.
Понятие критическая работа охватывает как основные строительно-монтажные, так и вспомогательные работы. Например, критической работой может оказаться доставка строительных деталей или технологического оборудования на строительную площадку.
Помимо критического пути, представляет интерес так называемая критическая зона, обусловливающая совокупность работ, имеющих малые резервы времени. Работы критической зоны, не лежащие на критическом пути, могут оказаться в нем даже при небольшом изменении продолжительности некоторых работ. Такие работы называются подкритическими. Различают также резервную зону, совокупность работ которой имеет значительные резервы времени.
Суммируя время, необходимое для выполнения всех работ, расположенных на критическом пути, определяют продолжительность строительства объекта
