Сеть – это ориентированный взвешенный граф без контуров G(X, U, W), |X|= n, |U|=m, |W|=m.
Вес ребра wi³0, wiÎW, i = 1,m .
Имеется только одна вершина без заходящих дуг, называемая источником. Имеется только одна вершина без исходящих дуг, называемая стоком.
Любой взвешенный ориентированный граф без контуров легко превратить в сеть путем введения фиктивных источника и стока и дуг с нулевыми весами.
ами.
Рис.8.1. Преобразование ориентированного
графа в сеть
В сетевом планировании элементы сети имеют свои специфические названия. Сама сеть называется сетевым графиком. Вершины сети называются событиями. Это результаты выполненных работ. Источник называется первоначальным событием и обозначается символом I. Сток называется завершающим событием и обозначается символом С.
Дуги сети называются работами, так как соответствуют некоторым процессам. Каждая работа ограничена двумя событиями: начальным xi и конечным xj (рис.8.2). Вес дуги tij обычно обозначает время, необходимое для ее выполнения.
Рис.8.2. Изображение работы на сетевом графике
Пример сетевого графика показан на рис.8.3.
Рис.8.3. Изображение сетевого графика
Параметры сетевого планирования
Основным параметром сетевого планирования является критический путь Iкр. Это наиболее протяженная по времени цепочка работ, ведущая от исходного события к завершающему.
На рисунке 8.3 критический путь выделен жирными линиями:
Iкр=I-x2-x4-C.
Длиной критического пути Tкр называется суммарное время выполнения работ критического пути.
Tкр=Σtij
На рис.8.3 Tкр=t12+t24+t45=3+8+11=22
Критический путь определяет время реализации всего комплекса работ. Если задержка на работах вне критического пути может не сказаться на выполнении всего объема работ, то любая затяжка работ на критическом пути неизменно скажется на увеличении времени выполнения всей программы работ и приведет к увеличению критического пути Ткр.
Каждое событие сети xiÎX, i=1,…, n характеризуется двумя сроками:
Трi – наиболее ранний из возможных сроков свершения события;
Тпi – наиболее поздний из допустимых сроков свершения события(рис.8.4).
Рис.8.4. Изображение сроков свершения событий
Трi-это срок, необходимый для выполнения всех работ, предшествующих данному событию.
Говоря другими словами, Трi соответствует пути максимальной длины от первоначального события i до данного события xi:
Tpi=t(Lmax(I-xi))
На рис.8.3. легко увидеть, что Тр(x4)=11. Действительно, Тр(x4)=max(t(x1-x2-x4), t(x1-x3-x4)=max(3+8,2+2)=max(11,4)=11.
Ранний срок свершения события имеет ясное содержательное толкование. Будем интерпретировать событие х4 на рис.8.3 как начало сооружения крыши здания, а предыдущие работы как сооружение фундамента и стен. Тогда понятно, что начинать крыть крышу мы можем лишь после того, как закончим все подготовительные работы, то есть через 11 единиц времени.
Тпi –это такой срок свершения события, превышение которого вызовет аналогичную задержку завершающего события С.
Тпi-соответствует разности между длиной критического пути Ткр и пути максимальной длины от данного события хi до завершающего события С:
Тпi=Ткр-t(Lmax(xi-C))
Для события х2 на рис.8.3 Тп(х2)=3. Действительно, Тп(х2)=Ткр-max(t(x2-x1)), t(x2-x4-x5))=22-max(4,8+11)=22-19=3
Ранние и поздние сроки свершения событий для сетевого графика (рис.8.3) приведены на рис.8.5 и представлены в виде одномерных массивов. Индекс массива соответствует номеру события. Очевидно, что при таком представлении события в сети должны быть пронумерованы подряд, начиная от единицы.
Рис.8.5. Сроки совершение событий
Из рис.8.5 следует, что для событий, находящихся на критическом пути, справедливо:
Трi=Тпi
Для событий же не принадлежащих критическому пути, выполняется:
Трi<Tпi
Это означает, что график свершения событий критического пути должен строго соблюдаться, то есть работы на критическом пути должны выполняться точно в срок. Их нельзя сдвигать. Работами же вне критического пути можно маневрировать, сдвигая их начало или окончание в пределах допустимых резервов времени.
Итак, мы подошли к понятию резерва времени, которое характеризует работы сетевого графика. Наибольшее распространение получили понятия полного и свободного резервов времени.
Полный резерв времени Rпij-это максимальное количество времени, на которое можно увеличить продолжительность данной работы tij, не изменяя длины критического пути.
Rпij=Tпj-Tpi-tij
Свободный резерв времени Rcij-это максимальное количество времени, на которое можно увеличить продолжительность данной работы tij, не изменяя ранних сроков начала последующих работ.
Rcij=Tpj-Tpi-tij
Значения Rп и Rc для сетевого графика, изображенного на рис.8.3, приведены на рис.8.6.
Из рисунка видно, что у работ критического пути нет резервов времени. У всех же работ, не принадлежащих критическому пути, имеется полный резерв времени Rп. Например,
Rп(х1-х3)=Тп(х3)-Тр(х1)-t13=9-0-2=7
Это означает, что начало или окончание работы х1-х2 может быть сдвинуто на 7 единиц времени.
Работы xi-xj
Rпij
Rcij
х1-х2
х1-х3
х2-х4
х2-х5
х3-х4
х4-х5
Рис.8.6. Резервы времени
Свободный резерв времени является более жестким резервом, чем полный резерв.
Rc(x1-x3)=Tп(х3)-Тр(х1)-t13=2-0-2=0
Действительно, полный резерв работы х1-х3 определяет, что она должна выполняться в такие сроки, чтобы событие х3 свершилось не позднее, чем через 9 единиц времени. Свободный же резерв времени данной работы свидетельствует о том, что событие х3 должно свершиться точно через 2 единицы времени.
Распространение получили также следующие параметры сетевого планирования.
Ранний срок начала работТрн-самый ранний из возможных сроков начала работы. Он равен продолжительности максимального пути от исходного события С до данного события i
Tpнij=Tpi
Ранний срок окончания работыТрo-это срок окончания работы при условии ее начала в самый ранний из возможных сроков.
Троij=Tpнij+tij
Поздний срок окончания работы Тпн-это предельно допустимый срок окончания работы при условии ее начала в самый ранний период из возможных сроков.
Тпоij=Тпi
Поздний срок начала работы Тпн-это самый поздний срок, в который может быть начата данная работа, без увеличения критического пути
Вес ребра wi³0, wiÎW, i = 1,m .
Изображение сроков свершения событий
