2. 1.2. Параметры сетевой модели с учетом временных характеристик

Исходная информация для модели включает сеть, продолжи­тельности t_ijвсех работ (i, j), момент начала выполнения комп­лексаТ₀, а также может содержать (но не обязательно) дирек­тивный срок Т_дирнаступления завершающего события. Продол­жительности работ задаются как детерминированные неотрица­тельные величины.

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

Важнейшим параметром является критическое время T_кр – ми­нимальное время, за которое может быть выполнен весь комплекс. Критическому времени соответствует критический путьL_кр, то есть полный путь, продолжительность которого и составляет критиче­ское время:t(L_кр)=Т_кр. Очевидно, что продолжительность лю­бого другого полного пути равна или меньше критического време­ниТ_кр, поэтому критический путь можно определить как путь, имеющий максимальную продолжительность.

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

В плане выполнения всего комплекса, естественно, должны быть определены моменты наступления всех событий, начала и окончания работ. Как правило, эти моменты устанавливаются не однозначно, а располагаются в некотором диапазоне. При анализе сетевой модели определяются параметры, ограничивающие эти диапазоны. Такими параметрами для каждого k-го события яв­ляются ранний срок наступления события и поздний срок на­ступления события .Используя эти параметры, можно вычис­лить и другие параметры, в том числе критическое времяT_кри критический путьL_кр, на основании которых составляется план выполнения комплекса. Поэтому начнем с рассмотрения парамет­ров и .

Предварительно заметим, что все временные параметры сетевой модели можно определять как календарные (при этом момент на­чала выполнения комплекса Т₀должен быть задан календарной датой) и как относительные (при этом принимаютТ₀=0). В после­дующем изложении принятоТ₀==0.

Рис. 1.3. Сетевая модель

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

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

(1.5)

где нулем обозначен номер исходного события.

Например, к событию 7 (рис.1.3) ведут три пути: 0–1–3–6–7, продолжительность которого равна 105 единицам времени;

0–1–2–5–7 с продолжительностью 60 ед. и 0–2–5–7 с продол­жительностью 85 ед. Очевидно, что событие 7 может наступить не раньше, чем через 105 ед. времени после исходного события, поэтому ед.

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

(1.6)

где N – номер завершающего события, причем= 0.

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

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

(1.7)

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

. (1.8)

Например, от события 6 (рис. 1.3) к завершающему событию ведут два пути: 6–7–8–9–10 с продолжительностью 195 ед. и 6–8–9–10, продолжительность которого равна 200 ед. Согласно формуле (1.8) . Очевидно, что если событие 6 наступит в момент(тo есть позднее), а на выполнение работ, составляющих путь 6–8–9–10, требует­ся 200 ед., то в результате завершающее событие наступит в мо­мент, превышающийТ_кр на столько, на сколькобольше. Действительно, вычислим поздний срок наступления события 6 как разность между Т_кр и продолжительностью первого пути:= Т_кр–195 = 305–195 = 110 ед. С этого момента требуется еще 200 ед. времени на выполнение работ второго пути, следовательно, завершающее событие наступит через 110+200=310 ед. после на­чала работ, то естьT_кр будет превышено на 5 ед.

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

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

= T_кр. (1.9)

Напишем формулу для вычисления .Обозначим черезмножество дуг (i,j), выходящих изi-й вершины, и допустим, что все значениядляj-х событий, которыми заканчивается каждая из дуг, уже вычислены. Тогда на основании формул (1.8) и (1.9) можно написать

(1.10)

где .

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

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

• ранний срок начала

• ранний срок окончания ,

• поздний срок начала ,

• поздний срок окончания .

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

; (1.11)

. (1.12)

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

; (1.13)

. (1.14)

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

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

, (1.15)

где k –номер события.

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

Для работ можно рассматривать различные виды резервов, из которых наиболее важными являются:

– полный резерв

, (1.16)

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

– свободный резерв

, (1.17)

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

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

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

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

Множество всех критических и подкритических работ называют критической зоной комплекса.