Сетевое планирование

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

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

на длительность выполнения всего проекта [8].

Наиболее  ранний возможный срок появления  события

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

T_j(E) – наиболее ранний возможный срок наступление j-ого события,

j = 1, 2, …, n, где n – число событий (узлов) в сети.

d_ij – длительность процесса j и i.

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

Допустим, что  от начального события (события 1) к j-му событию ведут r путей. Обозначим эти пути П₁,  П₂,…,П_r. Каждому пути соответствует некоторая мера, равная сумме продолжительности всех работ на данном пути. Следовательно,

 

                 (2.1)

 

Таким образом, самый длинный путь от начального узла (узел 1) до j-ого узла определяется как:

 

                               (2.2)

 

где максимум берется  по всем путям, соединяющим узлы 1 и j .

Удобно принять T₁(E)=0 (самый длинный путь к первому узлу равен нулю). Рассмотрим теперь все работы, ведущие к последующему событию. Вычисляем для каждой такой работы время, равное наиболее раннему возможному сроку наступления предыдущего события плюс продолжительность работы. Поскольку последующее событие не может появиться до завершения всех предшествующих работ, наиболее ранний возможный срок наступления рассматриваемого события равен максимуму этих двух различных промежутков времени. Иными словами, самый ранний возможный срок наступления j-го события определяется как:

 

                          (2.3)

 

где максимум берется по всем работам, завершающимся в j-м узле и выходящим из любого предшествующего j-го узла. Для сети с событиями, j=1, 2, …, n , вычисления продолжаются до тех пор, пока не будет определен наиболее ранний возможный срок наступления завершающего n-го события [9].

Пример 1. Рассмотрим построение сетевой модели, изображающей соотношение между работами, при сборке крупного станка (таблица 1). 

Таблица 1

Изготовление  крупного станка

Работа		Продолжительность	Непосредственно предшествующая  работа
Обозначение	Описание
A	Закупка деталей  для узла 1	5	–
B	Закупка деталей для узла 2	3	–
C	Закупка деталей  для узла 3	10	–
D	Изготовление  узла 1	7	A
E	Изготовление  узла 2	10	B
F	Изготовление  узла 4	5	D, E
G	Изготовление  узла 3	9	B, C
H	Окончательная сборка	4	F,G
I	Окончательная проверка и испытания	2	H

 

Построим сетевой график описанного выше проекта (рисунок 7):

 

             

Рисунок 7.Пример сети в виде модели узел-событие.

 

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

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

Начиная с n-го события, движемся в обратном направлении через каждое предшествующее событие. Чтобы гарантировать, что продолжительность критического (самого длинного) пути не будет превышена, необходимо начинать процедуру с приравнивание наиболее позднего допустимого срока наступления завершающего события наиболее раннему возможному сроку завершения проекта. Следовательно, T_n(L)=T_n(E)

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

 

              

                                    (2.4)

 

Минимум берется  по всем j-м событиям, соединенным с i-м событием работой (i, j). Вычисления ведутся до тех пор, пока не будет определен наиболее поздний срок наступления начального события (событие 1) [9].

Возвращаясь к  первому примеру, выполняем следующие  вычисления:

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

 

Отсюда следует, что

 

                                    (2.5)

 

где EF_ij – наиболее ранний возможный срок окончания работы (i, j).

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

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

 

                                           (2.6)

 

Резерв  времени 

Максимальное  время, на которое можно задержать  наступление некоторого события  без соответствующей задержки срока  завершения всего проекта, называется резервом времени для данного  события. Пусть S_i – резерв времени для i-го события. Тогда

 

                                       (2.7)

 

Если наиболее поздний допустимый и наиболее ранний возможный сроки наступления  события одинаковы (S_i = 0), то задержка наступления события не допускается. События с нулевым резервом времени находятся на критическом пути.

Резерв времени  является показателем гибкости планирования сроков в сетевой модели.

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

Вычисление  резерва времени 

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

 

    или                          (2.8)

 

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

 

                                            (2.9)

 

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

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

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

 

                                  (2.10)

 

Гарантированный резерв времени, SF_ij – максимальная возможная задержка работы, не влияющая на окончательный срок завершения проекта, если предшествующие работы выполняются с запаздыванием. Этот показатель резерва времени оказывается одним из наиболее удобных при планировании сроков выполнения определенной работы. Заметим, что он допускает задержку только последующих работ , а не всего проекта [9].

 

   или             (2.11)

 

 

2.3 Метод имитационного  моделирования (метод Монте-Карло)

 

Метод Монте-Карло – это численный метод решения математических задач при помощи моделирования случайных величин. Создателями этого метода считают английских математиков Дж. Неймана и С. Улама, которые анонсировали данный метод в статье The Monte Carlo method, J. Amer. statistical assoc., 1949. Название метода происходит от города в княжестве Монако, знаменитого своим игорным домом, так как одним из простейших механических приборов для получения случайных величин является рулетка [12].

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

Важной особенностью данного метода является то, что его реализация практически невозможна без использования компьютера [13].

Метод Монте-Карло  имеет две особенности:

• простая структура вычислительного алгоритма;
• погрешность вычислений, как правило, пропорциональна D/N, где D –некоторая постоянная, N – число испытаний. Отсюда видно, что для того, чтобы уменьшить погрешность в 10 раз (иначе говоря, чтобы получить в ответе еще один верный десятичный знак), нужно увеличить N (т.е. объем работы) в 100 раз [14].

Добиться высокой  точности таким путем невозможно. Поэтому обычно говорят, что метод Монте-Карло особенно эффективен при решении тех задач, в которых результат нужен с небольшой точностью (5-10%). Способ применения метода Монте-Карло довольно прост. Чтобы получить искусственную случайную выборку из совокупности величин, описываемой некоторой функцией распределения вероятностей:

1. задаются пределы изменения времени реализации каждой операции;
2. задается конкретные времена реализации для каждой операции с помощью датчика случайных чисел;
3. рассчитывается критический путь и время реализации всего проекта;
4. переход на операцию "2".