Текст книги "Системы управления предприятием"

Параметры раннего и позднего времени наступления события используются в маркировке вершин сетевого графика модели типа АоА. В левый сегмент записывается раннее время наступления соответствующего события (ЕETj), а в правый – позднее (LETj), что показано на рис 1.2.4.

Рис. 1.2.4.Пример маркировки времени наступления событий

В маркировке вершин сетевого графика модели типа AoN помимо индекса работ используются параметры (см. Рис. 1.2.5):

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

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

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

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

Рис.1.2.5. Пример маркировки вершин сетевого графика модели типа АоN

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

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

В качестве примера будем рассматривать модель, заданную изначально сетевым графиком, приведенным на рис. 1.2.6.

Рис. 1.2.6. Пример сетевого графика для иллюстрации методов расчета временных параметров

Как табличный, так и матричный метод расчета временных параметров сетевой модели основывается на следующих соотношениях, вытекающих из определений временных параметров. Для удобства понимания индекс работы, как правило, состоит из двух букв, например, [ij], первая из которых соответствует индексу начального события работы, а вторая – индексу конечного события работы. С учетом этого замечания:

• Раннее время начала работы [ij] совпадает с ранним временем наступления события [i], т.е. ESTij = EET [i].

• Позднее время окончания работы [ij] совпадает с поздним временем наступления события [j], т.е. LFTij = LET [j].

• Раннее время окончания работы [ij]: EFTij = ESTij + tij.

• Позднее время начала работы [ij]: LSTij = LFTij – tij.

• Раннее время наступления события [j] совпадает с самым поздним (максимальным) ранним временем окончания из всех тех работ, для которых данное событие является конечным, т.е. EET[j] = max { EFTrj, EFTnj, … EFTmj}, где [rj], [nj], … [mj] – индексы работ, для которых событие [j] является конечным.

• Позднее время наступления события [j] совпадает с самым ранним (минимальным) поздним временем начала из всех тех работ, для которых данное событие является начальным, т.е. LET[j] = min { LSTjr, LSTjn, … LSTjm}, где [jr], [jn], … [jm] – индексы работ, для которых событие [j] является начальным.

• Для исходного и заключительного события сетевой модели справедливо: EET[s] = LET[s]

• Но если для исходного события принимается, как правило, момент времени, равный 0, то для заключительного события он появляется в результате расчетов и по нему можно судить о продолжительности критического пути. Итак, для заключительного события справедливо: EET[f] = LET[f] = TK, где TK – продолжительность критического пути.

• Полный резерв времени выполнения работы [ij]: TFij = LЕT[j] – EET[i] – tij.

• Свободный резерв времени выполнения работы [ij]: FFij = EЕT[j] – EET[i] – tij.

• Независимый резерв времени выполнения работы [i]: IFi = EЕT[j] – LET[i] – tij.

Рассмотрим сначала матричный метод определения временных параметров.

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

Первый шаг заполнения матрицы заключается в следующем. Если события [i] и [j] соединяются какой-то работой, то продолжительность этой работы tij заносится в числители двух клеток: клетки, лежащей на пересечении i-й строки и j-го столбца, и клетки лежащей на пересечении j-й строки и i-го столбца. Эти действия выполняются для всех работ сетевой модели, а числители всех остальных клеток, кроме клеток, лежащих на главной (слева сверху вправо вниз) диагонали матрицы, заполняются нулями или вообще не заполняются.

Рис. 1.2.7. Разметка матрицы при определении временных параметров сетевой модели матричным методом

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

Нетрудно проверить по формулам, что раннее время окончания работы 1-2 равно 4, а работы 1-4 равно 7.

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

Рис. 1.2.8. Расчет раннего времени окончания работ

Раннее начало некоторого события, являющегося конечным для нескольких работ, равно моменту раннего окончания самой поздней из работ, которые заканчиваются данным событием. Значит, просто необходимо просмотреть знаменатели клеток столбца 2 сверху вниз до главной диагонали и выбрать максимальное значение, после чего записать его в числитель диагональной клетки 2. В нашем примере это будет знаменатель клетки 1-2, который равен 4.

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

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

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

Получив значение знаменателя последней диагональной клетки, можно вычислить значения знаменателей клеток (чьи числители больше 0), находящихся в той же строке слева (ниже) от главной диагонали. Они будут равны разнице значения знаменателя соответствующей диагональной клетки и значения числителя клетки, для которой производится расчет. Так, например, значение знаменателя клетки 8-7 будет равно 36-5=31, а клетки 8-4 будет равно 36-6=30.

Рис. 1.2.9 Значение раннего времени наступления завершающего со бытия

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

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

Из заполненной матрицы нетрудно увидеть не только продолжительность критического пути (числитель или знаменатель последней диагональной клетки), но также сам критический путь. Он проходит через события, у которых раннее и позднее время наступления равны, т.е. через события, у которых в соответствующих диагональных клетках совпадают числители и знаменатели. В нашем примере это будут события 1, 2, 4, 6, 8 (см. Рис. 1.2.9).

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

Так, для работы 3-5 полный резерв будет равен 29-9=20, свободный – 17-2-7=8, а независимый – 17-22-7=-12 (принимается равным 0). Для работы 2-6 полный резерв будет равен 26-12=14, свободный – 26-4-8=14 и независимый – 26-4-8=14.

На рис. 1.2.10 приведены результаты расчетов всех резервов времени на основании данных из таблицы на рис. 1.2.9.

Рисунок 1.2.10 Результаты расчетов всех резервов времени

Табличный метод. Составляется таблица, число строк в которой равно числу работ, включающая в себя следующие столбцы (в порядке их следования слева направо):

1. индекс работы;

2. индексы непосредственно предшествующих работ;

3. индексы непосредственно следующих работ;

4. продолжительность выполнения работы;

5. раннее время начала выполнения работы;

6. позднее время начала выполнения работы;

7. раннее время окончания выполнения работы;

8. позднее время окончания выполнения работы;

9. полный резерв времени работы;

10. свободный резерв времени работы;

11. независимый резерв времени работы.

Исходная информация, связанная с описанием топологии сетевой модели, содержится в столбцах (1), (2) и (4). Суть табличного метода расчета временных параметров сетевой модели состоит в последовательном заполнении остальных столбцов данной таблицы.

Алгоритм табличного метода предусматривает выполнение следующих последовательных шагов.

ШАГ 1. Определение индексов непосредственно следующих работ. Рассматриваем работу с индексом [i]. Непосредственно следующие за ней работы – это те работы, для которых работа [i] является непосредственно предшествующей. Следовательно, индексы непосредственно следующих работ – это индексы тех работ, у которых в столбце (2) содержится индекс работы [i].

ШАГ 2. Определение раннего времени начала и раннего времени окончания работ.

Определение раннего времени начала и раннего окончания работ, т.е. заполнение столбцов (5) и (7) таблицы должно осуществляться одновременно, т.к. время начала одних работ зависит от времени окончания других.

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

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

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

Продолжительность критического пути равна максимальному значению в столбце (7).

ШАГ 3. Определение позднего времени окончания и позднего времени начала работ.

Определение позднего времени окончания и позднего начала работ, т.е. заполнение столбцов (6) и (8) таблицы должно осуществляться также одновременно, т.к. время начала одних работ зависит от времени окончания других.

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

• Позднее время начала рассматриваемой работы равно позднему времени ее окончания (из столбца (8)) минус продолжительность работы (из столбца (4)).

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

Шаг 4. Определение полного резерва времени выполнения работы. Полный резерв времени работы [i] находится как разность значений ее позднего и раннего времени окончания (соответственно, столбцы (8) и (7)), либо как разность значений ее позднего и раннего начала выполнения (соответственно, столбцы (6) и (5)).

Шаг 5. Определение свободного резерва времени выполнения работы.

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

Шаг 6. Определение независимого резерва времени выполнения работы.

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

По приведенным выше правилам заполнена следующая табл. 1.2.3.

Таблица 1.2.3. Результат табличного метода

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

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

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

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

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

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

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

• математическое ожидание m продолжительности выполнения работы;

• дисперсия s2 продолжительности выполнения работы.

Во втором случае, когда точный закон распределения продолжительности выполнения работ неизвестен предполагается, что это распределение подчиняется нормальному закону и описывается b-функцией, которая имеет следующие математическое ожидание и дисперсию: m = 1/6(O + 4M + P); s2 =[1/6 (O – P)]2.

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

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

В этом случае говорить о том, что комплекс работ будет завершен к какой-то определенной дате (т.е. будет иметь какую-то фиксированную продолжительность выполнения Tk), можно лишь с некоторой вероятностью P(Tk < x) = P(TkN < z), определяемой по таблицам стандартного нормального распределения вероятностей, причем TkN=(x – mk )/sk , где: mk – ожидаемая продолжительность критического пути, а sk – квадратный корень из погрешности продолжительности критического пути.

Рассмотрим в качестве примера сетевую модель, определенную следующей табл. 1.2.4.

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

Сетевой график и его разметка с полученными временными характеристиками работ представлены на рис. 11:

Критический путь сетевого графика, приведенного на рис. 11, составляют работы A–F–G. Ожидаемая продолжительность критического пути равна 6,33 + 12,17 + 18,17 = 36,67, а суммарная погрешность продолжительности критического пути равна 1 + 1,36 + 1,36 = 3,72.

Таблица 1.2.4. Пример сетевой модели

Таблица 1.2.5. Результат расчета

Рисунок 1.2.11. Сетевой график по данным из табл. 1.2.4 и 1.2.5

Однако полученная ожидаемая продолжительность критического пути не означает, что весь комплекс работ, описанный сетевым графиком, будет завершен именно в течение данного промежутка времени. Утверждать, что этот комплекс работ будет завершен именно в данный промежуток времени, можно только с вероятностью 0,5, так как:

P(Tk < (37,7–36,7)/1,93)= P(TkN < 0).

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

С таким же успехом можно определить вероятность завершения комплекса работ до любого директивного срока Х, например, до Х=38. Тогда: P(Tk < (38-36,7)/1,93)= P(TkN < 0,69) < 0,7549.

Рисунок 1.2.12. Кривая нормального стандартного распределени я вероятностей

Кроме того, можно решить и обратную задачу, т.е. определить тот срок, к которому рассматриваемый комплекс работ может завершиться с некоторой заданной вероятностью Pd. Зная Pd, можно воспользоваться нормальным стандартным распределением (в форме таблиц или с помощью известной функциональной зависимости, описываемой интегралом нормального стандартного распределения) и найти zd, а имея zd, продолжительность критического пути Тd, соответствующая заданной вероятности Pd, будет равна Тd= zdsk + mk.

Так, для рассматриваемого здесь примера промежуток времени, в течение которого комплекс работ, описываемых сетевым графиком, будет завершен с вероятностью 0,95, равен:

Pd = 0,95; zd = 1,65; Тd = zdsk + mk = 1,65; 1,93 + 36,67 = 39,85.

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