Расчет характеристик сетевых моделей

Основные определения и этапы сетевого планирования

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

Анализ сетевой модели, представленной в графической или табличной (матричной) форме, позволяет:

• более четко выявить взаимосвязи этапов реализации проекта и,

• опре­делить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ.

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

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

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

• Основные понятия сетевой модели:

• работа

• событие,

• путь.

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

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

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

При графическом распределении работа изображается стрелкой, которая соединяет два события. Она обозначается парой заключеных в скобки чисел (i,j), где i — номер события, из которого работа выходит, а j — номер события, в которое она входит. Работа не может начаться раньше, чем свершится событие, из которого она выходит. Каждая работа имеет определенную продолжительность t(i,j). Например, запись t(2, 5) = 9 означает, что работа (2, 5) имеет продолжительность девять единиц времени (см. рис. 19.1). К работам относятся также такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой и не может выполняться, прежде чем дан­ная работа будет завершена. Такие работы называются фиктивными и на графике изображаются пунктирными стрелками.

Событияминазываются результаты выполнения одной или нескольких работ.

События не имеют протяженности во времени. Событие свершается в тот момент, когда оканчивается последняя из работ, входящая в него. Событие обозначается одним числом и при графическом представлении сетевой модели изображается кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i = 1, 2,., N).

В сетевых моделях имеется начальное событие (с номером 1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.

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

В приведенной на рис. 19.1 модели путями являются L1 = (1, 2, 5), L2 = (1, 4, 5) и др. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим и обозначают LKp, а его продолжительность — tKp.

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

Их несвоевременное выполнение ведет к срыву всего комплекса работ.

Расчет характеристик сетевых моделей

Для событий рассчитываюттри основные характеристики:

• ранний и

• поздний сроки свершения события, а также его резерв.

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

tp(0) = 0,

tp(j) = max{tp(i) + t(i,j)}; ,/ = 1,N (5.37)

характеризует самый ранний срок завершения всех путей, в него входящих.

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

• tn(i)= min {tn(j))-t(i,j)}; i=2,N-1 (5.38)

J

характеризует самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей, следующих за этим событием. Данный показатель определяется «обратным ходом», начиная с завершающего события, с учетом соотношения tn(N) = tp(N).

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

• ранний срок начала — tрн(i,j) = tр(,i); (5.40)

• ранний срок окончания — tpo(i,j) = tp(i) + t(i,j), (5.41)

• поздний срок окончания — t по(i,j) = tп(j); (5.42)

• поздний срок начала — t пн (i,j)= tп(j)-t(i,j) (5.43)

• полный резерв времени- Rп(i,j) = t п (i,j) – t р (i) – t(i,j) (5-44)

• независимый резерв времени - RH(i,j) =max{0;tр(i)–tп(i)-/(i,j)}, (5.45)

• или RH(i, j) = max {0; Rn(i, j) ~ R(i) - R(j)} (5.46)

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

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

Все события, за исключением событий, принадлежащих критическому пути, имеют резерв времени R(i): R(i) = tn(i) - tp(i). (5.39)

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

Путьхарактеризуется двумя показателями:

• продолжительностью и

• резервом.

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

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