Бесплатная консультация юриста
Круглосуточно
Звоните сейчас!
+7 (499) 322-26-53
Вы здесь:  / Юридические справки / Наиболее позднее время наступления события равно

Наиболее позднее время наступления события равно

Сети или сетевые модели имеют широкое практическое применение. Из всего разнообразия методов и моделей рассмотрим здесь лишь метод критического пути (МКП). Сеть в этом случае – это графическое отображение комплекса работ. Основными элементами сети здесь являются события и работы.
Событие – это момент завершения процесса, отображающий отдельный этап выполнения проекта. Комплекс работ начинается с исходного и заканчивается завершающим событием.
Работа – это протяжённый во времени процесс, необходимый для свершения события и, как правило, требующий затрат ресурсов.
События на сетевом графике обычно изображаются кружками, а работы – дугами, соединяющими события. Событие может свершиться только тогда, когда закончатся все работы, ему предшествующие.
В сетевом графике не должно быть "тупиковых" событий, за исключением завершающего, не должно быть событий, которым не предшествует хотя бы одна работа (кроме исходного), не должно быть замкнутых контуров и петель, а также параллельных работ.
Рассмотрение основных понятий и положений МКП будем вести на основе следующего примера. Пусть задана следующая последова­тельность работ с их временными характеристиками:

Работа1–21–31–42–53–43–64–54–64–7
Длительность10469783104
Работа5–86–76–97–87–107–98–109–10
Длительность5971286911

Построим сетевой график так, чтобы все дуги работы были
направлены слева направо (рис.2). Над дугами проставлены длительности работ.

Рис. 2. Сетевой график примера

Критический путь представляет собой путь от начальной до конечной работы, имеющий наибольшую длительность. Любое замедление в выполнении работ критического пути неизбежно приведёт к срыву выполнения всего комплекса работ, поэтому критическому пути и уделяется столько внимания.
Рассмотрим основные понятия, связанные с критическим путём.
Ранний срок наступления события (ЕТ). Он определяется для каждого события при движении по сети слева направо от начального к конечному событию. Для начального события ЕТ = 0. Для других определяется по формуле, где ЕТ1 – ранний срок наступления события i, предшествующего событию j; tij – продолжительность работы (ij).

Поздний срок наступления события (LТ) – это наиболее позд­ний срок, в который может наступить событие без задержки выполнения всего комплекса работ. Определяется он при движении по сети справа нале­во от конечного события к начальному по формуле:

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

Затем расчёты выполнить в обратном направлении и найти поздние сроки наступления событий.
Положить ЕТ10 = LT10. LT9 = LT10 – t9,10 = 51 –11 = 40.
LT8 = LT10 – t89 = 51 – 9 = 42, и т.д.
Возможен и другой способ вычисления показателей – табличный.
События отмечаются в квадратах "главной" диагонали. Работы отмечаются дважды в верхних и нижних "побочных" квадратах отно­сительно главной диагонали таблицы. В верхних "побочных" квад­ратах таблицы номер строки соответствует предыдущему событию, номер столбца – последующему. В нижних "побочных" квадратах на­оборот.
Порядок заполнения таблицы

1. Сначала заполняются числители верхних и нижних побочных квадратов. В них записываются продолжительности соответствующих работ.
2. Заполняются знаменатели верхних "побочных" квадратов как суммы числителя главного квадрата и числителя верхнего "по­бочного" в той же строке.
3. Числитель первого главного квадрата принимается равным нулю, числители остальных главных квадратов равны максимуму знаменателей верхних "побочных" квадратов в том же столбце.
4. Знаменатель последнего главного квадрата принимается равным числителю этого квадрата. Знаменатели нижних "побочных" квадратов равны разности знаменателя главного и числителя "ниж­него" побочного в той же строке.
5. Знаменатели главных квадратов равны минимуму знаменате­лей "нижних" побочных в том же столбце.
Расчёт показателей сетевого графика

Читать дальше:  Как заставить приставов взыскать долг по алиментам

6. Общие резервы времени работ (разность между знаменателем главного квадрата и знаменателем верхнего "побочного" в том же столбце).
7. Свободные резервы времени работ (разность между числите­лем главного квадрата и знаменателем верхнего "побочного" квадра­та в том же столбце).

Воспроизведём график сети, проставив над каждым событием слева – ранний, а справа – поздний сроки наступления события (рис.3).

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

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

Пусть lj р наиболее ранний возможный срок наступ­ления j-го события, j=0,1, 2, . n, где n+1 число событий (узлов) в сети. Величина tij продолжительность работы, соединяющей два события (узлы) — i-е и j-е.

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

Применяя формулу (1), предлагается запоминать для каждого j значение lj р и номер i(j), на котором достигается максимальное значение. Это позволит по окончании вычислений найти не только величину наиболее длинного пути, но и сам этот путь.

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

Длину критического пути обозначим Ткр. Тогда Ткр=ln р . Узлы, через которые проходит критический путь можно легко получить, исходя из следующего алгоритма :

Конечный узел критического пути всегда имеет номер n,

Если узел с номером j принадлежит критическому пути, то номер предшествующего ему узла равен i(j) (см.формулу (1)),

Начальный узел всегда имеет номер 0.

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

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

Последовательно применяя формулу (1) для j=0,1,2,3,…,8, получаем

l р =0, предшествующего события здесь нет.

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

Следовательно, в данном примере критический путь имеет вид

Наиболее поздний срок наступления события

Наиболее поздним допустимым сроком наступ­ления i-го события является наиболее поздний срок завершения всех работ, идущих к i-му узлу, не влияющий на время завершения всего проекта за Ткр.

Пусть li п ¾ наиболее поздний допустимый срок наступления i-го собы­тия. Чтобы гарантировать, что продолжительность критического пути не бу­дет превышена, необходимо положить ln п =Ткр.

Начиная с n-го события, двигаемся в обратном направлении к событию 0, вычисляя очередное li п при i п =Ткр=36. Затем последовательно применяя формулу (2) для j=8,…,1, получаем

Читать дальше:  Как происходит покупка квартиры за наличный расчет

Отметим, что при правильно проведенных вычислениях всегда должно получиться l п =0.

Исходным шагом для применения метода CPM является описание проекта в виде перечня выполняемых работ с указанием их взаимосвязи. Для описания проекта используются два основных способа: табличный и графический. Рассмотрим следующую таблицу, описывающую проект.

РаботаНепосредственно предшествующая работаВремя выполнения
At A
Bt B
CBt C
DA, Ct D

В первом столбце указаны наименования всех работ проекта. Их четыре: A, B, C, D. Во втором столбце указаны работы, непосредственно предшествующие данной. У работ A и B нет предшествующих. Работе C непосредственно предшествует работа B. Это означает, что работа C может быть начата только после того, как завершится работа B. Работе D непосредственно предшествуют две работы: A и C . Это означает, что работа D может быть начата только после того, как завершатся работы A и C . В третьем столбце таблицы для каждой работы указано время ее выполнения. На основе этой таблицы может быть построено следующее графическое описание проекта.

На рисунке проект представлен в виде графа с вершинами 1, 2, 3, 4 и дугами A, B, C, D. Каждая вершина графа отображает событие. Событие 1 означает начало выполнения проекта. Иногда такое событие обозначают буквой S ( start ). Событие 4 означает завершение проекта. Для обозначения такого события иногда используется буква F ( finish ). Любая работа проекта – это упорядоченная пара двух событий. Например, работа A есть упорядоченная пара событий (1, 3 ). Работа D — упорядоченная пара событий (3,4). Событие проекта состоит в том, что завершены все работы, "входящие" в соответствующую вершину. Например, событие 3 состоит в том, что завершены работы A и C.

Рассмотрим другой проект, представленный следующей таблицей.

РаботаНепосредственно предшествующая работаВремя выполнения
At A
Bt B
CBt C
DA, Ct D
ECt E
FCt F
GD, E, Ft G

Графическое описание проекта, построенное по этой таблице, имеет следующий вид.

В этом графическом описании проекта кроме тех работ, которые указаны в таблице, использованы две "фиктивные" работы (3,4) и (5,6). На рисунке эти работы показаны пунктиром. Эти работы не требуют времени на их выполнение и используются в графическом представлении проекта лишь для того, чтобы правильно отобразить взаимосвязь между работами.

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

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

Длина пути – суммарная продолжительность выполнения всех работ пути.

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

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

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

Пусть i и j — вершины или события проекта, (i,j) — работа проекта, s — событие "начало проекта" ( start )., f — событие "окончание проекта" ( finish ), T — длина критического пути.

Читать дальше:  Когда будут сносить дома по программе реновации

Введем следующие обозначения:

t ( i , j ) — время выполнения работы (i,j),

ES ( i , j ) — наиболее раннее время начала работы (i,j) ,

EF ( i , j ) — наиболее раннее время окончания работы (i,j) ,

LS ( i , j ) — наиболее позднее время начала работы(i,j) ,

LF ( i , j ) наиболее позднее время окончания работы (i,j) ,

E i — наиболее раннее время наступления события i ,

L i — наиболее позднее время наступления события i.

R ( i , j ) — полный резерв времени на выполнение работы (i,j) (время, на которое может быть отложена работа (i,j) без увеличения продолжительности выполнения всего проекта).

r ( i , j ) — свободный резерв времени на выполнение работы (i,j) , (время, на которое может быть отложена работа (i,j) без увеличения наиболее раннего времени E j наступления последующего события j).

Если (i,j) — работа проекта, то имеют место соотношения:

для любого j : ES ( i , j ) = E i ;

для любого i : LF ( i , j ) = L j .

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

наиболее раннее время начала работы ES ( i , j ) ,

наиболее раннее время окончания работы EF ( i , j ) ,

наиболее позднее время начала работы LS ( i , j ) ,

наиболее позднее время окончания работы LF ( i , j ) .

Метод CPM описывается следующими соотношениями.

1. ES ( s , j ) = 0 для любой работы ( s ,j), выходящей из стартовой вершины s проекта.

2. EF ( i , j ) = ES ( i , j ) + t ( i , j ) = E i + t ( i , j ) : наиболее раннее время окончания любой работы (i,j) превышает наиболее раннее время начала этой работы (время наступления предшествующего события i) на время ее выполнения.

3. ES ( q , j ) = max i EF ( i , q ) = E q : наиболее раннее время начала работы (q,i) равно наибольшему из значений наиболее раннего времени окончания непосредственно предшествующих ей работ.

4. T = E f = max i EF ( i , f ) : длина критического пути равна наиболее раннему времени завершения проекта.

5. LF ( i , f ) = T: наиболее позднее время окончания любой работы, завершающей проект, равно длине критического пути.

6. LS ( i , j ) = LF ( i , j ) — t ( i , j ) = L j — t ( i , j ) : наиболее позднее время начала любой работы меньше наиболее позднего времени окончания этой работы (времени наступления последующего события) на время ее выполнения.

7. LF ( i,q) = min j LS ( q , j ) = L q : наиболее позднее время окончания работы (i,q) равно наименьшему из значений наиболее позднего времени начала непосредственно следующих за ней работ.

8. R ( i , j ) = LS ( i , j ) — ES ( i , j ) = LF ( i , j ) — EF ( i , j ) = L j — t ( i , j ) — L i : полный резерв времени выполнения любой работы равен разности между наиболее поздним и наиболее ранним временем ее начала или разности между наиболее поздним и наиболее ранним временем ее окончания.

9. r ( i , j ) = L j — ES ( i , j ) — t ( i , j ) = L j — EF ( i , j ) = L j — E i — t ( i , j ) : свободный резерв времени выполнения любой работы равен разности между наиболее поздним временем наступления последующего события и наиболее ранним временем окончания работы.

Из приведенных выше определений и соотношений непосредственно следует:

1) Длина критического пути равна T.

2) Если R ( i , j ) = 0, то работа (i,j) лежит на критическом пути; если R ( i , j ) і 0, то работа (i,j) не лежит на критическом пути.

3) Если время начала работы (i,j), которая не лежит на критическом пути, отложить на срок меньший, чем r ( i , j ) , то наиболее раннее время наступления последующего события не изменится.

4) Если время начала работы (i,j), которая не лежит на критическом пути, отложить на срок меньший, чем R ( i , j ) , то время, необходимое на выполнение всего проекта, не увеличится.

Добавить комментарий

Your email address will not be published. Required fields are marked ( Обязательно )

Adblock detector