Сетевое планирование в условиях неопределенности. Анализ и оптимизация сетевого графика

tр(j)=max  tр(j) +(i,j);  j=2,N

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

tn (i) = min { tn (i) - t(i,j); j=2,N-1

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

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

R(i)= tn (i) - tp (i)

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

          Ранний срок начала              — tpn(i,j) = p(i),

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

Поздний срок окончания               — tno(U)=tn(j)

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

Полный резерв времени               —Rn(i,j) = tn(j) - tp(i) - t(i,j), Независимый резерв               — Rн(i,j)=max0;tp(j)–tn(i) - t(i,j)=

= max {0; Rn(i,j)-R(i)-R(j)}.

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

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

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

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

Перечисленные выше характеристики СМ могут быть получены на основе приведенных аналитических формул, а процесс вычислений отображен непосредственно на графике, либо в матрице (размерности N*N), либо в таблице.

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

KH=(i,j)=t(Lmax)-tkp  /tkp - tkp`= 1- Rn - Rn (i,j)/ tkp - tkp`

где t(L max) — продолжительность максимального пути, проходящего через работу (i,j);

tkp`— продолжительность отрезка рассматриваемого пути, совпадающего с критическим путем.

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

•   напряженные (KH(i,j) > 0,8);

•   под критические (0,6 < KH(i,j) < 0,8);             

•   резервные ( KH (i,j) < 0,6).

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

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

Таблица 1.

Соответствие между коэффициентов напряженности и уровнем, на котором контролируется работа.

1.3. Составление сетевого плана по таблице работ

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

              События нумеруются и изображаются кружками (рис. 3) На начальном этапе положение событий на графике произвольное.

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

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

В системе не должно быть замкнутых контуров (циклов) (рис. 3, a).

Происходит индексация работ от исходного до завершающего события. Между двумя событиями не должно быть 2-х или более работ (рис.3, b).

Если по логике проекта это случается, необходимо «расшивать» работы фиктивными связями. Провисающие события и работы не должны присутствовать на графике (см. рис.3, c).

Желательно избегать пересечения работ (рис.3, d).

2

Рис. 3.

Недопустимые элементы сетевого графика: a) Циклы, b) «Удвоенная» работа c) Провисающие события и работы d) Пересечения работ

2

В алгебре такой сетевой график называется ориентированным графом.

Далее производится расчет полученного сетевого графика (предварительно построенного на бумаге.) При расчете необходимо определить параметры:

Наиболее ранние из возможных и наиболее поздние из времен начальной работы.

Критический путь (с Rij=0).

Резервы времени (общий и частный) работ, не лежащих на критическом пути.

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

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

1.4. Оптимизация сетевого плана и нахождение коэффициентов

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

1.      По возможности максимально «распараллелить» все работы. Они должны, если позволяют ресурсы, идти не зависимо друг от друга.

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

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

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

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

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

1.      Составление интеллект-карты для написания произведения либо уточнения целевой функции;

2.      Написание плана-содержания основных моментов исследования или «конечного» документа;

3.      Составление текста по имеющимся плану и тезисам;

4.      Набор текста;

5.      Корректура текста;

6.      Подбор иллюстраций;

7.      Верстка текста.

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

1.5. Критический путь и другие параметры сетевого графика

              При обработке сетевых графиков существенное влияние на объем вычислительных работ оказывает порядок просмотра (нумерация) событий. Правило оптимальной нумерации связано с определением ранга событий.

              Начальному событию (входу) сопоставляется ранг 0. Ранг 1 получают события, в которые приводят работы, начинающиеся только в событиях ранга 0. Ранг 2 получают события, в которые приводят работы, начинающиеся только в событиях ранга 0 и 1 и т.д.

              Последующая нумерация ведется в соответствии с рангами по возрастанию номеров (при одинаковом ранге порядок произволен; нумерация не обязательно сплошная).

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

              Пусть для определенности начальное событие имеет номер 0 и конечное - номер N. Обозначим через Lj длину пути наибольшей протяженности от события 0 до события j.

По известному принципу оптимальности Р.Беллмана

Lj=max(ij)[Li+Tj] , j>0; L0=0

Величина Lj соответствует наиболее раннему возможному времени Tj0 наступления j-го события, т.е. самому раннему сроку завершения всех работ, предшествующих этому событию. Значение LN cоответствует критическому времени выполнения проекта Tкрит.

              Обозначим через Mi длину пути наибольшей протяженности от события i до события N. Тогда по тому же принципу

Mi=max(ik)[Tik+Mk] , i<N; LN=0

              Величина Ti1 = Tкрит - Mi соответствует наиболее позднему допустимому времени наступления i - го события, т.е. самому позднему сроку начала всех работ, последующих за этим событием. Совершенно очевидно, что для событий на критическом пути самое раннее и самое позднее времена их наступления будут совпадать.

Рассмотрим сетевой график (рис. 4)

              5              4

              2              2              6              2

              5              7

              1              2              6

              4

              7