Сетевые модели

Размещено на http://www.allbest.ru/

Сетевые модели

Сетевая модель и её элементы

Сеть - ориентированный граф, в котором существует лишь одна вершина, не имеющая входящих дуг, и лишь одна вершина, не имеющая выходящих дуг.

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

Понятие «работа» имеет следующие значения:

«действительная работа» - процесс, требующий затрат времени и ресурсов;

«фиктивная работа» - логическая связь между или несколькими работами, указывающая на то, что начало одной работы зависит от результатов другой. Фиктивная работа не требует затрат времени и ресурсов, продолжительность ее равна нулю.

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

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

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

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

На сетевой модели событиями соответствуют вершины графа.

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

Полный путь - путь от исходного события до завершающего.

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

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

Пусть информация о комплексе работ задана табл. 1.1, в которой работы условно обозначены символами а1, a2, . . . . Из таблицы видно, что работы а1, а5, а6 не имеют предшествующих, поэтому в сетевой модели дуги, соответствующие этим работам, будут выходить из исходного события комплекса. Работы а12, a13, a14 не предшествуют никаким другим работам, и поэтому дуги, соответствующие этим работам, будут входить в завершающее событие комплекса. Конечное событие работы а1 является начальным событием для работ a2, a2, a2; конечное событие для работы a2 является начальным для работы a14 и так далее Сетевой график комплекса изображен на рис. 1.1.

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

Таблица 1.1

Рис. 1.1 Сетевой график

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

Легко видеть, что событие любого ранга связано с событием предшествующего ранга одной дугой. Следовательно, событие k-го ранга обязательно связано с исходным событием путем, состоящим из k дуг; хотя, кроме того, событие k-го ранга может быть соединено с исходным событием и путем, состоящим из меньшего числа дуг. Так, например, событие 6 на сетевом графике рис. 1.1 связано с исходным событием тремя путями: 1) путем, состоящим из дуг (0, 1), (1, 6); 2) путем, состоящим из дуг (0, 3), (3, 4), (4, 6) и 3) путем, состоящим из дуг (0, 1), (1, 3), (3, 4), (4, 6). Ранг события 6 равен 4, так как последний путь содержит максимальное число дуг, равное 4.

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

После распределения всех событий по рангам нумерация осуществляется следующим образом. Исходное событие нулевого ранга получает номер 0. Событиям первого ранга в произвольном порядке присваивают номера 1, 2, . . ., n1, где п1 - число событий первого ранга; события второго ранга получают номера n1+1, n1+2, . . ., n1+ n2 где п2 - число событий второго ранга, и так далее.

Так как события одного ранга между собой не соединены, а события меньшего ранга имеют меньший номер, то для любой дуги (i, j) всегда i < j.

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

Заметим, что нумерация событий, при которой для любой дуги (i, j) всегда i < j обязательна при машинных методах расчета параметров сетевых моделей.

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

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

Модели второго типа относятся к задачам распределения ресурсов. Эти задачи являются оптимизационными и встречаются в разных постановках. В зависимости от принятого критерия оптимальности и характера ограничений их можно разбить на две основные группы:

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

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

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

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

Продолжительность работы (i, j) обозначают через tij. Оценка величины tij может производиться:

- по действующим нормативам;

- по накопленным данным с достаточно высоким процентом повторяемости работ;

- методом экспертных оценок;

- на основе вероятностных оценок.

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

В системах СПУ используются три вероятностные оценки:

aij - минимальное время, необходимое для выполнения работы при наиболее благоприятных условиях;

bij - максимальное время, необходимое для выполнения работы при наименее благоприятных условиях;

mij - наиболее вероятное время выполнения работы при нормальных, наиболее часто встречающихся условиях.

Все эти оценки даются ответственными исполнителями или экспертами.

Величины aij, bij и mij используются для вычисления ожидаемого значения продолжительности работы , представляющего собой математическое ожидание случайной величины tij, и дисперсии Dij. Полученные значения и Dij являются характеристиками случайной величины tij, распределенной по закону бета- распределения. Кривая бета- распределения изображена на рис.1.2

Рис. 1.2

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

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

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

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

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

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

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

- объединять в одну работу следует только такие группы работ, которые закреплены за одним ответственным исполнителем.

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

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

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

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

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

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

Предварительно заметим, что все временные параметры сетевой модели можно определять как календарные (при этом момент начала выполнения комплекса Т0 должен быть задан календарной датой) и как относительные (при этом принимают Т0=0). В последующем изложении принято Т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)

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

;(1.13)

.(1.14)

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

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

,(1.15)

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

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

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

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

,(1.16)

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

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

,(1.17)

параметр сетевая модель метод вычисление

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

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

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

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

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

Метод вычислений на сетевой модели

Для расчета параметров сетевых моделей применяют следующие три метода:

метод вычислений непосредственно на сетевом графике;

матричный метод;

табличный метод.

Рассмотрим метод вычислений непосредственно на сетевом графике.

Предварительно каждый кружок, изображающий вершину графика (событие), делится на четыре сектора: в верхний сектор записывается номер события k, в левый - значение Тk(p), в правый - Tk(n), а в нижний - Rk = Tk(n) -Тk(p) (рис. 2.1).

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

Обратимся к рис. 2.1, на котором изображена та же сетевая модель, что и на рис. 1.3. В левый сектор исходящего события сразу записывается значение T0(p) = 0. Далее находим: к событию 1 подходит одна дуга (0, 1), поэтому T1(p) = 0+20 = 20; к событию 2 подходят две дуги (0, 2) и (1, 2), поэтому T2(p) = max{0+45; 20+0}=45, и так далее Каждое вычисленное значение Tk(p)сразу записывается в соответствующий сектор.

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

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

Для нашего сетевого графика имеем T10(n) = T10(p) =305. Далее находим: из событий 9, 8, 7 выходит по одной дуге, поэтому T9(n) = 305-100 =205; T8(n) =205-90=115; T7(n) =115-5=110;

из события 6 выходят две дуги (6, 7) и (6, 8), поэтому T6(n) = min{110-0; 115-10} =105 и так далее.

После того, как рассчитаны все значения Tk(n) вычисляют резервы времени событий как разности между величинами, записанными в левых и правых секторах, и записывают их в нижние секторы. Остальные параметры сетевой модели вычисляют, по формулам (1.11)-(1.17).

Критический путь проходит через события, для которых Rj=0 (0-3-6-8-9-10).

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

Размещено на Allbest.ru