Учебное пособие 985

Таблица 3.2

Матрица смежности

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

Работу в сетевых графиках принято кодировать парой (i, j) , где i - номер начального, а j - номер конечного события (рис. 3.5). Так как

51

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

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

Пусть весь комплекс работ изображен в виде пронумерованного сетевого графика и известна продолжительность tij каждой работы. Естественно, возникает вопрос: какова минимальная продолжительность всего

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

всех работ, лежащих на этом пути. Обычно на сети существует несколько полных путей различной продолжительности. Минимальная продолжительность всех работ равна сумме продолжительностей работ, взятых вдоль самого длительного по времени полного пути. Такой путь называется критическим ( Lкр ), а его продолжительность называется критическим временем tкр . Таким образом, путь сетевого графика, имеющий наибольшую длину, называется критическим. В сети может быть несколько критических путей, имеющих одинаковую длину. Критический путь имеет особое значение в системе сетевого планирования, так как работы этого пути определяют общий цикл завершения всего комплекса работ, планируемых при помощи сетевого графика. Критическое время - это минимальное количество времени, необходимое для выполнения всего комплекса работ.

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

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

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

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

52

свершения. В связи с этим различают ранний и поздний сроки свершения события.

Ранний срок t р ( j) свершения события j равен минимальному сро-

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

где максимум распространяется на все события i , непосредственно предшествующие событию j . Для вычисления по формуле (3.1) надо по входящим стрелкам определить все события, непосредственно предшествующие данному, подсчитать для каждого предшествующего события сумму (t р (i) + tij ) и выбрать максимальную из полученных сумм. При расчете для исходного события принимают, что ранний срок свершения равен 0.

Определение ранних сроков свершения событий следует вести по формуле (3.1) последовательно от исходного события к завершающему. При этом около каждого вычисленного значения t р ( j) записываются номера тех из предшествующих событий, для которых в формуле (3.1) был достигнут максимум. Эти помеченные события используются при отыскании критического пути, а именно, двигаясь по ним от завершающего события к исходному, будет построен критический путь. Для каждой работы (i, j) , лежащей на критическом пути, очевидно, выполняется условие: t р ( j) = t р (i) + tij . Ранний срок свершения завершающего события опреде- ляет продолжительность критического пути tкр .

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

Поздний срок tп (i) свершения события i равен разности между про-

должительностью критического пути tкр и продолжительностью самого

дующие за событием i . Для вычисления по формуле (3.2) надо по стрелкам, выходящим из события i , определить все события, непосредственно следующие за данными, подсчитать для каждого из них разность tп ( j) − tij и выбрать минимальную из полученных разностей. При расчете принимают поздний срок свершения завершающего события равным раннему сроку, то есть критическому времени выполнения проекта.

53

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

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

иправый для вычисляемого позднего срока свершения события tп (i) .

Вкачестве примера вычислим временные параметры событий для сетевого графика, представленного на рис. 3.4. Результаты вычислений,

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

события 1, 4, 5, 7. На рис. 3.6 критический путь выделен двойными стрел-

ками.

2

Рис. 3.6

3.5. Моменты начала и окончания работ. Резервы времени

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

Ранний срок начала работы равен раннему сроку свершения ее начального события:

54

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

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

Полный резерв времени равен разности между поздним и ранним сроками начала (или окончания) работы, а с учетом соотношений (3.3)- (3.6) полный резерв равен разности между поздним сроком свершения конечного события работы и ранним сроком окончания этой работы:

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

которого войдет эта работа.

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

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

55

3.6. Табличный метод расчета временных параметров сетевой модели

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

Алгоритм табличного метода расчета состоит из семи пунктов при заполнении таблицы 3.3.

Таблица 3.3

Табличный метод расчета

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

2.В графу 2 записываются значения продолжительностей работ.

3.Графы 3 и 5 заполняются совместно по следующим правилам:

а) в графу 3 для всех работ, начинающихся в исходном событии, записывается срок раннего начала, равный нулю: t рн (0, j) = 0 . В графу 5 всех работ, начинающихся в исходном событии, записывается срок раннего окончания, равный продолжительности работы: t ро (0, j) = t0 j ;

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

t рн (i, j) = max t ро (k, i) ,

k

которые отыскиваются в расположенных выше строках графы 5. Полученное значение срока раннего начала работы записывается в графу 3;

56

в) срок раннего окончания работы равен сумме срока ее раннего начала и продолжительности:

t ро (i, j) = t рн (i) + tij ,

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

все строки граф 3 и 5.

4. Графы 4 и 6 заполняются совместно по следующим правилам:

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

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

tпо (i, j) = min tпн ( j, k ) ,

k

которые отыскиваются в расположенных ниже строках графы 4. Полученное значение срока позднего окончания работы записывается в графу 6;

в) срок позднего начала работы равен разности между сроком ее позднего окончания и продолжительностью:

tпн (i, j) = tпо (i, j) − tij ,

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

все строки граф 4 и 6.

5.Полный резерв времени работы определяется как разность между сроками ее позднего и раннего начала (или окончания). В графу 7 записывается разность чисел, содержащихся в графах 4 и 3 (или 6 и 5).

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

7.Из графы 7 выписываются все работы, для которых полный резерв времени равен нулю. Последовательность этих работ есть критический путь. Из таблицы 3.3 следует, что критический путь образуют работы (0,1), (1,4), (4,5), (5,7).

3.7. Линейная карта сети

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

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

грамму) сети.

57

Линейная карта может быть построена по ранним и поздним срокам свершения событий. При построении линейной карты по ранним срокам момент наступления исходного события считается равным нулю, т.е. все отрезки (0, j) откладываются от оси ординат. Отрезок (i, j) откладывается так, чтобы его начало лежало на одной вертикали с самым правым концом всех отрезков-работ, заканчивающихся событием i . Тем самым, начало каждой работы (i, j) соответствует раннему сроку t р (i) наступления события j . Линейная карта, построенная для сетевого графика рис. 3.4, приведена на рис. 3.7. На ней сплошными линиями показаны отрезки-работы, построенные по ранним срокам свершения событий.

По линейной карте можно определить критическое время, критический путь, а также резервы времени всех работ. Критическое время равно координате по оси времени самого правого конца всех отрезков линейной карты. В нашем случае критическое время ( tкр ) равно 13. Критический путь можно найти следующим образом. Находится отрезок, правый конец которого расположен на вертикали критического времени t = tкр , это будет работа (5,7). Затем находится отрезок, правый конец которого расположен на одной вертикали с левым концом работы (5,7), - это работа (4,5). После этого находится работа (1,4), и, наконец, работа (0,1), начинающаяся в момент времени t = 0 . Выделенные отрезки-работы образуют критический путь. Если критических путей несколько, то указанный способ позволяет найти все критические пути.

Свободный резерв времени Rс (i, j) работы (i, j) на линейной карте определяется как наибольшее расстояние, на которое можно сдвинуть вправо отрезок (i, j) , не сдвигая ни одного отрезка с началом j , т.е. не изменяя начала t р ( j) работ, выходящих из события j . На рис. 3.7 свободный резерв, например, работы (3,6) равен 4, так как отрезок (3,6) можно сдвинуть вправо на 4, не сдвигая отрезка (6,7). Работа же (4,6) не имеет свободного резерва, так как любой сдвиг вправо отрезка (4,6) возможен лишь при таком же сдвиге отрезка (6,7).

Линейная карта сети строится с целью анализа сетевой модели и определения возможности оптимизации хода выполнения работ. По линейной карте можно узнать, например, как распределены материальные или трудовые ресурсы в каждый момент времени. Допустим, что каждую работу выполняет один человек, при этом он может выполнять любую работу. Из рис.3.7 видно, что в промежутке времени 5 ≤ t ≤ 6 выполняется три работы (1,4), (3,4), (3,6), и, значит, в течение того времени будет занято три человека, а в промежутке 6 ≤ t ≤ 7 выполняется только одна работа (1,4), и необходим один человек. Однако, если сдвинуть работу (3,4) вправо на единицу (величина ее свободного резерва времени), то во всем промежутке 5 ≤ t ≤ 7 будет выполняться две работы, и будет занято два человека. По сетевому графику такие взаимосвязи обнаружить значительно труднее.

58

Рис. 3.7

Задачи и упражнения

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

59

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

60