Дискретно-непрерывная математика (стр. 66 )

Несколько операций можно, конечно, выполнить од­новременно, если ни одна из операций рассматриваемой группы не ограничена моментами выполнения других операций, входящих в группу. (Это произойдет в случае, если ни одна из рассматриваемых операций не входит в путь, ведущий из v1 в начальное событие дру­гой операции).

Предположим, что числа на дугах графа рис. 5.3 со­ответствуют продолжительностям операций.

Рис. 5.3.

(В данном случае считается, что продолжительность каждой oпeрации известна и постоянна. На самом деле продолжи­тельность операций часто меняется, и ее описывают не­которым распределением вероятности, общий вид которого известен, а оценки его параметров могут быть получены.)

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

T( v1)=0, T( vi)=ш'ах{t(Р)} (i≠1),

где t(P) обозначает длину пути Р и максимум берется по всем путям из v1 к vi.

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

Соответствующее дерево показано на рис. 5.4, про­должительности операций для него даны на рис. 5.3, а значения T(vi) приведены в вершинах.

Рис. 5.4.

Как уже упоминалось, наиболее ранний возможный момент начала операции (vi, vj) удален, по крайней ме­ре, на T(vi) единиц времени от начала проекта. С дру­гой стороны, график выполнения проекта, основанный на T(vi), является практически реализуемым. Более точ­но, если мы запланируем, что каждая операция (vi, vj) начинается в момент T(vi) и заканчивается в момент T(vi)+tij, (где tij — длительность соответствующей опе­рации), то ни одна операция не может быть начата раньше момента, определенного основными правилами, и проект в целом будет выполнен за T(v8) = 13 единиц времени, что соответствует наиболее раннему возможно­му моменту его окончания.

Упражнение 4. Доказать, что при предложенном способе пла­нирования операций отношение предшествования операций не нару­шается.

Длиннейший по времени путь от начального события v1 до конечного vn называется критическим путем. Его длина (в нашем примере 13) соответствует кратчайше­му времени, за которое может быть выполнен проект. Минимальное время достигается только в случае, если каждая операция критического пути начинается сразу же после окончания предшествующей. Вообще говоря, критический путь не является единственным. (Читатель может заметить другой критический путь в нашем при­мере.) Операция называется критической, если она при­надлежит одному или нескольким критическим путям. Если проект нужно выполнить за минимальное время, некоторые операции проекта остаются некритическими и существует определенная свобода в их планировании. Измерение этой свободы приводит к определению резер­ва времени операций. Задача нахождения резерва вре­мени операций будет рассмотрена ниже.

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

Таким образом, пусть

X(vn)=0, X(vi)=max{t(P)} для i≠п,

где t(P)—длина пути от vi до vn и максимум берется по всем возможным путям. Заметим, что в этом случае для определения X(vi) мы снова можем воспользовать­ся известным методом. Необходимо только временно поме­нять ориентацию каждой операции на обратную, найти длиннейшее покрывающее дерево с корнем vn, а затем восстановить первоначальную ориентацию дуг. На рис. 5.5 показано дерево, соответствующее нашему при­меру.

Рис. 5.5

В вершинах графа указаны значения X(vi). Так как величины X(vi) измеряются от конца проекта, а вре­мя выполнения всего проекта T(vn), то удобно связать эти времена следующим соотношением:

L(vi)= T(vn)- X(vi),

где L(vi) определяет самое позднее время осуществле­ния события vi, не увеличивающее длительности всего проекта. На рис. 5.6 показаны значения L(vi) для каж­дой вершины одновременно с определенными ранее зна­чениями T(vi). Величины T(vi) и L(vi) удовлетворяют отношению T(vi) ≤ L(vi).

Рис. 5.6.

Упражнение 5. Доказать предшествующее утверждение. Кроме того, доказать, что T(vi)=L(vi) тогда и только тогда, когда vi принадлежит некоторому критическому пути.

Величины T(vi) и L(vi) позволяют определить ре­зерв времени при планировании отдельных операций (при постоянном минимальном времени проекта). Например, время операции, соответствующей дуге от v2 к v3 (см. рис. 8.3), равно одной единице, и мы опреде­лили, что T(v2)=3, L(v2)=3, T(v3)=4, L(v3)=7. Сле­довательно, эту операцию можно было бы начать самое раннее в момент 3 и самое позднее в момент 6. При этом событие v3 наступило бы не позднее момента 7. Естественно, что если мы использовали некоторую часть резерва времени рассматриваемой операции, начав ее позже момента 3, то мы тем самым сократили резервы времени у последующих операций, в нашем случае у опе­раций (v3, v7) и (v7, v8). Вообще говоря, каждое собы­тие v будет происходить в интервале между T(v) и L(v) в зависимости от распределения резерва времени.

До сих пор мы предполагали, что на каждую опера­цию требуется постоянное время и что эта величина времени заранее известна. Если это не так (а на самом деле это почти всегда не так), то разумно предположить, что продолжительность каждой операции есть некоторая случайная величина, определяемая распределением ве­роятностей, соответствующим данной операции. Далее нужно получить возможно лучшие оценки параметров этого распределения и использовать их при последую­щем анализе. В первоначальном варианте метода ПЕРТ, например, предполагалось, что продолжительность опе­рации получается из так называемого «бета-распреде­ления» (природа «бета-распределения» для нас сейчас не существенна, интересующиеся могут найти подроб­ности в литературе, посвященной ПЕРТ). При этом для каждой операции находятся три временные оценки: а, т и b, где а и b соответственно оптимистическая и пес­симистическая оценка времени выполнения операции, а т —наиболее вероятная оценка. Среднее значение времени выполнения операций и ее стандартное откло­нение оцениваются по следующим формулам:

По вычисленным средним временам, описанным вы­ше способом, определяются T(vi), L(vi) и резерв времени. Кроме того, возможный разброс продолжительно­сти операции можно использовать для оценки вероятно­сти окончания проекта в заданный срок. При работе с переменной длительностью операций возникают серьезные математические трудности, даже если точно известно распределение, соответствующее каждой операции, и все распределения считаются неза­висимыми. В этом случае приходится использовать раз­личные приближенные методы. Проиллюстрируем одно из возможных осложнений общего характера. Предпо­ложим, что путь Р является критическим, а Р' — неко­торый путь из начального события в конечное, очень мало отличающийся от Р. Пусть Р и Р' найдены на основе средних значений вре­мен выполнения опера­ций. Может оказаться, что времена операций пути Р имеют малый разброс, а пути Р'—большой. Например, соответствующие рас­пределения могут иметь вид рис. 5.7.

Pис. 5.7

В этом случае су­ществует достаточно большая вероятность того, что вре­мя выполнения проекта будет определяться путем Р', а не P и выводы, сделанные из расчета того, что Р. является критическим путем, окажутся неточными.